February 28, 2013
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
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
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
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
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
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
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
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
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
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Top | Discussion index | About this forum | D home