February 09, 2013
On 2/9/13 3:49 PM, Walter Bright wrote:
> On 2/9/2013 12:43 PM, Walter Bright wrote:> Perhaps we can formalize
> this a bit. Define a SentinelInputRange, which has an
>  > additional manifest constant with the name 'sentinel'. empty becomes
> defined as:
>  >
>  > empty = front == sentinel;
>  >
>  > popFront() does not advance if empty. Advancing over a
> SentinelInputRange can be
>  > done the usual:
>  >
>  > for (r = range; !r.empty; r.popFront()) { auto e = r.front; }
>  >
>  > or can be done as:
>  >
>  > for (r = range; r.front != sentinel; r.popFront()) { auto e = r.front; }
>
> If it's not clear, SentinelInputRange.front can be called *before*
> checking empty. If it is empty, then the sentinel is returned.

Yah, that all would fit C-style strings and singly-linked lists like a glove. I've been long hoping the opportunity to define such a range would present itself :o).

Andrei
February 10, 2013
On Sunday, February 10, 2013 00:26:41 Dmitry Olshansky wrote:
> 09-Feb-2013 19:46, Andrei Alexandrescu пишет:
> > On 2/9/13 10:37 AM, Jacob Carlborg wrote:
> >> On 2013-02-09 16:10, Andrei Alexandrescu wrote:
> >>> Requiring a random-access range of ubyte with a terminating zero may be the most general approach to a fast lexer - and that's fine.
> >> 
> >> Requiring a random-access range probably makes it easier. People here seems to try to support ranges with less functionality, like input or forward ranges.
> > 
> > Yah. The way I see it is, start with a random-access range and then see what the use patterns are. Then possibly refine.
> 
> I don't get this. There is no sensible requirement to forbid non-random access. A couple of static ifs and you are done.
> 
> And I can confidently say that std.d.lexer has quite some room for optimization in both cases and it doesn't have to sacrifice the generic path.

It may end up being less efficient with some types of ranges, but it can still work, and someone's use case may not care about that extra loss of efficiency. Those who really do can use RA ranges or strings or whatever.

But if we throw too many extra restrictions on the ranges (like they have to be random access or end with 0), then pretty soon you might as well require that they use string, because the extra benefit of the few extra types of ranges which would work wolud be pretty minimal.

- Jonathan M Davis
February 28, 2013
On Saturday, 9 February 2013 at 07:55:04 UTC, Walter Bright wrote:
> On 2/4/2013 7:19 PM, Brian Schott wrote:
>> Still only half speed. I'm becoming more and more convinced that Walter is
>> actually a wizard.
>
> I worship the Dark Arts.

*recites incantations*
*merges pull requests*
*adds unit tests*

http://hackerpilot.github.com/experimental/std_lexer/images/times4.png
February 28, 2013
On 2/28/13, Brian Schott <briancschott@gmail.com> wrote:
> http://hackerpilot.github.com/experimental/std_lexer/images/times4.png

That's a nice plot, but what is the X axis?
February 28, 2013
On 2013-02-28 16:34, Andrej Mitrovic wrote:
> On 2/28/13, Brian Schott <briancschott@gmail.com> wrote:
>> http://hackerpilot.github.com/experimental/std_lexer/images/times4.png
>
> That's a nice plot, but what is the X axis?

Lexing time in milliseconds.

February 28, 2013
28-Feb-2013 13:09, Brian Schott пишет:
> On Saturday, 9 February 2013 at 07:55:04 UTC, Walter Bright wrote:
>> On 2/4/2013 7:19 PM, Brian Schott wrote:
>>> Still only half speed. I'm becoming more and more convinced that
>>> Walter is
>>> actually a wizard.
>>
>> I worship the Dark Arts.
>
> *recites incantations*
> *merges pull requests*
> *adds unit tests*
>
> http://hackerpilot.github.com/experimental/std_lexer/images/times4.png

Looking far better now. Keep in mind that we still don't use the original dmd's sentinel magic to avoid length check in std.d.lexer :)

Being that wizard who gave a couple of scrolls to Brain I'll outline some interesting data points collected while helping him out.

- D run-time takes some time to start up/shut down. It's on the order of 1ms for me vs 1/10th of ms for plain C
- expanding on the previous point - GC.malloc takes sometime and triggers collections from time to time (2 collections to lex datetime, there is next to no garbage, but they run regardless).

Even simply disabling GC at first and re-enabling it at the end of program speeds up the whole time by roughly 5% on my machine.

- opApply is definitely slower then inlined range-based foreach loop even with scope delegate.

Other then this specifics the prime spells that give the performance are:

- don't use built-in AA or subtle allocations (avoid GC as far as you can)

- lean common path, keep there only the operations that are required in *every* code-path

- avoid ever doing the same work twice (redesign, hack and whatnot but don't do it)


-- 
Dmitry Olshansky
February 28, 2013
28-Feb-2013 21:27, Dmitry Olshansky пишет:
> 28-Feb-2013 13:09, Brian Schott пишет:
>> On Saturday, 9 February 2013 at 07:55:04 UTC, Walter Bright wrote:
>>> On 2/4/2013 7:19 PM, Brian Schott wrote:
>>>> Still only half speed. I'm becoming more and more convinced that
>>>> Walter is
>>>> actually a wizard.
>>>
>>> I worship the Dark Arts.
>>
>> *recites incantations*
>> *merges pull requests*
>> *adds unit tests*
>>
>> http://hackerpilot.github.com/experimental/std_lexer/images/times4.png
>
> Looking far better now. Keep in mind that we still don't use the
> original dmd's sentinel magic to avoid length check in std.d.lexer :)
>
> Being that wizard who gave a couple of scrolls to Brain I'll outline
> some interesting data points collected while helping him out.
>

To clarify these are problems I observed but haven't solved/avoided completely:

> - D run-time takes some time to start up/shut down. It's on the order of
> 1ms for me vs 1/10th of ms for plain C
> - expanding on the previous point - GC.malloc takes sometime and
> triggers collections from time to time (2 collections to lex datetime,
> there is next to no garbage, but they run regardless).
>

And this one below is an experiment and not is not related to the numbers posted still.

> Even simply disabling GC at first and re-enabling it at the end of
> program speeds up the whole time by roughly 5% on my machine.


-- 
Dmitry Olshansky
9 10 11 12 13 14 15 16 17 18 19
Next ›   Last »