Branch-Avoiding Graph Algorithms
Oded Green, Marat Dukhan, Richard W. Vuduc · 2015
This paper quantifies the impact of branches and branch mispredictions on the single-core performance of certain graph problems, specifically for computing connected components. We show that branch mispredictions are costly and can reduce performance by as much as 30%-50%. This insight suggests that one should seek graph algorithms and implementations that avoid branches.