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

Remove Skip down pointer #13

Open
KyleJHarper opened this issue Feb 24, 2017 · 0 comments
Open

Remove Skip down pointer #13

KyleJHarper opened this issue Feb 24, 2017 · 0 comments
Assignees

Comments

@KyleJHarper
Copy link
Owner

KyleJHarper commented Feb 24, 2017

Consider removing the ->down pointer for skip lists and switching to fixed-size arrays:

L4--------------------------------------------------------->|NULL|
L3------------------------------------------------>| |*|--->|NULL|
L2------------>| |*|------------------------------>| |*|--->|NULL|
L1------------>| |*|--------------------->| |*|--->| |*|--->|NULL|
L0--->|1|*|--->|2|*|--->|3|*|--->|4|*|--->|5|*|--->|6|*|--->|NULL|
        ^_^      ^_^      ^_^      ^_^      ^_^      ^_^    ^____^

The areas denoted by ^_^ are arrays of pointers to further Skiplist Nodes. The left-to-right logic is still in place and works the same. However, when it's time to go "down" we don't use a pointer to the next-lower level. Instead, we have a fixed-size array associated with the node which allows us to go down by simply decrementing the level.

Note: this will fundamentally change how the skiplist is traversed at the physical level, while keeping the logical bits the same (forward and down). The primary concern I have is that my current SkiplistNode struct only requires 32 bytes; if I end up requiring a MAX_LEVELS (32) element array of pointers (8 bytes) PER NODE then we're going to drastically increase the amount of memory our skiplist consumes. This will need to be contrasted with the performance gains from better cache utilization.

My original statement above (about 15 minutes ago) indicated that we would still have the same number of SkiplistNodes in the Skip List; this was misleading. The pipes above |I2| are meant to indicate a single array as pat of a single SkiplistNode that contains that array. (I've updated the ASCII diagram accordingly).

Also of import: if we implement this, we will have to have a node per buffer no matter what, and the slnode will always be the same size so it really just becomes part of the cost of doing business. This means we will no longer need a nearest_neighbor concept which could eliminate a few things.

Update: for reference: http://ticki.github.io/blog/skip-lists-done-right/

For future reference, tyche version 0.0.17 performed as follows:

e.g.:  bin/tyche -m 1500000000 -p /tmp/ram_drive -d 60 -v -D 5 -U 5
U 0  D 0  100% mem:  323 million
U 5  D 0  100% mem:  235 million
U 0  D 5  100% mem:  186 million
U 5  D 5  100% mem:  139 million
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant