immutable lists/maps with faster than linear time append/mutation about built_collection.dart HOT 3 CLOSED

Maybe--I'd love to see benchmarks.

Note that built_value is already optimized so that updating a deeply nested structure of objects is O(length of path from modification to root), and not O(size of data structure).

from built_collection.dart.

Thanks John. Indeed, the idea was to keep the possibility of using such data structures open.

One reason we haven't looked at it yet is we don't really have a good use case to benchmark with.

The "addItem" example might look like a problem, but so far it's always been in UI code where adding an item corresponds to a click and subsequent redraw. In that case the rendering time is likely to be far higher than the list copy, so it's not a big concern. For larger updates that are caused by a single click, you're supposed to use builders rather than repeatedly rebuilding.

One other direction that might be worth exploring is based on the idea that in the most common use of 'rebuild', the original list may not ever be used again. So for "addItem" we could do this instead:

1. update the old BuiltList to say "I'm the new BuiltList minus the last item"; this is expensive if it's used, but we assume it probably won't be
2. create the new BuiltList by stealing the underlying list from the first and adding the item

Then, if the old list is never used again, we do nothing extra, and it's almost as fast as a mutable list to update, and as fast as a mutable list for reading. If the old list is used again then extra work is needed to either implement the list interface over a "BuiltList minus last item", or we just copy the underlying list and actually remove the last item.

In order to pursue this line of thought we'd also need a good use case to benchmark with.

So, bottom line is, let's find some code that actually wants fast immutable data structures :) and then, yes, please do go ahead and prototype something, I'd love to see it.

from built_collection.dart.

What about use cases like flutter_redux? Things like HAMT would be quite helpful when one want to update/diff a large amount of data between Flutter frames.

from built_collection.dart.