From 46c95940812ccd3f474dc5fab7a5351351e8f105 Mon Sep 17 00:00:00 2001 From: Ethan Buchman Date: Thu, 6 Aug 2015 12:39:07 -0400 Subject: trie: run codec tests, add benchmarks, faster --- trie/encoding.go | 36 ++++++++++++++------------------ trie/encoding_test.go | 58 +++++++++++++++++++++++++++++++++++++++++++++++---- 2 files changed, 70 insertions(+), 24 deletions(-) diff --git a/trie/encoding.go b/trie/encoding.go index 8daf503a3..9c862d78f 100644 --- a/trie/encoding.go +++ b/trie/encoding.go @@ -16,10 +16,6 @@ package trie -import ( - "bytes" -) - func CompactEncode(hexSlice []byte) []byte { terminator := 0 if hexSlice[len(hexSlice)-1] == 16 { @@ -38,12 +34,12 @@ func CompactEncode(hexSlice []byte) []byte { hexSlice = append([]byte{flags, 0}, hexSlice...) } - var buff bytes.Buffer - for i := 0; i < len(hexSlice); i += 2 { - buff.WriteByte(byte(16*hexSlice[i] + hexSlice[i+1])) + l := len(hexSlice) / 2 + var buf = make([]byte, l) + for i := 0; i < l; i++ { + buf[i] = 16*hexSlice[2*i] + hexSlice[2*i+1] } - - return buff.Bytes() + return buf } func CompactDecode(str []byte) []byte { @@ -62,22 +58,22 @@ func CompactDecode(str []byte) []byte { } func CompactHexDecode(str []byte) []byte { - var nibbles []byte - - for _, b := range str { - nibbles = append(nibbles, b/16) - nibbles = append(nibbles, b%16) + l := len(str)*2 + 1 + var nibbles = make([]byte, l) + for i, b := range str { + nibbles[i*2] = b / 16 + nibbles[i*2+1] = b % 16 } - nibbles = append(nibbles, 16) + nibbles[l-1] = 16 return nibbles } -// assumes key is odd length func DecodeCompact(key []byte) []byte { - var res []byte - for i := 0; i < len(key)-1; i += 2 { - v1, v0 := key[i], key[i+1] - res = append(res, v1*16+v0) + l := len(key) / 2 + var res = make([]byte, l) + for i := 0; i < l; i++ { + v1, v0 := key[2*i], key[2*i+1] + res[i] = v1*16 + v0 } return res } diff --git a/trie/encoding_test.go b/trie/encoding_test.go index faaa7f583..e49b57ef0 100644 --- a/trie/encoding_test.go +++ b/trie/encoding_test.go @@ -17,9 +17,14 @@ package trie import ( + "encoding/hex" + "testing" + checker "gopkg.in/check.v1" ) +func Test(t *testing.T) { checker.TestingT(t) } + type TrieEncodingSuite struct{} var _ = checker.Suite(&TrieEncodingSuite{}) @@ -28,22 +33,22 @@ func (s *TrieEncodingSuite) TestCompactEncode(c *checker.C) { // even compact encode test1 := []byte{1, 2, 3, 4, 5} res1 := CompactEncode(test1) - c.Assert(res1, checker.Equals, "\x11\x23\x45") + c.Assert(res1, checker.DeepEquals, []byte("\x11\x23\x45")) // odd compact encode test2 := []byte{0, 1, 2, 3, 4, 5} res2 := CompactEncode(test2) - c.Assert(res2, checker.Equals, "\x00\x01\x23\x45") + c.Assert(res2, checker.DeepEquals, []byte("\x00\x01\x23\x45")) //odd terminated compact encode test3 := []byte{0, 15, 1, 12, 11, 8 /*term*/, 16} res3 := CompactEncode(test3) - c.Assert(res3, checker.Equals, "\x20\x0f\x1c\xb8") + c.Assert(res3, checker.DeepEquals, []byte("\x20\x0f\x1c\xb8")) // even terminated compact encode test4 := []byte{15, 1, 12, 11, 8 /*term*/, 16} res4 := CompactEncode(test4) - c.Assert(res4, checker.Equals, "\x3f\x1c\xb8") + c.Assert(res4, checker.DeepEquals, []byte("\x3f\x1c\xb8")) } func (s *TrieEncodingSuite) TestCompactHexDecode(c *checker.C) { @@ -73,3 +78,48 @@ func (s *TrieEncodingSuite) TestCompactDecode(c *checker.C) { res = CompactDecode([]byte("\x3f\x1c\xb8")) c.Assert(res, checker.DeepEquals, exp) } + +func (s *TrieEncodingSuite) TestDecodeCompact(c *checker.C) { + exp, _ := hex.DecodeString("012345") + res := DecodeCompact([]byte{0, 1, 2, 3, 4, 5}) + c.Assert(res, checker.DeepEquals, exp) + + exp, _ = hex.DecodeString("012345") + res = DecodeCompact([]byte{0, 1, 2, 3, 4, 5, 16}) + c.Assert(res, checker.DeepEquals, exp) + + exp, _ = hex.DecodeString("abcdef") + res = DecodeCompact([]byte{10, 11, 12, 13, 14, 15}) + c.Assert(res, checker.DeepEquals, exp) +} + +func BenchmarkCompactEncode(b *testing.B) { + + testBytes := []byte{0, 15, 1, 12, 11, 8 /*term*/, 16} + for i := 0; i < b.N; i++ { + CompactEncode(testBytes) + } +} + +func BenchmarkCompactDecode(b *testing.B) { + testBytes := []byte{0, 15, 1, 12, 11, 8 /*term*/, 16} + for i := 0; i < b.N; i++ { + CompactDecode(testBytes) + } +} + +func BenchmarkCompactHexDecode(b *testing.B) { + testBytes := []byte{7, 6, 6, 5, 7, 2, 6, 2, 16} + for i := 0; i < b.N; i++ { + CompactHexDecode(testBytes) + } + +} + +func BenchmarkDecodeCompact(b *testing.B) { + testBytes := []byte{7, 6, 6, 5, 7, 2, 6, 2, 16} + for i := 0; i < b.N; i++ { + DecodeCompact(testBytes) + } + +} -- cgit v1.2.3