• 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
..
_compute_caller.dart Loading commit data...
_compute_caller_error.dart Loading commit data...
_compute_caller_invalid_error.dart Loading commit data...
_compute_caller_invalid_message.dart Loading commit data...
_compute_caller_unsound_null_safety.dart Loading commit data...
_compute_caller_unsound_null_safety_error.dart Loading commit data...
assertions_test.dart Loading commit data...
basic_types_test.dart Loading commit data...
binding_test.dart Loading commit data...
bit_field_test.dart Loading commit data...
caching_iterable_test.dart Loading commit data...
capture_output.dart Loading commit data...
change_notifier_test.dart Loading commit data...
collections_test.dart Loading commit data...
consolidate_response_test.dart Loading commit data...
constants_test.dart Loading commit data...
covariant_templates_test.dart Loading commit data...
debug_test.dart Loading commit data...
diagnostics_json_test.dart Loading commit data...
diagnostics_test.dart Loading commit data...
double_precision_test.dart Loading commit data...
error_reporting_test.dart Loading commit data...
isolates_test.dart Loading commit data...
licenses_test.dart Loading commit data...
math_test.dart Loading commit data...
observer_list_test.dart Loading commit data...
persistent_hash_map_test.dart Loading commit data...
print_test.dart Loading commit data...
reassemble_test.dart Loading commit data...
serialization_test.dart Loading commit data...
service_extensions_test.dart Loading commit data...
stack_frame_test.dart Loading commit data...
stack_trace_test.dart Loading commit data...
synchronous_future_test.dart Loading commit data...