View mode: basic / threaded / horizontal-split · Log in · Help
February 28, 2013
Re: Proposal for SentinelInputRange
28-Feb-2013 21:09, Steven Schveighoffer пишет:
> On Thu, 28 Feb 2013 11:43:06 -0500, Walter Bright
> <newshound2@digitalmars.com> wrote:
>
>> On 2/28/2013 6:59 AM, Andrei Alexandrescu wrote:
>>> On 2/28/13 2:37 AM, deadalnix wrote:
>>>> I don't see how defining a specific sentinel range here helps.
>>>
>>> On first blush I agree. It may as well be a range that by convention is
>>> sentinel-terminated, and there's calls to front and popFront but
>>> never to empty.
>>
>>
>> Consider the following code from lexer.c:
>>
>>     p++;
>>     switch (*p)
>>
>> Written using an InputRange:
>>
>>     popFront();
>>     switch (front)
>>
>> That code is INVALID. This is why a SentinelInputRange is necessary.
>> You can't just use an InputRange in an invalid manner by convention.
>
> Does switch(*p) include a case for 0?  If so, wouldn't it be equivalent
> to say if(empty) /* do stuff that case 0 does */ else switch(front)
>
> -Steve

No as a compiler will take it (or may depending on its brain) that 0 is 
what you want to test *first*. It may speed things up if branch is 
almost always taken but its not the case with sentinel. Thus its jsut 
dead code that needs to be decoded, evalutated and skipped (as 
predicated) *before* doing switch jump.

In fact some people avoid the overhead of switch by placing one or two 
of highly-frequent branches with tests before the switch (thus avoiding 
indirect branch it entails in these frequent cases).

-- 
Dmitry Olshansky
February 28, 2013
Re: Proposal for SentinelInputRange
On Thu, 28 Feb 2013 12:02:53 -0500, Walter Bright  
<newshound2@digitalmars.com> wrote:

> On 2/28/2013 7:40 AM, Steven Schveighoffer wrote:
>> If you look at lexer.c, case 0 is the first test.
>
> No, it is not. It is actually a table lookup - all done in parallel.
>
>      jmp cases[character]
>

You are comparing the assembly output of your solution with uncompiled D  
code.  Apples and oranges.

