[erlang-patches] improved orddict performance

[Björn Gustavsson]

On Mon, Sep 30, 2013 at 9:38 AM, Steve Vinoski <vinoski@REDACTED> 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/9053c464/attachment.htm>