Create a lot simpler sorted uint64 codec #2716
Merged
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
golangcibot
reviewed
Oct 31, 2018
manishrjain
commented
Oct 31, 2018
There was a problem hiding this comment.
Reviewable status: 0 of 4 files reviewed, 4 unresolved discussions (waiting on @golangcibot)
binary/codec.go, line 7 at r1 (raw file):
Previously, golangcibot (Bot from GolangCI) wrote…
func
packBlockis unused
Done.
binary/codec.go, line 27 at r1 (raw file):
Previously, golangcibot (Bot from GolangCI) wrote…
func
Encodeis unused
Done.
binary/codec.go, line 43 at r1 (raw file):
Previously, golangcibot (Bot from GolangCI) wrote…
func
NumUidsis unused
Done.
binary/codec.go, line 51 at r1 (raw file):
Previously, golangcibot (Bot from GolangCI) wrote…
func
Decodeis unused
Done.
dna2github
pushed a commit
to dna2fork/dgraph
that referenced
this pull request
Jul 19, 2019
This PR contains a simple encoder/decoder using concepts from binary packing building on protobuf's default varint encoding. We currently use bp128 package, a modification on a 3rd party library, which uses a complex piece of code, that hasn't been touched since it was written. It is hard to understand and debug, given a lot of it is using SIMD instructions generated via a python library. We have been seeing panics during rollups, and reads which indicate bugs in this implementation. Instead of trying to fix that up, I wrote this PR, which uses concepts from Binary Packing and the fact that protobufs use Varint encoding to write a very simple encoder/decoder for posting lists. This PR just contains the implementation, tests and benchmarks. Next PR would modify posting lists to replace the current bp128 with the new binary package. Benchmark output with artificial dataset list: ``` goos: linux goarch: amd64 pkg: github.com/dgraph-io/dgraph/binary BenchmarkGzip-4 10 112428082 ns/op --- BENCH: BenchmarkGzip-4 codec_test.go:77: Dataset Len=1000000. Size: 8.0 MB codec_test.go:95: Output size: 2.6 MB. Compression: 0.33 codec_test.go:77: Dataset Len=1000000. Size: 8.0 MB codec_test.go:95: Output size: 2.6 MB. Compression: 0.33 BenchmarkUidPack/encode/128-4 100 14213068 ns/op --- BENCH: BenchmarkUidPack/encode/128-4 codec_test.go:105: Dataset Len=1000000. Size: 8.0 MB codec_test.go:115: Output size: 1.1 MB. Compression: 0.13 codec_test.go:105: Dataset Len=1000000. Size: 8.0 MB codec_test.go:115: Output size: 1.1 MB. Compression: 0.13 BenchmarkUidPack/encode/256-4 100 12399005 ns/op --- BENCH: BenchmarkUidPack/encode/256-4 codec_test.go:105: Dataset Len=1000000. Size: 8.0 MB codec_test.go:115: Output size: 1.0 MB. Compression: 0.13 codec_test.go:105: Dataset Len=1000000. Size: 8.0 MB codec_test.go:115: Output size: 1.0 MB. Compression: 0.13 BenchmarkUidPack/decode/128-4 1000 2213527 ns/op --- BENCH: BenchmarkUidPack/decode/128-4 codec_test.go:140: Dataset Len=1000000. Size: 8.0 MB codec_test.go:145: Output size: 1.1 MB. Compression: 0.13 codec_test.go:140: Dataset Len=1000000. Size: 8.0 MB codec_test.go:145: Output size: 1.1 MB. Compression: 0.13 codec_test.go:140: Dataset Len=1000000. Size: 8.0 MB codec_test.go:145: Output size: 1.1 MB. Compression: 0.13 BenchmarkUidPack/decode/256-4 1000 2014434 ns/op --- BENCH: BenchmarkUidPack/decode/256-4 codec_test.go:140: Dataset Len=1000000. Size: 8.0 MB codec_test.go:145: Output size: 1.0 MB. Compression: 0.13 codec_test.go:140: Dataset Len=1000000. Size: 8.0 MB codec_test.go:145: Output size: 1.0 MB. Compression: 0.13 codec_test.go:140: Dataset Len=1000000. Size: 8.0 MB codec_test.go:145: Output size: 1.0 MB. Compression: 0.13 PASS ok github.com/dgraph-io/dgraph/binary 17.786s ```
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
We currently use bp128 package, a modification on a 3rd party library, which uses a complex piece of code, that hasn't been touched since it was written. It is hard to understand and debug, given a lot of it is using SIMD instructions, generated via a python library.
We have been seeing panics during rollups, and reads which indicate bugs in this implementation. Instead of trying to fix that up, I wrote this PR, which uses concepts from Binary Packing and the fact that protobufs use Varint encoding, to write a very simple encoder/decoder for posting lists.
This PR just contains the implementation, tests and benchmarks. Next PR would modify posting lists to replace the current bp128 with the new binary package.
This change is