[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.c++

expression template and FFT

Peng Yu

10/20/2008 12:49:00 AM

Hi,

Expression template can be used for the implementation of simple
operators without using temporaries (e.g. the ones in the book C++
Template).

I'm wondering whether expression template is useful for the
convolution operation.

For example, I have two arrays a1 and a2. To compute the convolution
between them I need to compute the FFT of both of them, which shall be
stored in two temporary arrays. These arrays then shall be multiplied
and FFT back, which also need a temporary arrays. There are totally
three temporary arrays.

It seems that expression template would not reduce the number of
temporary arrays. Are there any better way to reduce the temporaries?

Thanks,
Peng
12 Answers

aaragon

10/20/2008 3:53:00 AM

0

On Oct 19, 7:49 pm, Peng Yu <PengYu...@gmail.com> wrote:
> Hi,
>
> Expression template can be used for the implementation of simple
> operators without using temporaries (e.g. the ones in the book C++
> Template).
>
> I'm wondering whether expression template is useful for the
> convolution operation.
>
> For example, I have two arrays a1 and a2. To compute the convolution
> between them I need to compute the FFT of both of them, which shall be
> stored in two temporary arrays. These arrays then shall be multiplied
> and FFT back, which also need a temporary arrays. There are totally
> three temporary arrays.
>
> It seems that expression template would not reduce the number of
> temporary arrays. Are there any better way to reduce the temporaries?
>
> Thanks,
> Peng

If you want to reduce temporaries, try to read Alexandrescu's mojo
code. Expression templates are too advanced for what you need to do,
so it may not pay the time in coding it. Hope it helps,

aa

Maik

10/20/2008 10:01:00 AM

0

On 20 Okt., 05:53, aaragon <alejandro.ara...@gmail.com> wrote:
>
> If you want to reduce temporaries, try to read Alexandrescu's mojo
> code. Expression templates are too advanced for what you need to do,
> so it may not pay the time in coding it. Hope it helps,
>
> aa

Hm, I didn't know the term "mojo". Just search-machined for it and
found:
- http://www.ddj.com/database...
I'll have a look into this. Thanks for hint.

-- Maik

aaragon

10/20/2008 7:11:00 PM

0

On Oct 20, 5:01 am, Maik <Beckmann.M...@googlemail.com> wrote:
> On 20 Okt., 05:53, aaragon <alejandro.ara...@gmail.com> wrote:
>
>
>
> > If you want to reduce temporaries, try to read Alexandrescu's mojo
> > code. Expression templates are too advanced for what you need to do,
> > so it may not pay the time in coding it. Hope it helps,
>
> > aa
>
> Hm, I didn't know the term "mojo".  Just search-machined for it and
> found:
>  -http://www.ddj.com/database...
> I'll have a look into this. Thanks for hint.
>
> -- Maik

That is very easy to implement after you understand how it works. Good
luck,

aa

SG

10/20/2008 7:24:00 PM

0

On 20 Okt., 02:49, Peng Yu <PengYu...@gmail.com> wrote:
> I'm wondering whether expression template is useful for the
> convolution operation.

Calculating the FFT and inverse FFT can be done in-place. No
temporaries needed. If you want to keep the original signals 'a1' and
'a2' you can do it with TWO temporaries:

<pseudo code>
t1 = a1; fft(t1); // copy 'a1' to 't1' and do an FFT on it
t2 = a2; fft(t2); // copy 'a2' to 't2' and do an FFT on it
t1 *= t2; // element-wise complex product
ifft(t1); // t1 will contains the (circular-)convolution result
</pseudo code>

I don't think that expression templates can help here.

Cheers,
SG

Peng Yu

10/21/2008 1:34:00 AM

0

On Oct 20, 2:11 pm, aaragon <alejandro.ara...@gmail.com> wrote:
> On Oct 20, 5:01 am, Maik <Beckmann.M...@googlemail.com> wrote:
>
>
>
> > On 20 Okt., 05:53, aaragon <alejandro.ara...@gmail.com> wrote:
>
> > > If you want to reduce temporaries, try to read Alexandrescu's mojo
> > > code. Expression templates are too advanced for what you need to do,
> > > so it may not pay the time in coding it. Hope it helps,
>
> > > aa
>
> > Hm, I didn't know the term "mojo". Just search-machined for it and
> > found:
> > -http://www.ddj.com/database...
> > I'll have a look into this. Thanks for hint.
>
> > -- Maik
>
> That is very easy to implement after you understand how it works. Good
> luck,

Hi,

It is too long to read the webpage. Can somebody explain in a brief
way what the main point is and what the major steps to use mojo?

Thanks,
Peng

Hendrik Schober

10/21/2008 8:34:00 AM

0

Peng Yu wrote:
> On Oct 20, 2:11 pm, aaragon <alejandro.ara...@gmail.com> wrote:
>> On Oct 20, 5:01 am, Maik <Beckmann.M...@googlemail.com> wrote:
> [...]
>>> -http://www.ddj.com/database...
>>> I'll have a look into this. Thanks for hint.
>>> -- Maik
>> That is very easy to implement after you understand how it works. Good
>> luck,
>
> Hi,
>
> It is too long to read the webpage. Can somebody explain in a brief
> way what the main point is and what the major steps to use mojo?

It's main point is to avoid unnecessary copying. It does so by
"stealing" the data from temporary objects instead. This is what
rvalue references will be in C++0x.
If you want to use it to write fast code, you won't get around
reading and understanding it.

> Thanks,
> Peng

Schobi

Peng Yu

10/21/2008 3:48:00 PM

0

On Oct 21, 3:33 am, Hendrik Schober <spamt...@gmx.de> wrote:
> Peng Yu wrote:
> > On Oct 20, 2:11 pm, aaragon <alejandro.ara...@gmail.com> wrote:
> >> On Oct 20, 5:01 am, Maik <Beckmann.M...@googlemail.com> wrote:
> > [...]
> >>> -http://www.ddj.com/database...
> >>> I'll have a look into this. Thanks for hint.
> >>> -- Maik
> >> That is very easy to implement after you understand how it works. Good
> >> luck,
>
> > Hi,
>
> > It is too long to read the webpage. Can somebody explain in a brief
> > way what the main point is and what the major steps to usemojo?
>
> It's main point is to avoid unnecessary copying. It does so by
> "stealing" the data from temporary objects instead. This is what
> rvalue references will be in C++0x.
> If you want to use it to write fast code, you won't get around
> reading and understanding it.

So it is still quite useful even after 5 years since it was written,
and no other technique beats it right now? Is it a widely used and
necessary technique today?

Thanks,
Peng

Hendrik Schober

10/21/2008 4:28:00 PM

0

Peng Yu wrote:
> On Oct 21, 3:33 am, Hendrik Schober <spamt...@gmx.de> wrote:
>> Peng Yu wrote:
>>> On Oct 20, 2:11 pm, aaragon <alejandro.ara...@gmail.com> wrote:
>>>> On Oct 20, 5:01 am, Maik <Beckmann.M...@googlemail.com> wrote:
>>> [...]
>>>>> -http://www.ddj.com/database...
>>>>> I'll have a look into this. Thanks for hint.
>>>>> -- Maik
>>>> That is very easy to implement after you understand how it works. Good
>>>> luck,
>>> Hi,
>>> It is too long to read the webpage. Can somebody explain in a brief
>>> way what the main point is and what the major steps to usemojo?
>> It's main point is to avoid unnecessary copying. It does so by
>> "stealing" the data from temporary objects instead. This is what
>> rvalue references will be in C++0x.
>> If you want to use it to write fast code, you won't get around
>> reading and understanding it.
>
> So it is still quite useful even after 5 years since it was written,
> and no other technique beats it right now? Is it a widely used and
> necessary technique today?

From what I read, rvalue references seem to be better, but
until you get your hands on a compiler that has them, Andrei's
code and ideas are most likely the best you can get.

> Peng

Schobi

Peng Yu

10/21/2008 8:21:00 PM

0

On Oct 21, 11:28 am, Hendrik Schober <spamt...@gmx.de> wrote:
> Peng Yu wrote:
> > On Oct 21, 3:33 am, Hendrik Schober <spamt...@gmx.de> wrote:
> >> Peng Yu wrote:
> >>> On Oct 20, 2:11 pm, aaragon <alejandro.ara...@gmail.com> wrote:
> >>>> On Oct 20, 5:01 am, Maik <Beckmann.M...@googlemail.com> wrote:
> >>> [...]
> >>>>> -http://www.ddj.com/database...
> >>>>> I'll have a look into this. Thanks for hint.
> >>>>> -- Maik
> >>>> That is very easy to implement after you understand how it works. Good
> >>>> luck,
> >>> Hi,
> >>> It is too long to read the webpage. Can somebody explain in a brief
> >>> way what the main point is and what the major steps to usemojo?
> >> It's main point is to avoid unnecessary copying. It does so by
> >> "stealing" the data from temporary objects instead. This is what
> >> rvalue references will be in C++0x.
> >> If you want to use it to write fast code, you won't get around
> >> reading and understanding it.
>
> > So it is still quite useful even after 5 years since it was written,
> > and no other technique beats it right now? Is it a widely used and
> > necessary technique today?
>
> From what I read, rvalue references seem to be better, but
> until you get your hands on a compiler that has them, Andrei's
> code and ideas are most likely the best you can get.

I see a proposal to add rvalue reference in the standard. Is it in the
standard now? Is there any compiler that supports it?

Thanks,
Peng

Ian Collins

10/21/2008 8:28:00 PM

0

Peng Yu wrote:
>
> I see a proposal to add rvalue reference in the standard. Is it in the
> standard now? Is there any compiler that supports it?
>
Well you just said it's a proposal, didn't you? The new standard has
yet to be published.

Have a look at gcc 4.3.

--
Ian Collins