Hackerpilot/Dscanner — pull request #28 by blackwhale (2013-02-16 18:51:58+00:00)
Title: New buffering scheme for std.d.lexer

Okay, this is my first invasive change. It's not complete, this pull request is a preview for a change I believe has great merit both performance-wise and architecture-wise. I plan to finish it, but putting it here so we can coordinate and sync our efforts early on.

For the moment I've stubbed out some heredoc and tokenized lexing (easy to fix but I wasn't sure what I'm doing with them) and screwed in a couple of other places I guess.
Also I've cut some corners to make it work and introduced allocations in a couple of places etc. those should be marked with TODOs.

Anyway the current state of pull: it lexes std.datetime and some other modules (the ones without aforementioned strings). The number of tokens is a bit less though, like I said it's a preview and needs more testing. I've added a tiny inline unittest, but a lot more of these is required when we get to Phobos inclusion & formal review.

The key point in this pull is the new abstraction, I call it mark-slice range. It's an absolute minimal interface that lexer can *comfortably* deal with. Basically it's a forward range that can be told to remember stuff starting from some marked position and then get a slice of it up to current position.

Logically then all buffering is thrown out of lexer and into mark-slice range that sits on top of ForwardRange, the other one that wraps RA-range needs no buffering at all.

This is the second point - the buffering is largely unneeded in current test of lexer called on RA-range of bytes. The though points are unescaping strings and such, but I've handled it (or so I think ;) ). The last thing that might help is some support for lookahead in this mark-slice range...

Plus some things that flow from there: setTokenValue was generalized to use mark-slice, etc. etc. I probably again spoiled the original style, plus I really don't get scope(exit) as code doesn't handle exceptions in any nice way (non-exception safe) so killed thouse where applicable.

Anyway even in this frankenstein state of lexer I have these numbers on my linux VBox (I've re-enabled -O5 with ldc, *now* it seems to boost things).

//LDC -O2 this branch:
dmitry@dmitry-VirtualBox ~/Dscanner $ avgtime -q -r 200 ./dscanner-ldc --tokenCount phobos/std/datetime.d

------------------------
Total time (ms): 6912.11
Repetitions : 200
Sample mode : 34 (64 ocurrences)
Median time : 34.4125
Avg time : 34.5606
Std dev. : 1.57907
Minimum : 31.587
Maximum : 46.798
95% conf.int. : [31.4656, 37.6555] e = 3.09493
99% conf.int. : [30.4931, 38.628] e = 4.06742
EstimatedAvg95%: [34.3417, 34.7794] e = 0.218844
EstimatedAvg99%: [34.2729, 34.8482] e = 0.28761
dmitry@dmitry-VirtualBox ~/Dscanner $ nano build.sh
dmitry@dmitry-VirtualBox ~/Dscanner $ ./build.sh
dmitry@dmitry-VirtualBox ~/Dscanner $ avgtime -q -r 200 ./dscanner-ldc --tokenCount phobos/std/datetime.d

//with -O5
------------------------
Total time (ms): 5883.65
Repetitions : 200
Sample mode : 29 (99 ocurrences)
Median time : 29.325
Avg time : 29.4183
Std dev. : 1.15235
Minimum : 27.223
Maximum : 39.605
95% conf.int. : [27.1597, 31.6768] e = 2.25857
99% conf.int. : [26.45, 32.3865] e = 2.96826
EstimatedAvg95%: [29.2586, 29.578] e = 0.159705
EstimatedAvg99%: [29.2084, 29.6282] e = 0.209888

The old timings before and after better string cache was introduced (I can't recall switches I used with these though, but both with ldc):

dmitry@dmitry-VirtualBox ~/Dscanner $ avgtime -q -r 200 ./old-dscanner --tokenCount phobos/std/datetime.d

------------------------
Total time (ms): 7805.68
Repetitions : 200
Sample mode : 38 (98 ocurrences)
Median time : 38.722
Avg time : 39.0284
Std dev. : 1.73491
Minimum : 36.787
Maximum : 50.302
95% conf.int. : [35.6281, 42.4288] e = 3.40035
99% conf.int. : [34.5596, 43.4972] e = 4.46882
EstimatedAvg95%: [38.788, 39.2689] e = 0.240441
EstimatedAvg99%: [38.7124, 39.3444] e = 0.315993
dmitry@dmitry-VirtualBox ~/Dscanner $ avgtime -q -r 200 ./new-dscanner --tokenCount phobos/std/datetime.d

------------------------
Total time (ms): 7205.88
Repetitions : 200
Sample mode : 35 (89 ocurrences)
Median time : 35.618
Avg time : 36.0294
Std dev. : 2.11589
Minimum : 33.432
Maximum : 52.962
95% conf.int. : [31.8823, 40.1765] e = 4.14706
99% conf.int. : [30.5792, 41.4796] e = 5.45016
EstimatedAvg95%: [35.7362, 36.3226] e = 0.293241
EstimatedAvg99%: [35.644, 36.4148] e = 0.385385
dmitry@dmitry-VirtualBox ~/Dscanner $