README
¶
This is much better than skiplist and slist.
BenchmarkReadWrite/frac_0-8 3000000 537 ns/op
BenchmarkReadWrite/frac_1-8 3000000 503 ns/op
BenchmarkReadWrite/frac_2-8 3000000 492 ns/op
BenchmarkReadWrite/frac_3-8 3000000 475 ns/op
BenchmarkReadWrite/frac_4-8 3000000 440 ns/op
BenchmarkReadWrite/frac_5-8 5000000 442 ns/op
BenchmarkReadWrite/frac_6-8 5000000 380 ns/op
BenchmarkReadWrite/frac_7-8 5000000 338 ns/op
BenchmarkReadWrite/frac_8-8 5000000 294 ns/op
BenchmarkReadWrite/frac_9-8 10000000 268 ns/op
BenchmarkReadWrite/frac_10-8 100000000 26.3 ns/op
And even better than a simple map with read-write lock:
BenchmarkReadWriteMap/frac_0-8 2000000 774 ns/op
BenchmarkReadWriteMap/frac_1-8 2000000 647 ns/op
BenchmarkReadWriteMap/frac_2-8 3000000 605 ns/op
BenchmarkReadWriteMap/frac_3-8 3000000 603 ns/op
BenchmarkReadWriteMap/frac_4-8 3000000 556 ns/op
BenchmarkReadWriteMap/frac_5-8 3000000 472 ns/op
BenchmarkReadWriteMap/frac_6-8 3000000 476 ns/op
BenchmarkReadWriteMap/frac_7-8 3000000 457 ns/op
BenchmarkReadWriteMap/frac_8-8 5000000 444 ns/op
BenchmarkReadWriteMap/frac_9-8 5000000 361 ns/op
BenchmarkReadWriteMap/frac_10-8 10000000 212 ns/op
Node Pooling
Command used
rm -Rf tmp && /usr/bin/time -l ./populate -keys_mil 10
For pprof results, we run without using /usr/bin/time. There are four runs below.
Results seem to vary quite a bit between runs.
Before node pooling
1311.53MB of 1338.69MB total (97.97%)
Dropped 30 nodes (cum <= 6.69MB)
Showing top 10 nodes out of 37 (cum >= 12.50MB)
flat flat% sum% cum cum%
523.04MB 39.07% 39.07% 523.04MB 39.07% github.com/dgraph-io/badger/skl.(*Skiplist).Put
184.51MB 13.78% 52.85% 184.51MB 13.78% runtime.stringtoslicebyte
166.01MB 12.40% 65.25% 689.04MB 51.47% github.com/dgraph-io/badger/mem.(*Table).Put
165MB 12.33% 77.58% 165MB 12.33% runtime.convT2E
116.92MB 8.73% 86.31% 116.92MB 8.73% bytes.makeSlice
62.50MB 4.67% 90.98% 62.50MB 4.67% main.newValue
34.50MB 2.58% 93.56% 34.50MB 2.58% github.com/dgraph-io/badger/table.(*BlockIterator).parseKV
25.50MB 1.90% 95.46% 100.06MB 7.47% github.com/dgraph-io/badger/y.(*MergeIterator).Next
21.06MB 1.57% 97.04% 21.06MB 1.57% github.com/dgraph-io/badger/table.(*Table).read
12.50MB 0.93% 97.97% 12.50MB 0.93% github.com/dgraph-io/badger/table.header.Encode
128.31 real 329.37 user 17.11 sys
3355660288 maximum resident set size
0 average shared memory size
0 average unshared data size
0 average unshared stack size
2203080 page reclaims
764 page faults
0 swaps
275 block input operations
76 block output operations
0 messages sent
0 messages received
0 signals received
49173 voluntary context switches
599922 involuntary context switches
After node pooling
1963.13MB of 2026.09MB total (96.89%)
Dropped 29 nodes (cum <= 10.13MB)
Showing top 10 nodes out of 41 (cum >= 185.62MB)
flat flat% sum% cum cum%
658.05MB 32.48% 32.48% 658.05MB 32.48% github.com/dgraph-io/badger/skl.glob..func1
297.51MB 14.68% 47.16% 297.51MB 14.68% runtime.convT2E
257.51MB 12.71% 59.87% 257.51MB 12.71% runtime.stringtoslicebyte
249.01MB 12.29% 72.16% 1007.06MB 49.70% github.com/dgraph-io/badger/mem.(*Table).Put
142.43MB 7.03% 79.19% 142.43MB 7.03% bytes.makeSlice
100MB 4.94% 84.13% 758.05MB 37.41% github.com/dgraph-io/badger/skl.newNode
99.50MB 4.91% 89.04% 99.50MB 4.91% main.newValue
75MB 3.70% 92.74% 75MB 3.70% github.com/dgraph-io/badger/table.(*BlockIterator).parseKV
44.62MB 2.20% 94.94% 44.62MB 2.20% github.com/dgraph-io/badger/table.(*Table).read
39.50MB 1.95% 96.89% 185.62MB 9.16% github.com/dgraph-io/badger/y.(*MergeIterator).Next
135.58 real 374.29 user 17.65 sys
3740614656 maximum resident set size
0 average shared memory size
0 average unshared data size
0 average unshared stack size
2276566 page reclaims
770 page faults
0 swaps
128 block input operations
90 block output operations
0 messages sent
0 messages received
0 signals received
46434 voluntary context switches
597049 involuntary context switches
Documentation
¶
Index ¶
- Constants
- type Arena
- type Builder
- type Iterator
- func (s *Iterator) Close() error
- func (s *Iterator) Key() []byte
- func (s *Iterator) Next()
- func (s *Iterator) Prev()
- func (s *Iterator) Seek(target []byte)
- func (s *Iterator) SeekForPrev(target []byte)
- func (s *Iterator) SeekToFirst()
- func (s *Iterator) SeekToLast()
- func (s *Iterator) Valid() bool
- func (s *Iterator) Value() y.ValueStruct
- func (s *Iterator) ValueUint64() uint64
- type Skiplist
- func (s *Skiplist) DecrRef()
- func (s *Skiplist) Empty() bool
- func (s *Skiplist) Get(key []byte) y.ValueStruct
- func (s *Skiplist) IncrRef()
- func (s *Skiplist) MemSize() int64
- func (s *Skiplist) NewIterator() *Iterator
- func (s *Skiplist) NewUniIterator(reversed bool) *UniIterator
- func (s *Skiplist) Put(key []byte, v y.ValueStruct)
- type UniIterator
Constants ¶
const MaxNodeSize = int(unsafe.Sizeof(node{}))
MaxNodeSize is the memory footprint of a node of maximum height.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Arena ¶
type Arena struct {
// contains filtered or unexported fields
}
Arena should be lock-free.
type Builder ¶
type Builder struct {
// contains filtered or unexported fields
}
Builder can be used to efficiently create a skiplist given that the keys are known to be in a sorted order.
func NewBuilder ¶
type Iterator ¶
type Iterator struct {
// contains filtered or unexported fields
}
Iterator is an iterator over skiplist object. For new objects, you just need to initialize Iterator.list.
func (*Iterator) SeekForPrev ¶
SeekForPrev finds an entry with key <= target.
func (*Iterator) SeekToFirst ¶
func (s *Iterator) SeekToFirst()
SeekToFirst seeks position at the first entry in list. Final state of iterator is Valid() iff list is not empty.
func (*Iterator) SeekToLast ¶
func (s *Iterator) SeekToLast()
SeekToLast seeks position at the last entry in list. Final state of iterator is Valid() iff list is not empty.
func (*Iterator) ValueUint64 ¶
ValueUint64 returns the uint64 value of the current node.
type Skiplist ¶
type Skiplist struct {
OnClose func()
// contains filtered or unexported fields
}
func NewGrowingSkiplist ¶
NewGrowingSkiplist returns a new skiplist which can grow. Note that this skiplist is not thread safe and must be used for serial operations only.
func NewSkiplist ¶
NewSkiplist makes a new empty skiplist, with a given arena size
func (*Skiplist) DecrRef ¶
func (s *Skiplist) DecrRef()
DecrRef decrements the refcount, deallocating the Skiplist when done using it
func (*Skiplist) Get ¶
func (s *Skiplist) Get(key []byte) y.ValueStruct
Get gets the value associated with the key. It returns a valid value if it finds equal or earlier version of the same key.
func (*Skiplist) MemSize ¶
MemSize returns the size of the Skiplist in terms of how much memory is used within its internal arena.
func (*Skiplist) NewIterator ¶
NewIterator returns a skiplist iterator. You have to Close() the iterator.
func (*Skiplist) NewUniIterator ¶
func (s *Skiplist) NewUniIterator(reversed bool) *UniIterator
NewUniIterator returns a UniIterator.
type UniIterator ¶
type UniIterator struct {
// contains filtered or unexported fields
}
UniIterator is a unidirectional memtable iterator. It is a thin wrapper around Iterator. We like to keep Iterator as before, because it is more powerful and we might support bidirectional iterators in the future.
func (*UniIterator) Close ¶
func (s *UniIterator) Close() error
Close implements y.Interface (and frees up the iter's resources)
func (*UniIterator) Value ¶
func (s *UniIterator) Value() y.ValueStruct
Value implements y.Interface
Source Files