Go and generic programming on reddit, also touches on D

[Robert Jacques]

On Mon, 19 Sep 2011 12:00:17 -0400, Steven Schveighoffer <schveiguy at yahoo.com> wrote:

> On Mon, 19 Sep 2011 11:46:44 -0400, Robert Jacques <sandford at jhu.edu>
> wrote:
>
>> 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
>>>
>>
>> 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.