Repository: paritytech/ink
Pull request #508 (2020-10-05 11:05:25)

[core] Optimization for storage2::BinaryHeap
Stores two children in one storage cell.

This change reduces read operations, since left and right child are compared during the `sift_…` part of our binary heap algorithm.

## Benchmark before Optimization
```
BinaryHeap::push (empty cache)/largest value/8
                        time:   [628.70 ns 638.62 ns 651.07 ns]
BinaryHeap::push (empty cache)/smallest value/8
                        time:   [359.32 ns 364.94 ns 371.87 ns]
BinaryHeap::push (empty cache)/largest value/16
                        time:   [878.89 ns 892.55 ns 909.08 ns]
BinaryHeap::push (empty cache)/smallest value/16
                        time:   [372.59 ns 377.97 ns 384.54 ns]
BinaryHeap::push (empty cache)/largest value/32
                        time:   [1.0560 us 1.0684 us 1.0823 us]
BinaryHeap::push (empty cache)/smallest value/32
                        time:   [389.39 ns 393.98 ns 399.17 ns]
BinaryHeap::push (empty cache)/largest value/64
                        time:   [1.2848 us 1.3088 us 1.3378 us]
BinaryHeap::push (empty cache)/smallest value/64
                        time:   [383.83 ns 390.56 ns 398.07 ns]
BinaryHeap::push (populated cache)/largest value/8
                        time:   [197.76 ns 209.28 ns 222.89 ns]
BinaryHeap::push (populated cache)/smallest value/8
                        time:   [116.69 ns 123.92 ns 131.90 ns]
BinaryHeap::push (populated cache)/largest value/16
                        time:   [300.65 ns 320.07 ns 344.13 ns]
BinaryHeap::push (populated cache)/smallest value/16
                        time:   [206.11 ns 227.41 ns 250.72 ns]
BinaryHeap::push (populated cache)/largest value/32
                        time:   [553.16 ns 582.92 ns 611.42 ns]
BinaryHeap::push (populated cache)/smallest value/32
                        time:   [261.79 ns 272.77 ns 282.78 ns]
BinaryHeap::push (populated cache)/largest value/64
                        time:   [665.63 ns 695.96 ns 723.99 ns]
BinaryHeap::push (populated cache)/smallest value/64
                        time:   [260.07 ns 274.85 ns 287.76 ns]
BinaryHeap::pop (empty cache)/8
                        time:   [1.1737 us 1.2638 us 1.3680 us]
BinaryHeap::pop (empty cache)/16
                        time:   [1.4267 us 1.4767 us 1.5380 us]
BinaryHeap::pop (empty cache)/32
                        time:   [1.7468 us 1.7703 us 1.7992 us]
BinaryHeap::pop (empty cache)/64
                        time:   [2.1909 us 2.2202 us 2.2551 us]
BinaryHeap::pop (populated cache)/8
                        time:   [156.47 ns 157.73 ns 159.18 ns]
BinaryHeap::pop (populated cache)/16
                        time:   [308.37 ns 315.42 ns 321.60 ns]
BinaryHeap::pop (populated cache)/32
                        time:   [475.23 ns 493.56 ns 509.53 ns]
BinaryHeap::pop (populated cache)/64
                        time:   [652.62 ns 675.91 ns 695.98 ns]
```

## Benchmark after Optimization
```
BinaryHeap::push (empty cache)/largest value/8
                        time:   [1.1614 us 1.1780 us 1.1970 us]
BinaryHeap::push (empty cache)/smallest value/8
                        time:   [789.69 ns 828.85 ns 869.31 ns]
BinaryHeap::push (empty cache)/largest value/16
                        time:   [1.4326 us 1.4778 us 1.5301 us]
BinaryHeap::push (empty cache)/smallest value/16
                        time:   [678.03 ns 690.00 ns 703.94 ns]
BinaryHeap::push (empty cache)/largest value/32
                        time:   [1.7000 us 1.7236 us 1.7489 us]
BinaryHeap::push (empty cache)/smallest value/32
                        time:   [737.18 ns 752.03 ns 769.14 ns]
BinaryHeap::push (empty cache)/largest value/64
                        time:   [1.9599 us 1.9921 us 2.0334 us]
BinaryHeap::push (empty cache)/smallest value/64
                        time:   [777.05 ns 797.16 ns 822.13 ns]
BinaryHeap::push (populated cache)/largest value/8
                        time:   [190.49 ns 191.86 ns 193.48 ns]
BinaryHeap::push (populated cache)/smallest value/8
                        time:   [54.349 ns 55.339 ns 56.301 ns]
BinaryHeap::push (populated cache)/largest value/16
                        time:   [287.89 ns 307.08 ns 334.48 ns]
BinaryHeap::push (populated cache)/smallest value/16
                        time:   [74.062 ns 77.168 ns 81.155 ns]
BinaryHeap::push (populated cache)/largest value/32
                        time:   [487.12 ns 505.75 ns 525.41 ns]
BinaryHeap::push (populated cache)/smallest value/32
                        time:   [267.55 ns 285.80 ns 304.82 ns]
BinaryHeap::push (populated cache)/largest value/64
                        time:   [731.65 ns 788.39 ns 852.89 ns]
BinaryHeap::push (populated cache)/smallest value/64
                        time:   [213.00 ns 227.82 ns 242.97 ns]
BinaryHeap::pop (empty cache)/8
                        time:   [1.2227 us 1.2523 us 1.2875 us]
BinaryHeap::pop (empty cache)/16
                        time:   [1.5187 us 1.5565 us 1.6049 us]
BinaryHeap::pop (empty cache)/32
                        time:   [1.8776 us 1.9627 us 2.0936 us]
BinaryHeap::pop (empty cache)/64
                        time:   [2.1897 us 2.2886 us 2.4126 us]
BinaryHeap::pop (populated cache)/8
                        time:   [227.83 ns 231.19 ns 235.05 ns]
BinaryHeap::pop (populated cache)/16
                        time:   [338.14 ns 342.10 ns 346.36 ns]
BinaryHeap::pop (populated cache)/32
                        time:   [537.77 ns 549.11 ns 561.49 ns]
BinaryHeap::pop (populated cache)/64
                        time:   [740.54 ns 765.19 ns 788.06 ns]
```

ascjones: Comparing the benchmarks posted above:

|------------------------------------------|--------|-------|--------|------|---------| 
| before                                   |        | after |        | diff |         | 
| push (empty cache)/largest value/8       | 638.62 | ns    | 1.178  | us   | -45.79% | 
| push (empty cache)/smallest value/8      | 364.94 | ns    | 828.85 | ns   | -55.97% | 
| push (empty cache)/largest value/16      | 892.55 | ns    | 1.4778 | us   | -39.60% | 
| push (empty cache)/smallest value/16     | 377.97 | ns    | 690    | ns   | -45.22% | 
| push (empty cache)/largest value/32      | 1.0684 | us    | 1.7236 | us   | -38.01% | 
| push (empty cache)/smallest value/32     | 393.98 | ns    | 752.03 | ns   | -47.61% | 
| push (empty cache)/largest value/64      | 1.3088 | us    | 1.9921 | us   | -34.30% | 
| push (empty cache)/smallest value/64     | 390.56 | ns    | 797.16 | ns   | -51.01% | 
| push (populated cache)/largest value/8   | 209.28 | ns    | 191.86 | ns   | 9.08%   | 
| push (populated cache)/smallest value/8  | 123.92 | ns    | 55.339 | ns   | 123.93% | 
| push (populated cache)/largest value/16  | 320.07 | ns    | 307.08 | ns   | 4.23%   | 
| push (populated cache)/smallest value/16 | 227.41 | ns    | 77.168 | ns   | 194.69% | 
| push (populated cache)/largest value/32  | 582.92 | ns    | 505.75 | ns   | 15.26%  | 
| push (populated cache)/smallest value/32 | 272.77 | ns    | 285.8  | ns   | -4.56%  | 
| push (populated cache)/largest value/64  | 695.96 | ns    | 788.39 | ns   | -11.72% | 
| push (populated cache)/smallest value/64 | 274.85 | ns    | 227.82 | ns   | 20.64%  | 
| pop (empty cache)/8                      | 1.2638 | us    | 1.2523 | us   | 0.92%   | 
| pop (empty cache)/16                     | 1.4767 | us    | 1.5565 | us   | -5.13%  | 
| pop (empty cache)/32                     | 1.7703 | us    | 1.9627 | us   | -9.80%  | 
| pop (empty cache)/64                     | 2.2202 | us    | 2.2886 | us   | -2.99%  | 
| pop (populated cache)/8                  | 157.73 | ns    | 231.19 | ns   | -31.77% | 
| pop (populated cache)/16                 | 315.42 | ns    | 342.1  | ns   | -7.80%  | 

