GoVector
GoVector copied to clipboard
Make ReturnVCString Deterministic
Currently when getting the string representation for a vector clock, you will get a non-deterministic order of keys and values. The reason is that ranging over a map in Go gives you its keys in a random order. Nevertheless, the current implementation of ReturnVCString
in the vclock
package relies on ranging over the keys to sort the output (note that the comment is from the original code):
//sort
ids := make([]string, len(vc))
i := 0
for id := range vc {
ids[i] = id
i++
}
So I'm assuming that non-deterministic output is a bug and not intentional.
For some use-cases (notably: my use-case 🙂), this can be problematic. My proposal is to add an additional sort.Strings(ids)
step before using the array of keys so that iff v1 == v2 => v1.ReturnVCString() == v2.ReturnVCString()
. This should prevent any further surprises.
There is a performance overhead but I find it negligible. For a vector clock with 100 entries (quite large):
goos: darwin
goarch: amd64
pkg: github.com/DistributedClocks/GoVector/govec/vclock
cpu: Intel(R) Core(TM) i5-8210Y CPU @ 1.60GHz
BenchmarkVCString-4 28614 40648 ns/op
BenchmarkVCStringSorted-4 20901 57339 ns/op
PASS
ok github.com/DistributedClocks/GoVector/govec/vclock 3.386s
(This benchmark is not included in this PR, just illustrative.)
0.017ms is acceptable, although that difference is grows or shrinks with the size of the clock.