View mode: basic / threaded / horizontal-split · Log in · Help
February 28, 2013
Re: Proposal for SentinelInputRange
On 2/28/2013 9:10 AM, Andrei Alexandrescu wrote:
> I don't think what I said was understood.

I know the feeling :-)
February 28, 2013
Re: Proposal for SentinelInputRange
On 2/28/2013 9:06 AM, Dmitry Olshansky wrote:
> 28-Feb-2013 20:56, Walter Bright пишет:
>> The merit is having significantly faster speed.
> 5% is good but doesn't count as significant. But that was for std.regex quite
> sometime ago. In the lexer it might get be more.

Even 5% is worth getting, and especially so because it's low hanging fruit.

I hear from people who have switched over to D and compile speed was a BIG 
factor. And I know you are well cognizant of the fact that for regex, speed is 
also a very big deal.
February 28, 2013
Re: Proposal for SentinelInputRange
On 2/28/2013 9:25 AM, Steven Schveighoffer wrote:
> On Thu, 28 Feb 2013 12:00:48 -0500, Walter Bright <newshound2@digitalmars.com>
> wrote:
>
>> On 2/28/2013 6:31 AM, Steven Schveighoffer wrote:
>>> If this doesn't translate to the same code, I don't know why not.
>>
>> Try it and see with your favorite C compiler.
>
> A sample case of 1 does not prove it's not possible, or explain why those
> optimizers don't take that step.  A valid response would be to give a case why
> an optimizer COULDN'T make that leap.

No, it is not. DMD is compiled with real compilers, not abstract "sufficiently 
smart compilers".

>> Then try the lookahead cases I also posted.
>
> You have already stated it gets changed into a jump table.

Please, please listen to what I write. This is very frustrating. The code in 
lexer.c is there for all to see, and it amply illustrates everything I'm saying. 
For example, this code does not get translated into a jump table:

            case '+':
                p++;
                if (*p == '=')
                {   p++;
                    t->value = TOKaddass;
                }
                else if (*p == '+')
                {   p++;
                    t->value = TOKplusplus;
                }
                else
                    t->value = TOKadd;
                return;

> Such an optimization
> seems possible to me, even with the != 0 check outside the switch, even if not
> all C compilers employ it.

It doesn't matter if it is theoretically possible if the compilers we need to 
use do not do it.
February 28, 2013
Re: Proposal for SentinelInputRange
On 2/28/2013 9:18 AM, Steven Schveighoffer wrote:
> The point is, if the lexer simply requires an input range, and not a sentinel
> input range, it is more flexible for its input.  But when it does get called
> with a sentinel input range, the optimizer can reap the benefits.

I suggest you compile lexer.c with various compilers, add in a !empty() call 
before every front(), and verify your assumption about this.
February 28, 2013
Re: Proposal for SentinelInputRange
On 02/28/2013 10:40 PM, Walter Bright wrote:
> On 2/28/2013 9:05 AM, deadalnix wrote:
>> I see nothing that can't be done by an optimizing compiler. Maybe
>> something is,
>> but I can't find it. And the example you pointed me aren't.
>
> Tell me how front() will be optimized out to this.
>
>              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;


I'd be surprised if DMD couldn't do it already.

assume: popFront(){ p++; }, front()=>*p, empty()=>*p=='\0'

    case '>':
        popFront();
        if(!empty && front == '='){
            popFront();
            t->value = TOKge;                   // >=
        }else if(!empty && front == '>'){
            popFront();
            if(!empty && front == '='){
                popFront();
                t->value = TOKshrass;           // >>=
            }else if(!empty && front == '>'){
                popFront();
                if(!empty && front == '='){
                    popFront();
                    t->value = TOKushrass;      // >>>=
                }else t->value = TOKushr;       // >>>
            }else t->value = TOKshr;            // >>
        }else t->value = TOKgt;                 // >
        return;

    // inlining =>

    case '>':
        p++;
        if(!(*p=='\0') && *p == '='){
            p++;
            t->value = TOKge;                   // >=
        }else if(!(*p=='\0') && *p == '>'){
            p++;
            if(!(*p=='\0') && *p == '='){
                p++;
                t->value = TOKshrass;           // >>=
            }else if(!(*p=='\0') && *p == '>'){
                p++;
                if(!(*p=='\0') && *p == '='){
                    p++;
                    t->value = TOKushrass;      // >>>=
                }else t->value = TOKushr;       // >>>
            }else t->value = TOKshr;            // >>
        }else t->value = TOKgt;                 // >
        return;

    // expression simplification
    // (eg. trivial peephole for x!=a && x==b case sufficient)
    // =>

    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;
February 28, 2013
Re: Proposal for SentinelInputRange
On 2/28/2013 10:12 AM, deadalnix wrote:
> On Thursday, 28 February 2013 at 17:00:51 UTC, Walter Bright wrote:
>> On 2/28/2013 6:31 AM, Steven Schveighoffer wrote:
>>> If this doesn't translate to the same code, I don't know why not.
>>
>> Try it and see with your favorite C compiler.
>>
>> Then try the lookahead cases I also posted.
>
> You are being stubborn here.
>
> You claim that this is significantly faster, but give no numbers.
> You claim that the compiler can't do some optimization, when LLVM does it already.

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;
February 28, 2013
Re: Proposal for SentinelInputRange
On 2/28/2013 5:02 AM, Peter Alexander wrote:
> On Thursday, 28 February 2013 at 10:57:29 UTC, Walter Bright wrote:
>>> My worry here is that we are setting a precedent for adding new range concepts.
>>> If the only justification needed is that is saves a single operation in some
>>> niche area of computing then we are opening the door to a LOT of different range
>>> concepts.
>>
>> There are many cases where speed is a very big deal.
>
> Yes, are we going to add new range categories every time there's a performance
> benefit to doing so?
>
> has16ByteAlignedElements
> hasUniqueElements
> hasContiguousMemory
> isMonotonic
> isUnimodal
> ...
> ?

Depends on whether one can make a good case for them.
February 28, 2013
Re: Proposal for SentinelInputRange
On 2/28/2013 7:00 AM, Jacob Carlborg wrote:
> You'll have to convince Walter.

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.

Two corporate users of D have also told me that their motivating case to adopt D 
was - compile speed!

Throwing compile speed under the bus is what other compiler vendors do, and 
we're not going to do that.
February 28, 2013
Re: Proposal for SentinelInputRange
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.
February 28, 2013
Re: Proposal for SentinelInputRange
On 02/28/2013 11:17 PM, Walter Bright wrote:
> On 2/28/2013 10:12 AM, deadalnix wrote:
>> On Thursday, 28 February 2013 at 17:00:51 UTC, Walter Bright wrote:
>>> On 2/28/2013 6:31 AM, Steven Schveighoffer wrote:
>>>> If this doesn't translate to the same code, I don't know why not.
>>>
>>> Try it and see with your favorite C compiler.
>>>
>>> Then try the lookahead cases I also posted.
>>
>> You are being stubborn here.
>>
>> You claim that this is significantly faster, but give no numbers.
>> You claim that the compiler can't do some optimization, when LLVM does
>> it already.
>
> 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;

Why not? It boils down to a little CSE and a trivial implies check in an 
and expression.
8 9 10 11 12 13 14 15 16
Top | Discussion index | About this forum | D home