468,101 Members | 1,539 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,101 developers. It's quick & easy.

expression template and FFT

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
Oct 20 '08 #1
12 2241
On Oct 19, 7:49*pm, Peng Yu <PengYu...@gmail.comwrote:
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
Oct 20 '08 #2
On 20 Okt., 05:53, aaragon <alejandro.ara...@gmail.comwrote:
>
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
Oct 20 '08 #3
On Oct 20, 5:01*am, Maik <Beckmann.M...@googlemail.comwrote:
On 20 Okt., 05:53, aaragon <alejandro.ara...@gmail.comwrote:
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
That is very easy to implement after you understand how it works. Good
luck,

aa
Oct 20 '08 #4
SG
On 20 Okt., 02:49, Peng Yu <PengYu...@gmail.comwrote:
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
Oct 20 '08 #5
On Oct 20, 2:11 pm, aaragon <alejandro.ara...@gmail.comwrote:
On Oct 20, 5:01 am, Maik <Beckmann.M...@googlemail.comwrote:
On 20 Okt., 05:53, aaragon <alejandro.ara...@gmail.comwrote:
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

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
Oct 21 '08 #6
Peng Yu wrote:
On Oct 20, 2:11 pm, aaragon <alejandro.ara...@gmail.comwrote:
>On Oct 20, 5:01 am, Maik <Beckmann.M...@googlemail.comwrote:
[...]
>> -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 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
Oct 21 '08 #7
On Oct 21, 3:33 am, Hendrik Schober <spamt...@gmx.dewrote:
Peng Yu wrote:
On Oct 20, 2:11 pm, aaragon <alejandro.ara...@gmail.comwrote:
On Oct 20, 5:01 am, Maik <Beckmann.M...@googlemail.comwrote:
[...]
> -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?

Thanks,
Peng
Oct 21 '08 #8
Peng Yu wrote:
On Oct 21, 3:33 am, Hendrik Schober <spamt...@gmx.dewrote:
>Peng Yu wrote:
>>On Oct 20, 2:11 pm, aaragon <alejandro.ara...@gmail.comwrote:
On Oct 20, 5:01 am, Maik <Beckmann.M...@googlemail.comwrote:
[...]
-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.
Peng
Schobi
Oct 21 '08 #9
On Oct 21, 11:28 am, Hendrik Schober <spamt...@gmx.dewrote:
Peng Yu wrote:
On Oct 21, 3:33 am, Hendrik Schober <spamt...@gmx.dewrote:
Peng Yu wrote:
On Oct 20, 2:11 pm, aaragon <alejandro.ara...@gmail.comwrote:
On Oct 20, 5:01 am, Maik <Beckmann.M...@googlemail.comwrote:
[...]
-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
Oct 21 '08 #10
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
Oct 21 '08 #11
On Oct 21, 3:27*pm, Ian Collins <ian-n...@hotmail.comwrote:
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
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
Oct 30 '08 #12
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?
I just came across this:
http://gcc.gnu.org/projects/cxx0x.html

HTH!
Peng
Schobi
Oct 30 '08 #13

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

4 posts views Thread by Rex_chaos | last post: by
8 posts views Thread by bartek | last post: by
1 post views Thread by PengYu.UT | last post: by
28 posts views Thread by Marc Gravell | last post: by
3 posts views Thread by Dan Smithers | last post: by
2 posts views Thread by madhu.srikkanth | last post: by
1 post views Thread by Solo | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.