[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [OF miscellaneous] Hilbert curve: recursion faster than loop?
From: |
Juan Pablo Carbajal |
Subject: |
Re: [OF miscellaneous] Hilbert curve: recursion faster than loop? |
Date: |
Mon, 7 Aug 2017 11:07:29 +0200 |
> My next thought was, that the complex computation lowers the
> performance and replaced all complex computations by meaningless pure real
> ones.
What complex-to-real conversion do you refer to? The non-recursive is
only complex.
>Still this version is by factor 2 slower than the recursive one and
> with memory allocation by factor 10! So my guess is, that recursion for this
> example is faster than repetitive memory allocation within for-loops or the
> many data copy operations between z and zz, where also growing implicit
> memory allocations might happen as zz changes it's size depending on
> z(1:nz(k)) within a for-loop?
The non-recursive version with second input argument true, has the
same memory allocation as the recursive one (I refer to the final
output).
I did some changes to address your comment about copies. Indeed I get
a considerable improvement if I avoid zz. Check the latest version[1].
I get (I am in a different PC now):
for i=1:100; tic; hilbert_curve_nr(9,true); t(i)=toc; end; [mean(t) std(t)]
ans =
0.0088032 0.0024393
Still this is slower than without allocation
for i=1:100; tic; hilbert_curve_nr(9,false); t(i)=toc; end; [mean(t) std(t)]
ans =
0.0065030 0.0018694
and both are slower than the recursion (using dev version of miscellaneous [2])
for i=1:100; tic; hilbert_curve(2^9); t(i)=toc; end; [mean(t) std(t)]
ans =
1.9476e-03 8.0688e-04
The results from the profiler do not add up to the total time of the
non-recursive version. I take this as an indication that the time is
spent on the slicing and re-writing of the z vector (not reported by
the profiler), i.e. at each iteration the first 4^i elements are
re-written.
How can this re-writing could be faster? Is this something to improve
in core octave? (sadly I have not access to matlab to check)
[1]: https://bitbucket.org/KaKiLa/mymfiles/src/tip/hilbert_curve_nr.m
[2]: https://sourceforge.net/p/octave/miscellaneous/ci/default/tree/
- [OF miscellaneous] Hilbert curve: recursion faster than loop?, JuanPi, 2017/08/05
- Re: [OF miscellaneous] Hilbert curve: recursion faster than loop?, siko1056, 2017/08/06
- Re: [OF miscellaneous] Hilbert curve: recursion faster than loop?, Juan Pablo Carbajal, 2017/08/07
- Re: [OF miscellaneous] Hilbert curve: recursion faster than loop?, Juan Pablo Carbajal, 2017/08/07
- Re: [OF miscellaneous] Hilbert curve: recursion faster than loop?, siko1056, 2017/08/07
- Re: [OF miscellaneous] Hilbert curve: recursion faster than loop?,
Juan Pablo Carbajal <=
- Re: [OF miscellaneous] Hilbert curve: recursion faster than loop?, Julien Bect, 2017/08/07
- Re: [OF miscellaneous] Hilbert curve: recursion faster than loop?, siko1056, 2017/08/07
- Re: [OF miscellaneous] Hilbert curve: recursion faster than loop?, Juan Pablo Carbajal, 2017/08/07
- Re: [OF miscellaneous] Hilbert curve: recursion faster than loop?, Juan Pablo Carbajal, 2017/08/07