Re: [Bug-apl] Internal storage of iota

[Juergen Sauermann]

Hi Blake,

it is definitely saving space, but it most likely taking more time.

Consider Z←A ⍴ IDX← ⍳ N to represent the creation (IDX ← ⍳ N) and use (Z ← A ⍴ IDX) of IDX.

At ravel cell level a cell is created with constructor IntCell() and used with get_ravel(r). The
argument of IntCell is a simple integer that is incremented and that part can be neglected.

So the current implementation takes time

        A timeof(get_ravel) + N timeof(IntCell).

A lazy computation of ⍳ would take time

        A timeof(IntCell) instead.

Now timeof(get_ravel) is slightly smaller than timeof(IntCell) so you can gain only if A < N1 where
N1 is somewhere between N and 2N. For larger A lazy computation cost more.

An even worse thing is the collateral damage of such an optimization. We would get two types of Values: the
"normal ones" and those computed when referenced. The consequence would be that get_ravel() becomes
virtual which adds cost for all accesses to ravel cells. Currently get_ravel() is inlined and should be one or two
assembler instructions for a good compiler. A virtual get_ravel() would be a function call via the vtable of IDX
instead because the compiler cannot decide which type of value is being used.

That all suggests IMHO to not do it. The general problem with this and similar optimizations is that the
optimization considered alone can be drastic, but the overall gain of it can still be negative.

/// Jürgen


On 04/27/2014 06:27 PM, Blake McBride wrote:

Greetings,

Back when I coded in APL, there was discussion about the storage of iota.  For example:

a←⍳1000000

b←66+⍳1000000

c←6.2×4+⍳1000000

d←5+b

All of these can be represented as a simple equations internally rather than expanding it all out.  It would only be expanded when absolutely necessary.  This is incredibly more time and space efficient.

Just passing on some ideas.

Thanks.

Blake