#223 - Improve before-index performance

[jeff303]

Adding before-index implementation that uses take/drop instead of setval/srange

Adding new functional test to confirm behavior when operating on a string

Adding benchmark for old versus new implementation of before-index

(Work in progress; the before-index implementation would be swapped out in the final patch).

Sample benchmark output:

********************************                                                                                                                                                                                                 
[47/1113]

Benchmark: old versus new before-index implementation

Mean(us)        vs best         Code
0.0838           1.00            (setval (before-index-new insert-idx) -1 data)
136              1.62e+03                (setval (before-index-old insert-idx) -1 data)

[nathanmarz]

Before I can look at these PRs I'll need you to sign a contributor agreement. I sent it over to your email.

[jeff303]

Before I can look at these PRs I'll need you to sign a contributor agreement. I sent it over to your email.

Signed

[jeff303]

OK, I switched over to a protocol based implementation to handle the different approaches. Here is the output from my latest run of the new benchmark:

Benchmark: old versus new before-index implementation (vector)

Mean(us)        vs best         Code
42.9             1.00            (setval (before-index-new insert-idx) -1 vec-data)
210              4.89            (setval (before-index-old insert-idx) -1 vec-data)

********************************

Benchmark: old versus new before-index implementation (list)

Mean(us)        vs best         Code
0.0799           1.00            (setval (before-index-new insert-idx) -1 list-data)
15.0             188             (setval (before-index-old insert-idx) -1 list-data)

[nathanmarz]

Looks good to merge once after fixing up the old/new stuff.

[jeff303]

Looks good to merge once after fixing up the old/new stuff.

I presume that having the benchmark isn't worth keeping the old implementation around? Assuming that is the case, I removed it. Alternatively, the old implementation could be defined locally in the benchmark namespace, I suppose.

[nathanmarz]

It would still be nice to have a benchmark for this. Maybe we could have three benchmarks:

• comparing against srange on insertion into middle of vector
• comparing against srange on insertion into middle of list
• comparing against cons on insertion to front of list

[jeff303]

It would still be nice to have a benchmark for this. Maybe we could have three benchmarks:

• comparing against srange on insertion into middle of vector
• comparing against srange on insertion into middle of list
• comparing against cons on insertion to front of list

Something like this?

Benchmark: before-index insertion new impl vs. srange and list cons

Mean(us)        vs best         Code
0.00948                  1.00            (cons v data-lst)
13.7             1.45e+03                (setval (srange middle-idx middle-idx) [v] data-lst)
36.8             3.89e+03                (setval (before-index middle-idx) v data-vec)
163              1.71e+04                (setval (srange middle-idx middle-idx) [v] data-vec)

[nathanmarz]

I was thinking three separate benchmarks against comparable code in each case.

[jeff303]

I was thinking three separate benchmarks against comparable code in each case.

Oh, right, that makes more sense.

Benchmark: before-index vs. srange (vector)

Mean(us)        vs best         Code
37.3             1.00            (setval (before-index middle-idx) v data-vec)
179              4.80            (setval (srange middle-idx middle-idx) [v] data-vec)

********************************

Benchmark: before-index vs. srange (list)

Mean(us)        vs best         Code
0.102            1.00            (setval (before-index middle-idx) v data-lst)
15.2             148             (setval (srange middle-idx middle-idx) [v] data-lst)

********************************

Benchmark: before-index at 0 vs. cons (list)

Mean(us)        vs best         Code
0.0161           1.00            (cons v data-lst)
0.0995           6.17            (setval (before-index 0) v data-lst)

********************************

[nathanmarz]

Seems like (before-index 0) case on lists could be improved pretty easily by special casing index=0 to only do the cons and not the split-at or concat.

Also worth adding (setval (srange 0 0) [v] data-list) to the benchmark to get a sense of the improvement for that case vs. the old implementation.

[jeff303]

Seems like (before-index 0) case on lists could be improved pretty easily by special casing index=0 to only do the cons and not the split-at or concat.

Also worth adding (setval (srange 0 0) [v] data-list) to the benchmark to get a sense of the improvement for that case vs. the old implementation.

That makes it only 3x slower instead of 6x.

Benchmark: before-index at 0 vs. srange vs. cons (list)

Mean(us)        vs best         Code
0.0119           1.00            (cons v data-lst)
0.0396           3.33            (setval (before-index 0) v data-lst)
16.5             1.38e+03                (setval (srange 0 0) [v] data-lst)