Rewrite internals for performance improvements #66

natefaubion · 2023-08-10T23:49:55Z

Description of the change

Rewrites internals to use a height-balanced AVL tree (same as containers in Haskell) with an eye for performance. Most operations are 2-3x faster than the previous implementations, but specifically this targets set operations which were previously sub-optimal.

The interface is exactly the same as before, except for the Internal module.

Checklist:

Added the change to the changelog's "Unreleased" section with a reference to this PR (e.g. "- Made a change (#0000)")
Linked any existing issues or proposals that this pull request should close
Updated or added relevant documentation
Added a test for the contribution (if applicable)

Rewrites internals to use a height-balanced AVL tree (same as containers in Haskell) with an eye for performance. Most operations are 2-3x faster than the previous implementations, but specifically this targets set operations which were previously sub-optimal.

natefaubion · 2023-08-10T23:51:01Z

Result of running the benchmark comparison to current main:

Map
===
size
---------------
size: singleton map
mean   = 260.67 ns
stddev = 1.58 μs
min    = 125.00 ns
max    = 33.83 μs
size: small map (100)
mean   = 252.42 ns
stddev = 2.28 μs
min    = 125.00 ns
max    = 70.92 μs
size: midsize map (10000)
mean   = 590.85 ns
stddev = 4.33 μs
min    = 83.00 ns
max    = 43.25 μs
size: big map (1000000)
mean   = 6.25 μs
stddev = 17.47 μs
min    = 167.00 ns
max    = 55.88 μs

fromFoldable
------------
fromFoldable (10000)
mean   = 10.88 ms
stddev = 1.11 ms
min    = 9.52 ms
max    = 18.59 ms
fromFoldable (100000)
mean   = 132.24 ms
stddev = 4.66 ms
min    = 128.59 ms
max    = 144.81 ms

Foldable
---------------
Mapf149d5.foldr big map (1000000)
mean   = 53.13 ms
stddev = 3.60 ms
min    = 50.12 ms
max    = 60.54 ms
M.foldr big map (1000000)
mean   = 27.60 ms
stddev = 1.65 ms
min    = 24.02 ms
max    = 30.76 ms
Mapf149d5.foldl big map (1000000)
mean   = 54.10 ms
stddev = 5.45 ms
min    = 50.81 ms
max    = 66.31 ms
M.foldl big map (1000000)
mean   = 26.02 ms
stddev = 2.27 ms
min    = 20.44 ms
max    = 29.45 ms
Mapf149d5.foldMap big map (1000000)
mean   = 72.57 ms
stddev = 6.15 ms
min    = 69.17 ms
max    = 88.40 ms
M.foldMap big map (1000000)
mean   = 24.42 ms
stddev = 2.04 ms
min    = 19.51 ms
max    = 27.28 ms
Mapf149d5.foldrWithIndex big map (1000000)
mean   = 52.66 ms
stddev = 3.50 ms
min    = 50.12 ms
max    = 59.20 ms
M.foldrWithIndex big map (1000000)
mean   = 26.35 ms
stddev = 1.37 ms
min    = 23.77 ms
max    = 29.12 ms
Mapf149d5.foldlWithIndex big map (1000000)
mean   = 52.84 ms
stddev = 5.03 ms
min    = 49.84 ms
max    = 66.12 ms
M.foldlWithIndex big map (1000000)
mean   = 26.99 ms
stddev = 2.15 ms
min    = 21.14 ms
max    = 28.81 ms
Mapf149d5.foldMapWithIndex big map (1000000)
mean   = 79.44 ms
stddev = 8.68 ms
min    = 74.00 ms
max    = 98.57 ms
M.foldMapWithIndex big map (1000000)
mean   = 28.91 ms
stddev = 2.27 ms
min    = 25.17 ms
max    = 33.79 ms

union
---------------
Mapf149d5.union: big map (1000000)
mean   = 2.85 s
stddev = 111.48 ms
min    = 2.72 s
max    = 3.10 s
M.union: big map (1000000)
mean   = 235.55 μs
stddev = 407.68 μs
min    = 99.08 μs
max    = 1.40 ms

values
---------------
Mapf149d5.values: big map (1000000)
mean   = 144.21 ms
stddev = 8.81 ms
min    = 136.08 ms
max    = 165.81 ms
M.values: big map (1000000)
mean   = 86.42 ms
stddev = 6.28 ms
min    = 80.64 ms
max    = 103.34 ms

keys
---------------
Mapf149d5.keys: big map (1000000)
mean   = 155.97 ms
stddev = 12.91 ms
min    = 142.34 ms
max    = 189.32 ms
M.keys: big map (1000000)
mean   = 58.95 ms
stddev = 5.64 ms
min    = 52.76 ms
max    = 72.65 ms
difference
---------------
Mapf149d5.difference: small map (100)
mean   = 1.65 ms
stddev = 535.56 μs
min    = 950.25 μs
max    = 8.23 ms
M.difference: small map (100)
mean   = 11.55 μs
stddev = 32.43 μs
min    = 5.79 μs
max    = 941.58 μs
Mapf149d5.difference: midsize map (10000)
mean   = 14.48 ms
stddev = 1.32 ms
min    = 13.60 ms
max    = 25.76 ms
M.difference: midsize map (10000)
mean   = 514.34 μs
stddev = 445.94 μs
min    = 346.00 μs
max    = 2.94 ms
Mapf149d5.difference: big map (1000000)
mean   = 26.29 ms
stddev = 4.25 ms
min    = 23.43 ms
max    = 37.16 ms
M.difference: big map (1000000)
mean   = 921.66 μs
stddev = 909.42 μs
min    = 387.13 μs
max    = 3.07 msMap
===
size
---------------
size: singleton map
mean   = 260.67 ns
stddev = 1.58 μs
min    = 125.00 ns
max    = 33.83 μs
size: small map (100)
mean   = 252.42 ns
stddev = 2.28 μs
min    = 125.00 ns
max    = 70.92 μs
size: midsize map (10000)
mean   = 590.85 ns
stddev = 4.33 μs
min    = 83.00 ns
max    = 43.25 μs
size: big map (1000000)
mean   = 6.25 μs
stddev = 17.47 μs
min    = 167.00 ns
max    = 55.88 μs

fromFoldable
------------
fromFoldable (10000)
mean   = 10.88 ms
stddev = 1.11 ms
min    = 9.52 ms
max    = 18.59 ms
fromFoldable (100000)
mean   = 132.24 ms
stddev = 4.66 ms
min    = 128.59 ms
max    = 144.81 ms

Foldable
---------------
Mapf149d5.foldr big map (1000000)
mean   = 53.13 ms
stddev = 3.60 ms
min    = 50.12 ms
max    = 60.54 ms
M.foldr big map (1000000)
mean   = 27.60 ms
stddev = 1.65 ms
min    = 24.02 ms
max    = 30.76 ms
Mapf149d5.foldl big map (1000000)
mean   = 54.10 ms
stddev = 5.45 ms
min    = 50.81 ms
max    = 66.31 ms
M.foldl big map (1000000)
mean   = 26.02 ms
stddev = 2.27 ms
min    = 20.44 ms
max    = 29.45 ms
Mapf149d5.foldMap big map (1000000)
mean   = 72.57 ms
stddev = 6.15 ms
min    = 69.17 ms
max    = 88.40 ms
M.foldMap big map (1000000)
mean   = 24.42 ms
stddev = 2.04 ms
min    = 19.51 ms
max    = 27.28 ms
Mapf149d5.foldrWithIndex big map (1000000)
mean   = 52.66 ms
stddev = 3.50 ms
min    = 50.12 ms
max    = 59.20 ms
M.foldrWithIndex big map (1000000)
mean   = 26.35 ms
stddev = 1.37 ms
min    = 23.77 ms
max    = 29.12 ms
Mapf149d5.foldlWithIndex big map (1000000)
mean   = 52.84 ms
stddev = 5.03 ms
min    = 49.84 ms
max    = 66.12 ms
M.foldlWithIndex big map (1000000)
mean   = 26.99 ms
stddev = 2.15 ms
min    = 21.14 ms
max    = 28.81 ms
Mapf149d5.foldMapWithIndex big map (1000000)
mean   = 79.44 ms
stddev = 8.68 ms
min    = 74.00 ms
max    = 98.57 ms
M.foldMapWithIndex big map (1000000)
mean   = 28.91 ms
stddev = 2.27 ms
min    = 25.17 ms
max    = 33.79 ms

union
---------------
Mapf149d5.union: big map (1000000)
mean   = 2.85 s
stddev = 111.48 ms
min    = 2.72 s
max    = 3.10 s
M.union: big map (1000000)
mean   = 235.55 μs
stddev = 407.68 μs
min    = 99.08 μs
max    = 1.40 ms

values
---------------
Mapf149d5.values: big map (1000000)
mean   = 144.21 ms
stddev = 8.81 ms
min    = 136.08 ms
max    = 165.81 ms
M.values: big map (1000000)
mean   = 86.42 ms
stddev = 6.28 ms
min    = 80.64 ms
max    = 103.34 ms

keys
---------------
Mapf149d5.keys: big map (1000000)
mean   = 155.97 ms
stddev = 12.91 ms
min    = 142.34 ms
max    = 189.32 ms
M.keys: big map (1000000)
mean   = 58.95 ms
stddev = 5.64 ms
min    = 52.76 ms
max    = 72.65 ms
difference
---------------
Mapf149d5.difference: small map (100)
mean   = 1.65 ms
stddev = 535.56 μs
min    = 950.25 μs
max    = 8.23 ms
M.difference: small map (100)
mean   = 11.55 μs
stddev = 32.43 μs
min    = 5.79 μs
max    = 941.58 μs
Mapf149d5.difference: midsize map (10000)
mean   = 14.48 ms
stddev = 1.32 ms
min    = 13.60 ms
max    = 25.76 ms
M.difference: midsize map (10000)
mean   = 514.34 μs
stddev = 445.94 μs
min    = 346.00 μs
max    = 2.94 ms
Mapf149d5.difference: big map (1000000)
mean   = 26.29 ms
stddev = 4.25 ms
min    = 23.43 ms
max    = 37.16 ms
M.difference: big map (1000000)
mean   = 921.66 μs
stddev = 909.42 μs
min    = 387.13 μs
max    = 3.07 ms

