How efficient is a (SHA 256) hash in golang data where only the last few bytes change
Assuming you had 80 bytes of data and only the last 4 bytes were constantly changing, how would you effectively hash just 80 bytes with Go. Basically, the first 76 bytes are the same, and the last 4 bytes keep changing. Ideally, you want to keep a copy of the hash digest for the first 76 bytes and just keep changing the last 4.
source to share
You can try the following examples on the Go Playground . The test results are running out.
Note: the following implementations are not safe to use concurrently; I intentionally made them so that they are easier and faster.
Fastest when using only public API (always hashes entire input)
The general concept and interface of Go hash algorithms is an hash.Hash
interface. This prevents you from saving the hash state and going back or rewinding to the saved state. Thus, when using the standard Go standard hash APIs, you should always compute the hash from the beginning.
What the public API offers is to reuse an already built hasher to compute the hash of the new input using the method Hash.Reset()
. This is good, so no (memory) allocations are required to compute multiple hash values. You can also use an additional fragment that can be passed to Hash.Sum()
, which is used to add the current hash. This is nice, so you don't need any budget to get the hash results.
Here's an example that uses them:
type Cached1 struct {
hasher hash.Hash
result [sha256.Size]byte
}
func NewCached1() *Cached1 {
return &Cached1{hasher: sha256.New()}
}
func (c *Cached1) Sum(data []byte) []byte {
c.hasher.Reset()
c.hasher.Write(data)
return c.hasher.Sum(c.result[:0])
}
Test data
We will use the following test data:
var fixed = bytes.Repeat([]byte{1}, 76)
var variantA = []byte{1, 1, 1, 1}
var variantB = []byte{2, 2, 2, 2}
var data = append(append([]byte{}, fixed...), variantA...)
var data2 = append(append([]byte{}, fixed...), variantB...)
var c1 = NewCached1()
First, let's get reliable results (to make sure our hasher is working correctly):
fmt.Printf("%x\n", sha256.Sum256(data))
fmt.Printf("%x\n", sha256.Sum256(data2))
Output:
fb8e69bdfa2ad15be7cc8a346b74e773d059f96cfc92da89e631895422fe966a
10ef52823dad5d1212e8ac83b54c001bfb9a03dc0c7c3c83246fb988aa788c0c
Now let's take a look at our hasher Cached1
:
fmt.Printf("%x\n", c1.Sum(data))
fmt.Printf("%x\n", c1.Sum(data2))
The conclusion is the same:
fb8e69bdfa2ad15be7cc8a346b74e773d059f96cfc92da89e631895422fe966a
10ef52823dad5d1212e8ac83b54c001bfb9a03dc0c7c3c83246fb988aa788c0c
Even faster, but may break (in future Go releases): only the last 4 bytes are hashed
Now consider a less flexible solution that actually computes the hash of the first 76 fixed part only once.
The hasher crypto/sha256
is an unexported type sha256.digest
(more precisely, a pointer to this type):
// digest represents the partial evaluation of a checksum.
type digest struct {
h [8]uint32
x [chunk]byte
nx int
len uint64
is224 bool // mark if this digest is SHA-224
}
The struct type value digest
basically contains the current hash state.
What we can do is give the hacker a fixed, first 76 bytes, and then store that structure value. When we need to flatten a hash of about 80 bytes of data where the first 76 are the same, we use that stored value as a starting point and then load the variables for the last 4 bytes.
Note that it is fairly easy to store this structure value since it does not contain pointers and descriptor types such as fragments and maps. Otherwise, we would also have to make a copy of these, but we are "lucky". So this solution will need to be adjusted if a future implementation crypto/sha256
adds a pointer or slice field, for example.
Since it is sha256.digest
not supported, we can only use reflection ( reflect
package) to achieve our goals, which will in fact add some latency to the computation.
An example implementation that does this:
type Cached2 struct {
origv reflect.Value
hasherv reflect.Value
hasher hash.Hash
result [sha256.Size]byte
}
func NewCached2(fixed []byte) *Cached2 {
h := sha256.New()
h.Write(fixed)
c := &Cached2{origv: reflect.ValueOf(h).Elem()}
hasherv := reflect.New(c.origv.Type())
c.hasher = hasherv.Interface().(hash.Hash)
c.hasherv = hasherv.Elem()
return c
}
func (c *Cached2) Sum(data []byte) []byte {
// Set state of the fixed hash:
c.hasherv.Set(c.origv)
c.hasher.Write(data)
return c.hasher.Sum(c.result[:0])
}
Testing:
var c2 = NewCached2(fixed)
fmt.Printf("%x\n", c2.Sum(variantA))
fmt.Printf("%x\n", c2.Sum(variantB))
The output is the same again:
fb8e69bdfa2ad15be7cc8a346b74e773d059f96cfc92da89e631895422fe966a
10ef52823dad5d1212e8ac83b54c001bfb9a03dc0c7c3c83246fb988aa788c0c
This is how it works.
"Ultimate", fastest solution
Cached2
can be faster if reflection is not involved. If we want an even faster solution, we can simply make a copy of the type sha256.digest
and its methods in our package, so we can directly use it without resorting to reflection.
If we do this, we have access to the value of the struct digest
, and we can just make a copy of it:
var d digest
// init d
saved := d
And recovery: "
d = saved
I just "cloned" the package crypto/sha256
into my workspace and changed / exported the type digest
as digest
soon as for demonstration purposes. Then using this mysha256.Digest
type I implemented Cached3
as follows:
type Cached3 struct {
orig mysha256.Digest
result [sha256.Size]byte
}
func NewCached3(fixed []byte) *Cached3 {
var d mysha256.Digest
d.Reset()
d.Write(fixed)
return &Cached3{orig: d}
}
func (c *Cached3) Sum(data []byte) []byte {
// Make a copy of the fixed hash:
d := c.orig
d.Write(data)
return d.Sum(c.result[:0])
}
Testing:
var c3 = NewCached3(fixed)
fmt.Printf("%x\n", c3.Sum(variantA))
fmt.Printf("%x\n", c3.Sum(variantB))
The output is the same again. So this works too.
Benchmarks
We can compare the performance with this code:
func BenchmarkCached1(b *testing.B) {
for i := 0; i < b.N; i++ {
c1.Sum(data)
c1.Sum(data2)
}
}
func BenchmarkCached2(b *testing.B) {
for i := 0; i < b.N; i++ {
c2.Sum(variantA)
c2.Sum(variantB)
}
}
func BenchmarkCached3(b *testing.B) {
for i := 0; i < b.N; i++ {
c3.Sum(variantA)
c3.Sum(variantB)
}
}
Test results ( go test -bench . -benchmem
):
BenchmarkCached1-4 1000000 1569 ns/op 0 B/op 0 allocs/op BenchmarkCached2-4 2000000 926 ns/op 0 B/op 0 allocs/op BenchmarkCached3-4 2000000 872 ns/op 0 B/op 0 allocs/op
Cached2
about 41% faster than Cached1
, which is quite remarkable and enjoyable. Cached3
gives only a small increase in productivity compared to Cached2
, another 6% . Cached3
44% faster Cached1
.
Also note that none of the solutions use any distributions, which are fine as well.
Conclusion
For that extra 40% or 44%, I probably wouldn't go for solutions Cached2
or Cached3
. Of course, it really depends on how important performance is to you. If that's important, I think the solution Cached2
is a great compromise between minimal added complexity and noticeable performance gains. This poses a threat because future Go implementations might break it; if it is a problem, Cached3
solves it by copying the current implementation (and also slightly improving its performance).
source to share