In addition to fixing the bug, the check is now linear instead of quadratic.

Fixes #4469.

R=ken2
CC=golang-dev
https://golang.org/cl/7773047