DeleteVersion is quite slow

[ethanfrey]

While reworking the tests for #25, I decided to replicate the proper orphan cleanup. That is, after SaveVersion(version+1), I also call DeleteVersion(version-1).

Here are the rough results from local benchmarks, without DeleteVersion (no cleanup):

$ go test -bench=Medium -v
Init Tree took 96.26 MB
goos: linux
goarch: amd64
pkg: github.com/tendermint/iavl/benchmarks
BenchmarkMedium/memdb-100000-100-16-40/query-miss-8         	  300000	      5078 ns/op
BenchmarkMedium/memdb-100000-100-16-40/query-hits-8         	  300000	      5900 ns/op
BenchmarkMedium/memdb-100000-100-16-40/update-8             	   20000	     75020 ns/op
BenchmarkMedium/memdb-100000-100-16-40/block-8              	     200	   9160188 ns/op
Init Tree took 57.27 MB

And with DeleteVersion (as we use it min the sdk):

$ go test -bench=Medium -v
Init Tree took 96.25 MB
goos: linux
goarch: amd64
pkg: github.com/tendermint/iavl/benchmarks
BenchmarkMedium/memdb-100000-100-16-40/query-miss-8         	  200000	      5149 ns/op
BenchmarkMedium/memdb-100000-100-16-40/query-hits-8         	  300000	      5980 ns/op
BenchmarkMedium/memdb-100000-100-16-40/update-8             	   10000	    286915 ns/op
BenchmarkMedium/memdb-100000-100-16-40/block-8              	      50	  29462219 ns/op

context:
times for update is each call to update, committing to "disk"/"memdb" every 100 updates
time for block is the total time to call query/set on 100 different keys.
all of this is done with a db prep-populated with 100k key/value pairs
(the code is <dbtype>-<initial size>-<block size>-<key bytes>-<value bytes>)

We can see that adding the DeleteVersion cleanup triples the time.

I would show numbers for goleveldb, except that it crashes.... #27

[ethanfrey]

Pushed a new branch, which seems slower for memdb, but faster for goleveldb:

benchmarks:

$ go test -bench=Medium
Init Tree took 96.26 MB
goos: linux
goarch: amd64
pkg: github.com/tendermint/iavl/benchmarks
BenchmarkMedium/memdb-100000-100-16-40/query-miss-8         	  200000	      5887 ns/op
BenchmarkMedium/memdb-100000-100-16-40/query-hits-8         	  200000	      5998 ns/op
BenchmarkMedium/memdb-100000-100-16-40/update-8             	   10000	    308516 ns/op
BenchmarkMedium/memdb-100000-100-16-40/block-8              	      50	  30842091 ns/op
Init Tree took 47.10 MB
BenchmarkMedium/goleveldb-100000-100-16-40/query-miss-8     	  100000	     12957 ns/op
BenchmarkMedium/goleveldb-100000-100-16-40/query-hits-8     	  100000	     16911 ns/op
BenchmarkMedium/goleveldb-100000-100-16-40/update-8         	   10000	    355552 ns/op
BenchmarkMedium/goleveldb-100000-100-16-40/block-8          	      50	  37910863 ns/op
Init Tree took 40.12 MB
BenchmarkMedium/leveldb-100000-100-16-40/query-miss-8       	  100000	     12551 ns/op
BenchmarkMedium/leveldb-100000-100-16-40/query-hits-8       	  100000	     16016 ns/op
BenchmarkMedium/leveldb-100000-100-16-40/update-8           	   10000	    338798 ns/op
BenchmarkMedium/leveldb-100000-100-16-40/block-8            	      50	  36501120 ns/op
PASS
ok  	github.com/tendermint/iavl/benchmarks	33.513s

sdk2-benchmarks:

