www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Proposal for SentinelInputRange

reply Walter Bright <newshound2 digitalmars.com> writes:
A SentinelInputRange is an InputRange with the following additions:

1. a compile time property 'sentinel' that is the terminating value of the range
2. empty is defined as: empty = (front == sentinel)
3. it is not necessary for empty to be called before front

A C style 0-terminated string is an example of a SentinelInputRange.

The additions to std.range would be:

1. isSentinelInputRange(T) which returns true if T is a SentinelInputRange
2. a unittest
3. documentation of this

An addition to std.string would be a function that takes a char* and returns a 
SentinelInputRange.

Motivation:
1. easy conversion of C strings to ranges
2. necessary for a fast implementation of a lexer

Any takers?
Feb 27 2013
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 02/28/2013 02:11 AM, Walter Bright wrote:

 A SentinelInputRange is an InputRange with the following additions:

 1. a compile time property 'sentinel' that is the terminating value of
 the range
 2. empty is defined as: empty = (front == sentinel)
 3. it is not necessary for empty to be called before front

 A C style 0-terminated string is an example of a SentinelInputRange.

 The additions to std.range would be:

 1. isSentinelInputRange(T) which returns true if T is a SentinelInputRange
 2. a unittest
 3. documentation of this

 An addition to std.string would be a function that takes a char* and
 returns a SentinelInputRange.

 Motivation:
 1. easy conversion of C strings to ranges
 2. necessary for a fast implementation of a lexer

 Any takers?



This is not general enough. The concept is not exclusive to input ranges.
Feb 27 2013
parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Thursday, 28 February 2013 at 01:14:31 UTC, Timon Gehr wrote:

 On 02/28/2013 02:11 AM, Walter Bright wrote:

 A SentinelInputRange is an InputRange with the following 
 additions:

 1. a compile time property 'sentinel' that is the terminating 
 value of
 the range
 2. empty is defined as: empty = (front == sentinel)
 3. it is not necessary for empty to be called before front

 A C style 0-terminated string is an example of a 
 SentinelInputRange.

 The additions to std.range would be:

 1. isSentinelInputRange(T) which returns true if T is a 
 SentinelInputRange
 2. a unittest
 3. documentation of this

 An addition to std.string would be a function that takes a 
 char* and
 returns a SentinelInputRange.

 Motivation:
 1. easy conversion of C strings to ranges
 2. necessary for a fast implementation of a lexer

 Any takers?



 This is not general enough. The concept is not exclusive to 
 input ranges.


I presume you're remembering that if something is a forward, 
bidirectional or random access range it is also an input range.

What further generality would you want?
Feb 27 2013
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 02/28/2013 02:18 AM, John Colvin wrote:

 On Thursday, 28 February 2013 at 01:14:31 UTC, Timon Gehr wrote:

 On 02/28/2013 02:11 AM, Walter Bright wrote:

 A SentinelInputRange is an InputRange with the following additions:

 1. a compile time property 'sentinel' that is the terminating value of
 the range
 2. empty is defined as: empty = (front == sentinel)
 3. it is not necessary for empty to be called before front

 A C style 0-terminated string is an example of a SentinelInputRange.

 The additions to std.range would be:

 1. isSentinelInputRange(T) which returns true if T is a
 SentinelInputRange
 2. a unittest
 3. documentation of this

 An addition to std.string would be a function that takes a char* and
 returns a SentinelInputRange.

 Motivation:
 1. easy conversion of C strings to ranges
 2. necessary for a fast implementation of a lexer

 Any takers?



 This is not general enough. The concept is not exclusive to input ranges.


 I presume you're remembering that if something is a forward,
 bidirectional or random access range it is also an input range.

 What further generality would you want?


Never mind. I was confused.
Feb 27 2013
prev sibling next sibling parent reply "Zach the Mystic" <reachBUTMINUSTHISzach gOOGLYmail.com> writes:
On Thursday, 28 February 2013 at 01:12:19 UTC, Walter Bright 
wrote:

 A SentinelInputRange is an InputRange with the following 
 additions:

 1. a compile time property 'sentinel' that is the terminating 
 value of the range
 2. empty is defined as: empty = (front == sentinel)
 3. it is not necessary for empty to be called before front

 A C style 0-terminated string is an example of a 
 SentinelInputRange.

 The additions to std.range would be:

 1. isSentinelInputRange(T) which returns true if T is a 
 SentinelInputRange
 2. a unittest
 3. documentation of this

 An addition to std.string would be a function that takes a 
 char* and returns a SentinelInputRange.

 Motivation:
 1. easy conversion of C strings to ranges
 2. necessary for a fast implementation of a lexer

 Any takers?


Seems smart. Patches up a hole in the armor of Ranges. What if 
more than one value can end the range, EOF, '\0'?
Feb 27 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 2/27/2013 5:53 PM, Zach the Mystic wrote:

 What if more than one
 value can end the range, EOF, '\0'?


I have never seen a need for that.
Feb 27 2013
next sibling parent reply "Zach the Mystic" <reachBUTMINUSTHISzach gOOGLYmail.com> writes:
On Thursday, 28 February 2013 at 01:56:33 UTC, Walter Bright 
wrote:

 On 2/27/2013 5:53 PM, Zach the Mystic wrote:

 What if more than one
 value can end the range, EOF, '\0'?


 I have never seen a need for that.


Do you mean that you've never seen software that uses that, or 
that you've never been convinced that such software couldn't be 
made simpler?
Feb 27 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 2/27/2013 6:01 PM, Zach the Mystic wrote:

 On Thursday, 28 February 2013 at 01:56:33 UTC, Walter Bright wrote:

 On 2/27/2013 5:53 PM, Zach the Mystic wrote:

 What if more than one
 value can end the range, EOF, '\0'?


 I have never seen a need for that.


 Do you mean that you've never seen software that uses that, or that you've
never
 been convinced that such software couldn't be made simpler?


Pretty much both. For example, often a foreach loop will exit either when it 
runs out of data or some other condition is met. I don't see a need to work
both 
of those conditions into the definition of a range.
Feb 27 2013
parent reply "Zach the Mystic" <reachBUTMINUSTHISzach gOOGLYmail.com> writes:
On Thursday, 28 February 2013 at 03:37:25 UTC, Walter Bright 
wrote:

 On 2/27/2013 6:01 PM, Zach the Mystic wrote:

 On Thursday, 28 February 2013 at 01:56:33 UTC, Walter Bright 
 wrote:

 On 2/27/2013 5:53 PM, Zach the Mystic wrote:

 What if more than one
 value can end the range, EOF, '\0'?


 I have never seen a need for that.


 Do you mean that you've never seen software that uses that, or 
 that you've never
 been convinced that such software couldn't be made simpler?


 Pretty much both. For example, often a foreach loop will exit 
 either when it runs out of data or some other condition is met. 
 I don't see a need to work both of those conditions into the 
 definition of a range.


My understanding of the logic of Sentinel Ranges so far is that 
switch statements and other control flow can proceed eagerly, 
because "go" values can be checked before the sentinel "stop" 
value, and "!empty" is known implicitly. I don't know exactly 
where the speed benefits of having a single "stop" value known at 
compile time come from.

Is this design focused more on your knowledge of how the compiler 
optimizes machine code, or on something which can be grasped at a 
higher level?
Feb 27 2013
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 2/27/2013 8:53 PM, Zach the Mystic wrote:

 My understanding of the logic of Sentinel Ranges so far is that switch
 statements and other control flow can proceed eagerly, because "go" values can
 be checked before the sentinel "stop" value, and "!empty" is known implicitly.
I
 don't know exactly where the speed benefits of having a single "stop" value
 known at compile time come from.

 Is this design focused more on your knowledge of how the compiler optimizes
 machine code, or on something which can be grasped at a higher level?


Take a look at lexer.c.

With an InputRange, reading a character from a 0 terminated string requires two 
read operations. A SentinalInputRange requires only one.
Feb 27 2013
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Thursday, 28 February 2013 at 04:57:08 UTC, Walter Bright 
wrote:

 On 2/27/2013 8:53 PM, Zach the Mystic wrote:

 My understanding of the logic of Sentinel Ranges so far is 
 that switch
 statements and other control flow can proceed eagerly, because 
 "go" values can
 be checked before the sentinel "stop" value, and "!empty" is 
 known implicitly. I
 don't know exactly where the speed benefits of having a single 
 "stop" value
 known at compile time come from.

 Is this design focused more on your knowledge of how the 
 compiler optimizes
 machine code, or on something which can be grasped at a higher 
 level?


 Take a look at lexer.c.

 With an InputRange, reading a character from a 0 terminated 
 string requires two read operations. A SentinalInputRange 
 requires only one.


If the range define empty with something like front == sentinel, 
the inliner should kick in a reduce the whole stuff to only one 
read, no ?
Feb 27 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 2/27/2013 9:20 PM, deadalnix wrote:

 If the range define empty with something like front == sentinel, the inliner
 should kick in a reduce the whole stuff to only one read, no ?


     auto c = front;
     if (c == sentinel || c == XX)

is two reads. This may not seem important, but when you want high speed, it can 
halve it.
Feb 27 2013
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Thursday, 28 February 2013 at 05:28:47 UTC, Walter Bright 
wrote:

 On 2/27/2013 9:20 PM, deadalnix wrote:

 If the range define empty with something like front == 
 sentinel, the inliner
 should kick in a reduce the whole stuff to only one read, no ?


     auto c = front;
     if (c == sentinel || c == XX)

 is two reads. This may not seem important, but when you want 
 high speed, it can halve it.


Don't you have to check for both all the time ? You have to check 
for the sentinel anyway.
Feb 27 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 2/27/2013 10:02 PM, deadalnix wrote:

 On Thursday, 28 February 2013 at 05:28:47 UTC, Walter Bright wrote:

 On 2/27/2013 9:20 PM, deadalnix wrote:

 If the range define empty with something like front == sentinel, the inliner
 should kick in a reduce the whole stuff to only one read, no ?


     auto c = front;
     if (c == sentinel || c == XX)

 is two reads. This may not seem important, but when you want high speed, it
 can halve it.


 Don't you have to check for both all the time ? You have to check for the
 sentinel anyway.


I suggest again taking a look at the dmd source lexer.c for how to do it. There 
is no extra check.
Feb 27 2013
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Thursday, 28 February 2013 at 07:22:53 UTC, Walter Bright 
wrote:

 On 2/27/2013 10:02 PM, deadalnix wrote:

 On Thursday, 28 February 2013 at 05:28:47 UTC, Walter Bright 
 wrote:

 On 2/27/2013 9:20 PM, deadalnix wrote:

 If the range define empty with something like front == 
 sentinel, the inliner
 should kick in a reduce the whole stuff to only one read, no 
 ?


    auto c = front;
    if (c == sentinel || c == XX)

 is two reads. This may not seem important, but when you want 
 high speed, it
 can halve it.


 Don't you have to check for both all the time ? You have to 
 check for the
 sentinel anyway.


 I suggest again taking a look at the dmd source lexer.c for how 
 to do it. There is no extra check.


I did, in fact I know it for quite a while.

It does check for sentinel in many places (and it has to). How is 
it better than a empty property defined as front == sentinel ?

For instance,

if(!r.empty) {
    switch(r.front) {
        // cases
    }

    // somecode
} else {
     // error code
}

Will be optimized by adding a case for the sentinel in the switch 
(if dmd don't, then it has to be fixed, LLVM is definitively able 
to do stuff like that, and I didn't checked, but I'd bet that GCC 
can do it as well) in the given way :

switch(r.front) {
     case sentinel :
        // error code
        goto Label;

     // cases
}

// somecode

Label:

I don't see how defining a specific sentinel range here helps.
Feb 27 2013
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 2/27/2013 11:37 PM, deadalnix wrote:

 It does check for sentinel in many places (and it has to).


No, it doesn't. I suggest examining line 481 of lexer.c. Then examine line 558 
and 559.

https://github.com/D-Programming-Language/dmd/blob/master/src/lexer.c
Feb 28 2013
next sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
On Thursday, 28 February 2013 at 10:37:35 UTC, Walter Bright 
wrote:

 On 2/27/2013 11:37 PM, deadalnix wrote:

 It does check for sentinel in many places (and it has to).


 No, it doesn't. I suggest examining line 481 of lexer.c. Then 
 examine line 558 and 559.

 https://github.com/D-Programming-Language/dmd/blob/master/src/lexer.c


escapeSequence does check for it.
Feb 28 2013
parent Walter Bright <newshound2 digitalmars.com> writes:
On 2/28/2013 2:42 AM, deadalnix wrote:

 On Thursday, 28 February 2013 at 10:37:35 UTC, Walter Bright wrote:

 On 2/27/2013 11:37 PM, deadalnix wrote:

 It does check for sentinel in many places (and it has to).


 No, it doesn't. I suggest examining line 481 of lexer.c. Then examine line 558
 and 559.

 https://github.com/D-Programming-Language/dmd/blob/master/src/lexer.c


 escapeSequence does check for it.


