Performance benchmark

[justinlovinger]

The readme hints at a benchmark comparing the performance of ordered-collections with unordered-collections. Given that performance is the primary difference between these libraries, an extensive benchmark would be helpful.

[fehrenbach]

There are some in bench/. They also run in CI, but for some reason the output doesn't show up in the logs... CI is of course not an ideal environment for benchmarks, so you'd be better off running them yourself locally anyway.
I'd be more than happy to accept improvements to any aspect of the benchmarking situation.

[justinlovinger]

I think a table of benchmark results in the readme would be good.

[fehrenbach]

Agreed. I'd be happy to accept a PR that adds one.

[flip111]

The benchmarks don't run anymore. I tried to give a higher stack size when the default was not working.

» /usr/bin/time -v spago run --backend-args '--stack-size=64000'
Reading Spago workspace configuration...

✅ Selecting package to build: unordered-collections-bench

Downloading dependencies...
Building...
           Src   Lib   All
Warnings     0     0     0
Errors       0     0     0

✅ Build succeeded.

bulk loading from random order Array (Tuple Int String)
┌─────────┬───────┬───────────────────┬─────────────┬─────────────┬─────────────┬─────────────┬─────────┐
│ (index) │ size  │ name              │ min         │ mean        │ max         │ stdDev      │ runs    │
├─────────┼───────┼───────────────────┼─────────────┼─────────────┼─────────────┼─────────────┼─────────┤
│ 0       │ 100   │ 'HM.fromArray'    │ '3.52 μs'   │ '3.70 μs'   │ '749.18 μs' │ '1.51 μs'   │ 2726200 │
│ 1       │ 100   │ 'HM.fromFoldable' │ '3.86 μs'   │ '4.50 μs'   │ '102.86 μs' │ '3.77 μs'   │ 2223000 │
│ 2       │ 100   │ 'OM.fromFoldable' │ '13.61 μs'  │ '14.35 μs'  │ '116.41 μs' │ '4.16 μs'   │ 701300  │
│ 3       │ 10000 │ 'HM.fromArray'    │ '536.48 μs' │ '561.43 μs' │ '1.17 ms'   │ '65.26 μs'  │ 18000   │
│ 4       │ 10000 │ 'HM.fromFoldable' │ '940.93 μs' │ '1.15 ms'   │ '1.61 ms'   │ '125.27 μs' │ 8100    │
│ 5       │ 10000 │ 'OM.fromFoldable' │ '3.64 ms'   │ '3.96 ms'   │ '5.79 ms'   │ '158.34 μs' │ 2600    │
└─────────┴───────┴───────────────────┴─────────────┴─────────────┴─────────────┴─────────────┴─────────┘
look up all integer keys in random order
┌─────────┬───────┬─────────────┬─────────────┬─────────────┬─────────────┬────────────┬─────────┐
│ (index) │ size  │ name        │ min         │ mean        │ max         │ stdDev     │ runs    │
├─────────┼───────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼─────────┤
│ 0       │ 100   │ 'HM.lookup' │ '1.49 μs'   │ '1.86 μs'   │ '184.75 μs' │ '4.45 μs'  │ 5429000 │
│ 1       │ 100   │ 'OM.lookup' │ '3.86 μs'   │ '4.28 μs'   │ '180.96 μs' │ '5.02 μs'  │ 2380600 │
│ 2       │ 10000 │ 'HM.lookup' │ '308.26 μs' │ '349.87 μs' │ '763.14 μs' │ '80.74 μs' │ 28300   │
│ 3       │ 10000 │ 'OM.lookup' │ '1.16 ms'   │ '1.22 ms'   │ '2.18 ms'   │ '97.51 μs' │ 8400    │
└─────────┴───────┴─────────────┴─────────────┴─────────────┴─────────────┴────────────┴─────────┘
delete all integer keys in random order
┌─────────┬───────┬─────────────┬────────────┬────────────┬─────────────┬────────────┬─────────┐
│ (index) │ size  │ name        │ min        │ mean       │ max         │ stdDev     │ runs    │
├─────────┼───────┼─────────────┼────────────┼────────────┼─────────────┼────────────┼─────────┤
│ 0       │ 100   │ 'HM.delete' │ '5.86 μs'  │ '6.92 μs'  │ '199.90 μs' │ '8.27 μs'  │ 1562300 │
│ 1       │ 100   │ 'OM.delete' │ '14.13 μs' │ '15.07 μs' │ '210.01 μs' │ '8.44 μs'  │ 668500  │
│ 2       │ 10000 │ 'HM.delete' │ '1.66 ms'  │ '1.76 ms'  │ '2.39 ms'   │ '68.78 μs' │ 5800    │
│ 3       │ 10000 │ 'OM.delete' │ '4.34 ms'  │ '4.50 ms'  │ '4.97 ms'   │ '53.56 μs' │ 2300    │
└─────────┴───────┴─────────────┴────────────┴────────────┴─────────────┴────────────┴─────────┘
filter random map Int Int
┌─────────┬───────┬────────────────────────────────┬─────────────┬─────────────┬─────────────┬─────────────┬─────────┐
│ (index) │ size  │ name                           │ min         │ mean        │ max         │ stdDev      │ runs    │
├─────────┼───────┼────────────────────────────────┼─────────────┼─────────────┼─────────────┼─────────────┼─────────┤
│ 0       │ 100   │ 'HM.filterWithKey both   even' │ '1.66 μs'   │ '1.83 μs'   │ '170.25 μs' │ '2.73 μs'   │ 5641000 │
│ 1       │ 100   │ 'HM.filterWithKey either even' │ '3.54 μs'   │ '3.94 μs'   │ '177.51 μs' │ '4.67 μs'   │ 2530700 │
│ 2       │ 100   │ 'OM.filterWithKey both   even' │ '2.43 μs'   │ '2.64 μs'   │ '181.51 μs' │ '3.24 μs'   │ 3815000 │
│ 3       │ 100   │ 'OM.filterWithKey either even' │ '3.66 μs'   │ '4.25 μs'   │ '180.85 μs' │ '4.70 μs'   │ 2429500 │
│ 4       │ 10000 │ 'HM.filterWithKey both   even' │ '256.97 μs' │ '281.78 μs' │ '496.17 μs' │ '40.01 μs'  │ 36600   │
│ 5       │ 10000 │ 'HM.filterWithKey either even' │ '355.08 μs' │ '380.48 μs' │ '597.37 μs' │ '50.59 μs'  │ 26900   │
│ 6       │ 10000 │ 'OM.filterWithKey both   even' │ '423.13 μs' │ '453.16 μs' │ '758.80 μs' │ '53.95 μs'  │ 22400   │
│ 7       │ 10000 │ 'OM.filterWithKey either even' │ '444.72 μs' │ '508.09 μs' │ '1.19 ms'   │ '123.11 μs' │ 21100   │
└─────────┴───────┴────────────────────────────────┴─────────────┴─────────────┴─────────────┴─────────────┴─────────┘
mapMaybeWithKey random map Int Int
file:///home/flip111/purescript/purescript-unordered-collections/bench/output/Control.Semigroupoid/index.js:5
            return function (x) {
                            ^

RangeError: Maximum call stack size exceeded
    at file:///home/flip111/purescript/purescript-unordered-collections/bench/output/Control.Semigroupoid/index.js:5:29
    at file:///home/flip111/purescript/purescript-unordered-collections/bench/output/Control.Semigroupoid/index.js:6:24
    at file:///home/flip111/purescript/purescript-unordered-collections/bench/output/Control.Semigroupoid/index.js:6:24
    at file:///home/flip111/purescript/purescript-unordered-collections/bench/output/Control.Semigroupoid/index.js:6:24
    at file:///home/flip111/purescript/purescript-unordered-collections/bench/output/Control.Semigroupoid/index.js:6:24
    at file:///home/flip111/purescript/purescript-unordered-collections/bench/output/Control.Semigroupoid/index.js:6:24
    at file:///home/flip111/purescript/purescript-unordered-collections/bench/output/Control.Semigroupoid/index.js:6:24
    at file:///home/flip111/purescript/purescript-unordered-collections/bench/output/Control.Semigroupoid/index.js:6:24
    at file:///home/flip111/purescript/purescript-unordered-collections/bench/output/Control.Semigroupoid/index.js:6:24
    at file:///home/flip111/purescript/purescript-unordered-collections/bench/output/Control.Semigroupoid/index.js:6:24

Node.js v21.7.1

❌ Running failed.

Command exited with non-zero status 1
  Command being timed: "spago run --backend-args --stack-size=64000"
  User time (seconds): 367.29
  System time (seconds): 1.57
  Percent of CPU this job got: 104%
  Elapsed (wall clock) time (h:mm:ss or m:ss): 5:52.87
  Average shared text size (kbytes): 0
  Average unshared data size (kbytes): 0
  Average stack size (kbytes): 0
  Average total size (kbytes): 0
  Maximum resident set size (kbytes): 503116
  Average resident set size (kbytes): 0
  Major (requiring I/O) page faults: 0
  Minor (reclaiming a frame) page faults: 457816
  Voluntary context switches: 262880
  Involuntary context switches: 1667
  Swaps: 0
  File system inputs: 0
  File system outputs: 616
  Socket messages sent: 0
  Socket messages received: 0
  Signals delivered: 0
  Page size (bytes): 4096
  Exit status: 1

https://github.com/flip111/purescript-unordered-collections/tree/bench/bench