[Haskell-cafe] Data.IntMap union complexity

[wren ng thornton]

Evan Laforge <qdunkan at gmail.com> wrote:
 > I've wondered if it's faster to insert many keys by successive
 > insertion, or by building another map and then unioning, and likewise
 > with deletion.  I eventually decided on successive, thinking a log n
 > build + merge is going to be slower than a m*log n for successive
 > insertion.  So I wound up with:

If you don't already have the keys in a map, I don't think you gain much 
by building a map and then merging rather than just inserting them 
directly. It will produce extra garbage (unless you have some interest 
in the map you're building), and you have to make the same spine 
traversals in building the map as you would have inserting into the 
larger map (and then you have to traverse the larger map during 
merging). But again, thanks to Criterion, benchmarking is cheap and 
easy. No need to believe in the folklore or opinions of others :)

Though, if the set of keys to be added is very large, then the 
build+merge approach would allow you to parallelize the building of the 
map (split the key set in "half" and build maps for each set, recursing 
as necessary; then either merge the new maps together before merging 
with the target map, or just merge them with the target map in serial).

-- 
Live well,
~wren