Note the lookahead is done without checking first. This is the salient point. A 
sentinel means you are guaranteed to always be able to look one character ahead 
without checking.

This is used all over the lexer.

The other InputRange forms do not allow peeking ahead without testing *first*.
Feb 28 2013
prev sibling parent Jacob Carlborg <doob me.com> writes:
On 2013-02-28 11:37, Walter Bright wrote:


 No, it doesn't. I suggest examining line 481 of lexer.c. Then examine
 line 558 and 559.

 https://github.com/D-Programming-Language/dmd/blob/master/src/lexer.c


You know that you can link to a specific line by clicking on it in the 
margin.

-- 
/Jacob Carlborg
Feb 28 2013
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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.

Andrei
Feb 28 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
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.
Feb 28 2013
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
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
Feb 28 2013
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
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
Feb 28 2013
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
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
Feb 28 2013
parent Ary Borenszweig <ary esperanto.org.ar> writes:
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
   ]
Feb 28 2013
prev sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
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.
Feb 28 2013
next sibling parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
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
Feb 28 2013
prev sibling parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
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
Feb 28 2013
prev sibling parent FG <home fgda.pl> writes:
On 2013-02-28 17:43, Walter Bright wrote:

 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.



I do not understand... Why make a special type of InputRange when you can 
achieve exactly that with a normal string with an added extra '\0' at the end 
and then use it without any calls to empty():

while(1) {
     ...
     popFront();
     switch(front) {
         case '\0': return;
         ...
     }
}

Cstrings are a very special case because we know the terminator beforehand and 
the check is trivial CPU-wise.
Feb 28 2013
prev sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Thursday, February 28, 2013 05:53:13 Zach the Mystic wrote:

 My understanding of the logic of Sentinel Ranges so far is that
 switch statements and other control flow can proceed eagerly,
 because "go" values can be checked before the sentinel "stop"
 value, and "!empty" is known implicitly. I don't know exactly
 where the speed benefits of having a single "stop" value known at
 compile time come from.


Because the case value needs to be known at compile time, but even if it 
didn't have to be, it would be less efficient to have to call a function for it 
than it would be to have a value known at compile time.


 Is this design focused more on your knowledge of how the compiler
 optimizes machine code, or on something which can be grasped at a
 higher level?


I think that it's simply a matter of looking at how often empty has to be 
called in the lexer if you don't have a sentinel value. Most every time that 
you pop front, you'll have to check empty, whereas with a sentinel value, 
you'll almost never have to check it. That saves at least one operation for 
every character that's lexed.

Now, given that you're going to have to wrap any range in order for to be 
sentinel range (unless it was designed as one in the first place), in most 
cases, you're going to be stuck checking empty all the time anyway. For 
strings wrapped in a sentinel range, you can avoid it, because you can just 
make its last element 0 (though that may mean reallocating the entire string 
depending on whether you can append 0 to it without reallocating). But you're 
still stuck wrapping it.

I suspect that it would just be better to special case strings rather than to 
create this sentinel range idea, because I really don't see any benefit for it 
outside of strings, and it's not like it's hard to just use a couple of static 
ifs to avoid the check for empty and add the sentinel case when you're 
operating on strings.

- Jonathan M Davis
Feb 27 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 2/27/2013 9:06 PM, Jonathan M Davis wrote:

 Now, given that you're going to have to wrap any range in order for to be
 sentinel range


No. Look at how lexer.c is fed data.
Feb 27 2013
parent reply Jacob Carlborg <doob me.com> writes:
On 2013-02-28 06:13, Walter Bright wrote:


 No. Look at how lexer.c is fed data.


C strings have a sentinel from the beginning, '\0'.

-- 
/Jacob Carlborg
Feb 28 2013
parent Walter Bright <newshound2 digitalmars.com> writes:
On 2/28/2013 12:20 AM, Jacob Carlborg wrote:

 On 2013-02-28 06:13, Walter Bright wrote:


 No. Look at how lexer.c is fed data.


 C strings have a sentinel from the beginning, '\0'.


Look at how the source file is transformed into a 0 terminated input. Files are 
not C strings.

There are no extra copies and no extra tests.
Feb 28 2013
prev sibling next sibling parent reply "timotheecour" <thelastmammoth gmail.com> writes:
On Thursday, 28 February 2013 at 01:56:33 UTC, Walter Bright 
wrote:

 On 2/27/2013 5:53 PM, Zach the Mystic wrote:

 What if more than one
 value can end the range, EOF, '\0'?


 I have never seen a need for that.


how about a predicate isSentinel instead of a fixed sentinel 
value?
That'd allow more flexibility such as more than one sentinel 
value.
Feb 27 2013
next sibling parent reply Michel Fortin <michel.fortin michelf.ca> writes:
On 2013-02-28 02:05:20 +0000, "timotheecour" <thelastmammoth gmail.com> said:


 On Thursday, 28 February 2013 at 01:56:33 UTC, Walter Bright wrote:

 On 2/27/2013 5:53 PM, Zach the Mystic wrote:

 What if more than one
 value can end the range, EOF, '\0'?


 
 I have never seen a need for that.


 
 how about a predicate isSentinel instead of a fixed sentinel value?
 That'd allow more flexibility such as more than one sentinel value.


Not usable in a switch/case statement.

-- 
Michel Fortin
michel.fortin michelf.ca
http://michelf.ca/
Feb 27 2013
parent reply "timotheecour" <thelastmammoth gmail.com> writes:
 how about a predicate isSentinel instead of a fixed sentinel 
 value?
 That'd allow more flexibility such as more than one sentinel 
 value.


 Not usable in a switch/case statement.


why is that needed?
Feb 27 2013
parent Walter Bright <newshound2 digitalmars.com> writes:
On 2/27/2013 6:10 PM, timotheecour wrote:

 how about a predicate isSentinel instead of a fixed sentinel value?
 That'd allow more flexibility such as more than one sentinel value.


 Not usable in a switch/case statement.


 why is that needed?


Look at the lexer.c source code.

tl,dr: PERFORMANCE!
Feb 27 2013
prev sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 2/27/2013 6:05 PM, timotheecour wrote:

 On Thursday, 28 February 2013 at 01:56:33 UTC, Walter Bright wrote:

 On 2/27/2013 5:53 PM, Zach the Mystic wrote:

 What if more than one
 value can end the range, EOF, '\0'?


 I have never seen a need for that.


 how about a predicate isSentinel instead of a fixed sentinel value?
 That'd allow more flexibility such as more than one sentinel value.


A fixed sentinel value makes it clear that it should be a compile time value
for 
performance reasons. If it was a function, then there's really not much 
advantage to having a SentinelInputRange.
Feb 27 2013
prev sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
28-Feb-2013 05:56, Walter Bright пишет:

 On 2/27/2013 5:53 PM, Zach the Mystic wrote:

 What if more than one
 value can end the range, EOF, '\0'?


 I have never seen a need for that.


Inside of the D lexer:

EOF is 0 or 0x1a :)

-- 
Dmitry Olshansky
Feb 27 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 2/27/2013 11:02 PM, Dmitry Olshansky wrote:

 Inside of the D lexer:

 EOF is 0 or 0x1a :)


There is always a terminating 0, even if the file ends in 0x1a.

(The 0x1A comes from some old editors that end a file with a control Z.)
Feb 27 2013
parent reply Jacob Carlborg <doob me.com> writes:
On 2013-02-28 08:23, Walter Bright wrote:


 There is always a terminating 0, even if the file ends in 0x1a.

 (The 0x1A comes from some old editors that end a file with a control Z.)


http://dlang.org/lex.html, "End of File" shows this:

EndOfFile:
     physical end of the file
     \u0000
     \u001A

Doesn't that mean that the input is empty if the file is empty, \u0000 
or \u001A is encountered?

-- 
/Jacob Carlborg
Feb 28 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 2/28/2013 12:25 AM, Jacob Carlborg wrote:

 On 2013-02-28 08:23, Walter Bright wrote:


 There is always a terminating 0, even if the file ends in 0x1a.

 (The 0x1A comes from some old editors that end a file with a control Z.)


 http://dlang.org/lex.html, "End of File" shows this:

 EndOfFile:
      physical end of the file
      \u0000
      \u001A

 Doesn't that mean that the input is empty if the file is empty, \u0000 or
\u001A
 is encountered?


Please follow the source code from file to input to the lexer.

https://github.com/D-Programming-Language/dmd/blob/master/src/root/root.c

line 1012 and 1038
Feb 28 2013
next sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2013-02-28 11:44, Walter Bright wrote:


 Please follow the source code from file to input to the lexer.

 https://github.com/D-Programming-Language/dmd/blob/master/src/root/root.c

 line 1012 and 1038


I have no doubt in what you're saying. The spec just didn't look 
accurate according to what you said.

-- 
/Jacob Carlborg
Feb 28 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 2/28/2013 5:40 AM, Jacob Carlborg wrote:

 I have no doubt in what you're saying. The spec just didn't look accurate
 according to what you said.


I don't know what you mean.
Feb 28 2013
parent Jacob Carlborg <doob me.com> writes:
On 2013-02-28 17:31, Walter Bright wrote:


 I don't know what you mean.


I'm just saying that you and the spec disagree. At least that's how I 
read the spec.

-- 
/Jacob Carlborg
Feb 28 2013
prev sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
28-Feb-2013 14:44, Walter Bright пишет:

 On 2/28/2013 12:25 AM, Jacob Carlborg wrote:

 On 2013-02-28 08:23, Walter Bright wrote:


 There is always a terminating 0, even if the file ends in 0x1a.

 (The 0x1A comes from some old editors that end a file with a control Z.)


 http://dlang.org/lex.html, "End of File" shows this:

 EndOfFile:
      physical end of the file
      \u0000
      \u001A

 Doesn't that mean that the input is empty if the file is empty, \u0000
 or \u001A
 is encountered?






 Please follow the source code from file to input to the lexer.


Source as spec is no good. Either change the spec or  admit that having 
a tuple of sentinels as manifest constant is fine. In any case constant 
tuples are easily unrolled into case statements.


 https://github.com/D-Programming-Language/dmd/blob/master/src/root/root.c

 line 1012 and 1038



-- 
Dmitry Olshansky
Feb 28 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 2/28/2013 7:38 AM, Dmitry Olshansky wrote:

 28-Feb-2013 14:44, Walter Bright пишет:

 On 2/28/2013 12:25 AM, Jacob Carlborg wrote:

 On 2013-02-28 08:23, Walter Bright wrote:


 There is always a terminating 0, even if the file ends in 0x1a.

 (The 0x1A comes from some old editors that end a file with a control Z.)


 http://dlang.org/lex.html, "End of File" shows this:

 EndOfFile:
      physical end of the file
      \u0000
      \u001A

 Doesn't that mean that the input is empty if the file is empty, \u0000
 or \u001A
 is encountered?






 Please follow the source code from file to input to the lexer.


 Source as spec is no good. Either change the spec or  admit that having a tuple
 of sentinels as manifest constant is fine. In any case constant tuples are
 easily unrolled into case statements.


The spec is correct, so is the code, and tuple sentinels are entirely
unnecessary.
Feb 28 2013
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
28-Feb-2013 20:33, Walter Bright пишет:

 On 2/28/2013 7:38 AM, Dmitry Olshansky wrote:

 28-Feb-2013 14:44, Walter Bright пишет:

 On 2/28/2013 12:25 AM, Jacob Carlborg wrote:

 On 2013-02-28 08:23, Walter Bright wrote:


 There is always a terminating 0, even if the file ends in 0x1a.

 (The 0x1A comes from some old editors that end a file with a
 control Z.)


 http://dlang.org/lex.html, "End of File" shows this:

 EndOfFile:
      physical end of the file
      \u0000
      \u001A

 Doesn't that mean that the input is empty if the file is empty, \u0000
 or \u001A
 is encountered?






 Please follow the source code from file to input to the lexer.


 Source as spec is no good. Either change the spec or  admit that
 having a tuple
 of sentinels as manifest constant is fine. In any case constant tuples
 are
 easily unrolled into case statements.


 The spec is correct, so is the code, and tuple sentinels are entirely
 unnecessary.


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.

-- 
Dmitry Olshansky
Feb 28 2013
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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.
Feb 28 2013
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
28-Feb-2013 22:08, Timon Gehr пишет:

 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.


I thought 0 was proposed as such. Might have misunderstood the proposition.


 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.



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.

If that's the intended behavior I fail to decipher it from  here:
http://dlang.org/lex.html#EndOfFile


 The lexer may
 even encounter a 0 that is not a sentinel.



-- 
Dmitry Olshansky
Feb 28 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
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.
Feb 28 2013
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
01-Mar-2013 02:57, Walter Bright пишет:

 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.


So I thought.