$ go test -bench=Medium
Init Tree took 96.28 MB
goos: linux
goarch: amd64
pkg: github.com/tendermint/iavl/benchmarks
BenchmarkMedium/memdb-100000-100-16-40/query-miss-8         	  200000	      5638 ns/op
BenchmarkMedium/memdb-100000-100-16-40/query-hits-8         	  300000	      5928 ns/op
BenchmarkMedium/memdb-100000-100-16-40/update-8             	   10000	    384650 ns/op
BenchmarkMedium/memdb-100000-100-16-40/block-8              	      50	  39598483 ns/op
Init Tree took 46.90 MB
BenchmarkMedium/goleveldb-100000-100-16-40/query-miss-8     	  100000	     12671 ns/op
BenchmarkMedium/goleveldb-100000-100-16-40/query-hits-8     	  100000	     16332 ns/op
BenchmarkMedium/goleveldb-100000-100-16-40/update-8         	   10000	    178337 ns/op
BenchmarkMedium/goleveldb-100000-100-16-40/block-8          	     100	  20896586 ns/op
Init Tree took 36.58 MB
BenchmarkMedium/leveldb-100000-100-16-40/query-miss-8       	  100000	     12159 ns/op
BenchmarkMedium/leveldb-100000-100-16-40/query-hits-8       	  100000	     15502 ns/op
BenchmarkMedium/leveldb-100000-100-16-40/update-8           	   10000	    182112 ns/op
BenchmarkMedium/leveldb-100000-100-16-40/block-8            	     100	  21171320 ns/op
PASS
ok  	github.com/tendermint/iavl/benchmarks	32.408s

[ethanfrey]

Notes on history size...

Keep last 20 blocks:

$ go test -bench=Medium
Init Tree took 96.26 MB
goos: linux
goarch: amd64
pkg: github.com/tendermint/iavl/benchmarks
BenchmarkMedium/memdb-100000-100-16-40/query-miss-8         	  200000	      6164 ns/op
BenchmarkMedium/memdb-100000-100-16-40/query-hits-8         	  200000	      6866 ns/op
BenchmarkMedium/memdb-100000-100-16-40/update-8             	   10000	    400962 ns/op
BenchmarkMedium/memdb-100000-100-16-40/block-8              	      30	  49236804 ns/op
Init Tree took 46.78 MB
BenchmarkMedium/goleveldb-100000-100-16-40/query-miss-8     	  100000	     13312 ns/op
BenchmarkMedium/goleveldb-100000-100-16-40/query-hits-8     	  100000	     17522 ns/op
BenchmarkMedium/goleveldb-100000-100-16-40/update-8         	   10000	    208349 ns/op
BenchmarkMedium/goleveldb-100000-100-16-40/block-8          	     100	  25177730 ns/op
Init Tree took 38.86 MB
BenchmarkMedium/leveldb-100000-100-16-40/query-miss-8       	  100000	     13604 ns/op
BenchmarkMedium/leveldb-100000-100-16-40/query-hits-8       	  100000	     16315 ns/op
BenchmarkMedium/leveldb-100000-100-16-40/update-8           	   10000	    199900 ns/op
BenchmarkMedium/leveldb-100000-100-16-40/block-8            	     100	  25245517 ns/op
PASS
ok  	github.com/tendermint/iavl/benchmarks	32.959s

with history 100 (no cleanup over benchmark size):

$ go test -bench=Medium
Init Tree took 96.25 MB
goos: linux
goarch: amd64
pkg: github.com/tendermint/iavl/benchmarks
BenchmarkMedium/memdb-100000-100-16-40/query-miss-8         	  200000	      5496 ns/op
BenchmarkMedium/memdb-100000-100-16-40/query-hits-8         	  300000	      6336 ns/op
BenchmarkMedium/memdb-100000-100-16-40/update-8             	   20000	    760748 ns/op
BenchmarkMedium/memdb-100000-100-16-40/block-8              	      20	  72912023 ns/op
Init Tree took 46.96 MB
BenchmarkMedium/goleveldb-100000-100-16-40/query-miss-8     	  100000	     12529 ns/op
BenchmarkMedium/goleveldb-100000-100-16-40/query-hits-8     	  100000	     15921 ns/op
BenchmarkMedium/goleveldb-100000-100-16-40/update-8         	   10000	    143865 ns/op
BenchmarkMedium/goleveldb-100000-100-16-40/block-8          	     100	  28876857 ns/op
Init Tree took 36.96 MB
BenchmarkMedium/leveldb-100000-100-16-40/query-miss-8       	  100000	     12281 ns/op
BenchmarkMedium/leveldb-100000-100-16-40/query-hits-8       	  100000	     15568 ns/op
BenchmarkMedium/leveldb-100000-100-16-40/update-8           	   10000	    140960 ns/op
BenchmarkMedium/leveldb-100000-100-16-40/block-8            	      50	  27649330 ns/op
PASS
ok  	github.com/tendermint/iavl/benchmarks	43.172s

[jaekwon]

Did you compile with build tag +gcc? Looks like leveldb may be using goleveldb since it didn't find cleveldb? (Just guessing based on number similarity between goleveldb and leveldb metrics)