Skip to content

improve 64 bit clone #800

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
mkeskells merged 1 commit into from
Aug 31, 2025
Merged

improve 64 bit clone #800

mkeskells merged 1 commit into from
Aug 31, 2025

Conversation

@mkeskells
Copy link
Contributor

@mkeskells mkeskells commented Aug 22, 2025 •
edited
Loading

Improve clone implementation for Roaring64Bitmap
Add benchmark

I was seeing GC stats in non allocating code which was skewing some benchmarks on local code,. This noise was caused by the preceding clone in setup

I am unsure if additional unit tests are needed to ensure that clone is doing the right thing (i.e. no sharing of mutable structures etc

SUMMARY

Perform a clone from the memory structure, rather than hydration

Automated Checks

  • I have run ./gradlew test and made sure that my PR does not break any unit test.

Summary comparison
clone relates to the old implementation, cloneNew relates to the implementation in this PR

In all cases the new implementation used less CPU and produces less allocation. Full jmh table output in a comment below

Benchmark                                          size)  Mode  Cnt          Score          Error   Units
CloneBenchmark.clone                                  10  avgt    5        625.095 ┬▒       69.718   ns/op
CloneBenchmark.cloneNew                               10  avgt    5        210.615 ┬▒       39.083   ns/op
CloneBenchmark.clone:┬Àgc.alloc.rate.norm             10  avgt    5       2840.022 ┬▒        0.032    B/op
CloneBenchmark.cloneNew:┬Àgc.alloc.rate.norm          10  avgt    5       1568.007 ┬▒        0.011    B/op

CloneBenchmark.clone                                 100  avgt    5       5584.360 ┬▒      921.576   ns/op
CloneBenchmark.cloneNew                              100  avgt    5       1970.138 ┬▒      828.473   ns/op
CloneBenchmark.clone:┬Àgc.alloc.rate.norm            100  avgt    5      21632.180 ┬▒        0.350    B/op
CloneBenchmark.cloneNew:┬Àgc.alloc.rate.norm         100  avgt    5      15008.076 ┬▒        0.084    B/op

CloneBenchmark.clone                                1000  avgt    5      85887.355 ┬▒     9144.499   ns/op
CloneBenchmark.cloneNew                             1000  avgt    5      16343.272 ┬▒     1200.606   ns/op
CloneBenchmark.clone:┬Àgc.alloc.rate.norm           1000  avgt    5     225114.476 ┬▒        5.656    B/op
CloneBenchmark.cloneNew:┬Àgc.alloc.rate.norm        1000  avgt    5     123560.637 ┬▒        0.591    B/op

CloneBenchmark.clone                               10000  avgt    5    1241723.049 ┬▒   155992.370   ns/op
CloneBenchmark.cloneNew                            10000  avgt    5     181841.805 ┬▒    24764.820   ns/op
CloneBenchmark.clone:┬Àgc.alloc.rate.norm          10000  avgt    5    2026425.839 ┬▒       37.780    B/op
CloneBenchmark.cloneNew:┬Àgc.alloc.rate.norm       10000  avgt    5    1224454.353 ┬▒        8.496    B/op

CloneBenchmark.clone                              100000  avgt    5   14939194.016 ┬▒  1575918.366   ns/op
CloneBenchmark.cloneNew                           100000  avgt    5    2687041.109 ┬▒   539254.022   ns/op
CloneBenchmark.clone:┬Àgc.alloc.rate.norm         100000  avgt    5   22158801.841 ┬▒      720.266    B/op
CloneBenchmark.cloneNew:┬Àgc.alloc.rate.norm      100000  avgt    5   12951499.006 ┬▒      149.454    B/op

CloneBenchmark.clone                             1000000  avgt    5  275947512.500 ┬▒   7922621.325   ns/op
CloneBenchmark.cloneNew                          1000000  avgt    5   49577044.159 ┬▒  31849076.491   ns/op
CloneBenchmark.clone:┬Àgc.alloc.rate.norm        1000000  avgt    5  213738697.400 ┬▒     61712.986    B/op
CloneBenchmark.cloneNew:┬Àgc.alloc.rate.norm     1000000  avgt    5  120851247.997 ┬▒      6252.456    B/op

@mkeskells
Copy link
Contributor Author

mkeskells commented Aug 22, 2025

full raw benchmark


Benchmark                                               (size)  Mode  Cnt          Score          Error   Units
CloneBenchmark.clone                                        10  avgt    5        625.095 ┬▒       69.718   ns/op
CloneBenchmark.clone:┬Àgc.alloc.rate                         10  avgt    5       3467.135 ┬▒      397.707  MB/sec
CloneBenchmark.clone:┬Àgc.alloc.rate.norm                    10  avgt    5       2840.022 ┬▒        0.032    B/op
CloneBenchmark.clone:┬Àgc.churn.G1_Eden_Space                10  avgt    5       3679.058 ┬▒     4067.789  MB/sec
CloneBenchmark.clone:┬Àgc.churn.G1_Eden_Space.norm           10  avgt    5       3028.342 ┬▒     3505.284    B/op
CloneBenchmark.clone:┬Àgc.churn.G1_Survivor_Space            10  avgt    5          0.018 ┬▒        0.055  MB/sec
CloneBenchmark.clone:┬Àgc.churn.G1_Survivor_Space.norm       10  avgt    5          0.015 ┬▒        0.046    B/op
CloneBenchmark.clone:┬Àgc.count                              10  avgt    5          9.000                 counts
CloneBenchmark.clone:┬Àgc.time                               10  avgt    5         35.000                     ms
CloneBenchmark.clone                                       100  avgt    5       5584.360 ┬▒      921.576   ns/op
CloneBenchmark.clone:┬Àgc.alloc.rate                        100  avgt    5       2957.832 ┬▒      495.885  MB/sec
CloneBenchmark.clone:┬Àgc.alloc.rate.norm                   100  avgt    5      21632.180 ┬▒        0.350    B/op
CloneBenchmark.clone:┬Àgc.churn.G1_Eden_Space               100  avgt    5       3170.062 ┬▒     4482.721  MB/sec
CloneBenchmark.clone:┬Àgc.churn.G1_Eden_Space.norm          100  avgt    5      23213.518 ┬▒    33134.694    B/op
CloneBenchmark.clone:┬Àgc.churn.G1_Survivor_Space           100  avgt    5          0.023 ┬▒        0.089  MB/sec
CloneBenchmark.clone:┬Àgc.churn.G1_Survivor_Space.norm      100  avgt    5          0.172 ┬▒        0.654    B/op
CloneBenchmark.clone:┬Àgc.count                             100  avgt    5          8.000                 counts
CloneBenchmark.clone:┬Àgc.time                              100  avgt    5         32.000                     ms
CloneBenchmark.clone                                      1000  avgt    5      85887.355 ┬▒     9144.499   ns/op
CloneBenchmark.clone:┬Àgc.alloc.rate                       1000  avgt    5       1999.925 ┬▒      216.403  MB/sec
CloneBenchmark.clone:┬Àgc.alloc.rate.norm                  1000  avgt    5     225114.476 ┬▒        5.656    B/op
CloneBenchmark.clone:┬Àgc.churn.G1_Eden_Space              1000  avgt    5       2002.552 ┬▒     2586.454  MB/sec
CloneBenchmark.clone:┬Àgc.churn.G1_Eden_Space.norm         1000  avgt    5     226470.620 ┬▒   307186.675    B/op
CloneBenchmark.clone:┬Àgc.churn.G1_Survivor_Space          1000  avgt    5          0.030 ┬▒        0.151  MB/sec
CloneBenchmark.clone:┬Àgc.churn.G1_Survivor_Space.norm     1000  avgt    5          3.482 ┬▒       17.361    B/op
CloneBenchmark.clone:┬Àgc.count                            1000  avgt    5          7.000                 counts
CloneBenchmark.clone:┬Àgc.time                             1000  avgt    5         26.000                     ms
CloneBenchmark.clone                                     10000  avgt    5    1241723.049 ┬▒   155992.370   ns/op
CloneBenchmark.clone:┬Àgc.alloc.rate                      10000  avgt    5       1245.681 ┬▒      154.823  MB/sec
CloneBenchmark.clone:┬Àgc.alloc.rate.norm                 10000  avgt    5    2026425.839 ┬▒       37.780    B/op
CloneBenchmark.clone:┬Àgc.churn.G1_Eden_Space             10000  avgt    5        987.078 ┬▒     2296.407  MB/sec
CloneBenchmark.clone:┬Àgc.churn.G1_Eden_Space.norm        10000  avgt    5    1616112.587 ┬▒  3708236.593    B/op
CloneBenchmark.clone:┬Àgc.churn.G1_Survivor_Space         10000  avgt    5          0.042 ┬▒        0.248  MB/sec
CloneBenchmark.clone:┬Àgc.churn.G1_Survivor_Space.norm    10000  avgt    5         70.717 ┬▒      419.385    B/op
CloneBenchmark.clone:┬Àgc.count                           10000  avgt    5          4.000                 counts
CloneBenchmark.clone:┬Àgc.time                            10000  avgt    5         15.000                     ms
CloneBenchmark.clone                                    100000  avgt    5   14939194.016 ┬▒  1575918.366   ns/op
CloneBenchmark.clone:┬Àgc.alloc.rate                     100000  avgt    5       1132.290 ┬▒      118.703  MB/sec
CloneBenchmark.clone:┬Àgc.alloc.rate.norm                100000  avgt    5   22158801.841 ┬▒      720.266    B/op
CloneBenchmark.clone:┬Àgc.churn.G1_Eden_Space            100000  avgt    5       1085.122 ┬▒     2474.327  MB/sec
CloneBenchmark.clone:┬Àgc.churn.G1_Eden_Space.norm       100000  avgt    5   21440991.932 ┬▒ 49307810.929    B/op
CloneBenchmark.clone:┬Àgc.churn.G1_Survivor_Space        100000  avgt    5          0.362 ┬▒        3.119  MB/sec
CloneBenchmark.clone:┬Àgc.churn.G1_Survivor_Space.norm   100000  avgt    5       7320.172 ┬▒    63028.891    B/op
CloneBenchmark.clone:┬Àgc.count                          100000  avgt    5          5.000                 counts
CloneBenchmark.clone:┬Àgc.time                           100000  avgt    5         39.000                     ms
CloneBenchmark.clone                                   1000000  avgt    5  275947512.500 ┬▒  7922621.325   ns/op
CloneBenchmark.clone:┬Àgc.alloc.rate                    1000000  avgt    5        601.936 ┬▒       14.047  MB/sec
CloneBenchmark.clone:┬Àgc.alloc.rate.norm               1000000  avgt    5  213738697.400 ┬▒    61712.986    B/op
CloneBenchmark.clone:┬Àgc.churn.G1_Eden_Space           1000000  avgt    5        525.638 ┬▒       12.357  MB/sec
CloneBenchmark.clone:┬Àgc.churn.G1_Eden_Space.norm      1000000  avgt    5  186646528.000 ┬▒        0.001    B/op
CloneBenchmark.clone:┬Àgc.count                         1000000  avgt    5          5.000                 counts
CloneBenchmark.clone:┬Àgc.time                          1000000  avgt    5        787.000                     ms


Benchmark                                                  (size)  Mode  Cnt          Score           Error   Units
CloneBenchmark.cloneNew                                        10  avgt    5        210.615 ┬▒        39.083   ns/op
CloneBenchmark.cloneNew:┬Àgc.alloc.rate                         10  avgt    5       5688.124 ┬▒      1047.246  MB/sec
CloneBenchmark.cloneNew:┬Àgc.alloc.rate.norm                    10  avgt    5       1568.007 ┬▒         0.011    B/op
CloneBenchmark.cloneNew:┬Àgc.churn.G1_Eden_Space                10  avgt    5       5374.893 ┬▒      4783.066  MB/sec
CloneBenchmark.cloneNew:┬Àgc.churn.G1_Eden_Space.norm           10  avgt    5       1483.454 ┬▒      1368.579    B/op
CloneBenchmark.cloneNew:┬Àgc.churn.G1_Survivor_Space            10  avgt    5          0.301 ┬▒         2.148  MB/sec
CloneBenchmark.cloneNew:┬Àgc.churn.G1_Survivor_Space.norm       10  avgt    5          0.080 ┬▒         0.568    B/op
CloneBenchmark.cloneNew:┬Àgc.count                              10  avgt    5         10.000                  counts
CloneBenchmark.cloneNew:┬Àgc.time                               10  avgt    5         34.000                      ms
CloneBenchmark.cloneNew                                       100  avgt    5       1970.138 ┬▒       828.473   ns/op
CloneBenchmark.cloneNew:┬Àgc.alloc.rate                        100  avgt    5       5862.362 ┬▒      2370.315  MB/sec
CloneBenchmark.cloneNew:┬Àgc.alloc.rate.norm                   100  avgt    5      15008.076 ┬▒         0.084    B/op
CloneBenchmark.cloneNew:┬Àgc.churn.G1_Eden_Space               100  avgt    5       5464.767 ┬▒      4289.981  MB/sec
CloneBenchmark.cloneNew:┬Àgc.churn.G1_Eden_Space.norm          100  avgt    5      14040.266 ┬▒     11696.890    B/op
CloneBenchmark.cloneNew:┬Àgc.churn.G1_Survivor_Space           100  avgt    5          0.295 ┬▒         2.315  MB/sec
CloneBenchmark.cloneNew:┬Àgc.churn.G1_Survivor_Space.norm      100  avgt    5          0.705 ┬▒         5.490    B/op
CloneBenchmark.cloneNew:┬Àgc.count                             100  avgt    5         11.000                  counts
CloneBenchmark.cloneNew:┬Àgc.time                              100  avgt    5         41.000                      ms
CloneBenchmark.cloneNew                                      1000  avgt    5      16343.272 ┬▒      1200.606   ns/op
CloneBenchmark.cloneNew:┬Àgc.alloc.rate                       1000  avgt    5       5765.504 ┬▒       427.125  MB/sec
CloneBenchmark.cloneNew:┬Àgc.alloc.rate.norm                  1000  avgt    5     123560.637 ┬▒         0.591    B/op
CloneBenchmark.cloneNew:┬Àgc.churn.G1_Eden_Space              1000  avgt    5       5911.225 ┬▒      4050.076  MB/sec
CloneBenchmark.cloneNew:┬Àgc.churn.G1_Eden_Space.norm         1000  avgt    5     126480.777 ┬▒     81086.416    B/op
CloneBenchmark.cloneNew:┬Àgc.churn.G1_Survivor_Space          1000  avgt    5          0.310 ┬▒         2.355  MB/sec
CloneBenchmark.cloneNew:┬Àgc.churn.G1_Survivor_Space.norm     1000  avgt    5          6.623 ┬▒        50.336    B/op
CloneBenchmark.cloneNew:┬Àgc.count                            1000  avgt    5         10.000                  counts
CloneBenchmark.cloneNew:┬Àgc.time                             1000  avgt    5         39.000                      ms
CloneBenchmark.cloneNew                                     10000  avgt    5     181841.805 ┬▒     24764.820   ns/op
CloneBenchmark.cloneNew:┬Àgc.alloc.rate                      10000  avgt    5       5139.784 ┬▒       683.530  MB/sec
CloneBenchmark.cloneNew:┬Àgc.alloc.rate.norm                 10000  avgt    5    1224454.353 ┬▒         8.496    B/op
CloneBenchmark.cloneNew:┬Àgc.churn.G1_Eden_Space             10000  avgt    5       4899.464 ┬▒      6048.372  MB/sec
CloneBenchmark.cloneNew:┬Àgc.churn.G1_Eden_Space.norm        10000  avgt    5    1167655.364 ┬▒   1428732.032    B/op
CloneBenchmark.cloneNew:┬Àgc.churn.G1_Survivor_Space         10000  avgt    5          0.493 ┬▒         2.937  MB/sec
CloneBenchmark.cloneNew:┬Àgc.churn.G1_Survivor_Space.norm    10000  avgt    5        122.276 ┬▒       742.564    B/op
CloneBenchmark.cloneNew:┬Àgc.count                           10000  avgt    5         10.000                  counts
CloneBenchmark.cloneNew:┬Àgc.time                            10000  avgt    5         42.000                      ms
CloneBenchmark.cloneNew                                    100000  avgt    5    2687041.109 ┬▒    539254.022   ns/op
CloneBenchmark.cloneNew:┬Àgc.alloc.rate                     100000  avgt    5       3684.465 ┬▒       753.283  MB/sec
CloneBenchmark.cloneNew:┬Àgc.alloc.rate.norm                100000  avgt    5   12951499.006 ┬▒       149.454    B/op
CloneBenchmark.cloneNew:┬Àgc.churn.G1_Eden_Space            100000  avgt    5       3349.849 ┬▒      3070.906  MB/sec
CloneBenchmark.cloneNew:┬Àgc.churn.G1_Eden_Space.norm       100000  avgt    5   11720862.716 ┬▒   9348313.296    B/op
CloneBenchmark.cloneNew:┬Àgc.churn.G1_Survivor_Space        100000  avgt    5          0.916 ┬▒         3.370  MB/sec
CloneBenchmark.cloneNew:┬Àgc.churn.G1_Survivor_Space.norm   100000  avgt    5       3313.187 ┬▒     12287.214    B/op
CloneBenchmark.cloneNew:┬Àgc.count                          100000  avgt    5          7.000                  counts
CloneBenchmark.cloneNew:┬Àgc.time                           100000  avgt    5         43.000                      ms
CloneBenchmark.cloneNew                                   1000000  avgt    5   49577044.159 ┬▒  31849076.491   ns/op
CloneBenchmark.cloneNew:┬Àgc.alloc.rate                    1000000  avgt    5       1906.758 ┬▒      1250.752  MB/sec
CloneBenchmark.cloneNew:┬Àgc.alloc.rate.norm               1000000  avgt    5  120851247.997 ┬▒      6252.456    B/op
CloneBenchmark.cloneNew:┬Àgc.churn.G1_Eden_Space           1000000  avgt    5       1703.424 ┬▒        28.465  MB/sec
CloneBenchmark.cloneNew:┬Àgc.churn.G1_Eden_Space.norm      1000000  avgt    5  110465466.023 ┬▒  71114189.048    B/op
CloneBenchmark.cloneNew:┬Àgc.churn.G1_Old_Gen              1000000  avgt    5       1037.568 ┬▒      8933.772  MB/sec
CloneBenchmark.cloneNew:┬Àgc.churn.G1_Old_Gen.norm         1000000  avgt    5   80728015.812 ┬▒ 695092562.206    B/op
CloneBenchmark.cloneNew:┬Àgc.churn.G1_Survivor_Space       1000000  avgt    5         10.536 ┬▒        90.721  MB/sec
CloneBenchmark.cloneNew:┬Àgc.churn.G1_Survivor_Space.norm  1000000  avgt    5     819781.459 ┬▒   7058565.591    B/op
CloneBenchmark.cloneNew:┬Àgc.count                         1000000  avgt    5         18.000                  counts
CloneBenchmark.cloneNew:┬Àgc.time                          1000000  avgt    5       3371.000                      ms

@lemire
Copy link
Member

lemire commented Aug 23, 2025

@mkeskells Great. Can you sync with our main branch ? I have added some minimal tests for the clone function.

Currently, your PR does not get tested very much.

@mkeskells
add cloning benchmarks
deae25b 
add clone implementation for Roaring64Bitmap
@lemire
Copy link
Member

lemire commented Aug 25, 2025

We can merge if you'd like.

@mkeskells mkeskells merged commit 0d6531f into RoaringBitmap:master Aug 31, 2025
7 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

@mkeskells @lemire