expression template and FFT

[Peng Yu]

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

 

[aaragon]

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]

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/184403855
I'll have a look into this. Thanks for hint.

-- Maik

 

[aaragon]

Hm, I didn't know the term "mojo".  Just search-machined for it and
found:
 -http://www.ddj.com/database/184403855
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]

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]

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

 

[Peng Yu]

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

 

[Peng Yu]

Peng Yu wrote:
[...]
-http://www.ddj.com/database/184403855
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]

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.

 

[aaragon]

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.

You should try to use Andrei's code. It's only a header file and the
implementation is really a piece of cake. I think it's gonna take a
while until compilers support this idea of rvalue references. The idea
behind the mojo code is that if you use objects that allocate memory
dynamically, you can avoid the creation of temporaries (for example
when you return an object from a function) by stealing the pointer to
the memory allocated. This is what move constructors do. This can also
be done by the RVO (Return Value Optimization), but this is up to the
compiler because it depends on how messy the function is. The mojo
code works regardless, but it won't be useful unless you allocate a
lot of memory on the heap. I used it because I coded myself Matrix and
Vector classes to do numerical computations and all elements in these
objects were allocated through an array in the heap.

I hope it helps.

aa