mirror of
https://github.com/FlipsideCrypto/dcrd.git
synced 2026-02-06 19:06:51 +00:00
2c3a4e3054
This implements new version 2 filters which have 4 changes as compared to version 1 filters: - Support for independently specifying the false positive rate and Golomb coding bin size which allows minimizing the filter size - A faster (incompatible with version 1) reduction function - A more compact serialization for the number of members in the set - Deduplication of all hash collisions prior to reducing and serializing the deltas In addition, it adds a full set of tests and updates the benchmarks to use the new version 2 filters. The primary motivating factor for these changes is the ability to minimize the size of the filters, however, the following is a before and after comparison of version 1 and 2 filters in terms of performance and allocations. It is interesting to note the results for attempting to match a single item is not very representative due to the fact the actual hash value itself dominates to the point it can significantly vary due to the very low ns timings involved. Those differences average out when matching multiple items, which is the much more realistic scenario, and the performance increase is in line with the expected values. It is also worth nothing that filter construction now takes a bit longer due to the additional deduplication step. While the performance numbers for filter construction are about 25% larger in relative terms, it is only a few ms difference in practice and therefore is an acceptable trade off for the size savings provided. benchmark old ns/op new ns/op delta ----------------------------------------------------------------- BenchmarkFilterBuild50000 16194920 20279043 +25.22% BenchmarkFilterBuild100000 32609930 41629998 +27.66% BenchmarkFilterMatch 620 593 -4.35% BenchmarkFilterMatchAny 2687 2302 -14.33% benchmark old allocs new allocs delta ----------------------------------------------------------------- BenchmarkFilterBuild50000 6 17 +183.33% BenchmarkFilterBuild100000 6 18 +200.00% BenchmarkFilterMatch 0 0 +0.00% BenchmarkFilterMatchAny 0 0 +0.00% benchmark old bytes new bytes delta ----------------------------------------------------------------- BenchmarkFilterBuild50000 688366 2074653 +201.39% BenchmarkFilterBuild100000 1360064 4132627 +203.86% BenchmarkFilterMatch 0 0 +0.00% BenchmarkFilterMatchAny 0 0 +0.00%
111 lines
2.5 KiB
Go
111 lines
2.5 KiB
Go
// Copyright (c) 2019 The Decred developers
|
|
// Use of this source code is governed by an ISC
|
|
// license that can be found in the LICENSE file.
|
|
|
|
package gcs
|
|
|
|
import (
|
|
"testing"
|
|
)
|
|
|
|
// TestErrorCodeStringer tests the stringized output for the ErrorCode type.
|
|
func TestErrorCodeStringer(t *testing.T) {
|
|
tests := []struct {
|
|
in ErrorCode
|
|
want string
|
|
}{
|
|
{ErrNTooBig, "ErrNTooBig"},
|
|
{ErrPTooBig, "ErrPTooBig"},
|
|
{ErrBTooBig, "ErrBTooBig"},
|
|
{ErrMisserialized, "ErrMisserialized"},
|
|
{0xffff, "Unknown ErrorCode (65535)"},
|
|
}
|
|
|
|
// Detect additional error codes that don't have the stringer added.
|
|
if len(tests)-1 != int(numErrorCodes) {
|
|
t.Errorf("It appears an error code was added without adding an " +
|
|
"associated stringer test")
|
|
}
|
|
|
|
t.Logf("Running %d tests", len(tests))
|
|
for i, test := range tests {
|
|
result := test.in.String()
|
|
if result != test.want {
|
|
t.Errorf("String #%d\n got: %s want: %s", i, result, test.want)
|
|
continue
|
|
}
|
|
}
|
|
}
|
|
|
|
// TestError tests the error output for the Error type.
|
|
func TestError(t *testing.T) {
|
|
tests := []struct {
|
|
in Error
|
|
want string
|
|
}{{
|
|
Error{Description: "duplicate block"},
|
|
"duplicate block",
|
|
}, {
|
|
Error{Description: "human-readable error"},
|
|
"human-readable error",
|
|
},
|
|
}
|
|
|
|
t.Logf("Running %d tests", len(tests))
|
|
for i, test := range tests {
|
|
result := test.in.Error()
|
|
if result != test.want {
|
|
t.Errorf("Error #%d\n got: %s want: %s", i, result, test.want)
|
|
continue
|
|
}
|
|
}
|
|
}
|
|
|
|
// TestIsErrorCode ensures IsErrorCode works as intended.
|
|
func TestIsErrorCode(t *testing.T) {
|
|
tests := []struct {
|
|
name string
|
|
err error
|
|
code ErrorCode
|
|
want bool
|
|
}{{
|
|
name: "ErrNTooBig testing for ErrNTooBig",
|
|
err: makeError(ErrNTooBig, ""),
|
|
code: ErrNTooBig,
|
|
want: true,
|
|
}, {
|
|
name: "ErrPTooBig testing for ErrPTooBig",
|
|
err: makeError(ErrPTooBig, ""),
|
|
code: ErrPTooBig,
|
|
want: true,
|
|
}, {
|
|
name: "ErrMisserialized testing for ErrMisserialized",
|
|
err: makeError(ErrMisserialized, ""),
|
|
code: ErrMisserialized,
|
|
want: true,
|
|
}, {
|
|
name: "ErrNTooBig error testing for ErrPTooBig",
|
|
err: makeError(ErrNTooBig, ""),
|
|
code: ErrPTooBig,
|
|
want: false,
|
|
}, {
|
|
name: "ErrNTooBig error testing for unknown error code",
|
|
err: makeError(ErrNTooBig, ""),
|
|
code: 0xffff,
|
|
want: false,
|
|
}, {
|
|
name: "nil error testing for ErrNTooBig",
|
|
err: nil,
|
|
code: ErrNTooBig,
|
|
want: false,
|
|
}}
|
|
for _, test := range tests {
|
|
result := IsErrorCode(test.err, test.code)
|
|
if result != test.want {
|
|
t.Errorf("%s: unexpected result -- got: %v want: %v", test.name,
|
|
result, test.want)
|
|
continue
|
|
}
|
|
}
|
|
}
|