Skip to content

Split hash buckets from the unique node table values #4

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.

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

Open
SSoelvsten opened this issue Sep 9, 2021 · 0 comments
Open

Split hash buckets from the unique node table values #4

SSoelvsten opened this issue Sep 9, 2021 · 0 comments
Labels
enhancement New feature or request

Comments

@SSoelvsten
Copy link
Owner

SSoelvsten commented Sep 9, 2021

As far as I can tell the hash value in each node really is just a separate array for all buckets. Assuming it really is only used in bdd_makenode then we should be able to get the following new properties by splitting it.

  • This decreases the node struct size to be only 20 bytes, which may improve cache locality (though it still does not nicely fit into a 64 byte cache line). Combining this change with Change nodetable and cache indexing from int to ssize_t  #3 we get a node size of 32 bytes, which fits perfectly with the cache line.
    • Recursing through the BDD may run faster this way due to better cache behaviour.
    • One can hope that a lookup of the hash bucket leads to fewer nodes being thrown out of the cache, since merely another cache line with a hash value is thrown out instead. I find it unlikely, but maybe the cache behaviour of the hash function improves.
  • This allows the node table to not have to be a prime number in size and so make use of the entire addressable space.
@SSoelvsten SSoelvsten added the enhancement New feature or request label Sep 9, 2021
@SSoelvsten SSoelvsten changed the title Split 'hash' from Split hash buckets from the unique node table values Sep 9, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant