On 2/28/2013 10:39 AM, Dmitry Olshansky wrote:
> That would mean that when you see 0 or 0x1A you do a check to see if that's the
> end of input then decide it's really the end of input.

A 0 or a 0x1A is the end of valid D source. Period.

But that doesn't mean the sentinel has to be a tuple.

> I didn't say can't, I said didn't. llvm handles that case (which does surprise me), dmc, gcc, and vc do not. Furthermore, I'll say "cannot" on this:
>
>             case '|':
>                 p++;
>                 if (*p == '=')
>                 {   p++;
>                     t->value = TOKorass;
>                 }
>                 else if (*p == '|')
>                 {   p++;
>                     t->value = TOKoror;
>                 }
>                 else
>                     t->value = TOKor;
>                 return;

This code is correct without assuming that r is a sentinel range, and it is pretty close to your code above:

void foo(R)(ref R r, ref int tvalue)
{
    if(!r.empty)
        switch(r.front)
        {
            case '|':
                r.popFront();
                if (!r.empty && r.front == '=')
                {   r.popFront();
                    tvalue = 1;
                }
                else if (!r.empty && r.front == '|')
                {   r.popFront();
                    tvalue = 2;
                }
                else
                    tvalue = 3;
                return;
            default:
        }
}

If I add this:

struct R
{
    ubyte* p;
    @property front(){ return *p; }
    @property empty(){ return *p == 0; }
    void popFront() { p++; }
}

alias foo!R bar;

ldc2 -O3 -release compiles it to:

   0:  mov    (%rsi),%rax
   3:  cmpb   $0x7c,(%rax)
   6:  jne    3e
   8:  lea    0x1(%rax),%rcx
   c:  mov    %rcx,(%rsi)
   f:  mov    0x1(%rax),%cl
  12:  cmp    $0x7c,%cl
  15:  jne    25
  17:  add    $0x2,%rax
  1b:  mov    %rax,(%rsi)
  1e:  movl   $0x2,(%rdi)
  24:  retq
  25:  cmp    $0x3d,%cl
  28:  jne    38
  2a:  add    $0x2,%rax
  2e:  mov    %rax,(%rsi)
  31:  movl   $0x1,(%rdi)
  37:  retq
  38:  movl   $0x3,(%rdi)
  3e:  retq

On 2/28/2013 2:16 PM, Timon Gehr wrote:
>      // expression simplification
>      // (eg. trivial peephole for x!=a && x==b case sufficient)

Hmm, I hadn't thought of that. Some checking shows that VC and DMC do not do it, gcc and clang do.

On Thursday, February 28, 2013 13:42:34 Walter Bright wrote:
> On 2/28/2013 10:52 AM, Jonathan M Davis wrote:
> > Notice that it has to check for empty every time that the front is popped, and it can't avoid that,
> 
> Yes it can avoid it - that is the whole point. Notice there are no checks for the sentinel here - but the code is correct:
> 
> case '>':
> p++;
> if (*p == '=')
> { p++;
> t->value = TOKge; // >=
> }
> else if (*p == '>')
> { p++;
> if (*p == '=')
> { p++;
> t->value = TOKshrass; // >>=
> }
> else if (*p == '>')
> { p++;
> if (*p == '=')
> { p++;
> t->value = TOKushrass; // >>>=
> }
> else
> t->value = TOKushr; // >>>
> }
> else
> t->value = TOKshr; // >>
> }
> else
> t->value = TOKgt; // >
> return;

But that's with a pointer. You see every ++ there? That would be a popFront call, and for most ranges, that would mean checking empty internally if the range needs to have a sentinel value on its end, because most ranges will be a wrapper around another range, and the only way to know whether you've reached their end (and that therefore, front now needs to be the sentinel) is to check for empty. If a range isn't a wrapper around another range, then it's probably an array, but arrays won't work with the sentinel range scheme, because they won't pass isSentinelRange. So, they'll still need a wrapper which allows them to be treated as a sentinel range. And so the pretty much the only case where you get any performance gain is with strings wrapped in a sentinel range, and if that's the case, I'd just special case them to use sentinels and avoid the sentinel range concept entirely. I just don't see how you're going to get a performance gain from much of anything other than strings.

For the lexer I'm working on, I just use string mixins for any operation which might differ between range types (e.g. strings can't use front or they'll decode, whereas with a range of code units, you need to use front). So, instead of p++ like above, I might have something like

mixin(popCodeUnit!R());

But if you're dealing with strings, and you want your function to operate on ranges of code units, then you're pretty much stuck either casting the strings to arrays of ubyte to operate on them, wrapping them in another range, or special casing them. And wrapping them (like your solution would require) is arguably the worst, because you lose out on any possibility of any helper functions you use optimizing for your strings, unless you write all of them yourself, because they won't be recognized as strings - and that includes functions like std.utf.decode, which any unicode-aware lexer will have to use at least some of the time.

- Jonathan M Davis

On Thursday, February 28, 2013 23:32:16 FG wrote:
> On 2013-02-28 23:27, Walter Bright wrote:
> > I've spent a lot of time profiling compilers. The result is pretty obvious - dmc is by far the fastest C/C++ compiler available, and dmd blows away about every other language in compile speed.
> > 
> > Making this happen means you go after everything that eats time. Even a 5% improvement is a big deal. All those drips and draps add up to big speed increases.
> I get that, but it doesn't require introducing a new type of range.

Exactly.

- Jonathan M Davis

On 2/28/2013 4:07 PM, Jonathan M Davis wrote:
> But that's with a pointer. You see every ++ there? That would be a popFront
> call, and for most ranges, that would mean checking empty internally if the
> range needs to have a sentinel value on its end, because most ranges will be a
> wrapper around another range, and the only way to know whether you've reached
> their end (and that therefore, front now needs to be the sentinel) is to check
> for empty.

It's trivial to construct a SentinelInputRange that does not do this yet is correct.

> I just don't see how you're going to get a
> performance gain from much of anything other than strings.

I gave you other examples already. We're just going around in circles.

On 2/28/2013 3:14 PM, jerro wrote:
> ldc2 -O3 -release compiles it to:

As I posted to Timon, clang (i.e. ldc2) and gcc do do this optimization, dmc and vc do not.

On Thu, Feb 28, 2013 at 04:36:03PM -0800, Walter Bright wrote:
> On 2/28/2013 3:14 PM, jerro wrote:
> >ldc2 -O3 -release compiles it to:
> 
> As I posted to Timon, clang (i.e. ldc2) and gcc do do this
> optimization, dmc and vc do not.

Couldn't dmc be made to do this optimization?


T

-- 
It only takes one twig to burn down a forest.

On Thursday, 28 February 2013 at 23:24:01 UTC, Walter Bright wrote:
> On 2/28/2013 2:16 PM, Timon Gehr wrote:
>>     // expression simplification
>>     // (eg. trivial peephole for x!=a && x==b case sufficient)
>
> Hmm, I hadn't thought of that. Some checking shows that VC and DMC do not do it, gcc and clang do.

Finally we are getting somewhere.

On Friday, 1 March 2013 at 00:34:25 UTC, Walter Bright wrote:
>> I just don't see how you're going to get a
>> performance gain from much of anything other than strings.
>
> I gave you other examples already. We're just going around in circles.

You didn't posted a single example that wasn't optimized by LLVM. I do understand that some compiler may not do the optimization, but it is show already that this is clearly possible and in fact done. That is not an theoretical improvement.

I don't see the point in creating a new type of range simply because some compiler don't optimize properly.