Add function for checking indices of leaves which are set to zero

[seemenkina]

Part of #237

In general everything is ready, tests that helped to find problems from #248 are commented out for now.

[github-actions[bot]]

Benchmark for 80b3da6

Click to view benchmark

| Test | Base | PR | % | |------|--------------|------------------|---| | FullMerkleTree::compute_root | 0.0±0.00ns | 0.0±0.00ns | NaN% | | FullMerkleTree::delete | **843.4±11.26ns** | 856.1±5.48ns | **+1.51%** | | FullMerkleTree::get | **0.0±0.00ns** | 3.4±0.04ns | **+Infinity%** | | FullMerkleTree::get_empty_leaves_indices | 4.3±0.08ns | N/A | N/A | | FullMerkleTree::override_range | **2.1±0.02µs** | 2.2±0.13µs | **+4.76%** | | FullMerkleTree::set | **842.7±8.96ns** | 855.5±10.94ns | **+1.52%** | | OptimalMerkleTree::compute_root | **984.0±16.14ns** | 1027.4±17.15ns | **+4.41%** | | OptimalMerkleTree::delete | **985.9±6.57ns** | 1017.8±16.40ns | **+3.24%** | | OptimalMerkleTree::get | **18.6±0.27ns** | 23.4±0.20ns | **+25.81%** | | OptimalMerkleTree::get_empty_leaves_indices | 4.7±0.07ns | N/A | N/A | | OptimalMerkleTree::override_range | **4.9±0.04µs** | 5.1±0.23µs | **+4.08%** | | OptimalMerkleTree::set | **987.0±24.76ns** | 1015.8±11.38ns | **+2.92%** |

[github-actions[bot]]

Benchmark for 576e171

Click to view benchmark

| Test | Base | PR | % | |------|--------------|------------------|---| | FullMerkleTree::compute_root | 0.0±0.00ns | 0.0±0.00ns | NaN% | | FullMerkleTree::delete | 851.0±44.21ns | 853.6±12.32ns | +0.31% | | FullMerkleTree::get | **0.0±0.00ns** | 3.4±0.06ns | **+Infinity%** | | FullMerkleTree::get_empty_leaves_indices | 4.3±0.06ns | N/A | N/A | | FullMerkleTree::override_range | 2.1±0.03µs | 2.1±0.03µs | 0.00% | | FullMerkleTree::set | 844.0±11.01ns | 849.9±11.00ns | +0.70% | | OptimalMerkleTree::compute_root | **985.7±9.78ns** | 1016.7±29.97ns | **+3.14%** | | OptimalMerkleTree::delete | 986.4±14.90ns | 996.5±13.55ns | +1.02% | | OptimalMerkleTree::get | **18.5±0.23ns** | 23.5±0.43ns | **+27.03%** | | OptimalMerkleTree::get_empty_leaves_indices | 4.7±0.08ns | N/A | N/A | | OptimalMerkleTree::override_range | **4.9±0.04µs** | 5.1±0.05µs | **+4.08%** | | OptimalMerkleTree::set | 1000.7±75.19ns | 1001.8±37.74ns | +0.11% |

[github-actions[bot]]

Benchmark for 576e171

Click to view benchmark

| Test | Base | PR | % | |------|--------------|------------------|---| | FullMerkleTree::::full_height_gen | **14.9±0.28ms** | 15.9±0.29ms | **+6.71%** | | OptimalMerkleTree::::full_height_gen | **539.7±8.39µs** | 580.9±5.13µs | **+7.63%** | | Pmtree::compute_root | 0.0±0.00ns | 0.0±0.00ns | NaN% | | Pmtree::get | 352.6±4.61ns | **325.8±14.77ns** | **-7.60%** | | Pmtree::get_empty_leaves_indices | 8.4±0.16ns | N/A | N/A | | Pmtree::override_range | 239.5±3.85µs | 237.9±4.38µs | -0.67% | | Pmtree::set | 53.9±0.93µs | 54.0±0.73µs | +0.19% | | Pmtree:delete | 53.8±0.50µs | 54.0±0.67µs | +0.37% | | Set/FullMerkleTree::::set/1 | **544.0±6.31µs** | 555.7±22.26µs | **+2.15%** | | Set/FullMerkleTree::::set/10 | **5.5±0.03ms** | 5.6±0.03ms | **+1.82%** | | Set/FullMerkleTree::::set/100 | **55.0±0.26ms** | 55.7±0.18ms | **+1.27%** | | Set/FullMerkleTree::::set_range/1 | **544.8±5.58µs** | 552.5±6.15µs | **+1.41%** | | Set/FullMerkleTree::::set_range/10 | 748.9±13.43µs | 759.8±27.81µs | +1.46% | | Set/FullMerkleTree::::set_range/100 | 3.3±0.05ms | 3.3±0.01ms | 0.00% | | Set/OptimalMerkleTree::::set/1 | **541.1±7.97µs** | 553.6±5.77µs | **+2.31%** | | Set/OptimalMerkleTree::::set/10 | **5.4±0.02ms** | 5.5±0.01ms | **+1.85%** | | Set/OptimalMerkleTree::::set/100 | **54.3±0.18ms** | 55.6±0.20ms | **+2.39%** | | Set/OptimalMerkleTree::::set_range/1 | **539.0±5.68µs** | 552.3±8.12µs | **+2.47%** | | Set/OptimalMerkleTree::::set_range/10 | **5.4±0.02ms** | 5.5±0.02ms | **+1.85%** | | Set/OptimalMerkleTree::::set_range/100 | **54.2±0.10ms** | 55.9±2.01ms | **+3.14%** | | zkey::upload_from_folder | 3.3±0.01s | 3.3±0.01s | 0.00% |

