README
¶
This is much better than skiplist and slist.
BenchmarkReadWrite/frac_0-4 1000000 1516 ns/op
BenchmarkReadWrite/frac_1-4 1000000 1456 ns/op
BenchmarkReadWrite/frac_2-4 1000000 1354 ns/op
BenchmarkReadWrite/frac_3-4 1000000 1295 ns/op
BenchmarkReadWrite/frac_4-4 1000000 1142 ns/op
BenchmarkReadWrite/frac_5-4 1000000 1077 ns/op
BenchmarkReadWrite/frac_6-4 1000000 1003 ns/op
BenchmarkReadWrite/frac_7-4 2000000 1054 ns/op
BenchmarkReadWrite/frac_8-4 2000000 929 ns/op
BenchmarkReadWrite/frac_9-4 3000000 815 ns/op
BenchmarkReadWrite/frac_10-4 5000000 472 ns/op
But compared to a simple map with read-write lock, it is still slower.
BenchmarkReadWriteMap/frac_0-4 2000000 883 ns/op
BenchmarkReadWriteMap/frac_1-4 2000000 830 ns/op
BenchmarkReadWriteMap/frac_2-4 2000000 658 ns/op
BenchmarkReadWriteMap/frac_3-4 2000000 662 ns/op
BenchmarkReadWriteMap/frac_4-4 2000000 657 ns/op
BenchmarkReadWriteMap/frac_5-4 2000000 650 ns/op
BenchmarkReadWriteMap/frac_6-4 3000000 592 ns/op
BenchmarkReadWriteMap/frac_7-4 3000000 573 ns/op
BenchmarkReadWriteMap/frac_8-4 3000000 539 ns/op
BenchmarkReadWriteMap/frac_9-4 3000000 521 ns/op
BenchmarkReadWriteMap/frac_10-4 3000000 479 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 ¶
- type Arena
- type Iterator
- func (s *Iterator) Close() error
- func (s *Iterator) Key() []byte
- func (s *Iterator) Name() string
- 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
- type Skiplist
- func (s *Skiplist) DecrRef()
- func (s *Skiplist) Empty() bool
- func (s *Skiplist) Get(key []byte) y.ValueStruct
- func (s *Skiplist) Height() int32
- 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)
- func (s *Skiplist) Valid() bool
- type UniIterator
Constants ¶
This section is empty.
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.
func (*Arena) GetVal ¶
func (s *Arena) GetVal(offset uint32, size uint16) (ret y.ValueStruct)
GetVal returns byte slice at offset. The given size should be just the value size and should NOT include the meta bytes.
func (*Arena) PutVal ¶
func (s *Arena) PutVal(v y.ValueStruct) uint32
Put will *copy* val into arena. To make better use of this, reuse your input val buffer. Returns an offset into buf. User is responsible for remembering size of val. We could also store this size inside arena but the encoding and decoding will incur some overhead.
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.
type Skiplist ¶
type Skiplist struct {
// contains filtered or unexported fields
}
func NewSkiplist ¶
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 ¶
func (*Skiplist) NewUniIterator ¶
func (s *Skiplist) NewUniIterator(reversed bool) *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
func (*UniIterator) Key ¶
func (s *UniIterator) Key() []byte
func (*UniIterator) Name ¶
func (s *UniIterator) Name() string
func (*UniIterator) Next ¶
func (s *UniIterator) Next()
func (*UniIterator) Rewind ¶
func (s *UniIterator) Rewind()
func (*UniIterator) Seek ¶
func (s *UniIterator) Seek(key []byte)
func (*UniIterator) Valid ¶
func (s *UniIterator) Valid() bool
func (*UniIterator) Value ¶
func (s *UniIterator) Value() y.ValueStruct
Source Files
Click to show internal directories.
Click to hide internal directories.