godotengine
[Core] Optimize `OAHashMap`
Similar to #90082 and #90126.
Benchmarks OAHashMap<int, int>
| Elements | Time insert before(usec) | Time insert after(usec) |
|---|---|---|
| 5 | 4 | 0 |
| 25 | 0 | 0 |
| 125 | 8 | 4 |
| 625 | 42 | 15 |
| 3125 | 261 | 116 |
| 15625 | 1781 | 565 |
| 78125 | 8986 | 2711 |
| 390625 | 41887 | 20942 |
| 1953125 | 303047 | 108786 |
| 9765625 | 1560636 | 637230 |
| Elements | Time find before(nsec) | Time find after(nsec) |
|---|---|---|
| 10 | 304 | 368 |
| 50 | 727 | 647 |
| 250 | 3472 | 2605 |
| 1250 | 21905 | 15523 |
| 6250 | 143600 | 50483 |
| 31250 | 424157 | 300460 |
| 156250 | 2790448 | 1940480 |
| 781250 | 22462356 | 12027047 |
| 3906250 | 109030704 | 82341888 |
| 19531250 | 757996928 | 530154176 |
Are there any reasons why @Geometror didn't implement fastmod here? And can I add it here?
I'd suspect because this is largely a legacy class a far as I recall
Yeah, I think @AThousandShips is right, this is a legacy class. I think there might be some specific cases where it could be more performant than HashMap, but to be sure we should run some benchmarks (AStar and certain geometric operations use it). If I remember correctly we wanted to remove it at some point.
This data structure looks much better for trivial types than the standard one. We don't use extra 3 pointers that weigh 24 bytes in total, and we don't use extra system calls to allocate memory. It is also better friends with the cache.
Tested the regular and OA maps from the master branch. Time inserting HashMap: 114961 Time inserting OAHashMap: 141894
Time inserting HashMap: 111946 Time inserting OAHashMap: 140684
Time find HashMap: 54432136 nanosec Time find OAHashMap: 51467400 nanosec
The insertion is much worse because MAX_OCCUPANCY in hash_map is 0.75, and here it is 0.9.
It has the disadvantage that if the key and the pair weigh a lot, the insertion will be longer, because of SWAP(key, keys[pos]); SWAP(value, values[pos]);. But this can be fixed by setting MAX_OCCUPANCY to 0.65 for fewer hash collisions.
Your current changes have broken the function of the map somehow, as seen in a case where it's used and now not working
Maybe because I didn't do a rebase with master
That wouldn't cause that, it worked prior to your new changes
Edit: and indeed it's still broken
Yes. I thought so because I did tests locally and they passed. This is most likely due to the refactoring commit that I squashed.