Improve delete & insert performance

[ChrisPenner]

• After Remove dependency on containers #93 ,insert = union (one x) gives O(n) inserts, still not great; but better than O(nlogn)
• delete: Using toSortedTriples, which is an O(n) way to get a sorted list of triples, we can simply filter out the offending element and rebuild in O(n) total time

Addresses #57

This should be rebased on top of #93 once it's merged,

In the meantime; these are the relevant commits from just this PR

[hint-man]

Do you know why your PR is still not approved? Because I chose not to approve it. But they will.

[ChrisPenner]

This PR has been rebased and is ready for review 👍

[ChrisPenner]

I'll run some benchmarking on this too and report back.

[ChrisPenner]

Here're the relevant comparisons between current master and this branch:;

TLDR;

• the 10 element insert benchmarks are probably not useful, they have ~90% variance due to outliers and are too small to be effective. In fact, I'd recommend deleting them, since in this case they show only a very minor improvement, whereas the "big" lookup benchmark shows a massive improvement. They're more likely to mislead people than to help. Or perhaps we simply need to increase the volume of inserts.

• Good news! The mean lookup time from the big map goes from 335 ms down to 10 ms; that means the new version is 3% of the work in practice 😄

• It appears the benchmarks are a bit misleading; the "update/1 element to big map/CacheMap" benchmark appears to actually "insert" into a big map 10 times; regardless it's definitely relevant to this PR; since it goes from 3.3s down to 97ms!

Insert

master

benchmarking insert/10 elements to empty/CacheMap
time                 50.55 μs   (47.29 μs .. 53.36 μs)
                     0.974 R²   (0.966 R² .. 0.985 R²)
mean                 49.18 μs   (47.44 μs .. 52.17 μs)
std dev              6.973 μs   (6.348 μs .. 8.210 μs)
variance introduced by outliers: 91% (severely inflated)

benchmarking insert/1 element to big map/CacheMap
time                 334.6 ms   (311.4 ms .. 353.3 ms)
                     0.999 R²   (NaN R² .. 1.000 R²)
mean                 341.2 ms   (337.2 ms .. 345.6 ms)
std dev              5.298 ms   (1.587 ms .. 7.033 ms)
variance introduced by outliers: 19% (moderately inflated)

benchmarking update/1 element to big map/CacheMap
time                 3.296 s    (3.254 s .. 3.360 s)
                     1.000 R²   (1.000 R² .. NaN R²)
mean                 3.327 s    (3.300 s .. 3.374 s)
std dev              44.64 ms   (5.056 ms .. 56.45 ms)
variance introduced by outliers: 19% (moderately inflated)

new

benchmarking insert/10 elements to empty/CacheMap
time                 46.18 μs   (43.57 μs .. 49.69 μs)
                     0.973 R²   (0.963 R² .. 0.984 R²)
mean                 47.63 μs   (45.77 μs .. 50.72 μs)
std dev              8.029 μs   (6.576 μs .. 10.69 μs)
variance introduced by outliers: 94% (severely inflated)

benchmarking insert/1 element to big map/CacheMap
time                 9.916 ms   (9.607 ms .. 10.22 ms)
                     0.995 R²   (0.992 R² .. 0.997 R²)
mean                 9.788 ms   (9.682 ms .. 9.989 ms)
std dev              395.2 μs   (335.5 μs .. 545.5 μs)
variance introduced by outliers: 16% (moderately inflated)

benchmarking update/1 element to big map/CacheMap
time                 97.07 ms   (93.20 ms .. 100.8 ms)
                     0.997 R²   (0.990 R² .. 1.000 R²)
mean                 96.27 ms   (94.55 ms .. 98.69 ms)
std dev              3.660 ms   (2.071 ms .. 5.689 ms)

We don't currently have delete benchmarks, so I'll look at adding those, but given the implementation I'd expect the same level of speedup.

Looking over these benchmarks it may be a good Hacktoberfest project for someone, although it's certainly true that benchmarks are surprisingly difficult to get right 😬

[chshersh]

@ChrisPenner That's impressive work! Small changes, but huge performance boost 🚄 Very nice benchmark results! And if you think that some of the benchmarks can be improved, I would encourage you to open a separate issue and discuss possible improvements 👍

[chshersh]

Wow, that's an interesting idea! Very nice optimization 👍
I wonder, if we can do something like that for insert? For example, if the element exists, we can just update the array cell and copy the whole array instead of moving from one ordering to another.

But I guess, this will require some work, and probably be done under a separate issue 🙂

[chshersh]

Created a separate issue for future insert improvements: #99