On Mon, 19 Sep 2011 12:00:17 -0400, Steven Schveighoffer <schvei...@yahoo.com>
wrote:
On Mon, 19 Sep 2011 11:46:44 -0400, Robert Jacques <sandf...@jhu.edu>
wrote:
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
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;
}
I would hope something like this would be optimized by the compiler:
auto begin = ptrFront + T.sizeof * i;
if(ptrBack - begin >= 0)
ptrFront = begin;
If not, popFront could optimize it.
Certainly, to say popFront is going to perform *worse* using a
dual-pointer representation is false. Only one calculation is needed.
-Steve
Unfortunately, the compiler isn't going to auto-magically optimize the length
computation away. (Remember that end is not necessarily equal to ptrBack, for
an arbitrary set of ptrFront and ptrBack; it is the high level invariants
associated with arrays which make it true) The compiler could optimize the
slice operator, but it has to do so at a very high level; i.e. recognizing and
special casing statements like a[1..$]. (And such optimizations are notoriously
brittle) And yes, popFront could optimize the slicing operator. But having to
do so is a pretty good indication that something's wrong with the array design.
Also, I didn't say that popFront, by itself, is going to perform *worse*. I
said that popFront + empty require 1 extra subtraction and 1 less memory write.
On today's out of order desktop processors that probably amounts to a wash.
(And the benchmarks support this, see my other post). And given that the change
makes computations like empty, length and slicing much worse, I stated that
dual-pointers would, on the whole, be worse than ptr+length.
