3 ms·

Tangential - the skip list example seems different from how I learned them in data structures. Wouldn't a better skip list have "down pointers" at each node so

Tangential - the skip list example seems different from how I learned them in data structures. Wouldn't a better skip list have "down pointers" at each node so you don't have to retrace your work at each layer?

bob1029 5y ago
> Wouldn't a better skip list have "down pointers" at each node so you don't have to retrace your work at each layer? You don't have to retrace your work, per this example on 5 you could imagine there being implicit "down" pointers in that aggregate block, so you would go from L3 straight down to the data item once you hit that first logical element. This would be 2 I/O operations in my implementations. Think: public class SkipListNode { public SkipListNode? Layer3; public SkipListNode? Layer2; public SkipListNode? Layer1; public SkipListNode Layer0; } Once you find the one that has all 4 non-null, you can just grab the item at Layer0 without anymore searching.
- ntonozzi 5y ago
  I discussed this method a little more in a blog post (https://blog.twitter.com/engineering/en_us/topics/infrastructure/2020/reducing-search-indexing-latency-to-one-second https://blog.twitter.com/engineering/en_us/topics/infrastruc...), if you are trying to get an intuition here: > we only allocate one pointer for every level of the skip list. In a typical skip list, a node will have a value, a pointer to the next largest element in the list and a pointer to the lower level of the skip list. This means that a new value allocated into the second level will require the space for two values and four pointers. We avoid this by always allocating skip list towers contiguously. Each level K pointer will only point to other level K pointers, so to extract the value associated with a level K pointer P, you read the value at P - K. Once you reach a node with a value greater than the one you are searching for, you go back to the previous node, and descend a level by simply subtracting one from the pointer. This lets us allocate a value into the second level by just consuming the space for the value and two pointers. It also reduces the amount of time we need to spend chasing pointers, because a pointer into a tower is likely to be on the same cache line as the lower pointers in that tower.
dreamcompiler 5y ago
Skip lists are typically implemented with a short array of pointers at each node. When traversing a skip list in a loop the previous node is in a local variable. If you do it recursively the previous node is on the stack. "Retracing" is simply a matter of retrieving the previous node and adding 1 to the pointer array index.
jamesbriggs 5y ago
Yes your explanation is correct, if it hits an end block or overshoot the target it returns to the previous block in the next layer (not the start block), I submitted a change to the article and visual to make this clear - should be updated soon. Thanks for pointing it out!

bob1029 5y ago

> Wouldn't a better skip list have "down pointers" at each node so you don't have to retrace your work at each layer? You don't have to retrace your work, per this example on 5 you could imagine there being implicit "down" pointers in that aggregate block, so you would go from L3 straight down to the data item once you hit that first logical element. This would be 2 I/O operations in my implementations. Think: public class SkipListNode { public SkipListNode? Layer3; public SkipListNode? Layer2; public SkipListNode? Layer1; public SkipListNode Layer0; } Once you find the one that has all 4 non-null, you can just grab the item at Layer0 without anymore searching.

ntonozzi 5y ago
I discussed this method a little more in a blog post (https://blog.twitter.com/engineering/en_us/topics/infrastructure/2020/reducing-search-indexing-latency-to-one-second https://blog.twitter.com/engineering/en_us/topics/infrastruc...), if you are trying to get an intuition here: > we only allocate one pointer for every level of the skip list. In a typical skip list, a node will have a value, a pointer to the next largest element in the list and a pointer to the lower level of the skip list. This means that a new value allocated into the second level will require the space for two values and four pointers. We avoid this by always allocating skip list towers contiguously. Each level K pointer will only point to other level K pointers, so to extract the value associated with a level K pointer P, you read the value at P - K. Once you reach a node with a value greater than the one you are searching for, you go back to the previous node, and descend a level by simply subtracting one from the pointer. This lets us allocate a value into the second level by just consuming the space for the value and two pointers. It also reduces the amount of time we need to spend chasing pointers, because a pointer into a tower is likely to be on the same cache line as the lower pointers in that tower.

dreamcompiler 5y ago

Skip lists are typically implemented with a short array of pointers at each node. When traversing a skip list in a loop the previous node is in a local variable. If you do it recursively the previous node is on the stack. "Retracing" is simply a matter of retrieving the previous node and adding 1 to the pointer array index.

jamesbriggs 5y ago

Yes your explanation is correct, if it hits an end block or overshoot the target it returns to the previous block in the next layer (not the start block), I submitted a change to the article and visual to make this clear - should be updated soon. Thanks for pointing it out!