[erlang-questions] optimal way to append an element in a list inside a map

[scott ribe]

> On Aug 29, 2017, at 12:34 PM, Dmytro Lytovchenko <dmytro.lytovchenko@REDACTED> wrote:
> 
> 
> 
> 2017-08-29 20:19 GMT+02:00 Dmitry Kolesnikov <dmkolesnikov@REDACTED>:
> Hello,
> 
> Premature optimisation is an evil ;-)
> 
> I would use the following syntax:
> ```
> append(Key, Value, Map) ->
>    List = case Map of
>       #{Key := Tail} ->
>          [Value | Tail];
>       _ ->
>          [Value]
>    end,
>    Map#{Key => List}.
> ```
> 
> Lists are not copied they are referenced. Maps… Hmm, I am not sure. I hope the implementation is smart enough to keep reference as well.
> 
> In BEAM any object which does not fit into a machine register (such as a list or a map) will be placed on heap and a pointer will be used instead. But prepending to a list will change the list pointer value (the pointer to list head will change, the remaining tail elements will not move and will not change). This requires writing the new head into the map value. And this will incur a map update, which most likely will rebuild the map. I'm almost sure that the optimization possibilities for this are very limited and are similar to tuple optimizations (i.e. works only at creation time).

Actually, it's perfectly possible to optimize the map insertion in a way analogous to the list prepending. A new root will be created, sharing old structure. If you think of some tree, then in fact new nodes are created from the leaf value you just added back up to the root, so not as cheap as list prepending, but way cheaper than copying the tree.

--
Scott Ribe
scott_ribe@REDACTED
(303) 722-0567