Scene Graph Memory Management

Abstract

Due to the growing disparity in performance between memory and processors, it is becoming increasingly important to consider the layout of applications’ working set data in memory to make effective use of cache memories and avoid performance bottlenecks from memory latency. This thesis studies the effects of data layout on scene graphs, a common data structure for organising scenes in graphics applications. Specifically, it studies (1) which way of packing nodes in memory yield the best performance for typical scene graph traversal patterns, and (2) proposes a novel technique for maintaining such a data layout in a scene graph in which nodes are added and deleted. Three data layouts — orderings for nodes, in which they are packed in memory — are evaluated for static scene graphs: a depth-first order, a breadth-first order, and a van Emde Boas layout. These are compared against a “naïve” layout, wherein nodes are individually allocated on the heap. Inasetbenchmarksrepresentingtypicaloperationsonscenegraphs,alldatalayouts yield similar performance, which is up to three times faster than the naïve layout for large scene graphs. They show very similar performance to the naïve layout for smaller scene graphs, however. Further, the dynamic memory management system presented in this thesis yields better performance than the naïve layout, in an evaluation simulating a highly dynamic scene-graph application, by up to a factor two for large scene graphs. A limitation with the approach, though, is that memory usage increases on average by a factor of 2.2 in the evaluation.