Tree-based models have proven to be an effective solution for web ranking as well as other problems in diverse domains. This paper focuses on optimizing the runtime performance of applying such models to make predictions, given an already-trained model. Although exceedingly simple conceptually, most implementations of tree-based models do not efficiently utilize modern superscalar processor architectures. By laying out data structures in memory in a more cache-conscious fashion, removing branches from the execution flow using a technique called predication, and micro-batching predictions using a technique called vectorization, we are able to better exploit modern processor architectures and significantly improve the speed of tree-based models over hard-coded if-else blocks. Our work contributes to the exploration of architecture-conscious runtime implementations of machine learning algorithms.
@cite_1: The performance of microprocessors that power modern computers has continued to increase exponentially over the years for two main reasons. First, the transistors that are the heart of the circuits in all processors and memory chips have simply become faster over time on a course described by Moore’s law,1 and this directly affects the performance of processors built with those transistors. Moreover, actual processor performance has increased faster than Moore’s law would predict,2 because processor designers have been able to harness the increasing numbers of transistors available on modern chips to extract more parallelism from software. This is depicted in figure 1 for Intel’s processors.
We begin with an overview of modern processor architectures and recap advances over the past few decades. The broadest trend is perhaps the multi-core revolution @cite_1 : the relentless march of Moore's Law continues to increase the number of transistors on a chip exponentially, but experts widely agree that we are long past the point of diminishing returns in extracting instruction-level parallelism in hardware. Instead, adding more cores appears to be a better use of increased transistor density. Since prediction is an embarrassingly parallel problem, our techniques can ride the wave of increasing core counts.