Good predictions are worth a few comparisons

Nicolas Auger (1) , Cyril Nicaud (1) , Carine Pivoteau (1)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge

Most modern processors are heavily parallelized and use predictors to guess the outcome of conditional branches, in order to avoid costly stalls in their pipelines. We propose predictor-friendly versions of two classical algorithms: exponentiation by squaring and binary search in a sorted array. These variants result in less mispredictions on average, at the cost of an increased number of operations. These theoretical results are supported by experimentations that show that our algorithms perform significantly better than the standard ones, for primitive data types. 1998 ACM Subject Classification F.2.2 Nonnumerical Algorithms and Problems

Domaines: Informatique [cs]; Algorithme et structure de données [cs.DS]; Complexité [cs.CC]; Mathématique discrète [cs.DM]

Nicolas Auger, Cyril Nicaud, Carine Pivoteau. Good predictions are worth a few comparisons. STACS 2016, Feb 2016, Orléans, France. pp.12:1-12:14, ⟨10.4230/LIPIcs.STACS.2016.12⟩. ⟨hal-01212840⟩