March 04, 2013 Re: Lexer in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Namespace | 04-Mar-2013 23:19, Namespace пишет: > Yes, but I'm not as familiar with ranges. But I want to learn more about > them and try it then. > What do you mean, how much would entail the use of ranges compared to my > current method? 30%? Basically you copy Token structs and sometimes reallocate the whole array (I guess at 60% you don't reallocate but waste time on GC.malloc that zeroes out memory block). My estimate is no less then 10-15%. -- Dmitry Olshansky |
March 04, 2013 Re: Lexer in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Dmitry Olshansky | On Monday, 4 March 2013 at 18:10:48 UTC, Dmitry Olshansky wrote: > Brain listed graphs showing under 20 ms on his CPU. for all and <10 for every module in std except std.datetime. https://github.com/Hackerpilot/Dscanner/blob/range-based-lexer/perftest.sh I checked in the script that I use to generate the data for the graph last night. You can copy/paste its output into a spreadsheet (using tabs as field separators). |
March 04, 2013 Re: Lexer in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Brian Schott | 05-Mar-2013 01:35, Brian Schott пишет: > On Monday, 4 March 2013 at 18:10:48 UTC, Dmitry Olshansky wrote: >> Brain listed graphs showing under 20 ms on his CPU. for all and <10 >> for every module in std except std.datetime. > > https://github.com/Hackerpilot/Dscanner/blob/range-based-lexer/perftest.sh > > I checked in the script that I use to generate the data for the graph > last night. You can copy/paste its output into a spreadsheet (using tabs > as field separators). Great, thanks! I'll see if I can make a plot from it with std-dev shown as well. -- Dmitry Olshansky |
March 11, 2013 Re: Lexer in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Namespace | ------------------------ Total time (ms): 11374.4 Repetitions : 200 Sample mode : 56 (89 ocurrences) Median time : 56.312 Avg time : 56.872 Std dev. : 2.60698 Minimum : 53.978 Maximum : 81.602 95% conf.int. : [51.7624, 61.9816] e = 5.10959 99% conf.int. : [50.1569, 63.5871] e = 6.71514 EstimatedAvg95%: [56.5107, 57.2333] e = 0.361303 EstimatedAvg99%: [56.3972, 57.3468] e = 0.474832 I'm getting closer. |
March 11, 2013 Re: Lexer in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Namespace | ------------------------ Total time (ms): 10941.9 Repetitions : 200 Sample mode : 54 (118 ocurrences) Median time : 54.5855 Avg time : 54.7094 Std dev. : 1.33935 Minimum : 52.535 Maximum : 67.206 95% conf.int. : [52.0843, 57.3345] e = 2.62509 99% conf.int. : [51.2594, 58.1593] e = 3.44995 EstimatedAvg95%: [54.5238, 54.895] e = 0.185622 EstimatedAvg99%: [54.4654, 54.9533] e = 0.243948 And even a bit closer. I've also done some benchmarks. And I wonder why my appender is much faster if I enable memory reservation. My Appender: http://dpaste.1azy.net/1bb34d9a I'm also very interested to hear some improvements tips. In each benchmark 1_000_000 times these struct is appended: struct B { public: const int b; } Without memory reserve: My Appender: ------------------------ Total time (ms): 7638.67 Repetitions : 200 Sample mode : 38 (68 ocurrences) Median time : 38.0545 Avg time : 38.1934 Std dev. : 1.56827 Minimum : 35.859 Maximum : 47.586 95% conf.int. : [35.1196, 41.2671] e = 3.07375 99% conf.int. : [34.1538, 42.233] e = 4.0396 EstimatedAvg95%: [37.976, 38.4107] e = 0.217347 EstimatedAvg99%: [37.9077, 38.479] e = 0.285643 D's Appender: ------------------------ Total time (ms): 6972.66 Repetitions : 200 Sample mode : 34 (97 ocurrences) Median time : 34.7795 Avg time : 34.8633 Std dev. : 1.41623 Minimum : 32.96 Maximum : 49.579 95% conf.int. : [32.0876, 37.6391] e = 2.77576 99% conf.int. : [31.2153, 38.5113] e = 3.64797 EstimatedAvg95%: [34.667, 35.0596] e = 0.196276 EstimatedAvg99%: [34.6054, 35.1213] e = 0.257951 D array: ------------------------ Total time (ms): 22868.2 Repetitions : 200 Sample mode : 110 (198 ocurrences) Median time : 113.658 Avg time : 114.341 Std dev. : 1.97184 Minimum : 113.011 Maximum : 133.978 95% conf.int. : [110.477, 118.206] e = 3.86473 99% conf.int. : [109.262, 119.42] e = 5.07911 EstimatedAvg95%: [114.068, 114.615] e = 0.273277 EstimatedAvg99%: [113.982, 114.7] e = 0.359147 With memory reserve: My Appender: ------------------------ Total time (ms): 6197.48 Repetitions : 200 Sample mode : 30 (88 ocurrences) Median time : 30.617 Avg time : 30.9874 Std dev. : 2.86913 Minimum : 28.583 Maximum : 64.06 95% conf.int. : [25.364, 36.6108] e = 5.62339 99% conf.int. : [23.597, 38.3778] e = 7.39039 EstimatedAvg95%: [30.5897, 31.385] e = 0.397634 EstimatedAvg99%: [30.4648, 31.51] e = 0.52258 D's Appender: ------------------------ Total time (ms): 6628.31 Repetitions : 200 Sample mode : 32 (104 ocurrences) Median time : 32.6775 Avg time : 33.1415 Std dev. : 3.00344 Minimum : 31.506 Maximum : 57.493 95% conf.int. : [27.2549, 39.0282] e = 5.88663 99% conf.int. : [25.4052, 40.8779] e = 7.73635 EstimatedAvg95%: [32.7253, 33.5578] e = 0.416248 EstimatedAvg99%: [32.5945, 33.6886] e = 0.547042 D array: ------------------------ Total time (ms): 22849.9 Repetitions : 200 Sample mode : 110 (198 ocurrences) Median time : 113.025 Avg time : 114.249 Std dev. : 8.40906 Minimum : 112.355 Maximum : 222.982 95% conf.int. : [97.768, 130.731] e = 16.4815 99% conf.int. : [92.5891, 135.91] e = 21.6603 EstimatedAvg95%: [113.084, 115.415] e = 1.16542 EstimatedAvg99%: [112.718, 115.781] e = 1.53162 |
March 11, 2013 Re: Lexer in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Namespace | On 2013-03-11 16:11, Namespace wrote: > I've also done some benchmarks. And I wonder why my appender is much faster if I > enable memory reservation. Probably just because D's Appender has a better growth scheme than yours and you reallocate too often. Try to compare how often that happens. > I'm also very interested to hear some improvements tips. Well, you may add a check whether alloc/realloc actually succeeded. :) |
March 11, 2013 Re: Lexer in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to FG | On Monday, 11 March 2013 at 15:21:31 UTC, FG wrote: > On 2013-03-11 16:11, Namespace wrote: >> I've also done some benchmarks. And I wonder why my appender is much faster if I >> enable memory reservation. > > Probably just because D's Appender has a better growth scheme than yours and you reallocate too often. Try to compare how often that happens. D's: 24 extends, 9 moves (qalloc + memcpy). My Appender: 25 moves. But I do not think you can extend a memory block with C functions. >> I'm also very interested to hear some improvements tips. > > Well, you may add a check whether alloc/realloc actually succeeded. :) Maybe. :) |
March 11, 2013 Re: Lexer in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Namespace | > But I do not think you can extend a memory block with C functions.
What about realloc?
|
March 11, 2013 Re: Lexer in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to David | On Monday, 11 March 2013 at 15:51:58 UTC, David wrote:
>> But I do not think you can extend a memory block with C functions.
>
> What about realloc?
That's what I use. But it moves your old memory into the new allocated. Or proves it first if your current memory block could be extended?
|
March 11, 2013 Re: Lexer in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Namespace | On Monday, 11 March 2013 at 15:56:37 UTC, Namespace wrote: > On Monday, 11 March 2013 at 15:51:58 UTC, David wrote: >>> But I do not think you can extend a memory block with C functions. >> >> What about realloc? > > That's what I use. But it moves your old memory into the new allocated. Or proves it first if your current memory block could be extended? extends if possible. http://dpaste.dzfl.pl/f86e5db6 import core.stdc.stdlib; void main() { auto p1 = malloc(14); auto p2 = realloc(p1, 15); assert(p1 is p2); } |
Copyright © 1999-2021 by the D Language Foundation