Skip to content
  • Allison Vacanti's avatar
    Optimize the PointMap lookup in vtkExtractCells (12.8% speedup in D3). · 83d7e4cb
    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