• Vyacheslav Egorov's avatar
    Use persistent hash map to store _inheritedWidgets (#107068) · 81300293
    Vyacheslav Egorov authored
    * Use persistent hash map to store _inheritedWidgets
    
    Instead of using a HashMap and copying it down the tree
    which leads to quadratic time and space complexity
    use a persistent data structure which can amortize
    the cost by sharing parts of the structure.
    
    The data shows HAMT based PersistentHashMap to be
    5-10x faster for building _inheritedWidgets and
    considerably more space effecient (e.g. bringing
    amount of memory allocated when constructing
    _inheritedWidgets in a tree with 150 InheritedWidget
    down to 70Kb from 970Kb).
    
    PersistentHashMap is slower than HashMap for
    access: 2-3x in relative terms, but in absolute
    terms we are only talking about ~0.2ns slow down
    per access and various app benchmarks we run have
    have not revealed any significant regressions.
    81300293
foundation.dart 1.53 KB