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

[Sverker Eriksson]

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>:
>>
>>> 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> 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 list
>>>> erlang-questions@REDACTED
>>>> http://erlang.org/mailman/listinfo/erlang-questions
>>> _______________________________________________
>>> erlang-questions mailing list
>>> erlang-questions@REDACTED
>>> http://erlang.org/mailman/listinfo/erlang-questions
>>>
>>
>
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20170829/81a4dd82/attachment.htm>