Go and generic programming on reddit, also touches on D

[Robert Jacques]

On Mon, 19 Sep 2011 10:08:32 -0400, Andrei Alexandrescu <SeeWebsiteForEmail at erdani.org> wrote:
> On 9/19/11 6:25 AM, Steven Schveighoffer wrote:
>> On Sun, 18 Sep 2011 15:34:16 -0400, Timon Gehr <timon.gehr at gmx.ch> wrote:
>>
>>> On 09/18/2011 08:28 PM, Andrei Alexandrescu wrote:
>>>> That would allow us to e.g. switch from the
>>>> pointer+length representation to the arguably better pointer+pointer
>>>> representation with ease.
>>>
>>> In what way is that representation better?
>>
>> I agree, I don't see why the representation is inherently better. Some
>> operations become higher performance (i.e. popFront), and some become
>> worse (i.e. length). Most of the others are a wash.
>
> That's where frequency of use comes into play. I'm thinking popFront
> would be used most often, and it touches two words.
>
> Andrei
>

Well, looking at the two implementations:

popFront()

if(length) {
     ptr    += T.sizeof;
     length -= 1;
}

vs

if(ptrBack - ptrFront > 0) {
     ptrFront += T.sizeof;
}

And don't forget that every popFront call will be matched by a call to empty

empty()

return length;

vs

return ptrBack - ptrFront > 0;

I see that the 'new' popFront still needs to read 2 words and results in an extra subtraction. Without the guard statements, then the instruction counts are identical, but note that the current popFront implementation uses slices which are 'guarded' and I see every reason not to change this behavior. And given how memory works, I doubt there by any advantage to 1 vs 2 writes one after another to the same cache line.

By the way, for those wondering why I didn't use 'ptrBack > ptrFront', that's because comparisons are eventually reduced to a 'Jump if (Not) Zero', and I wanted to make the amount and types of hardware instructions clear.

The elephant in the room, of course, is that length now requires a division and that popFront is actually implemented using slicing:

a = a[i .. $];

which translates into:

auto begin = i;
auto end   = length;
if(end - begin >= 0  && length - end >= 0) {
     ptr     = ptr + T.sizeof * begin;
     length  = end - begin;
}

vs

auto length = (ptrBack - ptrFront) / T.sizeof;
auto begin  = ptrFront + T.sizeof * i;
auto end    = ptrFront + T.sizeof * length;
if(end - begin >= 0  && ptrBack - end >= 0) {
     ptrFront = begin;
     ptrBack  = end;
}

And both integer multiplication and division of non-power of 2 sizes is really, really, really slow, compared to +-. Now, the division is only needed whenever 'length' is called, but the extra multiplication is required on every slice.

So, on balance, I'd say the two pointers representation is categorically worse than the fat pointer representation.