-
Notifications
You must be signed in to change notification settings - Fork 271
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
[HashTreeCollections] Remove subtree count augmentation #236
Comments
Note that the CHAMP data structure, as discussed in the OOPSLA '15 paper, does not have sub-tree count augmentation. This can indeed be highly beneficial in terms of reducing memory footprints, depending on the memory alignment of the nodes. See Section 6 of the paper for a performance evaluation on the JVM platform. For In the end it's a trade-off between memory footprint and performance of some operations. |
Node references in persistent collections currently include the count of all items in the corresponding subtree. This makes
index(_:offsetBy:)
an operation with logarithmic complexity, but it wastes a bunch of memory on storing these counts. This is very unlikely to be a worthwhile trade off, as these data structures are unordered, and it seem improbable that someone would want to randomly jump around within them.Remove the count augmentation, to boost memory performance and to make these prefix trees even more competitive in memory use vs the standard
Set
andDictionary
.The text was updated successfully, but these errors were encountered: