Optimizations for toArray and fromArray

[dnlmlr]

I made some further optimizations to the _copyArray function that I missed last time (#43) and also optimized the _fromArray function. This in turn provides a large improvement when initializing the Denque from an array and also in some situations when exporting to an array.

Creating the queue from an array with the new preallocating code avoids growth and is a significant improvement on large arrays:

• 338 ops/sec vs 841 ops/sec

  Running fromArray.js
  denque x 338 ops/sec ±0.88% (84 runs sampled)
  denque (mod) x 841 ops/sec ±1.01% (85 runs sampled)
  double-ended-queue x 176 ops/sec ±0.90% (81 runs sampled)

Using Array.slice in _copyArray to create copies with the same size on contiguous buffer data is also a pretty good performance boost in situations where it applies. This applies in every situation where head < tail. Not sure why but before when head < tail and head != 0, is was noticeably slow. This is now fixed

• 92.41 ops/sec vs 156 ops/sec when head is 0, but no wrapping
• 39.84 ops/sec vs 151 ops/sec when head is not 0, but no wrapping
• 90.74 ops/sec vs 91.14 ops/sec when wrapping

  Running toArray.js
  denque (head at 0) x 92.41 ops/sec ±0.97% (68 runs sampled)
  denque (mod) (head at 0) x 156 ops/sec ±1.33% (72 runs sampled)
  double-ended-queue (head at 0) x 87.69 ops/sec ±1.05% (74 runs sampled)
  denque (non-contiguous) x 90.74 ops/sec ±0.89% (66 runs sampled)
  denque (mod) (non-contiguous) x 91.14 ops/sec ±0.91% (67 runs sampled)
  double-ended-queue (non-contiguous) x 88.43 ops/sec ±0.69% (75 runs sampled)
  denque (non zero head) x 39.84 ops/sec ±0.71% (53 runs sampled)
  denque (mod) (non zero head) x 151 ops/sec ±0.94% (70 runs sampled)
  double-ended-queue (non zero head) x 87.74 ops/sec ±0.73% (74 runs sampled)
  array copy (prealloc + for loop) x 94.32 ops/sec ±0.67% (71 runs sampled)
  array copy (no prealloc + for loop) x 27.99 ops/sec ±5.86% (48 runs sampled)
  array copy (slice) x 157 ops/sec ±0.43% (79 runs sampled)

The full benchmark results and scripts for validation is again found in the benchmark repository

PS: The _fromArray optimization adds a _nextPowerOf2 function that calculates the next power of 2 to directly allocate the buffer with the correct size. This could be used to implement #42.

[codecov[bot]]

Codecov Report

Merging #46 (a7fce30) into master (f400043) will not change coverage. The diff coverage is 100.00%.

:exclamation: Current head a7fce30 differs from pull request most recent head 61812bf. Consider uploading reports for the commit 61812bf to get more accurate results

@@            Coverage Diff            @@
##            master       #46   +/-   ##
=========================================
  Coverage   100.00%   100.00%           
=========================================
  Files            1         1           
  Lines          224       237   +13     
  Branches        48        49    +1     
=========================================
+ Hits           224       237   +13     

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 f400043...61812bf. Read the comment docs.