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