8000 Long2ObjectOpenHashMap is slower than HashMap in java.util · Issue #347 · vigna/fastutil · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Long2ObjectOpenHashMap is slower than HashMap in java.util #347

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
Closed
gengjun-git opened this issue May 7, 2025 · 3 comments
Closed

Long2ObjectOpenHashMap is slower than HashMap in java.util #347

gengjun-git opened this issue May 7, 2025 · 3 comments

Comments

@gengjun-git
Copy link
gengjun-git commented May 7, 2025 •
edited
Loading

This is my test code:

        final long TOTAL = 5000000L;
        Map<Long, Foo> map = new HashMap<>();
        // Map<Long, Foo> map = new Long2ObjectOpenHashMap<>();
        long maxW = -1L;
        long totalW = 0;
        long maxR = -1L;
        long totalR = 0;
        List<Long> wUsed = new ArrayList<>((int)TOTAL);
        List<Long> rUsed = new ArrayList<>((int)TOTAL);
        for (long i = 0; i < TOTAL; i++) {
            long start = System.nanoTime();
            Foo foo = new Foo();
            map.put(i, foo);
            long used = System.nanoTime() - start;
            maxW = Math.max(maxW, used);
            totalW += used;
            wUsed.add(used);
        }
        for (long i = 0; i < TOTAL; i++) {
            long start = System.nanoTime();
            map.get(i);
            long used = System.nanoTime() - start;
            maxR = Math.max(maxR, used);
            totalR += used;
            rUsed.add(used);
        }
        wUsed.sort(Comparator.reverseOrder());
        rUsed.sort(Comparator.reverseOrder());
        System.out.println("totalW: " + totalW + ", totalR: " + totalR
                + ", maxW: " + maxW + ", maxR: " + maxR
                + ", avgW: " + totalW / TOTAL + ", avgR: " + totalR / TOTAL
                + ", p99W: " + wUsed.get(50000) + ", p99R: " + rUsed.get(50000));

The result is

java.util.HashMap:
totalW: 663967578, totalR: 422418856, maxW: 63271855, maxR: 42850847, avgW: 132, avgR: 84, p99W: 137, p99R: 291
totalW: 651655688, totalR: 290515682, maxW: 56610865, maxR: 6989790, avgW: 130, avgR: 58, p99W: 135, p99R: 239
totalW: 700310638, totalR: 267878485, maxW: 53654800, maxR: 7820550, avgW: 140, avgR: 53, p99W: 146, p99R: 207

Long2ObjectOpenHashMap:
totalW: 1205439864, totalR: 736233534, maxW: 82863284, maxR: 373600, avgW: 241, avgR: 147, p99W: 359, p99R: 333
totalW: 1168520211, totalR: 789453626, maxW: 104233710, maxR: 1274739, avgW: 233, avgR: 157, p99W: 360, p99R: 352
totalW: 1142117792, totalR: 739646587, maxW: 109271044, maxR: 85790, avgW: 228, avgR: 147, p99W: 348, p99R: 336

jdk version is:

openjdk version "17.0.14" 2025-01-21
OpenJDK Runtime Environment Temurin-17.0.14+7 (build 17.0.14+7)
OpenJDK 64-Bit Server VM Temurin-17.0.14+7 (build 17.0.14+7, mixed mode)
@incaseoftrouble
Copy link
Collaborator
incaseoftrouble commented May 7, 2025 •
edited
Loading

a) this isn't really a good benchmark, you'd need to use JMH's blackhole or similar for to disallow the compiler from proving that map.get(...) is side-effect free.
b) this is a result of fastutil's hashcode for int and long -- Java uses identity hashing (hash of int i is i, hash of long l is (l ^ l >>> 32)) whereas fastutil uses mixing hashes. If you randomize the keys the difference is significant in the other way round

        final long TOTAL = 5000000L;
        Random rW = new Random(0);
        Map<Long, Object> map = new HashMap<>();
        long startW = System.nanoTime();
        for (long i = 0; i < TOTAL; i++) {
            map.put(rW.nextLong(), new Object());
        }
        long usedW = System.nanoTime() - startW;

        Random rG = new Random(0);
        long startG = System.nanoTime();
        for (long i = 0; i < TOTAL; i++) {
            map.get(rG.nextLong());
        }
        long usedG = System.nanoTime() - startG;
        System.out.println("totalW: " + usedG + ", totalR: " + usedW);

Here, java's map is approx. factor 1.5-2 slower on my machine.

(If you need to store "continuous" blocks, try https://github.com/incaseoftrouble/naturals-util ;) )

(Instead of using Random, you could also use, e.g. i * i as key, this will provoke hash collisions for both implementations)

@gengjun-git
Copy link
Author

@incaseoftrouble Thanks for your quick reply, which gives me confidence in using this tool. I will change my test code and try again.

@gengjun-git
Copy link
Author

@incaseoftrouble Yes, you are right, I change the key to i * i, and the fastutil is faster now.

java.util.HashMap:
totalW: 1642979535, totalR: 1707308666, maxW: 216114929, maxR: 82408299, avgW: 328, avgR: 341, p99W: 621, p99R: 707
totalW: 1614630442, totalR: 1587743806, maxW: 144624615, maxR: 588608, avgW: 322, avgR: 317, p99W: 642, p99R: 705
totalW: 1812878019, totalR: 1562808879, maxW: 221786315, maxR: 36302853, avgW: 362, avgR: 312, p99W: 633, p99R: 694

Long2ObjectOpenHashMap:
totalW: 1262341768, totalR: 1344185116, maxW: 92946906, maxR: 25478820, avgW: 252, avgR: 268, p99W: 546, p99R: 649
totalW: 1152699061, totalR: 940122576, maxW: 89912439, maxR: 814615, avgW: 230, avgR: 188, p99W: 405, p99R: 395
totalW: 1232091047, totalR: 1061720761, maxW: 95842036, maxR: 25598453, avgW: 246, avgR: 212, p99W: 407, p99R: 430

A great tool to save to memory footprint.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@incaseoftrouble @gengjun-git
0