Array append performance

JAnderson ask at me.com
Mon Aug 25 18:36:18 PDT 2008


Benji Smith wrote:
> 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.

But please don't come up with something like C#'s strings where you have 
to use stringbuilder to get around the very slow string pooling.  I 
think lazily evaluating it would be a good idea.

-Joel



More information about the Digitalmars-d mailing list