[seemenkina]

noticed the subtree test is included here, is that intended?

oh, It's just misprint in function name, thank you for noticed

[github-actions[bot]]

Benchmark for 911e860

Click to view benchmark

| Test | Base | PR | % | |------|--------------|------------------|---| | FullMerkleTree::compute_root | 0.0±0.00ns | 0.0±0.00ns | NaN% | | FullMerkleTree::delete | 846.9±13.20ns | 840.3±29.44ns | -0.78% | | FullMerkleTree::get | **0.0±0.00ns** | 3.4±0.16ns | **+Infinity%** | | FullMerkleTree::get_empty_leaves_indices | 4.3±0.07ns | N/A | N/A | | FullMerkleTree::override_range | **2.1±0.06µs** | 2.2±0.04µs | **+4.76%** | | FullMerkleTree::set | 842.4±16.80ns | **818.9±18.98ns** | **-2.79%** | | OptimalMerkleTree::compute_root | 987.5±32.79ns | 965.2±34.04ns | -2.26% | | OptimalMerkleTree::delete | **949.3±21.99ns** | 986.2±57.53ns | **+3.89%** | | OptimalMerkleTree::get | 27.0±0.60ns | **22.9±0.63ns** | **-15.19%** | | OptimalMerkleTree::get_empty_leaves_indices | 4.6±0.13ns | N/A | N/A | | OptimalMerkleTree::override_range | **4.8±0.14µs** | 5.1±0.14µs | **+6.25%** | | OptimalMerkleTree::set | **951.3±21.00ns** | 985.8±17.06ns | **+3.63%** |

[github-actions[bot]]

Benchmark for 911e860

Click to view benchmark

| Test | Base | PR | % | |------|--------------|------------------|---| | FullMerkleTree::::full_height_gen | 15.2±1.01ms | **14.6±0.11ms** | **-3.95%** | | OptimalMerkleTree::::full_height_gen | **543.8±12.11µs** | 574.0±4.74µs | **+5.55%** | | Pmtree::compute_root | 0.0±0.00ns | 0.0±0.00ns | NaN% | | Pmtree::get | 342.3±6.96ns | **329.4±3.35ns** | **-3.77%** | | Pmtree::get_empty_leaves_indices | 8.4±0.32ns | N/A | N/A | | Pmtree::override_range | 234.7±3.44µs | 231.9±3.63µs | -1.19% | | Pmtree::set | 54.2±1.96µs | 54.1±1.16µs | -0.18% | | Pmtree:delete | 53.6±0.62µs | 54.0±0.62µs | +0.75% | | Set/FullMerkleTree::::set/1 | **540.0±6.06µs** | 552.1±4.05µs | **+2.24%** | | Set/FullMerkleTree::::set/10 | **5.5±0.02ms** | 5.6±0.03ms | **+1.82%** | | Set/FullMerkleTree::::set/100 | **54.3±0.22ms** | 55.5±0.21ms | **+2.21%** | | Set/FullMerkleTree::::set_range/1 | **538.8±4.70µs** | 558.7±35.71µs | **+3.69%** | | Set/FullMerkleTree::::set_range/10 | **742.4±13.60µs** | 757.1±6.57µs | **+1.98%** | | Set/FullMerkleTree::::set_range/100 | **3.2±0.01ms** | 3.3±0.15ms | **+3.13%** | | Set/OptimalMerkleTree::::set/1 | **540.8±7.41µs** | 555.6±7.45µs | **+2.74%** | | Set/OptimalMerkleTree::::set/10 | **5.4±0.04ms** | 5.6±0.02ms | **+3.70%** | | Set/OptimalMerkleTree::::set/100 | **54.6±0.18ms** | 55.7±0.92ms | **+2.01%** | | Set/OptimalMerkleTree::::set_range/1 | **540.0±2.94µs** | 563.9±73.29µs | **+4.43%** | | Set/OptimalMerkleTree::::set_range/10 | **5.4±0.01ms** | 5.5±0.03ms | **+1.85%** | | Set/OptimalMerkleTree::::set_range/100 | **54.8±0.36ms** | 55.5±0.19ms | **+1.28%** | | zkey::upload_from_folder | 3.3±0.01s | 3.3±0.01s | 0.00% |

[github-actions[bot]]

Benchmark for 3a20f37

Click to view benchmark

| Test | Base | PR | % | |------|--------------|------------------|---| | FullMerkleTree::compute_root | 0.0±0.00ns | 0.0±0.00ns | NaN% | | FullMerkleTree::delete | 859.2±20.06ns | 875.4±80.11ns | +1.89% | | FullMerkleTree::get | **0.0±0.00ns** | 3.4±0.04ns | **+Infinity%** | | FullMerkleTree::get_empty_leaves_indices | 4.6±0.03ns | N/A | N/A | | FullMerkleTree::get_subtree_root | **0.6±0.01ns** | 3.6±0.12ns | **+500.00%** | | FullMerkleTree::override_range | **2.1±0.02µs** | 2.2±0.03µs | **+4.76%** | | FullMerkleTree::set | 863.6±6.38ns | 862.5±11.18ns | -0.13% | | OptimalMerkleTree::compute_root | 1003.0±8.08ns | 997.5±5.96ns | -0.55% | | OptimalMerkleTree::delete | 1013.0±12.00ns | 1003.4±25.99ns | -0.95% | | OptimalMerkleTree::get | **18.6±0.17ns** | 23.5±0.25ns | **+26.34%** | | OptimalMerkleTree::get_empty_leaves_indices | 4.6±0.07ns | N/A | N/A | | OptimalMerkleTree::get_subtree_root | **18.6±0.33ns** | 23.9±0.36ns | **+28.49%** | | OptimalMerkleTree::override_range | **5.0±0.07µs** | 5.1±0.14µs | **+2.00%** | | OptimalMerkleTree::set | 1014.8±6.56ns | **997.0±10.44ns** | **-1.75%** |

[github-actions[bot]]

Benchmark for 3a20f37

Click to view benchmark

| Test | Base | PR | % | |------|--------------|------------------|---| | FullMerkleTree::::full_height_gen | **14.0±0.11ms** | 15.1±0.06ms | **+7.86%** | | OptimalMerkleTree::::full_height_gen | **543.2±7.67µs** | 565.1±5.37µs | **+4.03%** | | Pmtree::compute_root | 0.0±0.00ns | 0.0±0.00ns | NaN% | | Pmtree::get | 340.1±3.75ns | **336.0±3.25ns** | **-1.21%** | | Pmtree::get_empty_leaves_indices | 8.4±0.10ns | N/A | N/A | | Pmtree::get_subtree_root | 474.0±7.79ns | 475.1±5.13ns | +0.23% | | Pmtree::override_range | 234.4±3.72µs | 233.1±4.36µs | -0.55% | | Pmtree::set | **53.7±0.30µs** | 54.5±0.56µs | **+1.49%** | | Pmtree:delete | 54.3±0.41µs | 54.5±1.41µs | +0.37% | | Set/FullMerkleTree::::set/1 | 544.9±7.38µs | 544.9±2.51µs | 0.00% | | Set/FullMerkleTree::::set/10 | 5.5±0.04ms | 5.5±0.02ms | 0.00% | | Set/FullMerkleTree::::set/100 | 54.8±0.21ms | 55.0±0.22ms | +0.36% | | Set/FullMerkleTree::::set_range/1 | 548.0±6.95µs | 546.9±12.14µs | -0.20% | | Set/FullMerkleTree::::set_range/10 | 747.8±8.60µs | 749.6±22.54µs | +0.24% | | Set/FullMerkleTree::::set_range/100 | 3.3±0.01ms | 3.3±0.01ms | 0.00% | | Set/OptimalMerkleTree::::set/1 | 545.0±4.06µs | 547.0±4.61µs | +0.37% | | Set/OptimalMerkleTree::::set/10 | **5.4±0.03ms** | 5.5±0.03ms | **+1.85%** | | Set/OptimalMerkleTree::::set/100 | 54.8±0.20ms | 54.9±0.19ms | +0.18% | | Set/OptimalMerkleTree::::set_range/1 | 544.4±3.30µs | 545.6±5.20µs | +0.22% | | Set/OptimalMerkleTree::::set_range/10 | 5.5±0.04ms | 5.5±0.02ms | 0.00% | | Set/OptimalMerkleTree::::set_range/100 | **54.9±0.23ms** | 55.3±2.55ms | **+0.73%** | | zkey::upload_from_folder | 3.3±0.01s | 3.3±0.01s | 0.00% |