cmichi: ## Benches with larger size

I'll post the read/write numbers of before/after shortly.

  | before |   | after |   | diff
-- | -- | -- | -- | -- | --
BinaryHeap::push (empty cache)/largest value/1024 | 2.0232 | us | 2.9138 | us | -30.56%
BinaryHeap::push (empty cache)/smallest value/1024 | 394.89 | ns | 792.3 | ns | -50.16%
BinaryHeap::push (empty cache)/largest value/2048 | 2.6272 | us | 3.7662 | us | -30.24%
BinaryHeap::push (empty cache)/smallest value/2048 | 431 | ns | 981.48 | ns | -56.09%
BinaryHeap::push (empty cache)/largest value/4096 | 2.8305 | us | 4.3419 | us | -34.81%
BinaryHeap::push (empty cache)/smallest value/4096 | 460.92 | ns | 1.0534 | us | -56.24%
BinaryHeap::push (empty cache)/largest value/8192 | 3.1984 | us | 5.0215 | us | -36.31%
BinaryHeap::push (empty cache)/smallest value/8192 | 517.23 | ns | 1.0831 | us | -52.25%
BinaryHeap::push (empty cache)/largest value/32768 | 3.4551 | us | 5.6881 | us | -39.26%
BinaryHeap::push (empty cache)/smallest value/32768 | 502.75 | ns | 1.059 | us | -52.53%
BinaryHeap::push (empty cache)/largest value/1048576 | 6.8871 | us | 2.6762 | us | 157.35%
BinaryHeap::push (empty cache)/smallest value/1048576 | 1.1811 | us | 809.95 | ns | 45.82%
BinaryHeap::push (populated cache)/largest value/1024 | 3.0996 | us | 3.4887 | us | -11.15%
BinaryHeap::push (populated cache)/smallest value/1024 | 882.69 | ns | 961.67 | ns | -8.21%
BinaryHeap::push (populated cache)/largest value/2048 | 3.6435 | us | 4.4267 | us | -17.69%
BinaryHeap::push (populated cache)/smallest value/2048 | 1.1216 | us | 1.0038 | us | 11.74%
BinaryHeap::push (populated cache)/largest value/4096 | 3.8745 | us | 4.816 | us | -19.55%
BinaryHeap::push (populated cache)/smallest value/4096 | 1.0237 | us | 1.0495 | us | -2.46%
BinaryHeap::push (populated cache)/largest value/8192 | 4.7239 | us | 6.0637 | us | -22.10%
BinaryHeap::push (populated cache)/smallest value/8192 | 1.3299 | us | 1.2762 | us | 4.21%
BinaryHeap::push (populated cache)/largest value/32768 | 4.9524 | us | 3.9016 | us | 26.93%
BinaryHeap::push (populated cache)/smallest value/32768 | 1.4623 | us | 4.8149 | us | -69.63%
BinaryHeap::push (populated cache)/largest value/1048576 | 4.2504 | us | 5.7549 | us | -26.14%
BinaryHeap::push (populated cache)/smallest value/1048576 | 783.11 | ns | 5.8212 | us | -86.55%
BinaryHeap::pop (empty cache)/1024 | 4.3175 | us | 9.0496 | us | -52.29%
BinaryHeap::pop (empty cache)/2048 | 4.8855 | us | 3.1413 | us | 55.52%
BinaryHeap::pop (empty cache)/4096 | 5.8303 | us | 3.8567 | us | 51.17%
BinaryHeap::pop (empty cache)/8192 | 7.3764 | us | 4.9945 | us | 47.69%
BinaryHeap::pop (empty cache)/32768 | 8.9877 | us | 5.7189 | us | 57.16%
BinaryHeap::pop (empty cache)/1048576 | 14.541 | us | 7.7791 | us | 86.92%
BinaryHeap::pop (populated cache)/1024 | 3.5771 | us | 4.292 | us | -16.66%
BinaryHeap::pop (populated cache)/2048 | 3.8543 | us | 1.1343 | us | 239.80%
BinaryHeap::pop (populated cache)/4096 | 4.5607 | us | 6.0818 | us | -25.01%
BinaryHeap::pop (populated cache)/8192 | 5.4652 | us | 1.8385 | us | 197.26%
BinaryHeap::pop (populated cache)/32768 | 10.568 | us | 29.868 | us | -64.62%
BinaryHeap::pop (populated cache)/1048576 | 8.6653 | us | 10.97 | us | -21.01%


cmichi: ## Reads/Writes Before/After

operation | heap size | reads before | reads after | diff |   | writes before | writes after | diff
-- | -- | -- | -- | -- | -- | -- | -- | --
pop | 4096 | 26 | 17 | -52.94% |   | 4111 | 2066 | -98.98%
pop | 8192 | 28 | 18 | -55.56% |   | 8208 | 4115 | -99.47%
pop | 32768 | 32 | 20 | -60.00% |   | 32786 | 16405 | -99.85%
  |   |   |   |   |   |   |   |  
push_largest_value | 4096 | 14 | 17 | 17.65% |   | 4111 | 2065 | -99.08%
push_largest_value | 8192 | 15 | 18 | 16.67% |   | 8208 | 4114 | -99.51%
push_largest_value | 32768 | 17 | 20 | 15.00% |   | 32786 | 16404 | -99.87%
  |   |   |   |   |   |   |   |  
push_smallest_value | 4096 | 3 | 6 | 50.00% |   | 4099 | 2053 | -99.66%
push_smallest_value | 8192 | 3 | 6 | 50.00% |   | 8195 | 4101 | -99.83%
push_smallest_value | 32768 | 3 | 6 | 50.00% |   | 32771 | 16389 | -99.96%


