-
Notifications
You must be signed in to change notification settings - Fork 98
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
Exponential growth strategy for BitmapIndexed
?!
#387
Labels
Comments
If we don't want to have the unused array slots using up memory and GC-time, we could limit this array growth strategy to certain functions like |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
So far, when we grow the array in a
BitmapIndexed
, we nearly always enhance it by one (the one exception isunion*
). For each of these enhancements, we allocate a fresh array and copy over the elements from the old one.It may be more efficient to grow these array by a factor of 2 or 1.5 instead, avoiding the allocations and copying for some of the enhancements. The unused slots at the end of the array could be marked with
Empty
or a dedicatedPlaceholder
element. Wherever we rely on the length of the array, we could use the popcount of the bitmap instead.Regarding the ideal growth factor, there is some discussion in https://stackoverflow.com/q/1100311/1013393.
The text was updated successfully, but these errors were encountered: