Proposal for SentinelInputRange

[Jonathan M Davis]

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