sean-public / fast-skiplist Goto Github PK
View Code? Open in Web Editor NEWA fast, threadsafe skip list in Go
License: MIT License
A fast, threadsafe skip list in Go
License: MIT License
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?
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.
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
......
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:
Lines 154 to 167 in 1de4bd3
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?
Hi, I see a couple possible enhancements in forks with un-PR'd commits:
Back()
) master...JakeCooper:masterpackage 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
}
(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:
Can concurrent modifications ever cause a problem?
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 ?
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.