cgal
cgal copied to clipboard
CGAL
Nef_3: Use sizeof(H) in Generic handle map
Summary of Changes
~I believe this is correct, no two addresses can be closer than sizeof(void*) apart, and a handle usually is that size, but if it's bigger then dividing by a smaller size is ok. This helps pack the handles into the hash map more tightly.~
As suggested by @afabri this updates Generic handle map to divide the address of the handle by the size of the pointee. This should provide a better distribution in the hashmap.
Release Management
- Affected package(s): Nef_3, Nef_S2
- Issue(s) solved (if any): performance
- License and copyright ownership: Returned to CGAL authors.
I basically agree but I am wondering if we can go further. Usually we divide by the size of the pointee. @sloriot any idea how to achieve that.
Also, although it does not really matter technically, it is not so much a question of tightness but about a better distribution in the hash map, I think.
I basically agree but I am wondering if we can go further. Usually we divide by the size of the pointee. @sloriot any idea how to achieve that.
Because the map contains generic handles, I think the best you can do is divide by the smallest or you'll have overlapping addresses, but maybe that doesn't matter as it's just a collision? Perhaps the Generic hash map needs to have a Types... parameter and you can find the min/max sizeof at compile time? If you can divide by variable sizes, you can probably just pass that through to the hash functor.
Also, although it does not really matter technically, it is not so much a question of tightness but about a better distribution in the hash map, I think.
Yeah, that's basically what I mean, the table index ( k % table_size) when table_size is 32, will never be odd, if the k is even, meaning only half the buckets will get filled.
I think I understand now why prime numbers are good for the table size.
@afabri The trouble with this approach I think is that the hashmap doesn't check the entries for equality, only the "hashes" of the entries. This works for handle addresses because they are unique (hence Unique_hash_map) but it doesn't work if you divide by the handle size, when the handle sizes differ, because you can get overlapping values.
I basically agree but I am wondering if we can go further. Usually we divide by the size of the pointee. @sloriot any idea how to achieve that.
@afabri So do you approve this PR and it can be integrated as is?
ah I see that https://github.com/CGAL/cgal/pull/6560 replaces it. @GilesBathgate shall we close this PR ?
@sloriot I am unsure about the right approach. I can close this draft if you want but I would rather leave it until the correct solution is merged.