Bounds Check Elimination (BCE) in Golang 1.7
This is an area of optimization that was figured out in the Pascal era, then forgotten during the C era. It&#x27;s good to see it coming back.  Work on Pascal was able to optimize out about 95% of bounds checks. Here&#x27;s an overview that has a literature survey.[1]<p>A big win is hoisting bounds checks out of loops. I think the Go compiler already optimized out the check for loops where the loop iteration variable is bounded by the range of the array. But that&#x27;s a special case.  The general case has a problem. Consider<p><pre><code>    func copy(src []int, dst []int) {
	for i := range(src) {
            dst[i] = src[i]
        }
    }
</code></pre>
This has a subscript out of range error if dst is shorter than src. It&#x27;s the classic C buffer overflow. For optimization purposes, we can look at this as<p><pre><code>    func copy(src []int, dst []int) {
	for i := range(src) {
            assert(i &lt; len(src)) &#x2F;&#x2F; subscript check
            assert(i &lt; len(dst)) &#x2F;&#x2F; subscript check 
            dst[i] = src[i]
        }
    }
</code></pre>
The FOR statement insures that i &lt; len(src), so a prover would see this as (i &lt; len(src) implies (i &lt; len(src)), which reduces to True, and we can discard that assert.  We still have the assert for &quot;dst&quot;. For that, it&#x27;s possible to hoist it out of the loop.  We generate the check<p><pre><code>    func copy(src []int, dst []int) {
        assert(len(src) &lt;= len(dst)) &#x2F;&#x2F; generated
	for i := range(src) {
            assert(i &lt; len(src)) &#x2F;&#x2F; optimized out
            assert(i &lt; len(dst)) &#x2F;&#x2F; subscript check 
            dst[i] = src[i]
        }
    }
</code></pre>
which gives us<p><pre><code>    len(src) &lt;= len(dst) and i &lt; len(src) implies (i &lt; len(dst))
</code></pre>
which simplifies to True. So assert(i &lt; len(dst) can be optimized out.
We have one run-time check remaining, and it&#x27;s outside the loop, done once.  This is hoisting a bounds check out of a loop, and it&#x27;s a huge win for inner loops.  Good test for a compiler: write a matrix multiply and make sure it can do this.<p>[1] <a href="http:&#x2F;&#x2F;www.cri.ensmp.fr&#x2F;classement&#x2F;doc&#x2F;E-235.ps" rel="nofollow">http:&#x2F;&#x2F;www.cri.ensmp.fr&#x2F;classement&#x2F;doc&#x2F;E-235.ps</a>