Skip to content

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

@harrisonrodgers

Description

@harrisonrodgers

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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions