[erlang-patches] improved orddict performance

Steve Vinoski <>
Thu Dec 19 15:41:54 CET 2013


Hi Björn, thanks for the explanation. Is there any more work I need to do
for this patch?

--steve


On Thu, Dec 19, 2013 at 6:23 AM, Björn Gustavsson <> wrote:

> On Mon, Sep 30, 2013 at 9:38 AM, Steve Vinoski <> wrote:
>
>> This patch improves the performance of some orddict functions by
>> reimplementing them using the lists module:
>>
>> https://github.com/erlang/otp/pull/91
>>
>> The commit message at the link above is very detailed and includes
>> performance measurements, so please read it to know more about the changes.
>>
>>
>>
> We like optimizations and we like simple, elegant
> code, so this patch has been a tricky one to review.
>
> In the end, we reached the conclusion that we like
> the improvements of orddict:from_list/1.
>
> We reject the optimizations of the other functions
> (is_key/2, fetch/2, find/2) for the following reasons:
>
> The optimization depends on the lists:keyfind/3 function
> being implemented as a BIF. That sort of
> optimization is fine in a specific application if you
> have measured and found that it really makes a difference;
> I would avoid it in other circumstances.
>
> All the compatibility code further destroys the
> elegance. Because of the compatibility code find/2 and
> is_key/2 do not get faster if the key is missing in
> the dictionary; that is unfortunate since you use find/2
> if you cannot be sure that the key is present and fetch/2
> if you know that the key is present.
>
> Because the internal representation of orddict is
> intentionally documented, an application can use
> lists:keyfind/3 directly if needed and it does not have
> to worry about about compatibility.
>
> Regarding the from_list/1 function, I am not sure that
> it is necessary to force a function_clause error.
> The original code could either crash in store/3 or in
> lists:foldl/3 when given illegal input. Also, from_list/1
> depends on lists:reverse/1 being implemented as a BIF; I
> think it would be more elegant to check and reverse at
> the same time:
>
> reverse_pairs([{_,_}=H|T], Acc) ->
>     reverse_pairs(T, [H|Acc]);
> reverse_pairs([], Acc) -> Acc.
>
> /Björn
>
> --
> Björn Gustavsson, Erlang/OTP, Ericsson AB
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-patches/attachments/20131219/71f00c38/attachment.html>


More information about the erlang-patches mailing list