February 28, 2013 Re: Proposal for SentinelInputRange | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | On 2/28/2013 9:10 AM, Andrei Alexandrescu wrote:
> I don't think what I said was understood.
I know the feeling :-)
|
February 28, 2013 Re: Proposal for SentinelInputRange | ||||
---|---|---|---|---|
| ||||
Posted in reply to Dmitry Olshansky | On 2/28/2013 9:06 AM, Dmitry Olshansky wrote:
> 28-Feb-2013 20:56, Walter Bright пишет:
>> The merit is having significantly faster speed.
> 5% is good but doesn't count as significant. But that was for std.regex quite
> sometime ago. In the lexer it might get be more.
Even 5% is worth getting, and especially so because it's low hanging fruit.
I hear from people who have switched over to D and compile speed was a BIG factor. And I know you are well cognizant of the fact that for regex, speed is also a very big deal.
|
February 28, 2013 Re: Proposal for SentinelInputRange | ||||
---|---|---|---|---|
| ||||
Posted in reply to Steven Schveighoffer | On 2/28/2013 9:25 AM, Steven Schveighoffer wrote: > On Thu, 28 Feb 2013 12:00:48 -0500, Walter Bright <newshound2@digitalmars.com> > wrote: > >> On 2/28/2013 6:31 AM, Steven Schveighoffer wrote: >>> If this doesn't translate to the same code, I don't know why not. >> >> Try it and see with your favorite C compiler. > > A sample case of 1 does not prove it's not possible, or explain why those > optimizers don't take that step. A valid response would be to give a case why > an optimizer COULDN'T make that leap. No, it is not. DMD is compiled with real compilers, not abstract "sufficiently smart compilers". >> Then try the lookahead cases I also posted. > > You have already stated it gets changed into a jump table. Please, please listen to what I write. This is very frustrating. The code in lexer.c is there for all to see, and it amply illustrates everything I'm saying. For example, this code does not get translated into a jump table: case '+': p++; if (*p == '=') { p++; t->value = TOKaddass; } else if (*p == '+') { p++; t->value = TOKplusplus; } else t->value = TOKadd; return; > Such an optimization > seems possible to me, even with the != 0 check outside the switch, even if not > all C compilers employ it. It doesn't matter if it is theoretically possible if the compilers we need to use do not do it. |
February 28, 2013 Re: Proposal for SentinelInputRange | ||||
---|---|---|---|---|
| ||||
Posted in reply to Steven Schveighoffer | On 2/28/2013 9:18 AM, Steven Schveighoffer wrote:
> The point is, if the lexer simply requires an input range, and not a sentinel
> input range, it is more flexible for its input. But when it does get called
> with a sentinel input range, the optimizer can reap the benefits.
I suggest you compile lexer.c with various compilers, add in a !empty() call before every front(), and verify your assumption about this.
|
February 28, 2013 Re: Proposal for SentinelInputRange | ||||
---|---|---|---|---|
| ||||
Posted in reply to Walter Bright | On 02/28/2013 10:40 PM, Walter Bright wrote:
> On 2/28/2013 9:05 AM, deadalnix wrote:
>> I see nothing that can't be done by an optimizing compiler. Maybe
>> something is,
>> but I can't find it. And the example you pointed me aren't.
>
> Tell me how front() will be optimized out to this.
>
> case '>':
> p++;
> if (*p == '=')
> { p++;
> t->value = TOKge; // >=
> }
> else if (*p == '>')
> { p++;
> if (*p == '=')
> { p++;
> t->value = TOKshrass; // >>=
> }
> else if (*p == '>')
> { p++;
> if (*p == '=')
> { p++;
> t->value = TOKushrass; // >>>=
> }
> else
> t->value = TOKushr; // >>>
> }
> else
> t->value = TOKshr; // >>
> }
> else
> t->value = TOKgt; // >
> return;
I'd be surprised if DMD couldn't do it already.
assume: popFront(){ p++; }, front()=>*p, empty()=>*p=='\0'
case '>':
popFront();
if(!empty && front == '='){
popFront();
t->value = TOKge; // >=
}else if(!empty && front == '>'){
popFront();
if(!empty && front == '='){
popFront();
t->value = TOKshrass; // >>=
}else if(!empty && front == '>'){
popFront();
if(!empty && front == '='){
popFront();
t->value = TOKushrass; // >>>=
}else t->value = TOKushr; // >>>
}else t->value = TOKshr; // >>
}else t->value = TOKgt; // >
return;
// inlining =>
case '>':
p++;
if(!(*p=='\0') && *p == '='){
p++;
t->value = TOKge; // >=
}else if(!(*p=='\0') && *p == '>'){
p++;
if(!(*p=='\0') && *p == '='){
p++;
t->value = TOKshrass; // >>=
}else if(!(*p=='\0') && *p == '>'){
p++;
if(!(*p=='\0') && *p == '='){
p++;
t->value = TOKushrass; // >>>=
}else t->value = TOKushr; // >>>
}else t->value = TOKshr; // >>
}else t->value = TOKgt; // >
return;
// expression simplification
// (eg. trivial peephole for x!=a && x==b case sufficient)
// =>
case '>':
p++;
if(*p == '='){
p++;
t->value = TOKge; // >=
}else if(*p == '>'){
p++;
if(*p == '='){
p++;
t->value = TOKshrass; // >>=
}else if(*p == '>'){
p++;
if(*p == '='){
p++;
t->value = TOKushrass; // >>>=
}else t->value = TOKushr; // >>>
}else t->value = TOKshr; // >>
}else t->value = TOKgt; // >
return;
|
February 28, 2013 Re: Proposal for SentinelInputRange | ||||
---|---|---|---|---|
| ||||
Posted in reply to deadalnix | On 2/28/2013 10:12 AM, deadalnix wrote:
> On Thursday, 28 February 2013 at 17:00:51 UTC, Walter Bright wrote:
>> On 2/28/2013 6:31 AM, Steven Schveighoffer wrote:
>>> If this doesn't translate to the same code, I don't know why not.
>>
>> Try it and see with your favorite C compiler.
>>
>> Then try the lookahead cases I also posted.
>
> You are being stubborn here.
>
> You claim that this is significantly faster, but give no numbers.
> You claim that the compiler can't do some optimization, when LLVM does it already.
I didn't say can't, I said didn't. llvm handles that case (which does surprise me), dmc, gcc, and vc do not. Furthermore, I'll say "cannot" on this:
case '|':
p++;
if (*p == '=')
{ p++;
t->value = TOKorass;
}
else if (*p == '|')
{ p++;
t->value = TOKoror;
}
else
t->value = TOKor;
return;
|
February 28, 2013 Re: Proposal for SentinelInputRange | ||||
---|---|---|---|---|
| ||||
Posted in reply to Peter Alexander | On 2/28/2013 5:02 AM, Peter Alexander wrote:
> On Thursday, 28 February 2013 at 10:57:29 UTC, Walter Bright wrote:
>>> My worry here is that we are setting a precedent for adding new range concepts.
>>> If the only justification needed is that is saves a single operation in some
>>> niche area of computing then we are opening the door to a LOT of different range
>>> concepts.
>>
>> There are many cases where speed is a very big deal.
>
> Yes, are we going to add new range categories every time there's a performance
> benefit to doing so?
>
> has16ByteAlignedElements
> hasUniqueElements
> hasContiguousMemory
> isMonotonic
> isUnimodal
> ...
> ?
Depends on whether one can make a good case for them.
|
February 28, 2013 Re: Proposal for SentinelInputRange | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jacob Carlborg | On 2/28/2013 7:00 AM, Jacob Carlborg wrote:
> You'll have to convince Walter.
I've spent a lot of time profiling compilers. The result is pretty obvious - dmc is by far the fastest C/C++ compiler available, and dmd blows away about every other language in compile speed.
Making this happen means you go after everything that eats time. Even a 5% improvement is a big deal. All those drips and draps add up to big speed increases.
Two corporate users of D have also told me that their motivating case to adopt D was - compile speed!
Throwing compile speed under the bus is what other compiler vendors do, and we're not going to do that.
|
February 28, 2013 Re: Proposal for SentinelInputRange | ||||
---|---|---|---|---|
| ||||
Posted in reply to Walter Bright | On 2013-02-28 23:27, Walter Bright wrote:
> I've spent a lot of time profiling compilers. The result is pretty obvious - dmc
> is by far the fastest C/C++ compiler available, and dmd blows away about every
> other language in compile speed.
>
> Making this happen means you go after everything that eats time. Even a 5%
> improvement is a big deal. All those drips and draps add up to big speed increases.
I get that, but it doesn't require introducing a new type of range.
|
February 28, 2013 Re: Proposal for SentinelInputRange | ||||
---|---|---|---|---|
| ||||
Posted in reply to Walter Bright | 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.
|
Copyright © 1999-2021 by the D Language Foundation