[github-actions[bot]]

Benchmark for 81048f0

Click to view benchmark

| Test | Base | PR | % | |------|--------------|------------------|---| | FullMerkleTree::compute_root | 0.0±0.00ns | 0.0±0.00ns | NaN% | | FullMerkleTree::delete | 854.6±15.63ns | **842.0±12.44ns** | **-1.47%** | | FullMerkleTree::get | 0.0±0.00ns | 0.0±0.00ns | NaN% | | FullMerkleTree::get_empty_leaves_indices | 7.1±0.08ns | N/A | N/A | | FullMerkleTree::get_subtree_root | 0.6±0.01ns | 0.6±0.01ns | 0.00% | | FullMerkleTree::override_range | 2.1±0.01µs | **1305.0±13.94ns** | **-37.86%** | | FullMerkleTree::set | 850.6±11.04ns | 843.3±12.48ns | -0.86% | | OptimalMerkleTree::compute_root | **995.0±7.07ns** | 1033.6±20.20ns | **+3.88%** | | OptimalMerkleTree::delete | **1006.8±47.33ns** | 1039.8±14.66ns | **+3.28%** | | OptimalMerkleTree::get | **18.6±0.23ns** | 23.3±0.21ns | **+25.27%** | | OptimalMerkleTree::get_empty_leaves_indices | 7.4±0.14ns | N/A | N/A | | OptimalMerkleTree::get_subtree_root | **18.7±0.77ns** | 23.8±0.37ns | **+27.27%** | | OptimalMerkleTree::override_range | 5.0±0.04µs | **4.2±0.25µs** | **-16.00%** | | OptimalMerkleTree::set | **1002.0±8.01ns** | 1042.8±14.52ns | **+4.07%** |

[github-actions[bot]]

Benchmark for 81048f0

Click to view benchmark

| Test | Base | PR | % | |------|--------------|------------------|---| | FullMerkleTree::::full_height_gen | **13.9±0.19ms** | 15.5±0.48ms | **+11.51%** | | OptimalMerkleTree::::full_height_gen | **544.3±5.90µs** | 569.9±7.61µs | **+4.70%** | | Pmtree::compute_root | 0.0±0.00ns | 0.0±0.00ns | NaN% | | Pmtree::get | **334.5±4.98ns** | 339.7±10.56ns | **+1.55%** | | Pmtree::get_empty_leaves_indices | 8.4±0.14ns | N/A | N/A | | Pmtree::get_subtree_root | 473.8±8.44ns | 478.7±8.45ns | +1.03% | | Pmtree::override_range | 234.0±4.69µs | 233.4±3.87µs | -0.26% | | Pmtree::set | 53.7±0.59µs | 53.7±0.35µs | 0.00% | | Pmtree:delete | 53.7±0.37µs | 53.9±1.01µs | +0.37% | | Set/FullMerkleTree::::set/1 | **542.9±4.11µs** | 547.9±8.31µs | **+0.92%** | | Set/FullMerkleTree::::set/10 | **5.4±0.15ms** | 5.5±0.03ms | **+1.85%** | | Set/FullMerkleTree::::set/100 | **54.8±0.25ms** | 55.1±0.26ms | **+0.55%** | | Set/FullMerkleTree::::set_range/1 | **542.2±4.27µs** | 548.0±6.08µs | **+1.07%** | | Set/FullMerkleTree::::set_range/10 | 745.0±5.96µs | 749.3±12.45µs | +0.58% | | Set/FullMerkleTree::::set_range/100 | 3.3±0.01ms | 3.3±0.01ms | 0.00% | | Set/OptimalMerkleTree::::set/1 | 547.8±4.11µs | 548.4±8.26µs | +0.11% | | Set/OptimalMerkleTree::::set/10 | 5.5±0.02ms | 5.5±0.02ms | 0.00% | | Set/OptimalMerkleTree::::set/100 | **54.8±0.23ms** | 55.0±0.14ms | **+0.36%** | | Set/OptimalMerkleTree::::set_range/1 | 545.1±5.97µs | 543.9±8.00µs | -0.22% | | Set/OptimalMerkleTree::::set_range/10 | 5.5±0.10ms | 5.5±0.01ms | 0.00% | | Set/OptimalMerkleTree::::set_range/100 | 55.0±0.35ms | 54.9±0.10ms | -0.18% | | zkey::upload_from_folder | 3.3±0.00s | 3.3±0.01s | 0.00% |