compress/bzip2: remove bit-tricks

Since compiler is now able to generate conditional moves, we can replace
bit-tricks with simple if/else. This even results in slightly better performance:

name            old time/op    new time/op    delta
DecodeDigits-6    13.4ms ± 4%    13.0ms ± 2%  -2.63%  (p=0.003 n=10+10)
DecodeTwain-6     37.5ms ± 1%    36.3ms ± 1%  -3.03%  (p=0.000 n=10+9)
DecodeRand-6      4.23ms ± 1%    4.07ms ± 1%  -3.67%  (p=0.000 n=10+9)

name            old speed      new speed      delta
DecodeDigits-6  7.47MB/s ± 4%  7.67MB/s ± 2%  +2.69%  (p=0.002 n=10+10)
DecodeTwain-6   10.4MB/s ± 1%  10.7MB/s ± 1%  +3.25%  (p=0.000 n=10+8)
DecodeRand-6    3.87MB/s ± 1%  4.03MB/s ± 2%  +4.08%  (p=0.000 n=10+10)
diff --git a/src/compress/bzip2/huffman.go b/src/compress/bzip2/huffman.go

Change-Id: Ie96ef1a9e07013b07e78f22cdccd531f3341caca
Reviewed-on: https://go-review.googlesource.com/102015
Run-TryBot: Ilya Tocar <ilya.tocar@intel.com>
Reviewed-by: Joe Tsai <joetsai@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>

1 files changed, 18 insertions, 14 deletions

diff --git a/src/compress/bzip2/huffman.go b/src/compress/bzip2/huffman.go
index 1683426adc..36ae954009 100644
--- a/src/compress/bzip2/huffman.go
+++ b/src/compress/bzip2/huffman.go
@@ -43,30 +43,34 @@ func (t *huffmanTree) Decode(br *bitReader) (v uint16) {
 		if br.bits > 0 {
 			// Get next bit - fast path.
 			br.bits--
-			bit = 0 - (uint16(br.n>>br.bits) & 1)
+			bit = uint16(br.n>>(br.bits&63)) & 1
 		} else {
 			// Get next bit - slow path.
 			// Use ReadBits to retrieve a single bit
 			// from the underling io.ByteReader.
-			bit = 0 - uint16(br.ReadBits(1))
+			bit = uint16(br.ReadBits(1))
 		}
-		// now
-		// bit = 0xffff if the next bit was 1
-		// bit = 0x0000 if the next bit was 0
 
-		// 1 means left, 0 means right.
-		//
-		// if bit == 0xffff {
-		//     nodeIndex = node.left
-		// } else {
-		//     nodeIndex = node.right
-		// }
-		nodeIndex = (bit & node.left) | (^bit & node.right)
+		// Trick a compiler into generating conditional move instead of branch,
+		// by making both loads unconditional.
+		l, r := node.left, node.right
+
+		if bit == 1 {
+			nodeIndex = l
+		} else {
+			nodeIndex = r
+		}
 
 		if nodeIndex == invalidNodeValue {
 			// We found a leaf. Use the value of bit to decide
 			// whether is a left or a right value.
-			return (bit & node.leftValue) | (^bit & node.rightValue)
+			l, r := node.leftValue, node.rightValue
+			if bit == 1 {
+				v = l
+			} else {
+				v = r
+			}
+			return
 		}
 	}
 }