[m-dev.] map.merge argument order

[Zoltan Somogyi]

On 09-Dec-2013, Paul Bone <paul at bone.id.au> wrote:
> Since in Mercury we don't have destructive update and usually have to
> reconstruct the parts of a tree that refer to the parts that actually
> changed.  Is there any significant extra cost to storing the size of the
> subtrees within each node?  (I don't expect to find current Mercury-specific
> benchmarks, but I wonder if some general benchmarks exist.)

No benchmarks, but yes, there is a significant cost, because

- every operation that returns a new map must allocate memory for and then
  fill in the size of the map;
- every operation that may change the size of the map must have all its levels
  reporting what the size change was;
- this will require extra parameter passing as well as extra calculations;
- every operation that does NOT care about the size must nevertheless
  navigate past it.

Whether the extra overhead is worth it depends on how frequently maps are
merged, compared to all the other operations. My guess is that it is worthwhile
ONLY if at least half of all operations on a map are merges; otherwise, most of
the maintenance of the map size will yield sizes that aren't actually used,
except to help calculate the NEXT size.

This is why we use set_tree234 far more than set_ctree234 in the compiler,
for example.

Zoltan.