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

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).

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

------------------------
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.

------------------------
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

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. :)

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. :)

> But I do not think you can extend a memory block with C functions.

What about realloc?

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?

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);
}