Session Name: | R-Trees -- Adapting out-of-core techniques to modern memory architectures |
Speaker(s): | Sebastian Sylvan |
Company Name(s): | Rare Ltd. |
Track / Format: | Programming |
Overview: | Code running on modern in-order CPUs pay a hefty cost for cache misses. This leads to major performance problem for pointer-heavy data structures, such as spatial hierarchies. This problem is similar to the problems encountered by people doing out-of-core processing for the last several decades. They needed to minimize disk seeks, we need to minimize memory fetches. An R-tree is a BV-hierarchy based on large fixed-size blocks, commonly used in disk based spatial processing. This talk shows how to adapt them for in-memory use, reaping major benefits with respect to cache behaviour, as well as SIMD processing, and more! |