Use persistent hash map to store _inheritedWidgets #107068
Conversation
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.
flutter-dashboard
bot
added
the
framework
|
I addressed @dnfield's comments and did some dart2js directed optimizations, mainly moved away from implicit This brings |
goderbauer
left a comment
goderbauer
left a comment
There was a problem hiding this comment.
(not a full review yet, will come back to this)
| // Use of this source code is governed by a BSD-style license that can be | ||
| // found in the LICENSE file. | ||
|
|
||
| /// A collection of key/value pairs, from which you can retrieve a value |
There was a problem hiding this comment.
There was a problem hiding this comment.
This sentence is copied from Map dartdoc. I am open to suggestions on how to rewrite it better.
There was a problem hiding this comment.
"A collection of key/value pairs, from which a value can be retrieved using its associated key."?
| /// | ||
| /// Note: unlike [Map] this class does not support `null` as a key value and | ||
| /// implements only a functionality needed for a specific use case at the | ||
| /// core of the framework. |
There was a problem hiding this comment.
Is this still general purpose enough to expose as public API?
There was a problem hiding this comment.
No, I would really like to avoid that, but I could not figure out how. It does not seem to be possible. Any suggestions?
Originally I just wanted to reference it as package:flutter/src/foundation/persistent_hash_map.dart making it clear that it is not a public API - but there is a lint check that prevents this sort of stuff.
Alternative is to put it in widgets/ and use just there - but it felt misplaced there (and I am not sure that tests would be able to import package:flutter/src/widgets/persistent_hash_map.dart
Any idea on how to approach this?
There was a problem hiding this comment.
The current approach is probably the best one to allow for testability.
goderbauer
left a comment
goderbauer
left a comment
There was a problem hiding this comment.
The implementation looks good to me. I do have a question about the benchmark data: Are those just coming from artificial benchmarks or has it been verified with some "real-world" app (e.g. OpenPay) that this actually gives us a real and measurable performance benefit and that the slower lookups don't actually end up hurting overall performance?
| // Use of this source code is governed by a BSD-style license that can be | ||
| // found in the LICENSE file. | ||
|
|
||
| /// A collection of key/value pairs, from which you can retrieve a value |
There was a problem hiding this comment.
"A collection of key/value pairs, from which a value can be retrieved using its associated key."?
| /// | ||
| /// Note: unlike [Map] this class does not support `null` as a key value and | ||
| /// implements only a functionality needed for a specific use case at the | ||
| /// core of the framework. |
There was a problem hiding this comment.
The current approach is probably the best one to allow for testability.
| /// * [Clojure's `PersistentHashMap`](https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentHashMap.java). | ||
| /// | ||
| class PersistentHashMap<K extends Object, V> { | ||
| /// An an empty hash map. |
There was a problem hiding this comment.
nit: replace the first "An" with "Creates"?
| final _TrieNode newNode = node.put( | ||
| bitIndex + _TrieNode.hashBitsPerLevel, key, keyHash, value); |
There was a problem hiding this comment.
nit: (here and elsewhere): Flutter style wants the line of the opening and closing parenthesis to have to same indentation. Either put this all on one line or format it with a trailing comma (each param on a separate line followed by the parenthesis on the next line.
You can see the data I have in go/flutter-persistent-hash-map-for-inherited-widgets - its a mix of real world data and microbenchmarks. (heads up: I am on vacation for the next two weeks) |
Thanks, that was a helpful read. I think this looks promising. Let's give it a try and keep an eye on the benchmarks after this is merged. LGTM after doc and style comments are addressed. |
|
@goderbauer I went ahead and addressed your doc/style nits so we can try to get this landed. @mraleph is going to be unavailable again for a week or two and I don't want this to get lost in the mean time. @mraleph when you get back if there any further concerns we can try to address them in follow up. |
dnfield
added
the
autosubmit
|
Sounds good. Thanks @dnfield. |
* 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.
8 participants
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 amortise
the cost by sharing parts of the structure.
The data shows HAMT based
PersistentHashMapto be5-10x faster for building
_inheritedWidgetsandconsiderably more space efficient (e.g. bringing
amount of memory allocated when constructing
_inheritedWidgetsin a tree with 150InheritedWidgetdown 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.
Pre-launch Checklist
///).If you need help, consider asking for advice on the #hackers-new channel on Discord.