Skip to content

perf improvements to categorical colors

Implementation Details

vtkScalarsToColors uses an idiosyncratic mechanism for matching scalar values to indexes when IndexedLookup is enabled. The changes in thus MR preserve that behavior, however minimizing the N^2 lookups which caused extremely poor performance for non-trivial number of indexed colors.

Old behavior

The old implementation has several oddities:

  1. Based on whether SetAnnotation(...) or SetAnnotations(...) was called first (or after any ResetAnnotations() call), the internal representation used to store annotation values could change. For former, a vtkVariantArray was used, for latter an array of the same type as passed in as argument was used. The oddity if after calling SetAnnotations(..), if one used SetAnnotation(...) to add/modify an annotation, you would end up with type conversions in some cases based on order of initial API use!!!
  2. Indexed lookup relies on first obtaining an index for annotated value. This index is simply the order in which that annotated value was first specified in SetAnnotation(..) or SetAnnotations(..) call. The index lookup used vtkVariant's == operator. If either of the operands was float or double, then == operator converts both to float or double and compares otherwise does a string value compare or int64 value compare. This "fuzziness" ensures that 1 (int) matches 1.0 (double) and vice-versa. The performance bottleneck was that since the variant couldn't directly be used as a key for a map (to allow for fuzzy matches), the implementation used a list and use sequential compares to lookup indexes resulting in a N**2 operation when mapping scalars in an array with non-trivial annotations.

New implementation

  • Instead of a list, we now use two internal std::unordered_maps with custom hash function to store the mapping from an annotated value to its index. The first map (Indices) directly stores the annotated value as a variant. If the annotated value is numeric than its double converted value is stored the second map (DoubleIndices).
  • The custom hash function, create a hash by calling std::hash<..>() on converted 64bit signed (or unsigned) int. float, double and string values are directly hashed using corresponding std::hash<..>().
  • When looking up an annotated value's index, we first look at the Indices map, if found, we have an exact match and we return that index. * For numeric values, we then convert the annotated value to double and lookup in the DoubleIndices map. This emulates the vtkVariant's == operator behavior when a double or float value was present in either of the operands.
  • Using unordered_map instead of a list to store the value/index mapping speeds up the lookup considerably. We further improve performance by storing a local cache of value to index mapping in vtkLookupTableIndexedMapData when mapping multiple values in an array. This avoids repeated vtkVariant conversions, improving performance.
  • vtkLookupTableIndexedMapData has also been updated to use vtkSMPTools to accelerator for-loops when multithreaded backend is being used. The change has no major impact when using sequential backend.


Some perf results:

  1. TestCategoricalColors without any changes to non-test code. (note: the test still has modifications in this MR to add this performance test)
(   0.000s) [main thread     ]TestCategoricalColors.c:153   INFO| { With Indexed Lookup
(   0.811s) [main thread     ]TestCategoricalColors.c:83    INFO| .   { MapScalars
( 270.199s) [main thread     ]TestCategoricalColors.c:83    INFO| .   } 269.388 s: MapScalars
( 270.201s) [main thread     ]TestCategoricalColors.c:153   INFO| } 270.200 s: With Indexed Lookup
  1. TestCategoricalColors with Changes + Sequential threading model:
(   0.000s) [main thread     ]TestCategoricalColors.c:153   INFO| { With Indexed Lookup
(   0.819s) [main thread     ]TestCategoricalColors.c:83    INFO| .   { MapScalars
(   9.229s) [main thread     ]TestCategoricalColors.c:83    INFO| .   } 8.410 s: MapScalars
(   9.231s) [main thread     ]TestCategoricalColors.c:153   INFO| } 9.230 s: With Indexed Lookup
  1. TestCategoricalColors with Changes + TBB:
(   0.001s) [main thread     ]TestCategoricalColors.c:153   INFO| { With Indexed Lookup
(   0.846s) [main thread     ]TestCategoricalColors.c:83    INFO| .   { MapScalars
(   6.756s) [main thread     ]TestCategoricalColors.c:83    INFO| .   } 5.909 s: MapScalars
(   6.758s) [main thread     ]TestCategoricalColors.c:153   INFO| } 6.757 s: With Indexed Lookup
Edited by Utkarsh Ayachit

Merge request reports