Skip to content
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

Java skiplists maxLevel/maxHeight should not be hardcoded. #21

Open
harrisonrodgers opened this issue Feb 8, 2017 · 0 comments
Open

Comments

@harrisonrodgers
Copy link
Contributor

Overview:

Most algorithms such as SequentialSkipListIntSet, CompositionalSkipListIntSet, TransactionalPughSkipListSet, and LazySkipList, currently use a hardcoded maxLevel/maxHeight.

Some algorithms like the NonBlockingFriendlySkipListMap have maintenance code to increase the level/height of the structure. Or are implemented using nodes for each level/height which are linked up and down, instead of pseudo-nodes.

Problem:

If the hardcoded maxLevel/maxHeight is

  1. smaller than log2(range) then the logarithmic nature of the skiplist is not maintained
  2. too large then structures which use an array of next pointers in their nodes are making their nodes unnecessarily large

Solution:

Update src/contention/benchmark/Test.java to create the skiplists with parameter log2(range), thus allowing the skiplists to use an appropriate maxLevel/maxHeight for the benchmark.

@harrisonrodgers harrisonrodgers changed the title Java skiplists maxLevel/maxHeight should not be static. Java skiplists maxLevel/maxHeight should not be hardcoded. Feb 8, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant