I recently had to dig into pure algorithmic code at work in order to implement a research paper.
Exploring the literature, I was pretty astonished to see how clean code is generally ignored in this sphere. I first assumed it was for performance reasons so I decided to investigate a bit further.
Let’s pick a classic Union-Find data structure, give a standard implementation then a clean one and benchmark both to see if there’s a difference.
Union-Find algorithms
Union-Find data structures are used to address dynamic connectivity problems . They always handle the 2 same functions :
connect 2 given nodes (using their specific data structure)
tell if 2 nodes are connected.
Connection rules are pretty simple :
a node p is connected to itself
if a node p is connected to a node q, then q is connected to p
if p is connected to q & q is connected to r, then p is connected to r
http://researchhubs.com/post/computing/algorithm-1/dynamic-connectivity.html
Our test algorithm
We’ll use the Weighted Quick-Union with Path Compression algorithm for our benchmarks.
And, here’s the sort of code you’ll usually encounter (golang) :
Original code
type UnionFinder interface {
Union(p, r int)
Connected(p, r int) bool
}
// wqupc : Weighted Quick Union with Path Compression algorithm
type wqupc struct {
ids []int
w []int
}
func NewWqupc(n int) UnionFinder {
result := &wqupc{}
result.ids = make([]int, n)
result.w = make([]int, n)
for x := range result.ids {
result.ids[x] = x
result.w[x] = 1
}
return result
}
func (q *wqupc) Connected(p, r int) bool {
return q.root(p) == q.root(r)
}
func (q *wqupc) Union(p, r int) {
qp := q.root(p)
qr := q.root(r)
if qr == qp {
return
}
if q.w[qr] > q.w[qp] {
q.ids[qp] = qr
q.w[qr] += q.w[qp]
return
}
q.ids[qr] = qp
q.w[qp] += q.w[qr]
}
func (q *wqupc) root(r int) int {
for {
if r == q.ids[r] {
return r
}
q.ids[r] = q.ids[q.ids[r]]
r = q.ids[r]
}
}
Pretty easy to grasp the logic of this algorithm, isn’t it ? :)
Nope ? Let’s refactor this to see if we can make it more readable.
Cleaner code
type UnionFinder interface {
Union(p, r int)
Connected(p, r int) bool
}
// clean : Weighted Quick Union with Path Compression algorithm
type clean struct {
ids []int
weights []int
}
func NewClean(size int) UnionFinder {
uf := &clean{}
uf.initializeArrays(size)
return uf
}
func (cleanUF *clean) Connected(nodeOne, nodeTwo int) bool {
return cleanUF.root(nodeOne) == cleanUF.root(nodeTwo)
}
func (cleanUF *clean) Union(nodeOne, nodeTwo int) {
rootOne := cleanUF.root(nodeOne)
rootTwo := cleanUF.root(nodetwo)
if haveTheSameRoot(rootOne, rootTwo) {
return
}
smallTreeRoot, largeTreeRoot := cleanUF.sortRootsByTreeLength(rootOne, rootTwo)
cleanUF.attachSmallTreeToLargeTreeRoot(smallTreeRoot, largeTreeRoot)
cleanUF.addSmallTreeLengthToLargeOne(smallTreeRoot, largeTreeRoot)
}
//
// privates
//
func (cleanUF *clean) root(node int) int {
for {
if cleanUF.isRoot(node) {
return node
}
node = cleanUF.attachToRootRoot(node)
}
}
func (cleanUF *clean) initializeArrays(size int) {
cleanUF.ids = intVectorOfSize(size)
cleanUF.weights = intVectorOfSize(size)
for x := 0; x < size; x++ {
cleanUF.ids[x] = x
cleanUF.weights[x] = 1
}
}
func intVectorOfSize(size int) []int {
return make([]int, size)
}
func (cleanUF *clean) addSmallTreeLengthToLargeOne(smallTreeRoot int, largeTreeRoot int) {
cleanUF.weights[largeTreeRoot] += cleanUF.weights[smallTreeRoot]
}
func (cleanUF *clean) attachSmallTreeToLargeTreeRoot(smallTreeRoot, largeTreeRoot int) {
cleanUF.ids[smallTreeRoot] = largeTreeRoot
}
func (cleanUF *clean) sortRootsByTreeLength(rootOne, rootTwo int) (int, int) {
if cleanUF.weights[rootOne] < cleanUF.weights[rootTwo] {
return rootOne, rootTwo
}
return rootTwo, rootOne
}
func haveTheSameRoot(rootFirst, rootSecond int) bool {
return rootFirst == rootSecond
}
func (cleanUF *clean) attachToRootRoot(node int) int {
newRoot := cleanUF.ids[cleanUF.ids[node]]
cleanUF.ids[node] = newRoot
return newRoot
}
func (cleanUF *clean) isRoot(r int) bool {
return r == cleanUF.ids[r]
}
Ok, the file is 30% longer but I hope the exported methods code is self-explanatory and you just have to read 20 lines in order to get the idea behind this implementation.
Benchmark !
BenchmarkMain/standard-4 300000 3700 ns/op
BenchmarkMain/clean-4 500000 3601 ns/op
BenchmarkMain/standard_second_time-4 500000 3630 ns/op
BenchmarkMain/clean_second_time-4 500000 3663 ns/op
The results are a bit flaky, so I ran the benchmarks twice for each algorithm.
As you can see, results are pretty much the sames. Sometimes the clean version is a bit faster, sometimes it’s a bit slower. My guess is they’re just as fast, it’s just the system is sometimes a bit more busy doing something else…