Array append performance

[Robert Jacques]

On Mon, 25 Aug 2008 11:41:51 -0400, Benji Smith <dlanguage at benjismith.net>  
wrote:

> 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.

This only works if strings are objects as there's an aliasing issue, so it  
won't work for D arrays. Consider:

string a = "foo";
string b = a;
int[string] counts;
counts[b] = 1;
a[0] = 'b'; // b's dirty bit isn't set
counts[b]++; // calls counts["foo"]++ and not counts["boo"]++

> So, while a stride field seems very useful for some very interesting  
> special cases,

Well, I would argue that games, scientific computing, throughput computing  
and (lightweight) databases aren't special cases.