Strings hash value memoized

[Koroskin Denis]

On Sat, 12 Jul 2008 16:36:53 +0400, bearophile <bearophileHUGS at lycos.com>  
wrote:

> I presume AAs are used often enough in D. If D 2.x strings are  
> immutable, then their hash function doesn't change, so it can be useful  
> to store the hash value inside the data structure of the string (Python  
> works like this), by default it can be initialized to a value like -1,  
> so it's computed only the first time it's actually needed, avoiding  
> wasting time to compute the hash value if it's not used.
>
> Having the hash value inside strings and other immutable data structures  
> allows quite faster AAs (and sets too, even if they are inside an  
> external library).
> Currently strings aren't special structures, they are just immutable  
> dynamical arrays of chars, so the has value (32 or 64 bit according to  
> the word size of the CPU, I presume) can't be stored in the dynamic  
> array record, so it may be stored in the -4/-8 bytes of the data block,  
> but this can't work for string slices. A possible solution is to create  
> a special string type that's just like the dynamic array struct, plus  
> the hash value, so this struct becomes bigger (12 instead of 8 bytes on  
> 32 bit CPUs), slowing down some operations a little.
>
> Bye,
> bearophile

Why distiguish between strings and other data type? Just wrap any  
invariant data type into a special structure that lazily computes and  
stores hash, and use it in a AA instead.