Re-implement instance terminators so that insertion/remove is no longer linear.

R=arv
BUG=

Review URL: https://codereview.appspot.com/8882044