Quoting directly from  
https://github.com/D-Programming-Language/dmd/blob/master/src/lexer.c#L479:

        switch (*p)
        {
            case 0:

As several others have pointed out, an optimizer can (and some do) make  
this rewrite automatically.

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.

-Steve
February 28, 2013
Re: Proposal for SentinelInputRange
28-Feb-2013 19:31, Andrei Alexandrescu пишет:
> On 2/28/13 5:54 AM, Walter Bright wrote:
>> On 2/27/2013 11:55 PM, Jonathan M Davis wrote:
>>>> Again, please see how lexer.c works. I assure you, there is no double
>>>> copying going on, nor is there a double test for the terminating 0.
>>>
>>> I know what the lexer does, and remember that it _doesn't_ operate on
>>> ranges,
>>> and there are subtle differences between being able to just use char*
>>> and
>>> trying to handle generic ranges.
>>
>> Hence the need to invent SentinelInputRange.
>
> I don't think the sentinel input range is a blocker for redoing the
> parser (with ranges) in D. This discussion has probably run its course.


> The right thing to do at this point is port the lexer and figure what
> primitives are necessary from its input.
>

No need to port - look at std.d.lexer again. It was revamped and is 
ready for the new round of review I should say. Let's not use the old 
source for the new module and go the long path of :
split off --> port --> patch up --> D-ify & re-write to ranges

Instead we can just tweak the current std.d.lexer a little bit more and 
we have good clean-room lexer written in the idiomatic D. Well, it's 
getting there w.r.t. idiomaticness but it supports ranges including both 
random-access and forward ones (by transparently specializing for each 
one).
-- 
Dmitry Olshansky
February 28, 2013
Re: Proposal for SentinelInputRange
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.

> Then try the lookahead cases I also posted.

You have already stated it gets changed into a jump table.  Such an  
optimization seems possible to me, even with the != 0 check outside the  
switch, even if not all C compilers employ it.

-Steve
February 28, 2013
Re: Proposal for SentinelInputRange
On Thu, 28 Feb 2013 12:13:27 -0500, Dmitry Olshansky  
<dmitry.olsh@gmail.com> wrote:

> No as a compiler will take it (or may depending on its brain) that 0 is  
> what you want to test *first*. It may speed things up if branch is  
> almost always taken but its not the case with sentinel. Thus its jsut  
> dead code that needs to be decoded, evalutated and skipped (as  
> predicated) *before* doing switch jump.

Well, according to lexer.c, case 0 is the first case.  Why does that not  
make the compiler decide to test 0 first?

Answer: it actually doesn't care, the switch compiles to a jump table.   
Which still begs the question, why can't the compiler make the leap to the  
equivalent code with a range?

are these not semantically equivalent?

if(x == 0)
{
   // case for 0
}
else
{
   switch(x)
   {
      case 1:
         // case for 1;
         break;
      case 2:
         // case for 2;
         break;
      ... // cases for everything but 0
   }
}

vs.

switch(x)
{
   case 0:
      // case for 0;
      break;
   case 1:
      // case for 1;
      break;
   case 2:
      // case for 2;
      break;
   ... // cases for everything but 0
}

They seem semantically identical.  It would not be impossible for an  
optimizer to make this leap.

Combined with inlining, the above could be:

if(r.empty)
{
   // case for 0;
}
else
  ...

and still be optimized the same.  I'm not saying it happens, I'm saying  
it's possible.  I have read several posts here claiming that llvm does  
this (I haven't tried this myself, but it sounds likely true).

-Steve
February 28, 2013
Re: Proposal for SentinelInputRange
On Thursday, 28 February 2013 at 17:13:36 UTC, Dmitry Olshansky 
wrote:
> No as a compiler will take it (or may depending on its brain) 
> that 0 is what you want to test *first*. It may speed things up 
> if branch is almost always taken but its not the case with 
> sentinel. Thus its jsut dead code that needs to be decoded, 
> evalutated and skipped (as predicated) *before* doing switch 
> jump.
>
> In fact some people avoid the overhead of switch by placing one 
> or two of highly-frequent branches with tests before the switch 
> (thus avoiding indirect branch it entails in these frequent 
> cases).

That won't work as expected with LLVM and full optimizations, as 
it will combine everything in a switch, unless you use branch 
weight, in which case it can do the reverse : extract common 
cases from the switch.

See : http://llvm.org/docs/BranchWeightMetadata.html

GCC does something similar.

This is another example of how people think they are doing high 
level assembly when in fact, the compiler is changing everything 
behind their back, and not doing at all what they think.
February 28, 2013
Re: Proposal for SentinelInputRange
On 2/28/13 2:32 PM, Steven Schveighoffer wrote:
> On Thu, 28 Feb 2013 12:13:27 -0500, Dmitry Olshansky
> <dmitry.olsh@gmail.com> wrote:
>
>> No as a compiler will take it (or may depending on its brain) that 0
>> is what you want to test *first*. It may speed things up if branch is
>> almost always taken but its not the case with sentinel. Thus its jsut
>> dead code that needs to be decoded, evalutated and skipped (as
>> predicated) *before* doing switch jump.
>
> Well, according to lexer.c, case 0 is the first case.  Why does that not
> make the compiler decide to test 0 first?
>
> Answer: it actually doesn't care, the switch compiles to a jump table.
> Which still begs the question, why can't the compiler make the leap to
> the equivalent code with a range?
>
> are these not semantically equivalent?
>
> if(x == 0)
> {
>     // case for 0
> }
> else
> {
>     switch(x)
>     {
>        case 1:
>           // case for 1;
>           break;
>        case 2:
>           // case for 2;
>           break;
>        ... // cases for everything but 0
>     }
> }
>
> vs.
>
> switch(x)
> {
>     case 0:
>        // case for 0;
>        break;
>     case 1:
>        // case for 1;
>        break;
>     case 2:
>        // case for 2;
>        break;
>     ... // cases for everything but 0
> }
>
> They seem semantically identical.  It would not be impossible for an
> optimizer to make this leap.
>
> Combined with inlining, the above could be:
>
> if(r.empty)
> {
>     // case for 0;
> }
> else
>    ...
>
> and still be optimized the same.  I'm not saying it happens, I'm saying
> it's possible.  I have read several posts here claiming that llvm does
> this (I haven't tried this myself, but it sounds likely true).

It is true. Compiling this Crystal program:

---
def my_fun(num)
  num == 0
end

num = ARGV[0].to_i

if my_fun(num)
  puts 0
else
  case num
  when 1
    puts 1
  when 2
    puts 2
  end
end
---

I see this somewhere in the generated llvm code:

switch i32 %25, label %crystal_main.exit [
    i32 0, label %then.i
    i32 1, label %then16.i
    i32 2, label %then20.i
  ]
February 28, 2013
Re: Proposal for SentinelInputRange
28-Feb-2013 21:38, deadalnix пишет:
> On Thursday, 28 February 2013 at 17:13:36 UTC, Dmitry Olshansky wrote:
>> No as a compiler will take it (or may depending on its brain) that 0
>> is what you want to test *first*. It may speed things up if branch is
>> almost always taken but its not the case with sentinel. Thus its jsut
>> dead code that needs to be decoded, evalutated and skipped (as
>> predicated) *before* doing switch jump.
>>
>> In fact some people avoid the overhead of switch by placing one or two
>> of highly-frequent branches with tests before the switch (thus
>> avoiding indirect branch it entails in these frequent cases).
>
> That won't work as expected with LLVM and full optimizations, as it will
> combine everything in a switch, unless you use branch weight, in which
> case it can do the reverse : extract common cases from the switch.
>
> See : http://llvm.org/docs/BranchWeightMetadata.html
>
> GCC does something similar.
>
> This is another example of how people think they are doing high level
> assembly when in fact, the compiler is changing everything behind their
> back, and not doing at all what they think.

Depends on the brains of compiler like I said. BTW it can't know the 
most frequent branches so jump-table may be actually slower (in some 
cases though they are niche).

-- 
Dmitry Olshansky
February 28, 2013
Re: Proposal for SentinelInputRange
28-Feb-2013 21:38, deadalnix пишет:
> On Thursday, 28 February 2013 at 17:13:36 UTC, Dmitry Olshansky wrote:
>> No as a compiler will take it (or may depending on its brain) that 0
>> is what you want to test *first*. It may speed things up if branch is
>> almost always taken but its not the case with sentinel. Thus its jsut
>> dead code that needs to be decoded, evalutated and skipped (as
>> predicated) *before* doing switch jump.
>>
>> In fact some people avoid the overhead of switch by placing one or two
>> of highly-frequent branches with tests before the switch (thus
>> avoiding indirect branch it entails in these frequent cases).
>
> That won't work as expected with LLVM and full optimizations, as it will
> combine everything in a switch, unless you use branch weight, in which
> case it can do the reverse : extract common cases from the switch.
>
> See : http://llvm.org/docs/BranchWeightMetadata.html
>
Mn I missed this point. Seems cool unlike relying on it doing magic 
behind the senescence. Then I stand corrected.

> GCC does something similar.
>



-- 
Dmitry Olshansky
February 28, 2013
Re: Proposal for SentinelInputRange
On 02/28/2013 05:48 PM, Dmitry Olshansky wrote:
> ...
>
> line 300:
>      case 0x1A:          // ^Z means end of file
>      case 0:
>                          break;
>
> On the lines you noted it claimed that that 0x1a is outdate. Along with
> the fact that you allocate filesize+2 and fill the last 2 bytes with zeros.
>
> In any case I see 0 and 0x1a as 2 values that act like sentinels i.e. a
> tuple. And this is what spec says - any one of them is a sentinel.
> Correct me if I'm wrong.
>

A sentinel is some data the original data is augmented with in order to 
simplify its processing.

The lexer acts the same on 0x1A and 0, but only the additional 0 at the 
end which does not occur in the input is the sentinel. The lexer may 
even encounter a 0 that is not a sentinel.
6 7 8 9 10 11 12 13 14
Top | Discussion index | About this forum | D home