Well, I can't see the difference between 2 sentinel values: both 0 and 
0x1A has to both work. For me that means both values have to be accepted 
as sentinels I'd call that a tuple of sentinels.


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


Should I say you are getting cryptic?

-- 
Dmitry Olshansky
Feb 28 2013
parent Jacob Carlborg <doob me.com> writes:
On 2013-03-01 07:12, Dmitry Olshansky wrote:


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


 So I thought.

 Well, I can't see the difference between 2 sentinel values: both 0 and
 0x1A has to both work. For me that means both values have to be accepted
 as sentinels I'd call that a tuple of sentinels.


I think I understand how Walter things here. The D code always ends with 
'0' or '0x1A'. Regardless of what the end character is, DMD will always 
add an '0' to the end.

But you do need to check for both 0 and 0x1A.

-- 
/Jacob Carlborg
Feb 28 2013
prev sibling next sibling parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Thursday, 28 February 2013 at 01:12:19 UTC, Walter Bright 
wrote:

 A SentinelInputRange is an InputRange with the following 
 additions:

 1. a compile time property 'sentinel' that is the terminating 
 value of the range
 2. empty is defined as: empty = (front == sentinel)
 3. it is not necessary for empty to be called before front

 A C style 0-terminated string is an example of a 
 SentinelInputRange.

 The additions to std.range would be:

 1. isSentinelInputRange(T) which returns true if T is a 
 SentinelInputRange
 2. a unittest
 3. documentation of this

 An addition to std.string would be a function that takes a 
 char* and returns a SentinelInputRange.

 Motivation:
 1. easy conversion of C strings to ranges
 2. necessary for a fast implementation of a lexer

 Any takers?


Why must sentinel be known at compile time? I don't see what's in 
the way of it being a runtime argument.
Feb 27 2013
next sibling parent Marco Leise <Marco.Leise gmx.de> writes:
Am Thu, 28 Feb 2013 05:01:39 +0100
schrieb "John Colvin" <john.loughran.colvin gmail.com>:


 On Thursday, 28 February 2013 at 01:12:19 UTC, Walter Bright 
 wrote:

 A SentinelInputRange is an InputRange with the following 
 additions:

 1. a compile time property 'sentinel' that is the terminating 
 value of the range
 2. empty is defined as: empty = (front == sentinel)
 3. it is not necessary for empty to be called before front

 A C style 0-terminated string is an example of a 
 SentinelInputRange.

 The additions to std.range would be:

 1. isSentinelInputRange(T) which returns true if T is a 
 SentinelInputRange
 2. a unittest
 3. documentation of this

 An addition to std.string would be a function that takes a 
 char* and returns a SentinelInputRange.

 Motivation:
 1. easy conversion of C strings to ranges
 2. necessary for a fast implementation of a lexer

 Any takers?


 
 Why must sentinel be known at compile time? I don't see what's in 
 the way of it being a runtime argument.


Possibly because a 0 check can be reduced to a simple bit
test on the CPU (and you need to do that often and possibly in
several source code locations when parsing long strings). A
runtime value means a memory read and comparison every time!
(For simple loops the compiler will keep the value in a
register, but that's not generally the case.)

-- 
Marco
Feb 27 2013
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 2/27/2013 8:01 PM, John Colvin wrote:

 Why must sentinel be known at compile time? I don't see what's in the way of it
 being a runtime argument.


Performance!

It should be usable as a case in a switch statement.
Feb 27 2013
next sibling parent reply "Andrej Mitrovic" <andrej.mitrovich gmail.com> writes:
On Thursday, 28 February 2013 at 04:58:23 UTC, Walter Bright 
wrote:

 On 2/27/2013 8:01 PM, John Colvin wrote:

 Why must sentinel be known at compile time? I don't see what's 
 in the way of it
 being a runtime argument.


 Performance!

 It should be usable as a case in a switch statement.


Little did you know about this bug: 
http://d.puremagic.com/issues/show_bug.cgi?id=5862

:)

But I guess this defeats the purpose of the switch statement 
(i.e. optimizations).

Btw can we get a clear opinion on whether 5862 is an actual bug 
that needs to be fixed?
Feb 27 2013
parent Walter Bright <newshound2 digitalmars.com> writes:
On 2/27/2013 9:03 PM, Andrej Mitrovic wrote:

 But I guess this defeats the purpose of the switch statement (i.e.
optimizations).


It certainly does defeat the performance of the switch statement, and hence the 
point of the sentinel.


 Btw can we get a clear opinion on whether 5862 is an actual bug that needs to
be
 fixed?


I'd have to investigate.
Feb 27 2013
prev sibling parent reply Ary Borenszweig <ary esperanto.org.ar> writes:
On 2/28/13 1:57 AM, Walter Bright wrote:

 On 2/27/2013 8:01 PM, John Colvin wrote:

 Why must sentinel be known at compile time? I don't see what's in the
 way of it
 being a runtime argument.


 Performance!

 It should be usable as a case in a switch statement.


Isn't it possible for the optimizer to inline the function call and then 
combine the next ifs?

if (isSentinel(value)) {
} else {
   switch(value) {
   case ...
   }
}
Feb 28 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 2/28/2013 6:48 AM, Ary Borenszweig wrote:

 On 2/28/13 1:57 AM, Walter Bright wrote:

 On 2/27/2013 8:01 PM, John Colvin wrote:

 Why must sentinel be known at compile time? I don't see what's in the
 way of it
 being a runtime argument.


 Performance!

 It should be usable as a case in a switch statement.


 Isn't it possible for the optimizer to inline the function call and then
combine
 the next ifs?

 if (isSentinel(value)) {
 } else {
    switch(value) {
    case ...
    }
 }


1. I don't know of any C compiler that would do that.

2. There are other cases, as I pointed out to deadalnix.

3. You still can't do lookahead without extra checks

Once again, guys, have a look at lexer.c at the lines I pointed out.
Feb 28 2013
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Thursday, 28 February 2013 at 16:36:44 UTC, Walter Bright 
wrote:

 On 2/28/2013 6:48 AM, Ary Borenszweig wrote:

 On 2/28/13 1:57 AM, Walter Bright wrote:

 On 2/27/2013 8:01 PM, John Colvin wrote:

 Why must sentinel be known at compile time? I don't see 
 what's in the
 way of it
 being a runtime argument.


 Performance!

 It should be usable as a case in a switch statement.


 Isn't it possible for the optimizer to inline the function 
 call and then combine
 the next ifs?

 if (isSentinel(value)) {
 } else {
   switch(value) {
   case ...
   }
 }


 1. I don't know of any C compiler that would do that.


As mentioned, LLVM is able to do this kind of things. I have to 
admit I was quite amazed when I discovered it.


 2. There are other cases, as I pointed out to deadalnix.

 3. You still can't do lookahead without extra checks


You need the actual check to do proper generic D code. But the 
compiler is able to optimize it away via inlining and mecanism 
described in 1.


 Once again, guys, have a look at lexer.c at the lines I pointed 
 out.


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.
Feb 28 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
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;
Feb 28 2013
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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;
Feb 28 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
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.
Feb 28 2013
next sibling parent "deadalnix" <deadalnix gmail.com> writes:
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.
Feb 28 2013
prev sibling parent Jacob Carlborg <doob me.com> writes:
On 2013-03-01 00:23, Walter Bright wrote:


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


Time for some new optimizations for DMC :)

-- 
/Jacob Carlborg
Feb 28 2013
prev sibling next sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
On Thursday, 28 February 2013 at 01:12:19 UTC, Walter Bright 
wrote:

 A SentinelInputRange is an InputRange with the following 
 additions:

 1. a compile time property 'sentinel' that is the terminating 
 value of the range
 2. empty is defined as: empty = (front == sentinel)
 3. it is not necessary for empty to be called before front

 A C style 0-terminated string is an example of a 
 SentinelInputRange.

 The additions to std.range would be:

 1. isSentinelInputRange(T) which returns true if T is a 
 SentinelInputRange
 2. a unittest
 3. documentation of this

 An addition to std.string would be a function that takes a 
 char* and returns a SentinelInputRange.

 Motivation:
 1. easy conversion of C strings to ranges
 2. necessary for a fast implementation of a lexer

 Any takers?


Can you explain what it does buy us ? Is it faster to check for 
the sentinel value that to check for emptiness ?

Is it really handy in generic code ? For instance, if I use a 
switch, the actual sentinel value may be conflicting with other 
element in the switch. How does this kind of problem are solved ? 
Do they are problems in the first place ?
Feb 27 2013
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Thursday, February 28, 2013 05:24:57 deadalnix wrote:

 Can you explain what it does buy us ? Is it faster to check for
 the sentinel value that to check for emptiness ?
 
 Is it really handy in generic code ? For instance, if I use a
 switch, the actual sentinel value may be conflicting with other
 element in the switch. How does this kind of problem are solved ?
 Do they are problems in the first place ?


In the case of a lexer, it allows you to skip checking for empty most of the 
time. You have something like

switch(front)
{
    case '+': ...
    case '>': ...
     ...
    case 0: //do whatever you do at the end
}

So, as far as the switch statement goes, you don't have to worry about whether 
the range is empty or not. The case for 0 takes care of it and will only get 
checked if it actually happens, whereas without the sentinel value, you have 
to check empty every time you pop front.

Now, the only real benefit that I see for this allowing you to make a string 
zero-terminated (which in the case of a lexer would probably mean copying the 
entire file into a new string which has zero on the end). In general, you'll be 
forced to wrap a range in a sentinel range to get this behavior, which means 
that you're _still_ checking empty all the time, because it has to keep 
checking whether it's supposed to make front 0 now. And that probably means 
that it'll be slightly _more_ expensive to do this for anything other than a 
string. That being the case, it might be better to just special case strings 
rather than come up with this whole new range idea.

I'm also not at all covinced that this is generally useful. It may be that 
it's a great idea for lexers, but what other use cases are there? I don't know 
that there isn't one, but I can't think of any. And the _only_ time that it's 
of any real benefit is definitely going to be when ranges are built with this 
idea in the first place rather than wrapping them, which almost guarantees that 
you're just dealing with arrays, which you can always just special case if you 
need this level of efficiency.

