search

redplanetlabs / specter

Clojure(Script)'s missing piece
Apache License 2.0
2.51k stars 102 forks source link

Improve performance of removing elements from sequences #307

Open jeff303 opened 3 years ago

jeff303 commented 3 years ago

Merging InsertBeforeIndex protocol into new IndexedOps protocol for optimized indexed based operations (which now includes inserting before and removing at)

Updating nthpath and keypath to use new helper fns

Adding tests and benchmarks

jeff303 commented 3 years ago

I think this change should also cover must because it calls do-keypath-transform. Output of new benchmarks from my machine:


Benchmark: set keypath and nthpath at index to NONE versus srange in middle (vector)

Mean(us)    vs best     Code
31.2         1.00        (setval (nthpath middle-idx) NONE data-vec)
32.1         1.03        (setval (keypath middle-idx) NONE data-vec)
145          4.65        (setval (srange middle-idx (inc middle-idx)) [] data-vec)

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

Benchmark: set keypath and nthpath at index to NONE versus srange in middle (list)

Mean(us)    vs best     Code
5.56         1.00        (setval (keypath middle-idx) NONE data-lst)
12.5         2.24        (setval (srange middle-idx (inc middle-idx)) [] data-lst)
12.7         2.29        (setval (nthpath middle-idx) NONE data-lst)

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

Benchmark: set keypath and nthpath at beginning to NONE versus srange and subvec (vector)

Mean(us)    vs best     Code
0.0179       1.00        (subvec data-vec 1)
0.150        8.39        (setval (keypath 0) NONE data-vec)
0.160        8.89        (setval (nthpath 0) NONE data-vec)
107          5.98e+03        (setval (srange 0 1) [] data-vec)

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

Benchmark: set keypath and nthpath at beginning to NONE versus srange and rest (list)

Mean(us)    vs best     Code
0.00733          1.00        (rest data-lst)
0.192        26.3        (setval (keypath 0) NONE data-lst)
12.5         1.71e+03        (setval (srange 0 1) [] data-lst)
12.8         1.75e+03        (setval (nthpath 0) NONE data-lst)

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

Benchmark: set keypath and nthpath at end to NONE versus srange and subvec (vector)

Mean(us)    vs best     Code
0.0148       1.00        (subvec data-vec 0 (dec size))
0.257        17.4        (setval (keypath (dec size)) NONE data-vec)
0.275        18.6        (setval (nthpath (dec size)) NONE data-vec)
194          1.31e+04        (setval (srange (dec size) size) [] data-vec)

********************************
jeff303 commented 3 years ago

This should cover most of #219, although it doesn't do anything to address srange performance.