• 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
Name
Last commit
Last update
..
lib Loading commit data...
test Loading commit data...
test_fixes Loading commit data...
test_private Loading commit data...
test_profile Loading commit data...
test_release Loading commit data...
LICENSE Loading commit data...
README.md Loading commit data...
analysis_options.yaml Loading commit data...
build.yaml Loading commit data...
dart_test.yaml Loading commit data...
pubspec.yaml Loading commit data...