Although most of the focus in SAT local search has been on search behavior (deciding which variable to flip next), the overall efficiency of an algorithm depends greatly on the efficiency of executing each variable flip and variable selection. This paper surveys, evaluates, and extends incremental data structures that have been used in SAT local search solvers (including the GSAT and Walksat families of solvers) to support efficient variable flips and selection.