Proposal: takeFront and takeBack

[Dmitry Olshansky]

On 04-Jul-12 19:17, Andrei Alexandrescu wrote:
> On 7/4/12 8:33 AM, deadalnix wrote:
>> Le 04/07/2012 13:04, Roman D. Boiko a écrit :
>>> On Wednesday, 4 July 2012 at 10:54:41 UTC, deadalnix wrote:
>>>> I do agree with that. However, the current proposal have the same
>>>> drawback but on the code that use the range.
>>>>
>>>> Both solutions are messy IMO.
>>>
>>> What is error-prone in current client code?
>>>
>>> If particular algorithm wants to take advantage of a potential speed-up,
>>> it may decide to check whether hasConsume!Range, and call consumeFront
>>> instead of front + popFront. Nobody is obliged to do so.
>>>
>>> The only problem I can see is potential code duplication, which is lower
>>> priority in performance-critical part of code, IMO.
>>>
>>
>> You have to maintain 2 version of you algorithm. This is more work to
>> test, to maintain, and it is likely to introduce more bugs.
>>
>> More code == more bugs. More NPATH = more bugs and harder to test and to
>> maintain.
>>
>> In addition, this will result in practice in less generic code, because
>> one may not need the version of the algorithm without consume primitives
>> in his/her own code and not code it at all.
>
> I agree. Can't get behind this proposal.
>
> First, it solves the problem of double decoding for UTF-8 and UTF-16
> strings. Before that, we need to estimate how bad the problem is and how
> we can optimize front/popFront() to alleviate it. For all I can tell, in
> ASCII-heavy strings we're looking at optimizing away ONE redundant
> comparison in a sequence that involves a bounds check, two word
> assignments, and another comparison.

It's about optimizing away the whole sequence. In current state it does 
this twice in decode and in stride. (front calls decode that does shrink 
temporary range)

  Off the top of my head I don't
> think the gains are going to be impressive.
>
I hate to say this but if we look at ASCII heavy then this is should be 
a baseline to race against:

dchar decode(ref char[] a)
{
	dchar ch = a[0];
	a = a[1..$];
	return ch;
}

Now it's abundantly clear that removing a comparison & redundant 
assignment is a big win, the extra ops per _iteration_ :

a = a[std.utf.stride(a, 0) .. $];

1) a = ... is redundant as decode is called in front
2) the following is redundant as we already  know the length when do decode:
       immutable c = str[index];
       if (c < 0x80)
           return 1;
memory access, comparison, 2 word assignments and a bounds check.
And with DMD it may also miss inlining thus adding extra call to the table.

>
> In theory all of these redundant operations can be done away with
> optimization techniques, but probably some aren't. So we should look
> first at optimizing this flow heavily before looking at an API addition
> that has disadvantages in other dimensions.
>
It is optimized but there is a limit to where it can go. Previously (say 
one year ago) it was far slower.


-- 
Dmitry Olshansky