Re: [Bug-apl] Internal storage of iota

[Blake McBride]

Dear Jürgen,

For starters, this discussion, in my mind, is just academic at this point.  Not knowing the details of GNU APL, I will speak somewhat abstractly.

1.  The intent is to save space and not time.  The space savings, depending on the application, can be extremely high.

2.  The time cost could easily be made next to zero IMO.  Imagine your existing code with just one IF statement added to each function.  IF special iota array do new code, otherwise do normal/regular/old code.  Time hit on normal/regular/old code is next to zero in this case. 

Here is an important idea, you don't create special iota arrays in every case.  You only do so when the array would be over a certain size threshold - perhaps programmer definable.  This way, again, we are left with no time hit when using normal arrays, and small iota arrays will be expanded as they are now.  So, the cost only comes for large arrays - you know - the ones that have a huge space cost.

Let's look at time hits on special iota arrays.  There are only three things you can do with an array:

a.  Get elements (i.e. x[400], y[633;], z,  etc.).  In this case you calculate the result rather than just get the data.  You can also associate usage heuristics with each array so you can calculate when it just makes sense to expand the array to a normal array.

b.  Put elements (i.e.  x[567]←55).  In this case, if the array element is actually being changed (as opposed to putting the same value), you always have to expand the array.  Timing again gets reduced to the same as normal arrays.

c.  Copy array (i.e.  x←y+2 : x becomes a modified copy of y).  In this case y is not modified and need not be changed.  x uses your normal algorithm for creating arrays (normal or special iota arrays).  If it is a special iota array, the copy will be significantly faster.

So it seems the space savings can be extremely significant, and there are times when their is a significant time savings too.  Normal time costs (when dealing with normal arrays) is near zero.  Time costs, in worse case scenarios for special iota arrays can be largely eliminated with a small amount of usage statistics and forced expansion.

Now, with all the other stuff going on, I consider this an academic discussion and not a feature request.

Thanks.

Blake

On Mon, Apr 28, 2014 at 7:20 AM, Juergen Sauermann <address@hidden> wrote:

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