skl

package
v1.4.0 Latest Latest
Warning

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

 Go to latest Published: May 2, 2018 License: Apache-2.0 Imports: 5 Imported by: 75

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

View Source 
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 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

Close frees the resources held by the iterator

func (*Iterator) Key 

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

Key returns the key at the current position.

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
}

Skiplist maps keys to values (in memory)

func NewSkiplist 

func NewSkiplist(arenaSize int64) *Skiplist

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

func (s *Skiplist) Empty() bool

Empty returns if the Skiplist is empty.

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

func (s *Skiplist) IncrRef()

IncrRef increases the refcount

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

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.

func (*Skiplist) Put 

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

Put inserts the key-value pair.

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

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

Key implements y.Interface

func (*UniIterator) Next 

func (s *UniIterator) Next()

Next implements y.Interface

func (*UniIterator) Rewind 

func (s *UniIterator) Rewind()

Rewind implements y.Interface

func (*UniIterator) Seek 

func (s *UniIterator) Seek(key []byte)

Seek implements y.Interface

func (*UniIterator) Valid 

func (s *UniIterator) Valid() bool

Valid implements y.Interface

func (*UniIterator) Value 

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

Value implements y.Interface

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.