<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Mon, Sep 30, 2013 at 9:38 AM, Steve Vinoski <span dir="ltr"><<a href="mailto:vinoski@ieee.org" target="_blank">vinoski@ieee.org</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr">This patch improves the performance of some orddict functions by reimplementing them using the lists module:<div>
<br></div><div><a href="https://github.com/erlang/otp/pull/91" target="_blank">https://github.com/erlang/otp/pull/91</a><br>
</div><div><br></div><div>The commit message at the link above is very detailed and includes performance measurements, so please read it to know more about the changes.</div><span class=""><font color="#888888"><div><br>
</div><div><br></div></font></span></div></blockquote></div><div class="gmail_extra"><br></div><div class="gmail_extra"><div class="gmail_extra">We like optimizations and we like simple, elegant</div><div class="gmail_extra">
code, so this patch has been a tricky one to review.</div><div class="gmail_extra"><br></div><div class="gmail_extra">In the end, we reached the conclusion that we like</div><div class="gmail_extra">the improvements of orddict:from_list/1.</div>
<div class="gmail_extra"><br></div><div class="gmail_extra">We reject the optimizations of the other functions</div><div class="gmail_extra">(is_key/2, fetch/2, find/2) for the following reasons:</div><div class="gmail_extra">
<br></div><div class="gmail_extra">The optimization depends on the lists:keyfind/3 function</div><div class="gmail_extra">being implemented as a BIF. That sort of</div><div class="gmail_extra">optimization is fine in a specific application if you</div>
<div class="gmail_extra">have measured and found that it really makes a difference;</div><div class="gmail_extra">I would avoid it in other circumstances.</div><div class="gmail_extra"><br></div><div class="gmail_extra">All the compatibility code further destroys the</div>
<div class="gmail_extra">elegance. Because of the compatibility code find/2 and</div><div class="gmail_extra">is_key/2 do not get faster if the key is missing in</div><div class="gmail_extra">the dictionary; that is unfortunate since you use find/2</div>
<div class="gmail_extra">if you cannot be sure that the key is present and fetch/2</div><div class="gmail_extra">if you know that the key is present.</div><div class="gmail_extra"><br></div><div class="gmail_extra">Because the internal representation of orddict is</div>
<div class="gmail_extra">intentionally documented, an application can use</div><div class="gmail_extra">lists:keyfind/3 directly if needed and it does not have</div><div class="gmail_extra">to worry about about compatibility.</div>
<div class="gmail_extra"><br></div><div class="gmail_extra">Regarding the from_list/1 function, I am not sure that</div><div class="gmail_extra">it is necessary to force a function_clause error.</div><div class="gmail_extra">
The original code could either crash in store/3 or in</div><div class="gmail_extra">lists:foldl/3 when given illegal input. Also, from_list/1</div><div class="gmail_extra">depends on lists:reverse/1 being implemented as a BIF; I</div>
<div class="gmail_extra">think it would be more elegant to check and reverse at</div><div class="gmail_extra">the same time:</div><div class="gmail_extra"><br></div><div class="gmail_extra">reverse_pairs([{_,_}=H|T], Acc) -></div>
<div class="gmail_extra">    reverse_pairs(T, [H|Acc]);</div><div class="gmail_extra">reverse_pairs([], Acc) -> Acc.</div><div><br></div></div>/Björn<br clear="all"><div><br></div>-- <br><div dir="ltr">Björn Gustavsson, Erlang/OTP, Ericsson AB<br>
</div>
</div></div>