View mode: basic / threaded / horizontal-split · Log in · Help
February 28, 2013
Re: Proposal for SentinelInputRange
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.
February 28, 2013
Re: Proposal for SentinelInputRange
> 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
February 28, 2013
Re: Proposal for SentinelInputRange
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.
March 01, 2013
Re: Proposal for SentinelInputRange
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
March 01, 2013
Re: Proposal for SentinelInputRange
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
March 01, 2013
Re: Proposal for SentinelInputRange
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.
March 01, 2013
Re: Proposal for SentinelInputRange
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.
March 01, 2013
Re: Proposal for SentinelInputRange
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.
March 01, 2013
Re: Proposal for SentinelInputRange
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.
March 01, 2013
Re: Proposal for SentinelInputRange
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.
9 10 11 12 13 14 15 16
Top | Discussion index | About this forum | D home