Exploiting SIMD instructions in current processors to improve classical string algorithms

Abstract. Current processors include instruction set extensions espe-cially designed for improving the performance of media, imaging, and 3D workloads. These instructions are rarely considered when implementing practical solutions for algorithms and compressed data structures, mostly because they are not directly generated by the compiler. In this paper, we proclaim their benefits and encourage their use, as they are an un-used asset included in almost all general-purpose computers. As a proof of concept, we perform an experimental evaluation by straightforwardly including some of these complex instructions in basic string algorithms used for indexing and search, obtaining significant speedups. This opens a new interesting line of research: designing new algorithms and data structures by taking into account the existence of these sets of instruc-tions, in order to achieve significant speedups at no extra cost.