skl

package
v0.0.0-...-f407625 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Sep 5, 2017 License: Apache-2.0 Imports: 7 Imported by: 0

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

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 NewArena 

func NewArena(n int64) *Arena

NewArena returns a new arena.

func (*Arena) GetKey 

func (s *Arena) GetKey(offset uint32, size uint16) []byte

GetKey returns byte slice at offset.

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) PutKey 

func (s *Arena) PutKey(key []byte) uint32

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.

func (*Arena) Reset 

func (s *Arena) Reset()

func (*Arena) Size 

func (s *Arena) Size() int64

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) Close 

func (s *Iterator) Close() error

func (*Iterator) Key 

func (s *Iterator) Key() []byte

Key returns the key at the current position.

func (*Iterator) Name 

func (s *Iterator) Name() string

func (*Iterator) Next 

func (s *Iterator) Next()

Next advances to the next position.

func (*Iterator) Prev 

func (s *Iterator) Prev()

Prev advances to the previous position.

func (*Iterator) Seek 

func (s *Iterator) Seek(target []byte)

Seek advances to the first entry with a key >= target.

func (*Iterator) SeekForPrev 

func (s *Iterator) SeekForPrev(target []byte)

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) Valid 

func (s *Iterator) Valid() bool

Valid returns true iff the iterator is positioned at a valid node.

func (*Iterator) Value 

func (s *Iterator) Value() y.ValueStruct

Value returns value.

type Skiplist 

type Skiplist struct {
	// contains filtered or unexported fields
}

func NewSkiplist 

func NewSkiplist(arenaSize int64) *Skiplist

func (*Skiplist) DecrRef 

func (s *Skiplist) DecrRef()

func (*Skiplist) Empty 

func (s *Skiplist) Empty() bool

Empty returns if the Skiplist is empty.

func (*Skiplist) Get 

func (s *Skiplist) Get(key []byte) y.ValueStruct

func (*Skiplist) Height 

func (s *Skiplist) Height() int32

func (*Skiplist) IncrRef 

func (s *Skiplist) IncrRef()

func (*Skiplist) MemSize 

func (s *Skiplist) MemSize() int64

MemSize returns the size of the Skiplist in terms of how much memory is used within its internal arena.

func (*Skiplist) NewIterator 

func (s *Skiplist) NewIterator() *Iterator

func (*Skiplist) NewUniIterator 

func (s *Skiplist) NewUniIterator(reversed bool) *UniIterator

func (*Skiplist) Put 

func (s *Skiplist) Put(key []byte, v y.ValueStruct)

Put inserts the key-value pair.

func (*Skiplist) Valid 

func (s *Skiplist) Valid() bool

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

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.