sean-public/fast-skiplist

A fast, threadsafe skip list in Go

fast-skiplist's Issues

How to get Element.value?

Unless I'm incorrect, there's no way to get an Element's value from an external package as value is a package private field.

Should key and value be Key and Value respectively?

Rare panic for high loads

Golang 1.12.9 linux/amd64
Single thread application
Calling code is something like:

list := skiplist.NewWithMaxLevel(4)
....
// playaround with ~4k of elements
....
element := list.Front()
value := element.Value()

Gets a panic:

panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x1 addr=0x20 pc=0x4e291b]
goroutine 553 [running]:
github.com/sean-public/fast-skiplist.(*Element).Value(...)
        /home/user/go/pkg/mod/github.com/sean-public/[email protected]/type.go:25
......

Help Needed - Optimistic Locking

I also have one doubt . It is saying in comments

// Set inserts a value in the list with the specified key, ordered by the key.
// If the key exists, it updates the value in the existing node.
// Returns a pointer to the new element.
// Locking is optimistic and happens only after searching.

But First line of function is

func (list *SkipList) Set(key float64, value interface{}) *Element {
	list.mutex.Lock()
	defer list.mutex.Unlock()

        // ----
}

which looks like lock during entire function ,

Can u pls help me understand ?

Question about locking claims in readme

(sorry for opening so many issues recently)

After seeing the code, I don't understand the locking claims in the first paragraph of this section of the readme.

These immediately lock:

• Set
• Get
• Remove

SetMaxLevel can alter existing data?

The docs claim that it doesn't.

In the function's code, downsizing "truncates" (eventually GC'd/overwritten?) and upsizing moves/copies, invalidating pointers when iterating over elements?

How does this compare to Go's map?

Unnecessary lock? and other changes in forks

Hi, I see a couple possible enhancements in forks with un-PR'd commits:

• (see "remove locking") master...pilosa:master
• (Back()) master...JakeCooper:master

skiplist created with NewWithMaxLevel(19+) panics on Set

panic: runtime error: index out of range

goroutine 1 [running]:
github.com/sean-public/fast-skiplist.(*SkipList).getPrevElementNodes(0xc42006e120, 0x0, 0xc42006e178, 0xc420067500, 0x7f793c60f000)
        /home/user/go/src/github.com/sean-public/fast-skiplist/skiplist.go:109 +0xd9
github.com/sean-public/fast-skiplist.(*SkipList).Set(0xc42006e120, 0x0, 0x468de0, 0x4de9b0, 0x0)
        /home/user/go/src/github.com/sean-public/fast-skiplist/skiplist.go:28 +0x8a
main.main()
        /home/user/test.go:5 +0x59
exit status 2

The code (test.go):

package main
import "github.com/sean-public/fast-skiplist"
func main(){
  s := skiplist.NewWithMaxLevel(19)
  s.Set(0, struct{}{}) // line 5
}

DefaultMaxLevel (18) is used instead of MaxLevel in lines 160, 161, and 165:

fast-skiplist/skiplist.go

Lines 154 to 167 in 1de4bd3

	func NewWithMaxLevel(maxLevel int) *SkipList {
	if maxLevel < 1 || maxLevel > 64 {
	panic("maxLevel for a SkipList must be a positive integer <= 64")
	}
	return &SkipList{
	elementNode: elementNode{next: make([]*Element, DefaultMaxLevel)},
	prevNodesCache: make([]*elementNode, DefaultMaxLevel),
	maxLevel: maxLevel,
	randSource: rand.New(rand.NewSource(time.Now().UnixNano())),
	probability: DefaultProbability,
	probTable: probabilityTable(DefaultProbability, DefaultMaxLevel),
	}
	}

Not threadsafe

There are a number of race conditions in this library, for example getPrevElementNodes is called without a lock, and it reads the value of list.maxLevel which could be concurrently set by list.SetMaxLevel (again without locking).

It may be worth considering removing the lock entirely and simply not advertising the library as threadsafe - or at least having a separate version of it. I imagine that true threadsafety will come at a significant performance penalty.

What are the guarantees when iterating with Front() and Next()?

Can concurrent modifications ever cause a problem?

i hava a test to show. skiplist is not fast!

package main

import (
"bytes"
"encoding/gob"
"io/ioutil"
"log"
"os"
"testing"

pqueuekey "github.com/474420502/focus/priority_queuekey"
skiplist "github.com/sean-public/fast-skiplist"

"github.com/474420502/focus/compare"
"github.com/Pallinder/go-randomdata"

)

// TestCreateData Before Benchmark, Execute the func for test
func TestCreateData(t *testing.T) {

f, err := os.OpenFile("l.log", os.O_CREATE|os.O_TRUNC|os.O_WRONLY, 0666)
if err != nil {
	log.Println(err)
}

var l []int

m := make(map[int]int)
for i := 0; len(l) < CompartorSize; i++ {
	v := randomdata.Number(0, NumberMax)
	if _, ok := m[v]; !ok {
		m[v] = v
		l = append(l, v)
	}
}

var result bytes.Buffer
encoder := gob.NewEncoder(&result)
encoder.Encode(l)
lbytes := result.Bytes()
f.Write(lbytes)

}

// BenchmarkSkiplist skiplist Benchmark
func BenchmarkSkiplist(b *testing.B) {

l := loadTestData()
execCount := 5
b.N = len(l) * execCount

var temp []float64
for _, v := range l {
	temp = append(temp, float64(v))
}

b.ResetTimer()
b.StartTimer()

for i := 0; i < execCount; i++ {
	pq := skiplist.New()
	for _, v := range temp {
		pq.Set(v, v)
	}
}

}

// BenchmarkPriorityQueue like skiplist tree
func BenchmarkPriorityQueue(b *testing.B) {

l := loadTestData()
execCount := 5
b.N = len(l) * execCount

b.ResetTimer()
b.StartTimer()

for i := 0; i < execCount; i++ {
	pq := pqueuekey.New(compare.Int)
	for _, v := range l {
		pq.Push(v, v)
	}
}

}

const CompartorSize = 1000000
const NumberMax = 50000000

func loadTestData() []int {
data, err := ioutil.ReadFile("./l.log")
if err != nil {
log.Println(err)
}
var l []int
decoder := gob.NewDecoder(bytes.NewReader(data))
decoder.Decode(&l)
return l
}