Also, I'd point out that even for strings, doing something like this means 
wrapping them, because their empty isn't defined in a manner which works with 
isSentinelRange. Unlike most other cases, the wrapper wouldn't have to keep 
checking for empty (it could just guarantee that the string it was given ended 
with 0 and then say that it's length was one less than the underlying string), 
but you're still dealing with a wrapper and relying on the compiler to 
optimize that cost away. Also, that totally screws with passing the range to 
any functions which special case strings. Those functions would now also have 
to special case the wrapper type if you wanted the extra efficiency that you
get 
from the function understanding that it's a string rather than a range of code 
units or code points (depending on which the sentinel range is claiming it is 
- probably code units in the case of the lexer).

So, I'm inclined to believe that we'd be better off just special casing strings 
in any algorithms that can take advantage of this sort of thing than we would 
be creating this sentinel range idea.

- Jonathan M Davis
Feb 27 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 2/27/2013 8:47 PM, Jonathan M Davis wrote:

 Now, the only real benefit that I see for this allowing you to make a string
 zero-terminated (which in the case of a lexer would probably mean copying the
 entire file into a new string which has zero on the end).


Nawp, there is no extra copy. Take a look at the compiler source. You have to 
read the file into memory anyway - so make the buffer one byte longer, and put
a 
0 at the end.


 In general, you'll be
 forced to wrap a range in a sentinel range to get this behavior, which means
 that you're _still_ checking empty all the time, because it has to keep
 checking whether it's supposed to make front 0 now. And that probably means
 that it'll be slightly _more_ expensive to do this for anything other than a
 string. That being the case, it might be better to just special case strings
 rather than come up with this whole new range idea.


Nope, not necessary to wrap it.



 I'm also not at all covinced that this is generally useful. It may be that
 it's a great idea for lexers, but what other use cases are there?


Anything that walks a C string. Lots of cases for that. Sentinels are often
used 
where high speed processing of data is desired. Google sentinel-terminated data 
for more examples.



 Also, I'd point out that even for strings, doing something like this means
 wrapping them, because their empty isn't defined in a manner which works with
 isSentinelRange.


For D strings, yes, for C strings, no need to wrap them.


 So, I'm inclined to believe that we'd be better off just special casing strings
 in any algorithms that can take advantage of this sort of thing than we would
 be creating this sentinel range idea.


0 terminated C strings are a classic case of this. Another case is a token 
stream ending with an EOF token.
Feb 27 2013
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, February 27, 2013 21:10:15 Walter Bright wrote:

 Also, I'd point out that even for strings, doing something like this means
 wrapping them, because their empty isn't defined in a manner which works
 with isSentinelRange.


 
 For D strings, yes, for C strings, no need to wrap them.


But you have to deal with D strings, not C strings if you're dealing with 
ranges. char* isn't a range. So, unless you're talking about wrapping a char* 
in a range, char* isn't going to work. And simply appending 0 to the end of a 
D string isn't enough, because isSentinelnputRange would fail, because 
std.array.empty doesn't match it. So, you need a wrapper even if it's only to 
pass the template constraint. That being the case, regardless of whether 
you're dealing with char* or string, you need a wrapper.

And what ranges other than strings can take advantage of anything like this? 
There's no way to append a value to range other than chain, which means that 
you're forced to either construct ranges specifically with the idea that 
they'll be used as sentinel ranges (in which case, they're a wrapper around 
whatever they're using to hold the data internally - probably an array - and 
if you're doing that, why not just use an array in the first place?), or you're 
forced to wrap an existing range (which would then require it to check for 
empty on each popFront so that it can make its front be 0 when it's empty).

What are we gaining here that can't be gained by simply using a few static ifs 
to special case strings? And I don't see how this idea is gaining us much of 
anything outside of strings and maybe arrays - both of which have to be 
wrapped in order for their empty to act appropriately (even if they can avoid 
the extra empty checks internally by appending the sentinel value to their 
end). So, why not just special case strings or arrays in the few situations 
where something like this is needed, especially when it would be so easy to 
do?

- Jonathan M Davis
Feb 27 2013
next sibling parent "Zach the Mystic" <reachBUTMINUSTHISzach gOOGLYmail.com> writes:
On Thursday, 28 February 2013 at 05:28:20 UTC, Jonathan M Davis 
wrote:

 What are we gaining here that can't be gained by simply using a 
 few static ifs to special case strings?


That's the question that is swaying me to your side at the 
moment. It's possible that the special performance which Sentinel 
Ranges offer is actually confined to a very narrow band of 
problems which can be dealt with transparently in the existing 
library. In which case the right thing to do is make an 
enhancement request asking for just such performance enhancing 
drugs to be administered. :-)
Feb 27 2013
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 2/27/2013 9:28 PM, Jonathan M Davis wrote:

 But you have to deal with D strings, not C strings if you're dealing with
 ranges. char* isn't a range. So, unless you're talking about wrapping a char*
 in a range, char* isn't going to work. And simply appending 0 to the end of a
 D string isn't enough, because isSentinelnputRange would fail, because
 std.array.empty doesn't match it. So, you need a wrapper even if it's only to
 pass the template constraint. That being the case, regardless of whether
 you're dealing with char* or string, you need a wrapper.


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.



 And what ranges other than strings can take advantage of anything like this?


I've mentioned a couple already in this thread, and I'll add another - an 
interpreter bytecode, you can see an example in the (former) std.regexp. Search 
for "REend".



 What are we gaining here


High speed processing.



So, why not just special case strings or arrays in the few situations
 where something like this is needed, especially when it would be so easy to
 do?


Sentinels structure the code differently.
Feb 27 2013
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, February 27, 2013 23:33:09 Walter Bright wrote:

 On 2/27/2013 9:28 PM, Jonathan M Davis wrote:

 But you have to deal with D strings, not C strings if you're dealing with
 ranges. char* isn't a range. So, unless you're talking about wrapping a
 char* in a range, char* isn't going to work. And simply appending 0 to
 the end of a D string isn't enough, because isSentinelnputRange would
 fail, because std.array.empty doesn't match it. So, you need a wrapper
 even if it's only to pass the template constraint. That being the case,
 regardless of whether you're dealing with char* or string, you need a
 wrapper.


 
 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.

And no, the lexer doesn't have a double test. The place you're going to be 
stuck with a double test is most any range which isn't a string, because such 
ranges won't have sentinel values, and there will be no way to add them (as 
you really can't append to ranges), and so they'll end up being wrapped in a 
SentinelRange which will have to check on each popFront whether the wrapped 
range is now empty making it so that front needs to be the sentinel value. And 
most any range which _was_ designed to have a sentinel value would have to be 
managing its own contents (because otherwise, it would just be back to 
wrapping a range and having to check empty), which likely means that it'll 
just be a thin wrapper around a string or array anyway.

Strings will still need to be wrapped, because they won't pass isSentinelRange 
otherwise, but they won't get any extra checks, because the wrapper can just 
check for 0 on the end and append it if it's not there.


So, why not just special case strings or arrays in the few situations

 where something like this is needed, especially when it would be so easy
 to
 do?


 
 Sentinels structure the code differently.


Given how a lexer works (and I have been working on a lexer off and on 
recently), the only real difference is that you'd just use a couple of static 
ifs like

static if(!isSomeString!R)
{
    if(range.empty)
        break; //or whatever you do at the end
}

static if(isSomeString!R)
{
    case 0:
        break; //or whatever you do at the end
}

So, in the case of a lexer, I don't see sentinel ranges as buying us much. You 
end up having to wrap most any range that you pass to the lexer or whatever 
(including strings so that they'll pass isSentinelRange), you lose out on any 
optimizations of any functions that you call which special-case strings 
(though there probably wouldn't be many of those in a lexer), and all you 
avoid is a couple of static ifs.

The idea of sentinels certainly isn't useless, but anything caring about that 
sort of speed is likely to just use strings or arrays, and those can trivially 
be special cased to avoid unnecessary empty checks and to add the check for 
the sentinel, making the whole sentinel range idea an unnecessary complication 
IMHO.

- Jonathan M Davis
Feb 27 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
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.



 Given how a lexer works (and I have been working on a lexer off and on
 recently), the only real difference is that you'd just use a couple of static
 ifs like

 static if(!isSomeString!R)
 {
      if(range.empty)
          break; //or whatever you do at the end
 }

 static if(isSomeString!R)
 {
      case 0:
          break; //or whatever you do at the end
 }


There are so many places where this would occur, it cries out for a new type.



 So, in the case of a lexer, I don't see sentinel ranges as buying us much. You
 end up having to wrap most any range that you pass to the lexer or whatever
 (including strings so that they'll pass isSentinelRange), you lose out on any
 optimizations of any functions that you call which special-case strings
 (though there probably wouldn't be many of those in a lexer), and all you
 avoid is a couple of static ifs.


And NO, THE SOURCE FILE INPUT IS NEITHER WRAPPED NOR DOUBLE COPIED. Here's how 
it's done:

https://github.com/D-Programming-Language/dmd/blob/master/src/root/root.c

line 1012 and 1038


 The idea of sentinels certainly isn't useless, but anything caring about that
 sort of speed is likely to just use strings or arrays, and those can trivially
 be special cased to avoid unnecessary empty checks and to add the check for
 the sentinel, making the whole sentinel range idea an unnecessary complication
 IMHO.


You can't do efficient lookahead without sentinels, either. Lexers are
sensitive 
to every instruction executed per character read. No sentinels mean double the 
number of instructions per source character.

InputRanges are an abject failure if "anyone caring about speed" is not going
to 
use them. And yes, I care very much about the D lexing speed.
Feb 28 2013
next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Thursday, February 28, 2013 02:54:24 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.
 

 Given how a lexer works (and I have been working on a lexer off and on
 recently), the only real difference is that you'd just use a couple of
 static ifs like
 
 static if(!isSomeString!R)
 {
 
      if(range.empty)
      
          break; //or whatever you do at the end
 
 }
 
 static if(isSomeString!R)
 {
 
      case 0:
          break; //or whatever you do at the end
 
 }


 
 There are so many places where this would occur, it cries out for a new
 type.


And you were just claiming that the lexer checked the sentinel type in only 
one place. If that's indeed the case (and I think that it's quite close to 
being true if it isn't true), then you _wouldn't_ need to use static ifs like 
this in many places. So, which is it? If you need to check the sentinel often 
enough that using static ifs is a problem, then it's probably not buying you 
much of anything over checking empty anyway.


 The idea of sentinels certainly isn't useless, but anything caring about
 that sort of speed is likely to just use strings or arrays, and those can
 trivially be special cased to avoid unnecessary empty checks and to add
 the check for the sentinel, making the whole sentinel range idea an
 unnecessary complication IMHO.


 
 You can't do efficient lookahead without sentinels, either. Lexers are
 sensitive to every instruction executed per character read. No sentinels
 mean double the number of instructions per source character.


But my point is that outside of strings or arrays, you're almost certainly 
stuck with that. Most ranges would have to be wrapped in order to act as a 
sentinel range, and the sentinel range would have to check empty on the 
internal range on every popFront. The only time that a sentinel range would 
buy you anything outside of strings or arrays is when you have a range type 
written specifically to be a sentinel range and which doesn't have to call 
empty on a range internally. But that means that it's going to have to manage 
whatever it's holding internally itself and can't wrap another range - and 
that memory will almost certainly be an array of some sort. And if that's the 
case, what did we buy by wrapping it in a sentinel range? Why not just use the 
array directly?

Pretty much the only type of range which isn't wrapping another range which 
wouldn't have an array internally would be one that was either reading from a 
file (or some other input) as it iterates or one which was generative. In 
either case, you would be unable to put a zero on the end without checking 
whether it was empty with each popFront, meaning that making it a sentinel 
range was pointless. So, pretty much the only ranges which could gain
efficiency 
as sentinel ranges are those that hold arrays internally, meaning that the 
only gain from having the sentinel range over special casing the code on 
strings or arrays is the fact that you won't have to special case strings or 
arrays at all with static ifs or template constraints, but I'm quite convinced 
that in most cases, the number of static ifs involved would be quite few, 
making it quite trivial to special case on strings, meaning that there's 
pretty much no gain in having the sentinel ranges. It just incurs more 
overhead that the compiler must optimize away, because you have to wrap 
strings for them to work as sentinel ranges, or no template constraint will be 
able to detect that they're sentinel ranges. Of course, you could special case 
them so that they're treated as sentinel ranges in spite of that, but if 
you're special casing, why use the sentinel ranges in the first place instead 
of just special casing on strings?


 InputRanges are an abject failure if "anyone caring about speed" is not
 going to use them. And yes, I care very much about the D lexing speed.


Pure input ranges fail utterly as you can't save them, so you get _zero_ 
lookahead unless you start copying their contents somewhere else - which is 
quite expensive in comparison to slicing an array and which complicates the 
code. Forward ranges do better, but the lack of random access can be a killer 
in some cases. For instance, anything involving unicode (which a lexer mostly 
avoids, because it rarely has to decode unicode, but it still happens 
sometimes) requires random access for speed at least some of the time 
(especially when skipping code units), and it makes comparisons faster, 
because you can compare slices at once rather than compare a character and 
then pop it, compare, pop, compare, pop... For the fastest results, you need 
random-access ranges.

There's tons of stuff that's fine with forward ranges (though I seriously 
question the viability of pure input ranges given how insanely limiting is to 
be unable to save their state), but there's also plenty of stuff that needs 
random access, and if you _really_ care about speed, there's a decent chance 
that you need random access (if nothing else, to be able to pop off multiple 
elements at a time). That doesn't necessarily mean that you're using an array, 
but odds are whatever you're using wraps an array if it isn't one. I don't 
think that there's much of anything which is random access without having an 
array or pointer underneath the hood. Reading from a file, I'd be very inclined 
to use something like MmFile or reading the whole file into an array rather 
than trying to wrap in something that's a pure input range. They're just too 
limiting.

- Jonathan M Davis
Feb 28 2013
next sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2013-02-28 12:29, Jonathan M Davis wrote:


 And you were just claiming that the lexer checked the sentinel type in only
 one place. If that's indeed the case (and I think that it's quite close to
 being true if it isn't true), then you _wouldn't_ need to use static ifs like
 this in many places. So, which is it? If you need to check the sentinel often
 enough that using static ifs is a problem, then it's probably not buying you
 much of anything over checking empty anyway.


You pick a sentinel that you need to check for anyway, i.e. null or eof. 
But if you don't manually add the sentinel there's nothing that says 
that the sentinel will be there, and therefore you weed to check for 
empty as well.

-- 
/Jacob Carlborg
Feb 28 2013
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/28/13 8:44 AM, Jacob Carlborg wrote:

 On 2013-02-28 12:29, Jonathan M Davis wrote:


 And you were just claiming that the lexer checked the sentinel type in
 only
 one place. If that's indeed the case (and I think that it's quite
 close to
 being true if it isn't true), then you _wouldn't_ need to use static
 ifs like
 this in many places. So, which is it? If you need to check the
 sentinel often
 enough that using static ifs is a problem, then it's probably not
 buying you
 much of anything over checking empty anyway.


 You pick a sentinel that you need to check for anyway, i.e. null or eof.
 But if you don't manually add the sentinel there's nothing that says
 that the sentinel will be there, and therefore you weed to check for
 empty as well.


auto range = assumeWithSentinel(input);

:o)

I'm only half-joking - the awesomeness of assumeSorted suggests we could 
reuse the pattern elsewhere.


Andrei
Feb 28 2013
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/28/13 6:29 AM, Jonathan M Davis wrote:

 There's tons of stuff that's fine with forward ranges (though I seriously
 question the viability of pure input ranges given how insanely limiting is to
 be unable to save their state), but there's also plenty of stuff that needs
 random access, and if you _really_ care about speed, there's a decent chance
 that you need random access (if nothing else, to be able to pop off multiple
 elements at a time). That doesn't necessarily mean that you're using an array,
 but odds are whatever you're using wraps an array if it isn't one. I don't
 think that there's much of anything which is random access without having an
 array or pointer underneath the hood. Reading from a file, I'd be very inclined
 to use something like MmFile or reading the whole file into an array rather
 than trying to wrap in something that's a pure input range. They're just too
 limiting.


I think this (and the long, long, long text above) is missing a point. 
The necessity here is defining new range primitives (such as lookahead), 
not force the existing range notions onto the needed functionality.

Again:

1. Port the blessed lexer as is to D already

2. Figure out what abstraction is needed for lexer's input

3. Reify that abstraction as an existing range type, a variation on an 
existing range type, or a new range type

Talking abstraction without concrete is a poor approach. Concrete first, 
abstraction extracted from it.


Andrei
Feb 28 2013
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 2/28/2013 3:29 AM, Jonathan M Davis wrote:

 And you were just claiming that the lexer checked the sentinel type in only
 one place. If that's indeed the case (and I think that it's quite close to
 being true if it isn't true), then you _wouldn't_ need to use static ifs like
 this in many places. So, which is it? If you need to check the sentinel often
 enough that using static ifs is a problem, then it's probably not buying you
 much of anything over checking empty anyway.


Please, again, examine lexer.c.

For example, look at what happens after line 719. Try 794 in particular.

Now look at line 996 and what follows. Note that there is not a single null 
check there, yet the code is correct and does not run off the end of the data.



 But my point is that outside of strings or arrays, you're almost certainly
 stuck with that.


I've given you two examples (lexer and regexp) where you are certainly not
stuck 
with that, and those two cases matter.



 Pure input ranges fail utterly as you can't save them, so you get _zero_
 lookahead [...]


Yet the lexer will work efficiently and correctly with a SentinelInputRange
that 
is also a ForwardRange. It fits in nicely with the range concepts.
Feb 28 2013
next sibling parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
28-Feb-2013 20:52, Walter Bright пишет:

 On 2/28/2013 3:29 AM, Jonathan M Davis wrote:

 And you were just claiming that the lexer checked the sentinel type in
 only
 one place. If that's indeed the case (and I think that it's quite
 close to
 being true if it isn't true), then you _wouldn't_ need to use static
 ifs like
 this in many places. So, which is it? If you need to check the
 sentinel often
 enough that using static ifs is a problem, then it's probably not
 buying you
 much of anything over checking empty anyway.


 Please, again, examine lexer.c.

 For example, look at what happens after line 719. Try 794 in particular.

 Now look at line 996 and what follows. Note that there is not a single
 null check there, yet the code is correct and does not run off the end
 of the data.



 But my point is that outside of strings or arrays, you're almost
 certainly
 stuck with that.


 I've given you two examples (lexer and regexp) where you are certainly
 not stuck with that, and those two cases matter.


I'll add that when I wrote current std.regex internal VM I've switched 
to the sentinel as terminator of the program instead of checking the 
length. The end result was about 5% of speed up gained back then 
(measured on DMD alone though, other compilers didn't compile it at the 
time).

In the lexer it may help a bit more given the lookahead.

-- 
Dmitry Olshansky
Feb 28 2013
prev sibling parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Thursday, February 28, 2013 08:52:45 Walter Bright wrote:

 I've given you two examples (lexer and regexp) where you are certainly not
 stuck with that, and those two cases matter.
 

 Pure input ranges fail utterly as you can't save them, so you get _zero_
 lookahead [...]




My point is that in almost all cases, what'll end up happening with a sentinel 
range which is something like this:

struct SRange(R)
    if(is(Unqual!(ElementType!R) == char))
{
    enum char sentinel = 0;

     property char front() { return _front; }
     property bool empty() { return _front == sentinel; }
    void popFront()
    {
        _range.popFront();
        if(_range.empty)
            _front = sentinel;
    }

    this(R range)
    {
        if(_range.empty)
            _front = sentinel;
        else
            _front = _rang.front;
    }

private:
    char _front;
    R _range;
}

Notice that it has to check for empty every time that the front is popped, and 
it can't avoid that, because it's wrapping another range which is not a 
sentinel range. The only time that it can avoid that is if it's managing its 
own memory internally via an array or pointer or whatnot. And if it's just 
going to be a string or an array, I'd argue for simply special casing strings 
or arrays to skip unnecessary empty checks.

Also, with sentinel ranges, you'll be forced to wrap strings because of that 
sentinel marker that's required for isSentinelRange, meaning that you'll get 
something like

struct SRange
{
    enum char sentinel = 0;

     property char front() { return _front; }
     property bool empty() { return _front == sentinel; }
    void popFront() { _str = _str[1 .. $]; }

    this(string str)
    {
        _str = str;

        if(_str.empty)
            _str = [sentinel];
        else if(_str[$ - 1] != sentinel)
            _str ~= sentinel;
    }

private:
    string _str;
}

And while the compiler will hopefully optimize away all of the extra overhead 
of the wrapper type, any functions which would be able to optimize what 
they're doing for a string or array will not special case for this wrapper 
type, because they probably won't even know about it. A prime case where that 
might be an issue would be with std.utf.decode or std.utf.decodeFront which do 
some special casing for strings and which any unicode-aware lexer would have 
to use at least some of the time (even if the vast majority of the time, it 
can just check ASCII stuff).

So, for the most part, the only time that you'll get any performance boost out 
of this is with strings or arrays, and you'll take a performance hit if you're 
using functions which special case strings or arrays but not the wrapper 
sentinel type. And yet special-casing strings and arrays will give you exactly 
the same performance boost without this sentinel range concept.

- Jonathan M Davis
Feb 28 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
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;
Feb 28 2013
parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
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
Feb 28 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
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.
Feb 28 2013
next sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
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.
Feb 28 2013
parent Walter Bright <newshound2 digitalmars.com> writes:
On 2/28/2013 5:00 PM, deadalnix wrote:

 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.


Search for [1] in lexer.c, i.e. lookahead cases, although these are less
important.

I admit I was surprised that LLVM did that, though the other compilers did not. 
There are some lingering issues with ordering. The sentinel is going to be the 
rare case, and you'd often want to sort the cases so that the most likely ones 
are tested first (if it doesn't all go into a jump table indexed by the value).


 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.


It's a good point.
Feb 28 2013
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/28/13 7:34 PM, Walter Bright wrote:

 On 2/28/2013 4:07 PM, Jonathan M Davis 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.


We're talking about an abstraction that doesn't exist, exemplifying with 
code that doesn't use it. No wonder there's going to be 
miscommunication. The solution is to spin some code.

Andrei
Feb 28 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 2/28/2013 5:29 PM, Andrei Alexandrescu wrote:

 On 2/28/13 7:34 PM, Walter Bright wrote:

 On 2/28/2013 4:07 PM, Jonathan M Davis 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.


 We're talking about an abstraction that doesn't exist, exemplifying with code
 that doesn't use it. No wonder there's going to be miscommunication. The
 solution is to spin some code.


std.regexp uses sentinels in the bytecode.
Feb 28 2013
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Friday, 1 March 2013 at 01:46:34 UTC, Walter Bright wrote:

 On 2/28/2013 5:29 PM, Andrei Alexandrescu wrote:

 On 2/28/13 7:34 PM, Walter Bright wrote:

 On 2/28/2013 4:07 PM, Jonathan M Davis 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.


 We're talking about an abstraction that doesn't exist, 
 exemplifying with code
 that doesn't use it. No wonder there's going to be 
 miscommunication. The
 solution is to spin some code.


 std.regexp uses sentinels in the bytecode.


I think nobody says that this technic is useless. Simply that a 
good compiler can take advantage of it without introducing an 
higher level concept of sentinel input range.
Feb 28 2013
parent reply "Chris Nicholson-Sauls" <ibisbasenji gmail.com> writes:
A use case that comes immediately to mind: a sentinal range that, 
yes wraps, an infinite (but predictable!) range, effectively 
allowing you to take a head-slice of the infinite range.

auto foo = infiniteRangeOfEvenNumbers();
auto upto1000 = GenericSentinalInputRange!1000( foo );

Yes, in this contrived example, one could use take(), but what 
about an infinite range that can be predicted to always hit 
certain points, but is not restricted to those points?


As for other cases of sentinal ranges wrapping others, in 
particular arrays, there seems to be no mention of what I expect 
would be the most common use case: wherein the code which 
instantiates the sentinal range can guarantee that the sentinal 
already exists in the source data/range, because it *put* it 
there -- the lexer remains a fine example, as it tacks the 
terminating \0 on.  There is no need for extra checks, because 
there is no need to *replace* the source data with the sentinel. 
It is naturally reduced to it through normal processing.


Other apparent use cases: list processing (Andrei has mentioned 
this already, for singly-linked lists); protocol processing with 
a terminate-transaction message, or similar; state sequences 
(which can include lexers and parsers, as it happens).  This is 
just off the top of my head.

Can we do it now, without a special type?  Yes.  Is there any 
gain from introducing the special type, versus what can be done 
now?  Yes, sometimes.  Is there any harm in introducing the 
special type?  No.  Is there significant cost in adding it?  No.  
Should this just be handled by compiler optimization?  Yes and no 
-- yes in that a great compiler should be able to optimize *many* 
(but not neccessarily all!) cases; but no in that including 
implementation details in a language spec is usually bad mojo.  
Of course, any compiler that could optimize the common cases, 
could at least as readily optimize the use of a sentinal range -- 
in fact, I'd expect it to open optimization paths for some of the 
corner cases that might otherwise not have been optimized.

So... I could live without a standard sentinal range concept 
(have so far, using sentinal injection with input ranges, which 
as Walter pointed out is really an incorrect use (abuse?) of 
input ranges), but I also know I'd be using it if it existed (and 
thereby cleaning up some code versus how I do it now).
Feb 28 2013
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Friday, 1 March 2013 at 06:19:19 UTC, Chris Nicholson-Sauls 
wrote:

 A use case that comes immediately to mind: a sentinal range 
 that, yes wraps, an infinite (but predictable!) range, 
 effectively allowing you to take a head-slice of the infinite 
 range.

 auto foo = infiniteRangeOfEvenNumbers();
 auto upto1000 = GenericSentinalInputRange!1000( foo );


struct GenericSentinelRange(R, Sentinel) {
     R r;

      property auto front() {
         return r.front;
     }

     void popFront() {
         r.popFront();
     }

      property empty() {
         return r.front == Sentinel;
     }
}

We don't need a new type of range at all. You confuse legitimate 
uses case for using a sentinel to terminate a range and uses case 
where an actual sentinel range is needed.


 So... I could live without a standard sentinal range concept 
 (have so far, using sentinal injection with input ranges, which 
 as Walter pointed out is really an incorrect use (abuse?) of 
 input ranges), but I also know I'd be using it if it existed 
 (and thereby cleaning up some code versus how I do it now).


You can live without, and guess what : if you use LDC (and 
probably GDC) you'll get the performance boost Walter is talking 
about.
Feb 28 2013
parent reply "Chris Nicholson-Sauls" <ibisbasenji gmail.com> writes:
On Friday, 1 March 2013 at 06:33:42 UTC, deadalnix wrote:

 struct GenericSentinelRange(R, Sentinel) {
     R r;

      property auto front() {
         return r.front;
     }

     void popFront() {
         r.popFront();
     }

      property empty() {
         return r.front == Sentinel;
     }
 }


That's exactly what I wrote as well, when I played with the idea 
before posting.  Except I just called the sentinel constant S and 
added 'enum sentinel = S;' -- not significant extra work.


 We don't need a new type of range at all. You confuse 
 legitimate uses case for using a sentinel to terminate a range 
 and uses case where an actual sentinel range is needed.


I'm not confused. The use case for a sentinel range /type/ is 
always going to be the same, and singular: automating legitimate 
use cases for sentinels.  So, in effect, an argument for one is 
as good as for the other, when I'm only responding to the calls 
for use case examples. My mistake was in not making it clear that 
I was responding just to those, sorry.


 You can live without, and guess what : if you use LDC (and 
 probably GDC) you'll get the performance boost Walter is 
 talking about.


Which presupposes that I *can* use LDC (or GDC). For many people, 
it may not be an option.  And last time I tried (which has been 
months now, admittedly) I couldn't get LDC to work for me at all, 
which is a shame since I'm actually very much interested in it.  
Either way, reliance on implementation details is not a good 
thing.
Feb 28 2013
parent "deadalnix" <deadalnix gmail.com> writes:
On Friday, 1 March 2013 at 07:02:51 UTC, Chris Nicholson-Sauls 
wrote:

 Which presupposes that I *can* use LDC (or GDC). For many 
 people, it may not be an option.  And last time I tried (which 
 has been months now, admittedly) I couldn't get LDC to work for 
 me at all, which is a shame since I'm actually very much 
 interested in it.  Either way, reliance on implementation 
 details is not a good thing.


You don't rely on any implementation detail as the whole stuff 
will work with all implementation. It will simply not be able to 
take advantage of sentinel for speedup with some compilers. But 
the behavior will be exactly the same.

Different compilers produces executable of different efficiency. 
That isn't something new.
Feb 28 2013
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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.

Andrei
Feb 28 2013
next sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 28 February 2013 at 15:31:21 UTC, Andrei 
Alexandrescu wrote:

 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.

 Andrei


An actual sentinel range is trivial to implement, and the 
algorithms that can *actually* truly exploit it are rare.

While I'm not against having such ranges in phobos, I'd just be 
weary to provide too many traits for them, or trying to have 
phobos exploit them either. Ranges have enough primitives as it 
is.

Just provide it with a disclaimer than it will only ever be 
useful for a select class of algorithms (parser), but that the 
optimization opportunity will be ignored by the rest of phobos.
Feb 28 2013
parent Walter Bright <newshound2 digitalmars.com> writes:
On 2/28/2013 7:37 AM, monarch_dodra wrote:

 Just provide it with a disclaimer than it will only ever be useful for a select
 class of algorithms (parser), but that the optimization opportunity will be
 ignored by the rest of phobos.


1. parsing text is very commonplace

2. it is used in std.regexp in the interpreter engine, a quite different use 
case, but also common to bytecode engines
Feb 28 2013
prev sibling next sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
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.


And it wasn't the problem that std.d.lexer had anyway. Check the latest 
results.

The merit of sentinel range IMHO is largely in tapping into C-strings 
and the like more naturally.



-- 
Dmitry Olshansky
Feb 28 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 2/28/2013 7:41 AM, Dmitry Olshansky wrote:

 The merit of sentinel range IMHO is largely in tapping into C-strings and the
 like more naturally.


The merit is having significantly faster speed.
Feb 28 2013
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Walter Bright:


 The merit is having significantly faster speed.


Maybe it's time to write two benchmarks to compare the two 
different speeds (and run the two benchmarks with DMD and LDC).

Bye,
bearophile
Feb 28 2013
prev sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
28-Feb-2013 20:56, Walter Bright пишет:

 On 2/28/2013 7:41 AM, Dmitry Olshansky wrote:

 The merit of sentinel range IMHO is largely in tapping into C-strings
 and the
 like more naturally.


 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.

I can try right away with std.d.lexer by Brain Schott and get rid of the 
check for the length and place a null byte right after the file buffer. 
Then I should be able to estimate the gain.

-- 
Dmitry Olshansky
Feb 28 2013
parent Walter Bright <newshound2 digitalmars.com> writes:
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.
Feb 28 2013
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 2/28/2013 7:31 AM, Andrei Alexandrescu wrote:

 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.


I don't agree. It is a blocker for getting a fast lexer.
Feb 28 2013
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/28/13 11:54 AM, Walter Bright wrote:

 On 2/28/2013 7:31 AM, Andrei Alexandrescu wrote:

 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.


 I don't agree. It is a blocker for getting a fast lexer.


I don't think what I said was understood.

Andrei
Feb 28 2013
parent Walter Bright <newshound2 digitalmars.com> writes:
On 2/28/2013 9:10 AM, Andrei Alexandrescu wrote:

 I don't think what I said was understood.


I know the feeling :-)
Feb 28 2013
prev sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
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
Feb 28 2013
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/28/13 12:20 PM, Dmitry Olshansky wrote:

 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).


I think that's a good idea but I took a look at 
https://github.com/bhelyer/std.d.lexer/blob/master/std/d/lexer.d and I 
will destroy it. In a good sense :o).

Andrei
Feb 28 2013
next sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
28-Feb-2013 22:38, Andrei Alexandrescu пишет:

 On 2/28/13 12:20 PM, Dmitry Olshansky wrote:

 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).


 I think that's a good idea but I took a look at
 https://github.com/bhelyer/std.d.lexer/blob/master/std/d/lexer.d and I
 will destroy it. In a good sense :o).


That's the wrong one. This is the one:
https://github.com/Hackerpilot/Dscanner/tree/range-based-lexer

Though feel free to destroy the other one too ;)
But I need your full powers with Dscanner first :o)


 Andrei



-- 
Dmitry Olshansky
Feb 28 2013
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/28/13 1:42 PM, Dmitry Olshansky wrote:

 That's the wrong one. This is the one:
 https://github.com/Hackerpilot/Dscanner/tree/range-based-lexer

 Though feel free to destroy the other one too ;)
 But I need your full powers with Dscanner first :o)


Whoa, that looks really good!

Andrei
Feb 28 2013
parent =?iso-8859-15?Q?Simen_Kj=E6r=E5s?= <simen.kjaras gmail.com> writes:
On Thu, 28 Feb 2013 19:53:05 +0100, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:


 On 2/28/13 1:42 PM, Dmitry Olshansky wrote:

 That's the wrong one. This is the one:
 https://github.com/Hackerpilot/Dscanner/tree/range-based-lexer

 Though feel free to destroy the other one too ;)
 But I need your full powers with Dscanner first :o)


 Whoa, that looks really good!


Nonono, destroy! :p


-- 
Simen
Mar 01 2013
prev sibling parent "Brian Schott" <briancschott gmail.com> writes:
On Thursday, 28 February 2013 at 18:38:59 UTC, Andrei 
Alexandrescu wrote:

 I think that's a good idea but I took a look at 
 https://github.com/bhelyer/std.d.lexer/blob/master/std/d/lexer.d 
 and I will destroy it. In a good sense :o).

 Andrei


https://github.com/Hackerpilot/Dscanner/blob/range-based-lexer/std/d/lexer.d
He's talking about this one.
Feb 28 2013
prev sibling next sibling parent reply "Peter Alexander" <peter.alexander.au gmail.com> writes:
On Thursday, 28 February 2013 at 01:12:19 UTC, Walter Bright 
wrote:

 Motivation:
 1. easy conversion of C strings to ranges


This is already easy.

struct CString
{
      property char front() { return *p; }
     void popFront() { ++p; }
      property bool empty() const { return !*p; }
     char* p;
}

(Yep, rubbish implementation, missing save, constructors etc., 
but you get the idea).


 2. necessary for a fast implementation of a lexer


This is very domain specific. Is a whole new range concept in the 
standard library necessary?

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.

Are there any other REAL uses for this other than in one line of 
a lexer implementation? I think inclusions into the standard 
library should require at least several distinct and realistic 
use cases.
Feb 28 2013
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 2/28/2013 1:19 AM, Peter Alexander wrote:

 On Thursday, 28 February 2013 at 01:12:19 UTC, Walter Bright wrote:

 Motivation:
 1. easy conversion of C strings to ranges


 This is already easy.

 struct CString
 {
       property char front() { return *p; }
      void popFront() { ++p; }
       property bool empty() const { return !*p; }
      char* p;
 }

 (Yep, rubbish implementation, missing save, constructors etc., but you get the
 idea).


Notice the double read of *p. This is what SentinelInputRange is trying to fix.



 2. necessary for a fast implementation of a lexer


 This is very domain specific. Is a whole new range concept in the standard
 library necessary?


I've posted in this thread several use cases.



 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.



 Are there any other REAL uses for this other than in one line of a lexer
 implementation? I think inclusions into the standard library should require at
 least several distinct and realistic use cases.


I've posted several - including one in Phobos.
Feb 28 2013
next sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
On Thursday, 28 February 2013 at 10:57:29 UTC, Walter Bright 
wrote:

 Notice the double read of *p. This is what SentinelInputRange 
 is trying to fix.


But it will be optimized away.
Feb 28 2013
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 28 Feb 2013 06:23:45 -0500, deadalnix <deadalnix gmail.com> wrote:


 On Thursday, 28 February 2013 at 10:57:29 UTC, Walter Bright wrote:

 Notice the double read of *p. This is what SentinelInputRange is trying  
 to fix.


 But it will be optimized away.


I have to say I agree with deadalnix.

you have essentially in lexer.c:

outer:
while(1)
{
    switch(r.front)
    {
       case 0:
         break outer;
       ...
    }
}

whereas a range where empty is defined as r.front == 0:

while(!r.empty)  // inlined to r.front != 0
{
    switch(r.front) // why would another load occur here?
    {
       // no need to check for 0, already done
       ...
    }
}

If this doesn't translate to the same code, I don't know why not.  The  
second implementation looks more elegant/straightforward.  I think others  
have pointed out that other compilers already do this.  I hope we aren't  
introducing library components to get around DMD optimizer shortcomings.

Note, r cannot be a D string in order to achieve the desired efficiency.   
With a sentinel range, length is never checked, and should not have to be  
updated.

I think it's not necessary to add extra isSentinelRange, etc. checks, just  
define your sentinel range like any other input range.

-Steve
Feb 28 2013
next sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2013-02-28 15:31, Steven Schveighoffer wrote:


 while(!r.empty)  // inlined to r.front != 0
 {
     switch(r.front) // why would another load occur here?
     {
        // no need to check for 0, already done
        ...
     }
 }


Don't you have to check for 0 anyway. You could still have more data in 
the buffer? I doesn't have to be the manually added sentential that is 
encountered.

-- 
/Jacob Carlborg
Feb 28 2013
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 28 Feb 2013 09:48:02 -0500, Jacob Carlborg <doob me.com> wrote:


 On 2013-02-28 15:31, Steven Schveighoffer wrote:


 while(!r.empty)  // inlined to r.front != 0
 {
     switch(r.front) // why would another load occur here?
     {
        // no need to check for 0, already done
        ...
     }
 }


 Don't you have to check for 0 anyway. You could still have more data in  
 the buffer? I doesn't have to be the manually added sentential that is  
 encountered.


You are missing the point.  Empty is DEFINED as r.front == 0.  Adding a  
check for 0, would essentially lead to dead code (and technically, the  
compiler could trim it out).

An important thing about a sentinel input range is that it is not an array  
-- you cannot maintain or process length, because length is defined by the  
sentinel.  This becomes an advantage when your goal is simply to process  
every element -- no time wasted updating length.

-Steve
Feb 28 2013
parent Jacob Carlborg <doob me.com> writes:
On 2013-02-28 15:53, Steven Schveighoffer wrote:


 You are missing the point.  Empty is DEFINED as r.front == 0.  Adding a
 check for 0, would essentially lead to dead code (and technically, the
 compiler could trim it out).


Ah, right.

-- 
/Jacob Carlborg
Feb 28 2013
prev sibling next sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 28 February 2013 at 14:31:08 UTC, Steven 
Schveighoffer wrote:

 On Thu, 28 Feb 2013 06:23:45 -0500, deadalnix

 I have to say I agree with deadalnix.

 you have essentially in lexer.c:

 outer:
 while(1)
 {
    switch(r.front)
    {
       case 0:
         break outer;
       ...
    }
 }

 whereas a range where empty is defined as r.front == 0:

 while(!r.empty)  // inlined to r.front != 0
 {
    switch(r.front) // why would another load occur here?
    {
       // no need to check for 0, already done
       ...
    }
 }

 If this doesn't translate to the same code, I don't know why 
 not[SNIP].

 -Steve


The difference is that by doing "!r.empty" first, you are 
actually executing "r.front == 0" each and every time, before 
doing the rest of the checks proper.

Doing it the other way around however, the only time you actually 
check the sentinel value is once you've reached the actual 
sentinel value, or you've run out of values "of interest": EG not 
actually on every element.

You are basically re-ordering the tests to speed up the usual 
case.

//----

This is kind of the same logic as in C++'s "operator=": It is 
recommended to always check for self assignment. However, most 
quality implementations will *not* execute this check, instead 
being extra careful about instruction ordering.

While the rare self-assignement case becomes more expensive, the 
common assignment becomes cheaper. That's where the win is.
Feb 28 2013
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 28 Feb 2013 10:31:42 -0500, monarch_dodra <monarchdodra gmail.com>  
wrote:


 On Thursday, 28 February 2013 at 14:31:08 UTC, Steven Schveighoffer  
 wrote:

 On Thu, 28 Feb 2013 06:23:45 -0500, deadalnix

 I have to say I agree with deadalnix.

 you have essentially in lexer.c:

 outer:
 while(1)
 {
    switch(r.front)
    {
       case 0:
         break outer;
       ...
    }
 }

 whereas a range where empty is defined as r.front == 0:

 while(!r.empty)  // inlined to r.front != 0
 {
    switch(r.front) // why would another load occur here?
    {
       // no need to check for 0, already done
       ...
    }
 }

 If this doesn't translate to the same code, I don't know why not[SNIP].


 The difference is that by doing "!r.empty" first, you are actually  
 executing "r.front == 0" each and every time, before doing the rest of  
 the checks proper.

 Doing it the other way around however, the only time you actually check  
 the sentinel value is once you've reached the actual sentinel value, or  
 you've run out of values "of interest": EG not actually on every element.

 You are basically re-ordering the tests to speed up the usual case.


If you look at lexer.c, case 0 is the first test.  How is it that the  
compiler knows that's the least likely case to check?  Even it if it does,  
sure, the compiler could reorder it.  But then it could include the while  
loop test into the switch statement, as others have suggested, and we get  
the same result.

Besides, I don't think a jnz instruction is that expensive.

My impression from Walter's other posts is to avoid the double load/double  
check, not to change the ordering.

-Steve
Feb 28 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
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]
Feb 28 2013
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
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
Feb 28 2013
parent Walter Bright <newshound2 digitalmars.com> writes:
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.
Feb 28 2013
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
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.
Feb 28 2013
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
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
Feb 28 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
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.
Feb 28 2013
next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 28 Feb 2013 17:00:06 -0500, Walter Bright  
<newshound2 digitalmars.com> wrote:


 On 2/28/2013 9:25 AM, Steven Schveighoffer wrote:

 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;


I don't need to add any more to this discussion, it seems more qualified  
people are making the points I am making, but in a more understandable way.

Sorry to add to your frustration.

-Steve
Mar 01 2013
prev sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
On Thursday, 28 February 2013 at 22:00:11 UTC, Walter Bright 
wrote:

 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".


I finally decided to write a post about such imaginary 
"sufficiently smart compilers" that clearly don't exists today, 
never will and so we have to clutter the language : 
http://www.deadalnix.me/2013/03/23/a-story-about-optimization-llvm-and-the-sentinelinputrange/

I really hope that someone wrote this imaginary LLVM thing 
everybody is talking about !
Mar 24 2013
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/24/13 7:32 AM, deadalnix wrote:

 I finally decided to write a post about such imaginary "sufficiently
 smart compilers" that clearly don't exists today, never will and so we
 have to clutter the language :
 http://www.deadalnix.me/2013/03/23/a-story-about-optimization-llvm-and-the-sentinelinputrange/


 I really hope that someone wrote this imaginary LLVM thing everybody is
 talking about !


Looking great (also love the page design). The piece has a few 
systematic English language errors that should be easy to fix. Would you 
want to accept a copyedit step from a native speaker, and if so, is 
anyone here inclined to do that?


Thanks,

Andrei
Mar 24 2013
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Sunday, 24 March 2013 at 11:49:17 UTC, Andrei Alexandrescu 
wrote:

 On 3/24/13 7:32 AM, deadalnix wrote:

 I finally decided to write a post about such imaginary 
 "sufficiently
 smart compilers" that clearly don't exists today, never will 
 and so we
 have to clutter the language :
 http://www.deadalnix.me/2013/03/23/a-story-about-optimization-llvm-and-the-sentinelinputrange/


 I really hope that someone wrote this imaginary LLVM thing 
 everybody is
 talking about !


 Looking great (also love the page design). The piece has a few 
 systematic English language errors that should be easy to fix. 
 Would you want to accept a copyedit step from a native speaker, 
 and if so, is anyone here inclined to do that?


I'd be happy to, if someone want to do it.
Mar 24 2013
next sibling parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Sunday, 24 March 2013 at 12:22:37 UTC, deadalnix wrote:

 On Sunday, 24 March 2013 at 11:49:17 UTC, Andrei Alexandrescu 
 wrote:

 On 3/24/13 7:32 AM, deadalnix wrote:

 I finally decided to write a post about such imaginary 
 "sufficiently
 smart compilers" that clearly don't exists today, never will 
 and so we
 have to clutter the language :
 http://www.deadalnix.me/2013/03/23/a-story-about-optimization-llvm-and-the-sentinelinputrange/


 I really hope that someone wrote this imaginary LLVM thing 
 everybody is
 talking about !


 Looking great (also love the page design). The piece has a few 
 systematic English language errors that should be easy to fix. 
 Would you want to accept a copyedit step from a native 
 speaker, and if so, is anyone here inclined to do that?


 I'd be happy to, if someone want to do it.



Native English speaker here; I'd be happy to edit for grammar.
Mar 24 2013
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/24/13 9:07 AM, John Colvin wrote:

 On Sunday, 24 March 2013 at 12:22:37 UTC, deadalnix wrote:

 On Sunday, 24 March 2013 at 11:49:17 UTC, Andrei Alexandrescu wrote:

 On 3/24/13 7:32 AM, deadalnix wrote:

 I finally decided to write a post about such imaginary "sufficiently
 smart compilers" that clearly don't exists today, never will and so we
 have to clutter the language :
 http://www.deadalnix.me/2013/03/23/a-story-about-optimization-llvm-and-the-sentinelinputrange/



 I really hope that someone wrote this imaginary LLVM thing everybody is
 talking about !


 Looking great (also love the page design). The piece has a few
 systematic English language errors that should be easy to fix. Would
 you want to accept a copyedit step from a native speaker, and if so,
 is anyone here inclined to do that?


 I'd be happy to, if someone want to do it.



 Native English speaker here; I'd be happy to edit for grammar.


Great, please go ahead! Something that worked for my reviewers was to 
just email a bunch of "before" -> "after" sentences, e.g.:

* "Developers want code that run fast." -> "Developers want code that 
runs fast."

* "And this is how the SentinelInputRange get into the discussion." -> 
"And this is how the SentinelInputRange gets into the discussion."

...


Andrei
Mar 24 2013
prev sibling parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Sunday, 24 March 2013 at 12:22:37 UTC, deadalnix wrote:

 On Sunday, 24 March 2013 at 11:49:17 UTC, Andrei Alexandrescu 
 wrote:

 On 3/24/13 7:32 AM, deadalnix wrote:

 I finally decided to write a post about such imaginary 
 "sufficiently
 smart compilers" that clearly don't exists today, never will 
 and so we
 have to clutter the language :
 http://www.deadalnix.me/2013/03/23/a-story-about-optimization-llvm-and-the-sentinelinputrange/


 I really hope that someone wrote this imaginary LLVM thing 
 everybody is
 talking about !


 Looking great (also love the page design). The piece has a few 
 systematic English language errors that should be easy to fix. 
 Would you want to accept a copyedit step from a native 
 speaker, and if so, is anyone here inclined to do that?


 I'd be happy to, if someone want to do it.


I copied and pasted in to libreoffice for editing: 
http://dl.dropbox.com/u/910836/sentinal.odt  or  
http://dl.dropbox.com/u/910836/sentinal.doc


There are 2 comments from me, they are in [] and highlighted in 
yellow. You'll probably want to address them and then delete them.

There were a lot of grammatical mistakes that have now been fixed 
and a couple of sentences have been rearranged. I had planned to 
work as Andrei suggested with "before -> after" but I quickly 
realised the edit file would be longer than the document!

P.S.
I may have accidentally introduced some British English by 
accident, perhaps a native American English speaker will spot 
them.
Mar 24 2013
parent "deadalnix" <deadalnix gmail.com> writes:
On Sunday, 24 March 2013 at 14:37:18 UTC, John Colvin wrote:

 On Sunday, 24 March 2013 at 12:22:37 UTC, deadalnix wrote:

 On Sunday, 24 March 2013 at 11:49:17 UTC, Andrei Alexandrescu 
 wrote:

 On 3/24/13 7:32 AM, deadalnix wrote:

 I finally decided to write a post about such imaginary 
 "sufficiently
 smart compilers" that clearly don't exists today, never will 
 and so we
 have to clutter the language :
 http://www.deadalnix.me/2013/03/23/a-story-about-optimization-llvm-and-the-sentinelinputrange/


 I really hope that someone wrote this imaginary LLVM thing 
 everybody is
 talking about !


 Looking great (also love the page design). The piece has a 
 few systematic English language errors that should be easy to 
 fix. Would you want to accept a copyedit step from a native 
 speaker, and if so, is anyone here inclined to do that?


 I'd be happy to, if someone want to do it.


 I copied and pasted in to libreoffice for editing: 
 http://dl.dropbox.com/u/910836/sentinal.odt  or  
 http://dl.dropbox.com/u/910836/sentinal.doc


 There are 2 comments from me, they are in [] and highlighted in 
 yellow. You'll probably want to address them and then delete 
 them.

 There were a lot of grammatical mistakes that have now been 
 fixed and a couple of sentences have been rearranged. I had 
 planned to work as Andrei suggested with "before -> after" but 
 I quickly realised the edit file would be longer than the 
 document!

 P.S.
 I may have accidentally introduced some British English by 
 accident, perhaps a native American English speaker will spot 
 them.


That is much better now. Thank a lot, I updated the article.
Mar 24 2013
prev sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
deadalnix:


 http://www.deadalnix.me/2013/03/23/a-story-about-optimization-llvm-and-the-sentinelinputrange/


A nice article. I'd like to see longer lines for the 
non-proportional text of the code.

Another way to improve the article is to show what GDC does here.

Bye,
bearophile
Mar 24 2013
prev sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
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.

See sample code bellow, which is a typical structure find in 
lexer.c :

int bar(int n) {
	switch(n) {
		case 0:
			return 0; // Bad case !
		
		case 25:
			return 75;
		
		case 42:
			return 69;
		
		case 666:
			return 999;
		
		default:
			return -1;
	}
}

int foo(int n) {
	switch(n) {
		case 1:
			return 23;
		
		case 2:
		case 3:
			return n;
			
		default:
			return bar(n);
	}
}

As we see, foo don't check for 0, and bar does, but only when 
necessary, as bar isn't called. Or this is what you think. Let's 
see how SDC compile this :

define i32  _D3barFiZi(i32 %arg.n) {
   %n = alloca i32
   store i32 %arg.n, i32* %n
   br label %body

body:                                             ; preds = %0
   %1 = load i32* %n
   switch i32 %1, label %default [
     i32 0, label %.case
     i32 25, label %.case1
     i32 42, label %.case2
     i32 666, label %.case3
   ]

switchstart:                                      ; No 
predecessors!
   br label %.case

.case:                                            ; preds = 
%body, %switchstart
   ret i32 0

.case1:                                           ; preds = %body
   ret i32 75

.case2:                                           ; preds = %body
   ret i32 69

.case3:                                           ; preds = %body
   ret i32 999

default:                                          ; preds = %body
   ret i32 -1

switchend:                                        ; No 
predecessors!
   unreachable
}

define i32  _D3fooFiZi(i32 %arg.n) {
   %n = alloca i32
   store i32 %arg.n, i32* %n
   br label %body

body:                                             ; preds = %0
   %1 = load i32* %n
   switch i32 %1, label %default [
     i32 1, label %.case
     i32 2, label %.case1
     i32 3, label %.case2
   ]

switchstart:                                      ; No 
predecessors!
   br label %.case

.case:                                            ; preds = 
%body, %switchstart
   ret i32 23

.case1:                                           ; preds = %body
   br label %.case2

.case2:                                           ; preds = 
%body, %.case1
   %2 = load i32* %n
   ret i32 %2

default:                                          ; preds = %body
   %3 = load i32* %n
   %4 = call i32  _D3barFiZi(i32 %3)
   ret i32 %4

switchend:                                        ; No 
predecessors!
   unreachable
}

Here is the raw result of the frontend in LLVM IR. Now here is 
what the optimizer give us :

define i32  _D3barFiZi(i32 %arg.n) nounwind readnone {
body:
   switch i32 %arg.n, label %default [
     i32 0, label %.case
     i32 25, label %.case1
     i32 42, label %.case2
     i32 666, label %.case3
   ]

.case:                                            ; preds = 
%default, %.case3, %.case2, %.case1, %body
   %merge = phi i32 [ 0, %body ], [ 75, %.case1 ], [ 69, %.case2 
], [ 999, %.case3 ], [ -1, %default ]
   ret i32 %merge

.case1:                                           ; preds = %body
   br label %.case

.case2:                                           ; preds = %body
   br label %.case

.case3:                                           ; preds = %body
   br label %.case

default:                                          ; preds = %body
   br label %.case
}

define i32  _D3fooFiZi(i32 %arg.n) nounwind readnone {
body:
   switch i32 %arg.n, label %default.i [
     i32 1, label %.case
     i32 2, label %.case2
     i32 3, label %.case2
     i32 0, label %_D3barFiZi.exit
     i32 25, label %.case1.i
     i32 42, label %.case2.i
     i32 666, label %.case3.i
   ]

.case:                                            ; preds = 
%body, %_D3barFiZi.exit, %.case2
   %merge = phi i32 [ 23, %body ], [ %arg.n, %.case2 ], [ 
%merge.i, %_D3barFiZi.exit ]
   ret i32 %merge

.case2:                                           ; preds = 
%body, %body
   br label %.case

.case1.i:                                         ; preds = %body
   br label %_D3barFiZi.exit

.case2.i:                                         ; preds = %body
   br label %_D3barFiZi.exit

.case3.i:                                         ; preds = %body
   br label %_D3barFiZi.exit

default.i:                                        ; preds = %body
   br label %_D3barFiZi.exit

_D3barFiZi.exit:                                  ; preds = 
%body, %.case1.i, %.case2.i, %.case3.i, %default.i
   %merge.i = phi i32 [ 75, %.case1.i ], [ 69, %.case2.i ], [ 999, 
%.case3.i ], [ -1, %default.i ], [ 0, %body ]
   br label %.case
}