codecov-commenter: # [Codecov](https://codecov.io/gh/paritytech/ink/pull/508?src=pr&el=h1) Report
> Merging [#508](https://codecov.io/gh/paritytech/ink/pull/508?src=pr&el=desc) into [aj-binary-heap](https://codecov.io/gh/paritytech/ink/commit/63e519444034bee8fa467b55daab1913d615f28c?el=desc) will **increase** coverage by `15.80%`.
> The diff coverage is `94.31%`.

[![Impacted file tree graph](https://codecov.io/gh/paritytech/ink/pull/508/graphs/tree.svg?width=650&height=150&src=pr&token=tYyVaCZb7o)](https://codecov.io/gh/paritytech/ink/pull/508?src=pr&el=tree)

```diff
@@                 Coverage Diff                 @@
##           aj-binary-heap     #508       +/-   ##
===================================================
+ Coverage           66.77%   82.58%   +15.80%     
===================================================
  Files                 151      153        +2     
  Lines                6490     6656      +166     
===================================================
+ Hits                 4334     5497     +1163     
+ Misses               2156     1159      -997     
```


| [Impacted Files](https://codecov.io/gh/paritytech/ink/pull/508?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [...es/storage/src/collections/binary\_heap/children.rs](https://codecov.io/gh/paritytech/ink/pull/508/diff?src=pr&el=tree#diff-Y3JhdGVzL3N0b3JhZ2Uvc3JjL2NvbGxlY3Rpb25zL2JpbmFyeV9oZWFwL2NoaWxkcmVuLnJz) | `88.57% <88.57%> (ø)` | |
| [...rates/storage/src/collections/binary\_heap/tests.rs](https://codecov.io/gh/paritytech/ink/pull/508/diff?src=pr&el=tree#diff-Y3JhdGVzL3N0b3JhZ2Uvc3JjL2NvbGxlY3Rpb25zL2JpbmFyeV9oZWFwL3Rlc3RzLnJz) | `94.00% <92.85%> (-0.60%)` | :arrow_down: |
| [...torage/src/collections/binary\_heap/children\_vec.rs](https://codecov.io/gh/paritytech/ink/pull/508/diff?src=pr&el=tree#diff-Y3JhdGVzL3N0b3JhZ2Uvc3JjL2NvbGxlY3Rpb25zL2JpbmFyeV9oZWFwL2NoaWxkcmVuX3ZlYy5ycw==) | `95.37% <95.37%> (ø)` | |
| [...rates/storage/src/collections/binary\_heap/impls.rs](https://codecov.io/gh/paritytech/ink/pull/508/diff?src=pr&el=tree#diff-Y3JhdGVzL3N0b3JhZ2Uvc3JjL2NvbGxlY3Rpb25zL2JpbmFyeV9oZWFwL2ltcGxzLnJz) | `100.00% <100.00%> (ø)` | |
| [crates/storage/src/collections/binary\_heap/mod.rs](https://codecov.io/gh/paritytech/ink/pull/508/diff?src=pr&el=tree#diff-Y3JhdGVzL3N0b3JhZ2Uvc3JjL2NvbGxlY3Rpb25zL2JpbmFyeV9oZWFwL21vZC5ycw==) | `100.00% <100.00%> (ø)` | |
| [...tes/storage/src/collections/binary\_heap/storage.rs](https://codecov.io/gh/paritytech/ink/pull/508/diff?src=pr&el=tree#diff-Y3JhdGVzL3N0b3JhZ2Uvc3JjL2NvbGxlY3Rpb25zL2JpbmFyeV9oZWFwL3N0b3JhZ2UucnM=) | `100.00% <100.00%> (ø)` | |
| [crates/storage/src/collections/vec/mod.rs](https://codecov.io/gh/paritytech/ink/pull/508/diff?src=pr&el=tree#diff-Y3JhdGVzL3N0b3JhZ2Uvc3JjL2NvbGxlY3Rpb25zL3ZlYy9tb2QucnM=) | `96.77% <0.00%> (-1.08%)` | :arrow_down: |
| [crates/storage/src/lazy/mod.rs](https://codecov.io/gh/paritytech/ink/pull/508/diff?src=pr&el=tree#diff-Y3JhdGVzL3N0b3JhZ2Uvc3JjL2xhenkvbW9kLnJz) | `93.54% <0.00%> (+0.95%)` | :arrow_up: |
| ... and [26 more](https://codecov.io/gh/paritytech/ink/pull/508/diff?src=pr&el=tree-more) | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/paritytech/ink/pull/508?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/paritytech/ink/pull/508?src=pr&el=footer). Last update [63e5194...ab85970](https://codecov.io/gh/paritytech/ink/pull/508?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

codecov-io: # [Codecov](https://codecov.io/gh/paritytech/ink/pull/508?src=pr&el=h1) Report
> Merging [#508](https://codecov.io/gh/paritytech/ink/pull/508?src=pr&el=desc) into [aj-binary-heap](https://codecov.io/gh/paritytech/ink/commit/63e519444034bee8fa467b55daab1913d615f28c?el=desc) will **increase** coverage by `15.80%`.
> The diff coverage is `94.31%`.

[![Impacted file tree graph](https://codecov.io/gh/paritytech/ink/pull/508/graphs/tree.svg?width=650&height=150&src=pr&token=tYyVaCZb7o)](https://codecov.io/gh/paritytech/ink/pull/508?src=pr&el=tree)

```diff
@@                 Coverage Diff                 @@
##           aj-binary-heap     #508       +/-   ##
===================================================
+ Coverage           66.77%   82.58%   +15.80%     
===================================================
  Files                 151      153        +2     
  Lines                6490     6656      +166     
===================================================
+ Hits                 4334     5497     +1163     
+ Misses               2156     1159      -997     
```


| [Impacted Files](https://codecov.io/gh/paritytech/ink/pull/508?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [...es/storage/src/collections/binary\_heap/children.rs](https://codecov.io/gh/paritytech/ink/pull/508/diff?src=pr&el=tree#diff-Y3JhdGVzL3N0b3JhZ2Uvc3JjL2NvbGxlY3Rpb25zL2JpbmFyeV9oZWFwL2NoaWxkcmVuLnJz) | `88.57% <88.57%> (ø)` | |
| [...rates/storage/src/collections/binary\_heap/tests.rs](https://codecov.io/gh/paritytech/ink/pull/508/diff?src=pr&el=tree#diff-Y3JhdGVzL3N0b3JhZ2Uvc3JjL2NvbGxlY3Rpb25zL2JpbmFyeV9oZWFwL3Rlc3RzLnJz) | `94.00% <92.85%> (-0.60%)` | :arrow_down: |
| [...torage/src/collections/binary\_heap/children\_vec.rs](https://codecov.io/gh/paritytech/ink/pull/508/diff?src=pr&el=tree#diff-Y3JhdGVzL3N0b3JhZ2Uvc3JjL2NvbGxlY3Rpb25zL2JpbmFyeV9oZWFwL2NoaWxkcmVuX3ZlYy5ycw==) | `95.37% <95.37%> (ø)` | |
| [...rates/storage/src/collections/binary\_heap/impls.rs](https://codecov.io/gh/paritytech/ink/pull/508/diff?src=pr&el=tree#diff-Y3JhdGVzL3N0b3JhZ2Uvc3JjL2NvbGxlY3Rpb25zL2JpbmFyeV9oZWFwL2ltcGxzLnJz) | `100.00% <100.00%> (ø)` | |
| [crates/storage/src/collections/binary\_heap/mod.rs](https://codecov.io/gh/paritytech/ink/pull/508/diff?src=pr&el=tree#diff-Y3JhdGVzL3N0b3JhZ2Uvc3JjL2NvbGxlY3Rpb25zL2JpbmFyeV9oZWFwL21vZC5ycw==) | `100.00% <100.00%> (ø)` | |
| [...tes/storage/src/collections/binary\_heap/storage.rs](https://codecov.io/gh/paritytech/ink/pull/508/diff?src=pr&el=tree#diff-Y3JhdGVzL3N0b3JhZ2Uvc3JjL2NvbGxlY3Rpb25zL2JpbmFyeV9oZWFwL3N0b3JhZ2UucnM=) | `100.00% <100.00%> (ø)` | |
| [crates/storage/src/collections/vec/mod.rs](https://codecov.io/gh/paritytech/ink/pull/508/diff?src=pr&el=tree#diff-Y3JhdGVzL3N0b3JhZ2Uvc3JjL2NvbGxlY3Rpb25zL3ZlYy9tb2QucnM=) | `96.77% <0.00%> (-1.08%)` | :arrow_down: |
| [crates/storage/src/lazy/mod.rs](https://codecov.io/gh/paritytech/ink/pull/508/diff?src=pr&el=tree#diff-Y3JhdGVzL3N0b3JhZ2Uvc3JjL2xhenkvbW9kLnJz) | `93.54% <0.00%> (+0.95%)` | :arrow_up: |
| ... and [26 more](https://codecov.io/gh/paritytech/ink/pull/508/diff?src=pr&el=tree-more) | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/paritytech/ink/pull/508?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/paritytech/ink/pull/508?src=pr&el=footer). Last update [63e5194...9b1a670](https://codecov.io/gh/paritytech/ink/pull/508?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

Robbepop: Waiting for CI to approve for merge.

Patch:
diff --git a/crates/storage/src/collections/binary_heap/children.rs b/crates/storage/src/collections/binary_heap/children.rs
new file mode 100644
index 0000000000..1e84f49d90
--- /dev/null
+++ b/crates/storage/src/collections/binary_heap/children.rs
@@ -0,0 +1,209 @@
+// Copyright 2018-2020 Parity Technologies (UK) Ltd.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+//! A `Children` object consists of two elements: a left and right child.
+
+use crate::traits::{
+    forward_clear_packed,
+    forward_pull_packed,
+    forward_push_packed,
+    KeyPtr,
+    PackedLayout,
+    SpreadLayout,
+};
+use ink_primitives::Key;
+
+#[cfg(feature = "std")]
+use scale_info::TypeInfo;
+
+/// Each `Children` object may contain up to two elements. It is always
+/// stored in one single storage cell. This reduces storage access operations
+/// of the binary heap algorithm.
+#[cfg_attr(feature = "std", derive(TypeInfo))]
+#[derive(scale::Encode, scale::Decode, Default, PartialEq, Eq, Debug)]
+pub(super) struct Children<T: PackedLayout + Ord> {
+    left: Option<T>,
+    right: Option<T>,
+}
+
+/// The position which a child has in a `Children` object.
+#[derive(Copy, Clone, PartialEq, Debug)]
+pub(super) enum ChildPosition {
+    Left,
+    Right,
+}
+
+/// Number of elements stored in each `Children` object.
+///
+/// Note that the first `Children` object (at index `0`) will only ever
+/// contain one element (the root element).
+pub(super) const CHILDREN_PER_NODE: u32 = 2;
+
+/// Returns the index of the `Children` object in which the `n`-th element of
+/// the heap is stored.
+pub(super) fn get_children_storage_index(n: u32) -> u32 {
+    if n == 0 {
+        return 0
+    }
+    // The first `Children` object only ever contains the root element:
+    // `[Some(root), None]`. So when calculating indices we need to account
+    // for the items which have been left empty in the first `Children` object.
+    let padding = CHILDREN_PER_NODE - 1;
+    (n + padding) / CHILDREN_PER_NODE
+}
+
+/// Returns the `ChildPosition` of the `n`-th heap element.
+///
+/// For example, the element `3` is found at the child position `0`
+/// (within the `Children` object at storage index `2`).
+pub(super) fn get_child_pos(n: u32) -> ChildPosition {
+    let storage_index = get_children_storage_index(n);
+    match (storage_index, n) {
+        (0, 0) => ChildPosition::Left,
+        (0, _) => panic!("first children object contains only the root element"),
+        (_, _) => {
+            let child_pos = (n - 1) % CHILDREN_PER_NODE;
+            match child_pos {
+                0 => ChildPosition::Left,
+                1 => ChildPosition::Right,
+                _ => {
+                    unreachable!(
+                        "CHILDREN_PER_NODE is 2, following the modulo op index must be 0 or 1"
+                    )
+                }
+            }
+        }
+    }
+}
+
+impl<T> Children<T>
+where
+    T: PackedLayout + Ord,
+{
+    /// Creates a new `Children` object with a left and right element.
+    pub fn new(left: Option<T>, right: Option<T>) -> Self {
+        Self { left, right }
+    }
+
+    /// Returns the number of existent children in this object.
+    pub fn count(&self) -> usize {
+        self.left.is_some() as usize + self.right.is_some() as usize
+    }
+
+    /// Returns a shared reference to the element at `which`.
+    pub fn child(&self, which: ChildPosition) -> &Option<T> {
+        match which {
+            ChildPosition::Left => &self.left,
+            ChildPosition::Right => &self.right,
+        }
+    }
+
+    /// Returns an exclusive reference to the element at `which`.
+    pub fn child_mut(&mut self, which: ChildPosition) -> &mut Option<T> {
+        match which {
+            ChildPosition::Left => &mut self.left,
+            ChildPosition::Right => &mut self.right,
+        }
+    }
+}
+
+#[cfg(feature = "std")]
+const _: () = {
+    use crate::traits::StorageLayout;
+    use ink_metadata::layout::{
+        CellLayout,
+        Layout,
+        LayoutKey,
+    };
+
+    impl<T> StorageLayout for Children<T>
+    where
+        T: PackedLayout + Ord + TypeInfo + 'static,
+    {
+        fn layout(key_ptr: &mut KeyPtr) -> Layout {
+            Layout::Cell(CellLayout::new::<Children<T>>(LayoutKey::from(
+                key_ptr.advance_by(1),
+            )))
+        }
+    }
+};
+
+impl<T> SpreadLayout for Children<T>
+where
+    T: PackedLayout + Ord,
+{
+    const FOOTPRINT: u64 = 1;
+    const REQUIRES_DEEP_CLEAN_UP: bool = false;
+
+    fn pull_spread(ptr: &mut KeyPtr) -> Self {
+        forward_pull_packed::<Self>(ptr)
+    }
+
+    fn push_spread(&self, ptr: &mut KeyPtr) {
+        forward_push_packed::<Self>(self, ptr)
+    }
+
+    fn clear_spread(&self, ptr: &mut KeyPtr) {
+        forward_clear_packed::<Self>(self, ptr)
+    }
+}
+
+impl<T> PackedLayout for Children<T>
+where
+    T: PackedLayout + Ord,
+{
+    fn push_packed(&self, at: &Key) {
+        <Option<T> as PackedLayout>::push_packed(&self.left, at);
+        <Option<T> as PackedLayout>::push_packed(&self.right, at);
+    }
+
+    fn clear_packed(&self, at: &Key) {
+        <Option<T> as PackedLayout>::clear_packed(&self.left, at);
+        <Option<T> as PackedLayout>::clear_packed(&self.right, at);
+    }
+
+    fn pull_packed(&mut self, at: &Key) {
+        <Option<T> as PackedLayout>::pull_packed(&mut self.left, at);
+        <Option<T> as PackedLayout>::pull_packed(&mut self.right, at);
+    }
+}
+
+#[test]
+fn get_children_storage_index_works() {
+    // root is in cell 0
+    assert_eq!(get_children_storage_index(0), 0);
+
+    // element 1 + 2 are childrent of element 0 and
+    // should be in one cell together
+    assert_eq!(get_children_storage_index(1), 1);
+    assert_eq!(get_children_storage_index(2), 1);
+
+    // element 3 and 4 should be in one cell
+    assert_eq!(get_children_storage_index(3), 2);
+    assert_eq!(get_children_storage_index(4), 2);
+}
+
+#[test]
+fn get_child_pos_works() {
+    assert_eq!(get_child_pos(0), ChildPosition::Left);
+
+    assert_eq!(get_child_pos(1), ChildPosition::Left);
+    assert_eq!(get_child_pos(2), ChildPosition::Right);
+
+    assert_eq!(get_child_pos(3), ChildPosition::Left);
+    assert_eq!(get_child_pos(4), ChildPosition::Right);
+
+    assert_eq!(get_child_pos(5), ChildPosition::Left);
+    assert_eq!(get_child_pos(6), ChildPosition::Right);
+}
diff --git a/crates/storage/src/collections/binary_heap/children_vec.rs b/crates/storage/src/collections/binary_heap/children_vec.rs
new file mode 100644
index 0000000000..69a8b5a056
--- /dev/null
+++ b/crates/storage/src/collections/binary_heap/children_vec.rs
@@ -0,0 +1,469 @@
+// Copyright 2018-2020 Parity Technologies (UK) Ltd.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+//! Provides an interface around the vector used to store elements of the
+//! [`BinaryHeap`](`super::BinaryHeap`) in storage. This is necessary since
+//! we don't just store each element in it's own storage cell, but rather
+//! optimize storage access by putting children together in one storage cell.
+
+use super::{
+    children,
+    children::Children,
+    StorageVec,
+};
+use crate::{
+    collections::extend_lifetime,
+    traits::{
+        KeyPtr,
+        PackedLayout,
+        SpreadLayout,
+    },
+    Lazy,
+};
+
+/// Provides an interface for accessing elements in the `BinaryHeap`.
+///
+/// Elements of the heap are stored in a vector of `Children` objects, whereby
+/// each `Children` object contains two elements. When operating on indices of
+/// the `BinaryHeap` this interface transposes heap indices to the child inside
+/// the `Children` object, in which the element is stored.
+#[derive(Default, PartialEq, Eq, Debug)]
+pub struct ChildrenVec<T>
+where
+    T: PackedLayout + Ord,
+{
+    /// The number of elements stored in the heap.
+    /// We cannot use the length of the storage vector, since each entry (i.e. each
+    /// `Children` object) in the vector contains two child elements (except the root
+    /// element which occupies a `Children` object on its own.
+    len: Lazy<u32>,
+    /// The underlying storage vec containing the `Children`.
+    children: StorageVec<Children<T>>,
+}
+
+/// Encapsulates information regarding a particular child.
+pub(super) struct ChildInfo<'a, T> {
+    /// A reference to the value in this child, if existent.
+    pub child: &'a Option<T>,
+}
+
+impl<'a, T> ChildInfo<'a, T> {
+    /// Creates a new `ChildInfo` object.
+    fn new(child: &'a Option<T>) -> Self {
+        Self { child }
+    }
+}
+
+/// Encapsulates information regarding a particular child.
+pub(super) struct ChildInfoMut<'a, T> {
+    /// A mutable reference to the value in this child, if existent.
+    pub child: &'a mut Option<T>,
+    /// The number of children which are set in this `Children` object.
+    ///
+    /// This property exists only in `ChildInfoMut`, but not in `ChildInfo`.
+    /// The reason is that in the case of pop-ping a child from a `Children`
+    /// object we need to check if the child count of that object is `0` after
+    /// the pop operation. In that case no children are left in the object
+    /// and it can be removed altogether from the heap.
+    pub child_count: usize,
+}
+
+impl<'a, T> ChildInfoMut<'a, T> {
+    /// Creates a new `ChildInfoMut` object.
+    fn new(child: &'a mut Option<T>, child_count: usize) -> Self {
+        Self { child, child_count }
+    }
+}
+
+impl<T> ChildrenVec<T>
+where
+    T: PackedLayout + Ord,
+{
+    /// Creates a new empty storage heap.
+    #[inline]
+    pub fn new() -> Self {
+        Self {
+            len: Lazy::new(0),
+            children: StorageVec::new(),
+        }
+    }
+
+    /// Returns the number of elements in the heap, also referred to as its 'length'.
+    #[inline]
+    pub fn len(&self) -> u32 {
+        *self.len
+    }
+
+    /// Returns the amount of `Children` objects stored in the vector.
+    #[allow(dead_code)]
+    #[cfg(all(test, feature = "ink-fuzz-tests"))]
+    pub fn children_count(&self) -> u32 {
+        self.children.len()
+    }
+
+    /// Returns `true` if the heap contains no elements.
+    #[inline]
+    pub fn is_empty(&self) -> bool {
+        self.len() == 0
+    }
+
+    /// Returns a shared reference to the indexed element.
+    ///
+    /// Returns `None` if `index` is out of bounds.
+    pub fn get(&self, index: u32) -> Option<&T> {
+        self.get_child(index)?.child.as_ref()
+    }
+
+    /// Returns an exclusive reference to the indexed element.
+    /// The element in a `Children` is an `Option<T>`.
+    ///
+    /// Returns `None` if `index` is out of bounds.
+    pub fn get_mut(&mut self, index: u32) -> Option<&mut T> {
+        let child_info = self.get_child_mut(index)?;
+        child_info.child.as_mut()
+    }
+
+    /// Swaps the elements at the given indices.
+    ///
+    /// # Panics
+    ///
+    /// If one or both indices are out of bounds.
+    pub fn swap(&mut self, a: u32, b: u32) {
+        if a == b {
+            return
+        }
+        assert!(a < self.len(), "a is out of bounds");
+        assert!(b < self.len(), "b is out of bounds");
+
+        let child_info_a = self.get_child_mut(a).expect("index a must exist");
+        let a_opt = child_info_a.child.take();
+
+        let child_info_b = self.get_child_mut(b).expect("index b must exist");
+        let b_opt = core::mem::replace(child_info_b.child, a_opt);
+
+        let child_info_a = self.get_child_mut(a).expect("index a must exist");
+        *child_info_a.child = b_opt;
+    }
+
+    /// Removes the element at `index` from the heap and returns it.
+    ///
+    /// The last element of the heap is put into the slot at `index`.
+    /// Returns `None` and does not mutate the heap if it is empty.
+    pub fn swap_remove(&mut self, index: u32) -> Option<T> {
+        if self.is_empty() {
+            return None
+        }
+        self.swap(index, self.len() - 1);
+        self.pop()
+    }
+
+    /// Returns an iterator yielding shared references to all elements of the heap.
+    ///
+    /// # Note
+    ///
+    /// Avoid unbounded iteration over big storage heaps.
+    /// Prefer using methods like `Iterator::take` in order to limit the number
+    /// of yielded elements.
+    pub fn iter(&self) -> Iter<T> {
+        Iter::new(&self)
+    }
+
+    /// Returns an iterator yielding exclusive references to all elements of the heap.
+    ///
+    /// # Note
+    ///
+    /// Avoid unbounded iteration over big storage heaps.
+    /// Prefer using methods like `Iterator::take` in order to limit the number
+    /// of yielded elements.
+    pub fn iter_mut(&mut self) -> IterMut<T> {
+        IterMut::new(self)
+    }
+
+    /// Returns a shared reference to the first element if any.
+    pub fn first(&self) -> Option<&T> {
+        if self.is_empty() {
+            return None
+        }
+        self.get(0)
+    }
+
+    /// Returns an exclusive reference to the first element if any.
+    pub fn first_mut(&mut self) -> Option<&mut T> {
+        if self.is_empty() {
+            return None
+        }
+        self.get_mut(0)
+    }
+
+    /// Removes all elements from this heap.
+    ///
+    /// # Note
+    ///
+    /// Use this method to clear the heap instead of e.g. iterative `pop()`.
+    /// This method performs significantly better and does not actually read
+    /// any of the elements (whereas `pop()` does).
+    pub fn clear(&mut self) {
+        if self.is_empty() {
+            return
+        }
+        self.children.clear();
+        self.len = Lazy::new(0);
+    }
+
+    /// Appends an element to the back of the heap.
+    pub fn push(&mut self, value: T) {
+        assert!(
+            self.len() < core::u32::MAX,
+            "cannot push more elements into the storage heap"
+        );
+        let last_index = self.len();
+        *self.len += 1;
+        self.insert(last_index, Some(value));
+    }
+
+    /// Returns information about the child at the heap index if any.
+    pub(super) fn get_child(&self, index: u32) -> Option<ChildInfo<T>> {
+        let storage_index = children::get_children_storage_index(index);
+        let child_pos = children::get_child_pos(index);
+        let children = self.children.get(storage_index)?;
+        let child = children.child(child_pos);
+        Some(ChildInfo::new(child))
+    }
+
+    /// Returns information about the child at the heap index if any.
+    ///
+    /// The returned `ChildInfoMut` contains a mutable reference to the value `T`.
+    pub(super) fn get_child_mut(&mut self, index: u32) -> Option<ChildInfoMut<T>> {
+        let storage_index = children::get_children_storage_index(index);
+        let child_pos = children::get_child_pos(index);
+        let children = self.children.get_mut(storage_index)?;
+        let count = children.count();
+        let child = children.child_mut(child_pos);
+        Some(ChildInfoMut::new(child, count))
+    }
+
+    /// Inserts `value` at the heap index `index`.
+    ///
+    /// If there is already a child in storage which `index` resolves to
+    /// then `value` is inserted there. Otherwise a new child is created.
+    fn insert(&mut self, index: u32, value: Option<T>) {
+        let info = self.get_child_mut(index);
+        if let Some(info) = info {
+            *info.child = value;
+            return
+        }
+
+        self.children.push(Children::new(value, None));
+        debug_assert!(
+            {
+                let storage_index = children::get_children_storage_index(index);
+                self.children.get(storage_index).is_some()
+            },
+            "the new children were not placed at children_index!"
+        );
+    }
+
+    /// Pops the last element from the heap and returns it.
+    //
+    /// Returns `None` if the heap is empty.
+    fn pop(&mut self) -> Option<T> {
+        if self.is_empty() {
+            return None
+        }
+        let last_index = self.len() - 1;
+        *self.len = last_index;
+
+        let info = self
+            .get_child_mut(last_index)
+            .expect("children must exist at last_index");
+        let popped_val = info.child.take();
+        if info.child_count == 1 {
+            // if both children are non-existent the entire `Children` object can be removed
+            self.children.pop();
+        }
+        popped_val
+    }
+}
+
+impl<T> SpreadLayout for ChildrenVec<T>
+where
+    T: SpreadLayout + Ord + PackedLayout,
+{
+    const FOOTPRINT: u64 = 1 + <StorageVec<Children<T>> as SpreadLayout>::FOOTPRINT;
+
+    fn pull_spread(ptr: &mut KeyPtr) -> Self {
+        let len = SpreadLayout::pull_spread(ptr);
+        let children = SpreadLayout::pull_spread(ptr);
+        Self { len, children }
+    }
+
+    fn push_spread(&self, ptr: &mut KeyPtr) {
+        SpreadLayout::push_spread(&self.len, ptr);
+        SpreadLayout::push_spread(&self.children, ptr);
+    }
+
+    fn clear_spread(&self, ptr: &mut KeyPtr) {
+        SpreadLayout::clear_spread(&self.len, ptr);
+        SpreadLayout::clear_spread(&self.children, ptr);
+    }
+}
+
+/// An iterator over shared references to the elements of the `BinaryHeap`.
+#[derive(Debug, Clone, Copy)]
+pub struct Iter<'a, T>
+where
+    T: PackedLayout + Ord,
+{
+    /// The heap elements to iterate over.
+    elements: &'a ChildrenVec<T>,
+    /// The current begin of the iteration.
+    begin: u32,
+    /// The current end of the iteration.
+    end: u32,
+}
+
+impl<'a, T> Iter<'a, T>
+where
+    T: PackedLayout + Ord,
+{
+    /// Creates a new iterator for the given heap elements.
+    pub fn new(elements: &'a ChildrenVec<T>) -> Self {
+        Self {
+            elements,
+            begin: 0,
+            end: elements.len(),
+        }
+    }
+
+    /// Returns the amount of remaining elements to yield by the iterator.
+    fn remaining(&self) -> u32 {
+        self.end - self.begin
+    }
+}
+
+impl<'a, T> Iterator for Iter<'a, T>
+where
+    T: PackedLayout + Ord,
+{
+    type Item = &'a T;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        <Self as Iterator>::nth(self, 0)
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        let remaining = self.remaining() as usize;
+        (remaining, Some(remaining))
+    }
+
+    fn count(self) -> usize {
+        self.remaining() as usize
+    }
+
+    fn nth(&mut self, n: usize) -> Option<Self::Item> {
+        debug_assert!(self.begin <= self.end);
+        let n = n as u32;
+        if self.begin + n >= self.end {
+            return None
+        }
+        let cur = self.begin + n;
+        self.begin += 1 + n;
+
+        self.elements.get_child(cur)?.child.as_ref()
+    }
+}
+
+/// An iterator over exclusive references to the elements of a heap.
+#[derive(Debug)]
+pub struct IterMut<'a, T>
+where
+    T: PackedLayout + Ord,
+{
+    /// The heap elements to iterate over.
+    elements: &'a mut ChildrenVec<T>,
+    /// The current begin of the iteration.
+    begin: u32,
+    /// The current end of the iteration.
+    end: u32,
+}
+
+impl<'a, T> IterMut<'a, T>
+where
+    T: PackedLayout + Ord,
+{
+    /// Creates a new iterator for the given heap elements.
+    pub fn new(elements: &'a mut ChildrenVec<T>) -> Self {
+        let end = elements.len();
+        Self {
+            elements,
+            begin: 0,
+            end,
+        }
+    }
+
+    /// Returns the amount of remaining elements to yield by the iterator.
+    fn remaining(&self) -> u32 {
+        self.end - self.begin
+    }
+}
+
+impl<'a, T> IterMut<'a, T>
+where
+    T: PackedLayout + Ord,
+{
+    fn get_mut<'b>(&'b mut self, at: u32) -> Option<&'a mut T> {
+        let child_mut = self.elements.get_child_mut(at)?.child.as_mut();
+        child_mut.map(|value| {
+            // SAFETY: We extend the lifetime of the reference here.
+            //
+            //         This is safe because the iterator yields an exclusive
+            //         reference to every element in the iterated heap
+            //         just once and also there can be only one such iterator
+            //         for the same heap at the same time which is
+            //         guaranteed by the constructor of the iterator.
+            unsafe { extend_lifetime::<'b, 'a, T>(value) }
+        })
+    }
+}
+
+impl<'a, T> Iterator for IterMut<'a, T>
+where
+    T: PackedLayout + Ord,
+{
+    type Item = &'a mut T;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        <Self as Iterator>::nth(self, 0)
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        let remaining = self.remaining() as usize;
+        (remaining, Some(remaining))
+    }
+
+    fn count(self) -> usize {
+        self.remaining() as usize
+    }
+
+    fn nth(&mut self, n: usize) -> Option<Self::Item> {
+        debug_assert!(self.begin <= self.end);
+        let n = n as u32;
+        if self.begin + n >= self.end {
+            return None
+        }
+        let cur = self.begin + n;
+        self.begin += 1 + n;
+        self.get_mut(cur).expect("access is out of bounds").into()
+    }
+}
diff --git a/crates/storage/src/collections/binary_heap/impls.rs b/crates/storage/src/collections/binary_heap/impls.rs
index b849f914b4..e205f7268e 100644
--- a/crates/storage/src/collections/binary_heap/impls.rs
+++ b/crates/storage/src/collections/binary_heap/impls.rs
@@ -41,8 +41,8 @@ where
     where
         I: IntoIterator<Item = T>,
     {
-        let mut vec = Self::new();
-        vec.extend(iter);
-        vec
+        let mut heap = Self::new();
+        heap.extend(iter);
+        heap
     }
 }
diff --git a/crates/storage/src/collections/binary_heap/mod.rs b/crates/storage/src/collections/binary_heap/mod.rs
index 69652593bf..35e06c72d1 100644
--- a/crates/storage/src/collections/binary_heap/mod.rs
+++ b/crates/storage/src/collections/binary_heap/mod.rs
@@ -17,6 +17,8 @@
 //! Insertion and popping the largest element have `O(log(n))` complexity.
 //! Checking the largest element is `O(1)`.
 
+mod children;
+mod children_vec;
 mod impls;
 mod reverse;
 mod storage;
@@ -24,12 +26,16 @@ mod storage;
 #[cfg(test)]
 mod tests;
 
-use super::vec::{
+use self::children_vec::ChildrenVec;
+use crate::{
+    collections::vec::Vec as StorageVec,
+    traits::PackedLayout,
+};
+
+pub use children_vec::{
     Iter,
     IterMut,
-    Vec as StorageVec,
 };
-use crate::traits::PackedLayout;
 pub use reverse::Reverse;
 
 /// A priority queue implemented with a binary heap.
@@ -45,8 +51,8 @@ pub struct BinaryHeap<T>
 where
     T: PackedLayout + Ord,
 {
-    /// The underlying storage vec.
-    elems: StorageVec<T>,
+    /// The individual elements of the heap.
+    elements: ChildrenVec<T>,
 }
 
 impl<T> BinaryHeap<T>
@@ -56,18 +62,18 @@ where
     /// Creates a new empty storage heap.
     pub fn new() -> Self {
         Self {
-            elems: StorageVec::new(),
+            elements: ChildrenVec::new(),
         }
     }
 
     /// Returns the number of elements in the heap, also referred to as its 'length'.
     pub fn len(&self) -> u32 {
-        self.elems.len()
+        self.elements.len()
     }
 
     /// Returns `true` if the heap contains no elements.
     pub fn is_empty(&self) -> bool {
-        self.elems.is_empty()
+        self.elements.is_empty()
     }
 }
 
@@ -83,7 +89,7 @@ where
     /// Prefer using methods like `Iterator::take` in order to limit the number
     /// of yielded elements.
     pub fn iter(&self) -> Iter<T> {
-        self.elems.iter()
+        self.elements.iter()
     }
 
     /// Returns an iterator yielding exclusive references to all elements of the heap.
@@ -94,14 +100,14 @@ where
     /// Prefer using methods like `Iterator::take` in order to limit the number
     /// of yielded elements.
     pub fn iter_mut(&mut self) -> IterMut<T> {
-        self.elems.iter_mut()
+        self.elements.iter_mut()
     }
 
     /// Returns a shared reference to the greatest element of the heap
     ///
     /// Returns `None` if the heap is empty
     pub fn peek(&self) -> Option<&T> {
-        self.elems.first()
+        self.elements.first()
     }
 
     /// Returns an exclusive reference to the greatest element of the heap
@@ -147,14 +153,14 @@ where
         while child < end {
             let right = child + 1;
             // compare with the greater of the two children
-            if right < end && self.elems.get(child) <= self.elems.get(right) {
+            if right < end && self.elements.get(child) <= self.elements.get(right) {
                 child = right;
             }
             // if we are already in order, stop.
-            if self.elems.get(pos) >= self.elems.get(child) {
+            if self.elements.get(pos) >= self.elements.get(child) {
                 break
             }
-            self.elems.swap(child, pos);
+            self.elements.swap(child, pos);
             pos = child;
             child = 2 * pos + 1;
         }
@@ -165,7 +171,7 @@ where
     /// Returns `None` if the heap is empty
     pub fn pop(&mut self) -> Option<T> {
         // replace the root of the heap with the last element
-        let elem = self.elems.swap_remove(0);
+        let elem = self.elements.swap_remove(0);
         self.sift_down(0);
         elem
     }
@@ -174,11 +180,11 @@ where
     ///
     /// # Note
     ///
-    /// Use this method to clear the vector instead of e.g. iterative `pop()`.
+    /// Use this method to clear the heap instead of e.g. iterative `pop()`.
     /// This method performs significantly better and does not actually read
     /// any of the elements (whereas `pop()` does).
     pub fn clear(&mut self) {
-        self.elems.clear()
+        self.elements.clear()
     }
 }
 
@@ -191,10 +197,10 @@ where
     fn sift_up(&mut self, mut pos: u32) {
         while pos > 0 {
             let parent = (pos - 1) / 2;
-            if self.elems.get(pos) <= self.elems.get(parent) {
+            if self.elements.get(pos) <= self.elements.get(parent) {
                 break
             }
-            self.elems.swap(parent, pos);
+            self.elements.swap(parent, pos);
             pos = parent;
         }
     }
@@ -202,7 +208,7 @@ where
     /// Pushes the given element to the binary heap.
     pub fn push(&mut self, value: T) {
         let old_len = self.len();
-        self.elems.push(value);
+        self.elements.push(value);
         self.sift_up(old_len)
     }
 }
@@ -242,7 +248,7 @@ where
     type Target = T;
     fn deref(&self) -> &T {
         self.heap
-            .elems
+            .elements
             .first()
             .expect("PeekMut is only instantiated for non-empty heaps")
     }
@@ -254,7 +260,7 @@ where
 {
     fn deref_mut(&mut self) -> &mut T {
         self.heap
-            .elems
+            .elements
             .first_mut()
             .expect("PeekMut is only instantiated for non-empty heaps")
     }
diff --git a/crates/storage/src/collections/binary_heap/storage.rs b/crates/storage/src/collections/binary_heap/storage.rs
index cd96eb813c..8232f64509 100644
--- a/crates/storage/src/collections/binary_heap/storage.rs
+++ b/crates/storage/src/collections/binary_heap/storage.rs
@@ -14,14 +14,14 @@
 
 //! Implementation of ink! storage traits.
 
-use super::BinaryHeap;
-use crate::{
-    collections::Vec as StorageVec,
-    traits::{
-        KeyPtr,
-        PackedLayout,
-        SpreadLayout,
-    },
+use super::{
+    BinaryHeap,
+    ChildrenVec,
+};
+use crate::traits::{
+    KeyPtr,
+    PackedLayout,
+    SpreadLayout,
 };
 
 #[cfg(feature = "std")]
@@ -40,30 +40,61 @@ const _: () = {
     {
         fn layout(key_ptr: &mut KeyPtr) -> Layout {
             Layout::Struct(StructLayout::new(vec![FieldLayout::new(
-                "elems",
-                <StorageVec<T> as StorageLayout>::layout(key_ptr),
+                "elements",
+                <ChildrenVec<T> as StorageLayout>::layout(key_ptr),
             )]))
         }
     }
 };
 
+#[cfg(feature = "std")]
+const _: () = {
+    use super::children::Children;
+    use crate::{
+        collections::binary_heap::StorageVec,
+        lazy::Lazy,
+        traits::StorageLayout,
+    };
+    use ink_metadata::layout::{
+        FieldLayout,
+        Layout,
+        StructLayout,
+    };
+    use scale_info::TypeInfo;
+
+    impl<T> StorageLayout for ChildrenVec<T>
+    where
+        T: PackedLayout + Ord + TypeInfo + 'static,
+    {
+        fn layout(key_ptr: &mut KeyPtr) -> Layout {
+            Layout::Struct(StructLayout::new(vec![
+                FieldLayout::new("len", <Lazy<u32> as StorageLayout>::layout(key_ptr)),
+                FieldLayout::new(
+                    "children",
+                    <StorageVec<Children<T>> as StorageLayout>::layout(key_ptr),
+                ),
+            ]))
+        }
+    }
+};
+
 impl<T> SpreadLayout for BinaryHeap<T>
 where
     T: PackedLayout + Ord,
 {
-    const FOOTPRINT: u64 = 1 + <StorageVec<T> as SpreadLayout>::FOOTPRINT;
+    const FOOTPRINT: u64 = <ChildrenVec<T> as SpreadLayout>::FOOTPRINT;
 
     fn pull_spread(ptr: &mut KeyPtr) -> Self {
         Self {
-            elems: SpreadLayout::pull_spread(ptr),
+            elements: SpreadLayout::pull_spread(ptr),
         }
     }
 
     fn push_spread(&self, ptr: &mut KeyPtr) {
-        SpreadLayout::push_spread(&self.elems, ptr);
+        SpreadLayout::push_spread(&self.elements, ptr);
     }
 
     fn clear_spread(&self, ptr: &mut KeyPtr) {
-        SpreadLayout::clear_spread(&self.elems, ptr);
+        SpreadLayout::clear_spread(&self.elements, ptr);
     }
 }
diff --git a/crates/storage/src/traits/spread.rs b/crates/storage/src/traits/spread.rs
index d3541e006f..057dfc6809 100644
--- a/crates/storage/src/traits/spread.rs
+++ b/crates/storage/src/traits/spread.rs
@@ -74,7 +74,7 @@ pub trait SpreadLayout {
     /// - Tries to clean `Self` from contract storage as if `self` was stored
     ///   in it using spread layout.
     /// - The key pointer denotes the position where the instance is being cleared
-    /// from the contract storage.
+    ///   from the contract storage.
     ///
     /// # Note
     ///


Test patch:
diff --git a/crates/storage/src/collections/binary_heap/tests.rs b/crates/storage/src/collections/binary_heap/tests.rs
index d7a535228e..e9b50f271d 100644
--- a/crates/storage/src/collections/binary_heap/tests.rs
+++ b/crates/storage/src/collections/binary_heap/tests.rs
@@ -40,6 +40,26 @@ fn heap_of_size(n: u32) -> BinaryHeap<u32> {
         .collect()
 }
 
+/// Returns the number of cells a binary tree of `heap_size` occupies
+/// in the storage.
+///
+/// *Note*: `heap_size` must be even, if it is odd we cannot calculate
+/// the number of cells with certainty, since for e.g. `heap_size = 5`
+/// there might be two leaf cells with one element each or alternatively
+/// one leaf with two elements.
+fn get_count_cells(heap_size: u32) -> u32 {
+    fn division_round_up(dividend: u32, divisor: u32) -> u32 {
+        (dividend + divisor - 1) / divisor
+    }
+    assert!(heap_size % 2 == 0, "heap_size must be even");
+    let rest = match heap_size {
+        0 => 0,
+        1 => 0,
+        _ => division_round_up(heap_size, super::children::CHILDREN_PER_NODE),
+    };
+    rest + 1
+}
+
 #[test]
 fn new_binary_heap_works() {
     // `BinaryHeap::new`
@@ -279,7 +299,13 @@ where
         let (base_reads, base_writes) = ink_env::test::get_contract_storage_rw::<
             ink_env::DefaultEnvironment,
         >(&contract_account)?;
-        assert_eq!((base_reads as u32, base_writes as u32), (0, heap_size + 1));
+
+        // elements.len + vec.len
+        const CONST_WRITES: u32 = 2;
+        assert_eq!(
+            (base_reads as u32, base_writes as u32),
+            (0, CONST_WRITES + get_count_cells(heap_size))
+        );
 
         heap_op(&mut lazy_heap);
 
@@ -309,12 +335,17 @@ where
 
 #[test]
 fn push_largest_value_complexity_big_o_log_n() -> ink_env::Result<()> {
-    const CONST_READ_WRITES: usize = 2;
+    // 1 elements overhead (#508) + 1 elements.len + 1 heap overhead (#508) + 1 heap.len + 1 cell
+    const CONST_READS: usize = 5;
+
+    // 1 elements.len + 1 cell which was pushed to
+    // vec.len doesn't get larger because no cell is added
+    const CONST_WRITES: usize = 2;
 
     for (n, log_n) in &[(2, 1), (4, 2), (8, 3), (16, 4), (32, 5), (64, 6)] {
         let largest_value = n + 1;
-        let expected_reads = log_n + CONST_READ_WRITES;
-        let expected_writes = log_n + CONST_READ_WRITES;
+        let expected_reads = log_n + CONST_READS;
+        let expected_writes = log_n + CONST_WRITES;
         check_complexity_read_writes(
             *n,
             |heap| heap.push(largest_value),
@@ -328,13 +359,21 @@ fn push_largest_value_complexity_big_o_log_n() -> ink_env::Result<()> {
 #[test]
 fn push_smallest_value_complexity_big_o_1() -> ink_env::Result<()> {
     const SMALLEST_VALUE: u32 = 0;
-    const EXPECTED_READS: usize = 3;
+
+    // 1 elements overhead (#508) + 1 elements.len + 1 vec overhead (#508) +
+    // 1 vec.len + 1 vec.cell in which to insert + 1 parent cell during `sift_up`
+    const EXPECTED_READS: usize = 6;
+
+    // binary heap len + one cell
+    // vec.len doesn't get larger because no cell is added
     const EXPECTED_WRITES: usize = 2;
 
     for n in &[2, 4, 8, 16, 32, 64] {
         check_complexity_read_writes(
             *n,
-            |heap| heap.push(SMALLEST_VALUE),
+            |heap| {
+                heap.push(SMALLEST_VALUE);
+            },
             EXPECTED_READS,
             EXPECTED_WRITES,
         )?;
@@ -344,11 +383,17 @@ fn push_smallest_value_complexity_big_o_1() -> ink_env::Result<()> {
 
 #[test]
 fn pop_complexity_big_o_log_n() -> ink_env::Result<()> {
-    const CONST_READ_WRITES: usize = 2;
+    // 1 elements overhead (#508) + elements.len + 1 vec overhead (#508) +
+    // 1 vec.len + 1 vec.cell from which to pop
+    const CONST_READS: usize = 5;
+
+    // 1 elements.len + 1 vec.len + cell which was modified
+    const CONST_WRITES: usize = 3;
 
     for (n, log_n) in &[(2, 1), (4, 2), (8, 3), (16, 4), (32, 5), (64, 6)] {
-        let expected_reads = log_n * 2 + CONST_READ_WRITES;
-        let expected_writes = log_n + CONST_READ_WRITES;
+        let expected_reads = log_n + CONST_READS;
+        let expected_writes = log_n + CONST_WRITES;
+
         check_complexity_read_writes(
             *n,
             |heap| {
@@ -373,6 +418,11 @@ fn pop_always_returns_largest_element(xs: Vec<i32>) {
             assert_eq!(Some(*x), heap.pop())
         }
 
+        assert_eq!(heap.len(), 0);
+
+        // all elements must have been removed as well
+        assert_eq!(heap.elements.children_count(), 0);
+
         Ok(())
     })
     .unwrap()