lazy contiguous subrange indexing

[Jaroslav Hajek]

Hello,

please consider the attached two patches.

Summary (1st patch):
If a dense indexing expression can be reduced to a contiguous subrange
(like x(2:end-1), A(:,:,3:10) etc.), a shared (i.e. cheap) copy is
made and the actual extraction is postponed until (if ever) the value
is written to. The obvious benefit is greater performance of various
operations with indexed expressions, such as y = x(1:n-1) + x(2:n),
which will avoid making two temporary copies. This is done by
modifying Array<T> to allow it work with contiguous subranges of its
(possibly shared) data. There is an obvious risk of increased memory
consumption, because a big block of memory may be kept allocated while
only part of it is actually used.
This is resolved by checking prior to storing a value to a "permanent"
location (same where checks for null matrices are done), and possibly
economizing if an orphaned block is detected. The detection (see
Array<T>::maybe_economize) is fairly simple and could be improved at
the cost of performance of the operation. Since most indexing
expressions do not live longer than their parent object I suppose this
will seldom be an issue, but it is still easily possible to construct
an example where memory is wastefully kept allocated.
However, the issue is easy to avoid if you know what you do, so I
think it's OK. Comments are welcome.

To get an idea of the performance speed up, here's a simplistic test
(set n to suitable value):

n = 2e7;
x = 1/n * [1:n]; y = x.^2;
# compute 2nd-order differences
tic; d2y = diff (y, 2); toc
# compute integral
tic; int = trapz (x, y); toc

with a recent tip, I get:

Elapsed time is 0.697262 seconds.
Elapsed time is 0.960276 seconds.

with the new patch, I got:

Elapsed time is 0.213054 seconds.
Elapsed time is 0.497459 seconds.

which means speedups by 228% and 93%.
P.S. I picked some benefitted functions because measuring directly the
performance speed-up of the affected indexing expressions is
meaningless.


Summary (2nd patch):
This is a long-postponed cleanup of Array<T>, DiagArray2<T> and
PermMatrix, to allow the private members of Array<T> to become really
private,
and reimplement DiagArray and PermMatrix without the dangerous abuse
of Array<T>::dimensions (that has caused me quite a pain with the
previous patch).
This patch should probably be applied in any case, I'm putting it here
because right now it's created on top of the 1st patch and I've only
ran make check on the result.

comments? OK to push?

cheers to Octave

-- 
RNDr. Jaroslav Hajek
computing expert
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz

lazy.diff
Description: Text Data

arclp.diff
Description: Text Data