Array append performance

[Benji Smith]

Robert Jacques wrote:
> On Sun, 24 Aug 2008 22:14:36 -0400, bearophile 
> <bearophileHUGS at lycos.com> wrote:
>> And, why the stride? I presume it's useful if you want a 2D matrix.
> 
> Yes, stride is a key enabler for integrating 2D/3D/nD matrices with 
> built-in arrays.
> Other pros:
> - Fast O(1) reversing of an array. Looping through an array in reverse 
> was a common enough operation to create an additional keyword and 
> language feature (foreach_reverse) specifically for it.
> - Slicing out a struct element. i.e. slice the red channel out of an 
> image or the first name from an Employee array.
> - Accessing every Nth element. This is a common MATLAB operation and 
> often used in visualization (i.e. a quick and simple resolution 
> adjustment for a line plot). Also, some parallel algorithms benefit from 
> interleaving data. This is a fairly standard multi-threading technique, 
> particularly when processing data[x] may take longer than processing 
> data[y] (though it's not the first thing I'd try).

That's very convincing. Seems like stride ought to be in there.

But it also got me thinking about what other 4-byte value could be 
stuffed into that extra space (satisfying the 16-bit alignment 
requirement), and I can't help but yearn for hashcode memoization.

Strings are, arguably, the most common types of arrays in most programs. 
  And strings are, arguably the most common key-type in associative 
arrays. And every time you perform an associative array lookup, you have 
to re-compute the hashcode (which is silly for immutable strings, since 
the hashcode can't ever change).

In languages where Strings are objects (please!!! please, Walter!!!) you 
can do things like memoize the hashcode to avoid redundant future 
calculations. If Strings are mutable, you can mark a "dirty" bit when 
the string is changed, lazily recalculating a memoized hashcode based on 
that dirty bit. But only if you have a field for memoizing the hashcode 
in the first place.

So, while a stride field seems very useful for some very interesting 
special cases, to me it seems like the more compelling general case is 
for a memoized hashcode.

--benji