On the Surprising Difficulty of Simple Things: the Case of Radix Partitioning

摘要

In this mini paper, we saw that even a trivial algorithm such as radix partition can be significantly improved by making it aware of current hardware features, leading to an improvement over the original version of factor 2.5x. Figure 8 gives a complete overview over all evaluated methods in comparison to two state-of-the-art implementations used in . As a side-effect of our evaluation, we were even able to improve over the existing methods in all tested configurations. For smaller number of partitions, using larger partition buffers without micro layouts shows the best performance. For 32 partitions, we recommend using the original version without any optimizations. For larger partition numbers, the layout-optimized single cache-line version pays off the most. Further, prefetching hints have a high impact on the runtime and are an option as soon as cache-space becomes the limiting factor. Additionally to the identification of an absolute winner in terms of runtime, we carefully investigated the individual positive and negative impact of each optimization. Figure 9 summarizes for all tested optimization paths of Figure 2 those, that improved over the original version. This final overview showing the influenceability of the techniques by the partition count and their varying impact on the runtime clearly demonstrates a surprising difficulty of simple things.