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 < [email protected]> 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 > > >
