Optimized growth and array copy

[dnlmlr]

I changed the _copyArray and _growArray functions to use an array with predefined size (new Array(N)) to avoid implicit copies & reallocations. Despite some sources saying that preallocation using new Array(N) does not improve performance, all my tests and benchmarks suggest otherwise. All tests are of course still working. I made a comprehensive benchmark setup that contains the orginal benchmarks and a few extra, comparing the original and modified implementations.

Some of the benchmarks with large numbers of operations / sec and similar performance between original and modified were really inconsistent and traded places when running in a different order. So I would not count those as regressions.

However the splice benchmark showed consistently better performance and the newly added growth and toArray benchmarks had major performance improvements compared to the original.

The growth benchmark tests the actual performance while growing and shifting at the same time (1000x push, 500x shift, 1000x push, 1500x shift).

The toArray benchmark simply measures the time it takes to run toArray (which also uses the _copyArray function directly).

Running growth.js denque x 27,636 ops/sec ±1.73% (82 runs sampled) denque (mod) x 50,995 ops/sec ±0.30% (93 runs sampled) double-ended-queue x 21,171 ops/sec ±0.16% (95 runs sampled)

Running splice.js denque.splice x 827,636 ops/sec ±20.30% (77 runs sampled) denque.splice (mod) x 955,175 ops/sec ±7.15% (84 runs sampled) native array splice x 10,934 ops/sec ±36.89% (28 runs sampled)

Running toArray.js denque x 22.74 ops/sec ±2.37% (41 runs sampled) denque (mod) x 106 ops/sec ±0.42% (76 runs sampled) double-ended-queue x 99.84 ops/sec ±0.48% (73 runs sampled)

For the full benchmark results and how to run it please refer to the repository.

I normally work with lower level languages so it is entirely possible that my testing is flawed or I missed anything else. Therefore I invite everyone to validate or challenge my results.

[CLAassistant]

All committers have signed the CLA.

[codecov[bot]]

Codecov Report

Merging #43 (36f3f5d) into master (a299325) will not change coverage. The diff coverage is 100.00%.

:exclamation: Current head 36f3f5d differs from pull request most recent head 4414b53. Consider uploading reports for the commit 4414b53 to get more accurate results

@@            Coverage Diff            @@
##            master       #43   +/-   ##
=========================================
  Coverage   100.00%   100.00%           
=========================================
  Files            1         1           
  Lines          221       224    +3     
  Branches        48        48           
=========================================
+ Hits           221       224    +3     

Impacted Files	Coverage Δ
index.js	100.00% <100.00%> (ø)

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update a299325...4414b53. Read the comment docs.

[Salakar]

This is such a well put together PR with detailed benchmark which made it extremely easy to review and test out, thank you! I'm happy to ship this

[Salakar]

I'd also be happy to accept the growth benchmark as a PR, it'd be good to have to make sure no regressions in future.

[Salakar]

Will ship this on Monday, thanks again