Page MenuHome

RNA: use binary search for enum identifier lookups (investigation)
Needs ReviewPublic

Authored by Campbell Barton (campbellbarton) on Aug 17 2021, 3:42 PM.

Details

Summary

Support using binary search for looking up enum identifiers.

Currently looking up identifiers (from Python arguments for example)
loops over each item comparing their string.

This patch adds a lazily initialized order field to the EnumProperty
that can be used for a binary search.

This is only used for static enums.

NOTE: if thread-safety is an issue the order data could be initialized at startup.
NOTE: a separate array could be used to perform a binary search on the value, this would be used when a buttons value for example needs to look-up the enum array.

This patch is to check if it's worthwhile to use a binary search for enum lookups.

In practice it's there is almost no real-world difference, loading key-maps is almost the same speed (under 1ms faster).

Accessing the last icon in the icon enum (with over 900 items) is over 70x faster in an isolated/artificial benchmark.

This would help prevent performance issues if larger enums are added in the future.

Diff Detail

Repository
rB Blender
Branch
TEMP-ENUM-BINARY-SEARCH (branched from master)
Build Status
Buildable 16476
Build 16476: arc lint + arc unit

Event Timeline

Campbell Barton (campbellbarton) requested review of this revision.Aug 17 2021, 3:42 PM
Campbell Barton (campbellbarton) created this revision.
Campbell Barton (campbellbarton) retitled this revision from RNA: use binary search for enum identifier lookups to RNA: use binary search for enum identifier lookups (investigate).Aug 17 2021, 4:08 PM
Campbell Barton (campbellbarton) edited the summary of this revision. (Show Details)
Campbell Barton (campbellbarton) retitled this revision from RNA: use binary search for enum identifier lookups (investigate) to RNA: use binary search for enum identifier lookups (investigation).
Campbell Barton (campbellbarton) edited the summary of this revision. (Show Details)
  • Always free stored order

Ignore PROP_INTERN_FREE_POINTERS flag when freeing order data

Campbell Barton (campbellbarton) edited the summary of this revision. (Show Details)

that's an interesting investigation, but personally I'd avoid adding extra complexity here unless there is a clear real use-case benefit?

And thread safety would be an issue indeed, we already have a few accessors in RNA that are not and need their own lock, would really, really avoid more cases like that.