JordanMartinez · 2023-08-11T16:14:37Z

This comment is no longer relevant due to switching from a 2-3 tree to an AVL tree, right? If you don't plan on updating it, can the comment be removed?

natefaubion · 2023-08-11T16:17:19Z

Can you clarify what comment you are referring to (perhaps a link to the full file). That link does not direct to something useful, likely because GH is collapsing diffs.

JordanMartinez · 2023-08-11T16:51:35Z

Can you clarify what comment you are referring to (perhaps a link to the full file). That link does not direct to something useful, likely because GH is collapsing diffs.

This one (line 413):

-- We can take advantage of the invariants of the tree structure to reduce
    -- the amount of work we need to do. For example, in the following tree:
    --
    --      [2][4]
    --      / |  \
    --     /  |   \
    --   [1] [3] [5]
    --
    -- If we are given a lower bound of 3, we do not need to inspect the left
    -- subtree, because we know that every entry in it is less than or equal to
    -- 2. Similarly, if we are given a lower bound of 5, we do not need to
    -- inspect the central subtree, because we know that every entry in it must
    -- be less than or equal to 4.
    --
    -- Unfortunately we cannot extract `if cond then x else mempty` into a
    -- function because of strictness.

JordanMartinez

Some minor things I found.

src/Data/Map/Internal.purs

natefaubion · 2023-08-11T16:53:52Z

I'll remove the comment. It's not relevant anymore.

JordanMartinez · 2023-08-11T16:58:17Z

On a separate note, for MapIterStep's eq instance, your first pattern match (i.e. case stepAsc a of) is on the terminating case IterDone while your second one (i.e. case stepAsc b of) is on the recursive case IterNext.

Could you clarify why? I assume most maps will not be empty, so does matching on the recursive case in case stepAsc a of speed up the eq instance?

natefaubion · 2023-08-11T17:02:40Z

Could you clarify why? I assume most maps will not be empty, so does matching on the recursive case in case stepAsc a of speed up the eq instance?

I don't have a reason to believe this is necessarily the case compared to the other overhead. But I could make a benchmark to check equality performance.

JordanMartinez

LGTM otherwise.

natefaubion · 2023-08-11T18:19:32Z

Could you clarify why? I assume most maps will not be empty, so does matching on the recursive case in case stepAsc a of speed up the eq instance?

I went ahead and did this. It seems to have a small effect for the main backend.

JordanMartinez · 2023-08-11T18:25:18Z

Ok, cool. Is there anything else you want to do? Or is this ready to be merged?

natefaubion · 2023-08-11T19:47:39Z

I have no other changes to make.

garyb · 2023-08-11T20:07:09Z

Nice work ❤️

natefaubion added 2 commits August 11, 2023 07:16

Update test command

7a31b87

Expose gc for bench

6e293b7

Share benchmark init for faster startup

64ae506

JordanMartinez reviewed Aug 11, 2023

View reviewed changes

src/Data/Map/Internal.purs Outdated Show resolved Hide resolved

src/Data/Map/Internal.purs Show resolved Hide resolved

src/Data/Map/Internal.purs Outdated Show resolved Hide resolved

Cleanup

c5642c5

JordanMartinez approved these changes Aug 11, 2023

View reviewed changes

natefaubion added 2 commits August 11, 2023 11:15

Rearrange eq checks

a229c3d

Fix eq test

40fb181

Update CHANGELOG

7d26f23

JordanMartinez merged commit 85ee3ba into master Aug 11, 2023

JordanMartinez deleted the nf/rewrite-internals branch August 11, 2023 19:51

Rewrite internals for performance improvements #66

Rewrite internals for performance improvements #66

Uh oh!

Conversation

natefaubion commented Aug 10, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

natefaubion commented Aug 10, 2023

Uh oh!

JordanMartinez commented Aug 11, 2023

Uh oh!

natefaubion commented Aug 11, 2023

Uh oh!

JordanMartinez commented Aug 11, 2023

Uh oh!

JordanMartinez left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

natefaubion commented Aug 11, 2023

Uh oh!

JordanMartinez commented Aug 11, 2023

Uh oh!

natefaubion commented Aug 11, 2023

Uh oh!

JordanMartinez left a comment

Choose a reason for hiding this comment

Uh oh!

natefaubion commented Aug 11, 2023

Uh oh!

JordanMartinez commented Aug 11, 2023

Uh oh!

natefaubion commented Aug 11, 2023

Uh oh!

garyb commented Aug 11, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

natefaubion commented Aug 10, 2023 •

edited

Loading