On Mon, 19 Sep 2011 10:08:32 -0400, Andrei Alexandrescu
<seewebsiteforem...@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.g...@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.
