<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, Oct 4, 2013 at 6:23 AM, Anthony Ramine <span dir="ltr"><<a href="mailto:n.oxyde@gmail.com" target="_blank">n.oxyde@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hello Steve,<br>
<br>
Btw did you measure a call to is_key/2 with a very large orddict not containing the given key? Wouldn't the short-circuiting due to ordering allow for better performances than using keyfind/3?<br></blockquote><div><br>
</div><div>Yes, this is definitely a scenario for which the R16B02 orddict can be much faster. Where the difference point lies depends on the terms involved. My posted tests don't include this scenario but instead measure the time it takes to find a key halfway through the list.</div>
<div><br></div><div>Perhaps instead of trying to reuse the lists module as it does now, which has obviously proven to be tricky and can't take advantage of list order, this patch should instead introduce either an ordered list find function into the lists module as a BIF, or go all the way and introduce a BIF ordered lists module and reimplement orddict on top of that. I'd be willing to give either of the latter a try if the OTP team feels they would be better approaches.</div>
<div> <br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Also please note there is nearly no way to totally address backwards-compatibility with lists functions, due to the short-circuiting:<br>

<br>
        orddict:is_key(b, [{a,1},{c,3},not_a_pair]).<br></blockquote><div><br></div><div>To handle this my latest (amended) commit does a check for pairs only up until it sees a key equal or greater than the key being requested.</div>
<div><br></div><div>--steve</div><div><br></div><div><br></div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Le 4 oct. 2013 à 02:58, Steve Vinoski a écrit :<br>
<div class="HOEnZb"><div class="h5"><br>
> OK, Anthony brought up yet another issue with my previous modified orddict, which is that if someone passes an improper list instead of an orddict, the new version acts differently than the old. Since the goal is backwards compatibility with improved performance, I've added a fourth commit that deals with these issues.<br>

><br>
> Notably, the original orddict, if passed an improper list or a list with elements that are not 2-tuples, will still work properly if the key being dealt with occurs before the problematic part of the list. For example, this works with the R16B02 orddict:<br>

><br>
> {ok,2} = orddict:find(1,[{1,2},{2,3,4}]).<br>
><br>
> I believe the latest commit addresses this and the previous comments, while still providing an orddict with improved performance:<br>
><br>
> <a href="https://github.com/vinoski/otp/commit/a261aae36f617e39c5e53dc8a16fa186e4c5830c" target="_blank">https://github.com/vinoski/otp/commit/a261aae36f617e39c5e53dc8a16fa186e4c5830c</a><br>
><br>
> Thanks again to Anthony and Richard for their excellent feedback.<br>
><br>
> --steve<br>
><br>
><br>
><br>
> On Wed, Oct 2, 2013 at 5:36 PM, Steve Vinoski <<a href="mailto:vinoski@ieee.org">vinoski@ieee.org</a>> wrote:<br>
> I've added a third commit to this branch to address new concerns and suggestions from Anthony Ramine and Richard Carlsson. I appreciate your help, guys.<br>
><br>
> Please refetch.<br>
><br>
> --steve<br>
><br>
><br>
> On Wed, Oct 2, 2013 at 3:02 AM, Steve Vinoski <<a href="mailto:vinoski@ieee.org">vinoski@ieee.org</a>> wrote:<br>
> I've added a new commit to this branch that addresses the concerns Anthony raised. Please refetch.<br>
><br>
> --steve<br>
><br>
><br>
> On Mon, Sep 30, 2013 at 5:32 AM, Steve Vinoski <<a href="mailto:vinoski@ieee.org">vinoski@ieee.org</a>> wrote:<br>
> Great feedback, Anthony -- thanks very much. Clearly there are more backward compatibility issues I need to address.<br>
><br>
> --steve<br>
><br>
><br>
> On Mon, Sep 30, 2013 at 4:00 AM, Anthony Ramine <<a href="mailto:n.oxyde@gmail.com">n.oxyde@gmail.com</a>> wrote:<br>
> Hello Steve,<br>
><br>
> Great patch, I added a few comments about some edge cases.<br>
><br>
> Regards,<br>
><br>
> Le 30 sept. 2013 à 09:38, Steve Vinoski a écrit :<br>
><br>
> > This patch improves the performance of some orddict functions by reimplementing them using the lists module:<br>
> ><br>
> > <a href="https://github.com/erlang/otp/pull/91" target="_blank">https://github.com/erlang/otp/pull/91</a><br>
> ><br>
> > The commit message at the link above is very detailed and includes performance measurements, so please read it to know more about the changes.<br>
> ><br>
> > --steve<br>
> > _______________________________________________<br>
> > erlang-patches mailing list<br>
> > <a href="mailto:erlang-patches@erlang.org">erlang-patches@erlang.org</a><br>
> > <a href="http://erlang.org/mailman/listinfo/erlang-patches" target="_blank">http://erlang.org/mailman/listinfo/erlang-patches</a><br>
><br>
> --<br>
> Anthony Ramine<br>
><br>
><br>
><br>
><br>
><br>
<br>
</div></div><span class="HOEnZb"><font color="#888888">--<br>
Anthony Ramine<br>
<br>
</font></span></blockquote></div><br></div></div>