See, foo don't even call bar anymore. No let's include the null 
check, as it would have been done if checking for empty on a 
regular range (that happen to internally use a sentinel) :

int foo(int n) {
	if(n != 0) {
		switch(n) {
			case 1:
				return 23;
		
			case 2:
			case 3:
				return n;
			
			default:
				return bar(n);
		}
	}
	
	return bar(n);
}

I didn't repeated bar as it doesn't change.

Which is optimized as :
define i32  _D3fooFiZi(i32 %arg.n) nounwind readnone {
body:
   switch i32 %arg.n, label %default.i [
     i32 0, label %_D3barFiZi.exit8
     i32 1, label %.case
     i32 2, label %.case2
     i32 3, label %.case2
     i32 666, label %.case3.i
     i32 25, label %_D3barFiZi.exit
     i32 42, label %.case2.i
   ]

.case:                                            ; preds = 
%body, %_D3barFiZi.exit8, %_D3barFiZi.exit, %.case2
   %merge = phi i32 [ %arg.n, %.case2 ], [ %merge.i, 
%_D3barFiZi.exit ], [ 0, %_D3barFiZi.exit8 ], [ 23, %body ]
   ret i32 %merge

.case2:                                           ; preds = 
%body, %body
   br label %.case

.case2.i:                                         ; preds = %body
   br label %_D3barFiZi.exit

.case3.i:                                         ; preds = %body
   br label %_D3barFiZi.exit

default.i:                                        ; preds = %body
   br label %_D3barFiZi.exit

_D3barFiZi.exit:                                  ; preds = 
%body, %.case2.i, %.case3.i, %default.i
   %merge.i = phi i32 [ 69, %.case2.i ], [ 999, %.case3.i ], [ -1, 
%default.i ], [ 75, %body ]
   br label %.case

_D3barFiZi.exit8:                                 ; preds = %body
   br label %.case
}

The exact damn same thing ! Let's try with a different schemes, 
we check first an early return :

int foo(int n) {
	if(n == 0) {
		return bar(n);	
	}
	
	switch(n) {
		case 1:
			return 23;
	
		case 2:
		case 3:
			return n;
		
		default:
			return bar(n);
	}
}

Guess what ? It is optimized as :
define i32  _D3fooFiZi(i32 %arg.n) nounwind readnone {
body:
   switch i32 %arg.n, label %default.i7 [
     i32 0, label %_D3barFiZi.exit
     i32 1, label %.case
     i32 2, label %.case2
     i32 3, label %.case2
     i32 666, label %.case3.i6
     i32 25, label %_D3barFiZi.exit8
     i32 42, label %.case2.i5
   ]

_D3barFiZi.exit:                                  ; preds = 
%body, %_D3barFiZi.exit8, %.case2, %.case
   %merge9 = phi i32 [ 0, %body ], [ 23, %.case ], [ %arg.n, 
%.case2 ], [ %merge.i3, %_D3barFiZi.exit8 ]
   ret i32 %merge9

.case:                                            ; preds = %body
   br label %_D3barFiZi.exit

.case2:                                           ; preds = 
%body, %body
   br label %_D3barFiZi.exit

.case2.i5:                                        ; preds = %body
   br label %_D3barFiZi.exit8

.case3.i6:                                        ; preds = %body
   br label %_D3barFiZi.exit8

default.i7:                                       ; preds = %body
   br label %_D3barFiZi.exit8

_D3barFiZi.exit8:                                 ; preds = 
%body, %.case2.i5, %.case3.i6, %default.i7
   %merge.i3 = phi i32 [ 69, %.case2.i5 ], [ 999, %.case3.i6 ], [ 
-1, %default.i7 ], [ 75, %body ]
   br label %_D3barFiZi.exit
}

Yet again the same thing.

A range using a sentinel internally is clearly beneficial for a 
lexer (like C strings). Defining explicitly a range that does so 
is plain useless.
Feb 28 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
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;
Feb 28 2013
next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
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.
Feb 28 2013
prev sibling parent reply "jerro" <a a.com> writes:
 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
Feb 28 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
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.
Feb 28 2013
parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
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.
Feb 28 2013
parent Walter Bright <newshound2 digitalmars.com> writes:
On 2/28/2013 4:47 PM, H. S. Teoh wrote:

 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?


Yes, it could.
Feb 28 2013
prev sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 2/28/2013 3:23 AM, deadalnix wrote:

 On Thursday, 28 February 2013 at 10:57:29 UTC, Walter Bright wrote:

 Notice the double read of *p. This is what SentinelInputRange is trying to fix.


 But it will be optimized away.


(c == 1 || c == 5) does not optimize to (c == 5).
Feb 28 2013
prev sibling parent reply "Peter Alexander" <peter.alexander.au gmail.com> writes:
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
...
?
Feb 28 2013
parent Walter Bright <newshound2 digitalmars.com> writes:
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.
Feb 28 2013
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/28/13 4:19 AM, Peter Alexander wrote:

 Are there any other REAL uses for this other than in one line of a lexer
 implementation? I think inclusions into the standard library should
 require at least several distinct and realistic use cases.


Singly-linked lists.

Andrei
Feb 28 2013
prev sibling parent reply Artur Skawina <art.08.09 gmail.com> writes:
On 02/28/13 02:11, Walter Bright wrote:

 A SentinelInputRange is an InputRange with the following additions:
 
 1. a compile time property 'sentinel' that is the terminating value of the
range
 2. empty is defined as: empty = (front == sentinel)
 3. it is not necessary for empty to be called before front
 
 A C style 0-terminated string is an example of a SentinelInputRange.
 
 The additions to std.range would be:
 
 1. isSentinelInputRange(T) which returns true if T is a SentinelInputRange
 2. a unittest
 3. documentation of this
 
 An addition to std.string would be a function that takes a char* and returns a
SentinelInputRange.
 
 Motivation:
 1. easy conversion of C strings to ranges
 2. necessary for a fast implementation of a lexer


LookAheadRange, that not only defines 'sentinel', but also 'lookahead' which
defines how far one can safely look ahead. When 'lookahead==0' it becomes
equivalent to your SentinelInputRange, where 'front' and '[0]' is always
valid and can contain the sentinel. When 'lookahead==N', accessing '[N]' is
always valid.

Having said that, I've used this approach in a D lexer, and it does not really
matter in practice - avoiding the length (or '\0' sentinel) check makes a
<~1ms difference when lexing "datetime.d" sized objects (1.5Mbytes+, 460k+
tokens).
Which is practically irrelevant both in an IDE context and a compiler context
- other processing will be be orders of magnitude more expensive. An IDE doesn't
need to re-lex the whole file after every key press and 1ms won't make any
difference for a compiler run.

"Necessary for a fast implementation of a lexer" is an exaggeration, but yes,
it is an obvious optimization that has a measurable impact. Before implementing
it I was expecting a larger improvement too; and was somewhat surprised when the
resulting gain was in the noise (~1ms +/- ~3ms). /Relatively/ it is significant
(10% perf gain is never insignificant), but the /absolute/ perf difference isn't
that large.
Which of course isn't an argument against (SentinelInputLookAhead)Range; a std
API like that would be a good thing.

The advantage of SentinelInputRange/LookAheadRange is that it, unlike an array,
can be lazy. Which starts to matter when you're dealing with /token/ streams.

artur
Feb 28 2013
parent reply Jacob Carlborg <doob me.com> writes:
On 2013-02-28 15:08, Artur Skawina wrote:


 Having said that, I've used this approach in a D lexer, and it does not really
 matter in practice - avoiding the length (or '\0' sentinel) check makes a
 <~1ms difference when lexing "datetime.d" sized objects (1.5Mbytes+, 460k+
tokens).
 Which is practically irrelevant both in an IDE context and a compiler context
 - other processing will be be orders of magnitude more expensive. An IDE
doesn't
 need to re-lex the whole file after every key press and 1ms won't make any
 difference for a compiler run.


It's not about lexing a single file like std.datetime. We're takling be 
able to fast lex, I don't know, 100 or 1000 of files like std.datetime.

-- 
/Jacob Carlborg
Feb 28 2013
parent reply Artur Skawina <art.08.09 gmail.com> writes:
On 02/28/13 15:20, Jacob Carlborg wrote:

 On 2013-02-28 15:08, Artur Skawina wrote:
 

 Having said that, I've used this approach in a D lexer, and it does not really
 matter in practice - avoiding the length (or '\0' sentinel) check makes a
 <~1ms difference when lexing "datetime.d" sized objects (1.5Mbytes+, 460k+
tokens).
 Which is practically irrelevant both in an IDE context and a compiler context
 - other processing will be be orders of magnitude more expensive. An IDE
doesn't
 need to re-lex the whole file after every key press and 1ms won't make any
 difference for a compiler run.


 
 It's not about lexing a single file like std.datetime. We're takling be able
to fast lex, I don't know, 100 or 1000 of files like std.datetime.


Define "fast". Lexing std.datetime takes at most ~10-20ms (possibly a
single-digit
ms number, but i'd need to write some code to check the actual number). Smaller
objects take proportionally less. Meaning you'll be I/O bound, even /one/ (disk)
cache miss will have more impact then these kind of optimizations. 
Lexing a hundred small files or one 100x as big file is basically the same
operation;
the difference will be in I/O + setup/teardown costs, which will be /outside/
the
lexer, so aren't affected by how it accesses input.

artur
Feb 28 2013
parent reply Jacob Carlborg <doob me.com> writes:
On 2013-02-28 15:47, Artur Skawina wrote:


 Define "fast". Lexing std.datetime takes at most ~10-20ms (possibly a
single-digit
 ms number, but i'd need to write some code to check the actual number). Smaller
 objects take proportionally less. Meaning you'll be I/O bound, even /one/
(disk)
 cache miss will have more impact then these kind of optimizations.
 Lexing a hundred small files or one 100x as big file is basically the same
operation;
 the difference will be in I/O + setup/teardown costs, which will be /outside/
the
 lexer, so aren't affected by how it accesses input.


You'll have to convince Walter.

-- 
/Jacob Carlborg
Feb 28 2013
next sibling parent Artur Skawina <art.08.09 gmail.com> writes:
On 02/28/13 16:00, Jacob Carlborg wrote:

 On 2013-02-28 15:47, Artur Skawina wrote:
 

 Define "fast". Lexing std.datetime takes at most ~10-20ms (possibly a
single-digit
 ms number, but i'd need to write some code to check the actual number). Smaller
 objects take proportionally less. Meaning you'll be I/O bound, even /one/
(disk)
 cache miss will have more impact then these kind of optimizations.
 Lexing a hundred small files or one 100x as big file is basically the same
operation;
 the difference will be in I/O + setup/teardown costs, which will be /outside/
the
 lexer, so aren't affected by how it accesses input.


 
 You'll have to convince Walter.


Actually, no -- like i said: /I'd like to have such std ranges/ - there are
real gains to be had. I'm just saying that for the "fast lexer" case the
/absolute/ improvement isn't necessarily very large. Modern compilers can do
wonders.

The advantage of defining /std/ range types is, well, that they are "std";
everybody doesn't have to reinvent them, often with inadequate docs and
subtle differences in behavior. In this case the interesting properties are:

a) terminating sentinel
b) limited lookahead ("a" is a special case of "b")
c) lazyness

It's better to have a common interface than having everybody invent a
private one every time some of the above features are needed. 


artur
Feb 28 2013
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
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.
Feb 28 2013
next sibling parent reply FG <home fgda.pl> writes:
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.
Feb 28 2013
parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
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
Feb 28 2013
prev sibling parent Marco Leise <Marco.Leise gmx.de> writes:
Am Thu, 28 Feb 2013 14:27:28 -0800
schrieb Walter Bright <newshound2 digitalmars.com>:


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


That's what I thought and why I keep telling that Carthago has
to..., I mean that Phobos and the GC is not the ultimate
performance platform. You just don't get fast + safe +
convenient in one package, it's a compromise.


 Throwing compile speed under the bus is what other compiler vendors do, and 
 we're not going to do that.


I certainly hope so :D. It's just amazing that you barely
notice a delay when compiling a medium sized program. DMD
practically competes with interpreted languages here in terms
of turn-around time.

-- 
Marco
Feb 28 2013