You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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
smaller than log2(range) then the logarithmic nature of the skiplist is not maintained
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.
The text was updated successfully, but these errors were encountered:
harrisonrodgers
changed the title
Java skiplists maxLevel/maxHeight should not be static.
Java skiplists maxLevel/maxHeight should not be hardcoded.
Feb 8, 2017
Overview:
Most algorithms such as
SequentialSkipListIntSet
,CompositionalSkipListIntSet
,TransactionalPughSkipListSet
, andLazySkipList
, 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
log2(range)
then the logarithmic nature of the skiplist is not maintainedSolution:
Update
src/contention/benchmark/Test.java
to create the skiplists with parameterlog2(range)
, thus allowing the skiplists to use an appropriate maxLevel/maxHeight for the benchmark.The text was updated successfully, but these errors were encountered: