search

vigna / fastutil

fastutil extends the Java™ Collections Framework by providing type-specific maps, sets, lists and queues.
Apache License 2.0
1.81k stars 199 forks source link

OpenHashMaps.mergePRIMITIVE: Avoid double-hashing key #337

Open mhansen opened 3 days ago

mhansen commented 3 days ago

The #if VALUES_PRIMITIVE && ! VALUE_CLASS_Boolean comes from the superclass in Map.drv: https://github.com/vigna/fastutil/blob/355d8ebfaf2bcc4032cc1c25bec9f3fe827f8175/drv/Map.drv#L649

The implementation mostly is copied from the method below (merge), with dead code removed because VALUES_PRIMITIVE is always true.

I'm using the METHOD_ARG_VALUE_BINARY_OPERATOR so that we prefer using the JDK ${Primitive}BinaryOperator classes, and fall back to the fastutil primitive-BinaryOperators where not present in the JDK.

I ran the junit tests locally and they pass.

Towards #336

vigna commented 3 days ago

Looks good to me. Disambiguation will happen at the interface level, and it should be inlined.

vigna commented 3 days ago

BTW, did you check that your code is actually executed (either by prints or by coverage tools)? The dispatch of that stuff is absolutely devilish...

mhansen commented 2 days ago

Thank you! You're right, I should check this is actually executing. I think I'll write a test with an object that counts how many times it was hashed, asserting it was just hashed once after. I'll just need to be a little careful about rehashing.

vigna commented 2 days ago

You can also just use a coverage tool. Or add a print in the code and make a one-off test, checking that something is printed.

mhansen commented 2 days ago

I've confirmed it's executing. It's actually down from 3 hashes (get, containsKey, put) down to 1. I'm pretty happy to write a test for this; fastutil is a long-term project and it seems worth adding some test to stop this unintentionally regressing in future.

mhansen commented 2 days ago

I think I can add a test in Object2IntOpenHashMapTest.

mhansen commented 2 days ago

PTAL; I've added a test in commit 1, then reduced the allocations in commit 2.