A fast and vectorizable alternative to binary search in O(1) with wide applicability to arrays of floating point numbers

摘要

AbstractGiven an arrayXofN+1strictly ordered floating point numbers and a floating point numberzbelonging to the interval[X0,XN), a common problem in numerical methods is to find the indexiof the interval[Xi,Xi+1)containingz, i.e. the index of the largest number in the arrayXwhich is smaller or equal thanz. This problem arises for instance in the context of spline interpolation or the computation of empirical probability distribution from empirical data. Often it needs to be solved for a large number of different valueszand the same arrayX, which makes it worth investing resources upfront in pre-processing the arrayXwith the goal of speeding up subsequent search operations. In some cases the valueszto be processed are known simultaneously in blocks of sizeM, which offers the opportunity to solve the problem vectorially, exploiting the parallel capabilities of modern CPUs. The common solution is to sequentially invokeMtimes the well knownbinary searchalgorithm, which has complexityO(log2N)per individual search and, in its classic formulation, is not vectorizable, i.e. it is not SIMD friendly. This paper describes technical improvements to thebinary searchalgorithm, which make it faster and vectorizable. Next it proposes a new vectorizable algorithm, based on an indexing technique, applicable to a wide family ofXpartitions, which solves the problem with complexityO(1)per individual search at the cost of introducing an initial overhead to compute the index and requiring extra memory for its storage. Test results using streaming SIMD extensions compare the performance of the algorithm versus various benchmarks and demonstrate its effectiveness. Depending on the test case, the algorithm can produce a throughput up to two orders of magnitude larger than the classicbinary search. Applicability limitations and cache-friendliness related aspects are also discussed.Highlights•The problem of finding the insertion point in a sorted numerical array is discussed.•Optimized and vectorizable variations of the binary search algorithm are proposed.•A new algorithm significantly faster with complexityO(1)is proposed.•Applicability and limitations of the new algorithm are discussed.•Performance test results including various SIMD implementations are presented.