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

[Caragea Silviu]

Hello,

Thanks for clarification. I thought that in background erlang can see when
there is no other reference to the original map/list (for example in case
of accumulator inside a recursive fun) and will append to the original
object while updating the reference instead of making partial copy.

Silviu

On Tue, Aug 29, 2017 at 10:01 PM, Sverker Eriksson <
sverker.eriksson@REDACTED> wrote:

> Maps have two implementations depending on number of keys.
>
> Small maps (<= 32 keys) are basically a key-tuple and a value tuple.
> Updating the value of an existing key will copy the value-tuple
> while reusing the key-tuple.
>
> Large maps (> 32 keys) are basically a tree (HAMT).
> All nodes from the root to the one containing the key must be copied
> while all other nodes can be reused.
>
> /Sverker
>
> On 08/29/2017 08:41 PM, Caragea Silviu wrote:
>
> Hmm,
>
> Basically what you are saying is that any update over a map requires
> rebuilding of the entire map ? I doubt as time implementation seems so
> lame..
>
> Any way that we con confirm or not this theory ?
>
> Silviu
>
> On Tue, Aug 29, 2017 at 9:34 PM, Dmytro Lytovchenko <dmytro.lytovchenko@REDACTED> wrote:
>
>
>
> 2017-08-29 20:19 GMT+02:00 Dmitry Kolesnikov <dmkolesnikov@REDACTED> <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).
>
>
>
> - Dmitry
>
>
>
> On 29 Aug 2017, at 20.34, Caragea Silviu <silviu.cpp@REDACTED> <silviu.cpp@REDACTED> wrote:
>
> Hello,
>
> Having a map where the value of each element it's a list :
>
> #{ 1 => [], 2 => [], ... n => []}
>
> and you need to append elements in the list for a specific key, what's
>
> the most optimal way to do this without copying the lists and the map
> inside the VM lot of times ?
>
> Anything better than the following solution:
>
> append_element(Key, Value, Map) ->
>     case maps:find(Key, Map) of
>         {ok, V} ->
>             maps:put(Key, [Value | V], Map);
>         _ ->
>             maps:put(Key, [Value], Map)
>     end.
>
> Kind regards,
> Silviu
> _______________________________________________
> erlang-questions mailing listerlang-questions@REDACTED://erlang.org/mailman/listinfo/erlang-questions
>
> _______________________________________________
> erlang-questions mailing listerlang-questions@REDACTED://erlang.org/mailman/listinfo/erlang-questions
>
>
>
> _______________________________________________
> erlang-questions mailing listerlang-questions@REDACTED://erlang.org/mailman/listinfo/erlang-questions
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20170829/c0a66d6c/attachment.htm>