-
Allison Vacanti authored
Profiling reveals that most of the time executing D3 is spent in vtkExtractCells::findInSortedList, which implements a binary search of a sorted list of point ids. When testing with lucy.ply (14M points), this map requires ~25 random memory accesses every lookup. Since the algorithm is mapping cell ids, it's usually the case that the requested point ids will be close together in the point map array. This patch exploits this behavior by caching the input/output ids of the last lookup and using this information to reduce the number of random memory access. By knowing the properties of the list (unique, sorted) and the relationship between the inputs and outputs, the query can be restricted to a much smaller subset of the id map array. This also uses the CPU cache more efficiently, since less of the array needs to be traversed.
83d7e4cb