[erlang-patches] improved orddict performance

Anthony Ramine <>
Fri Oct 4 12:23:41 CEST 2013


Hello Steve,

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?

Also please note there is nearly no way to totally address backwards-compatibility with lists functions, due to the short-circuiting:

	orddict:is_key(b, [{a,1},{c,3},not_a_pair]).

Le 4 oct. 2013 à 02:58, Steve Vinoski a écrit :

> 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.
> 
> 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:
> 
> {ok,2} = orddict:find(1,[{1,2},{2,3,4}]).
> 
> I believe the latest commit addresses this and the previous comments, while still providing an orddict with improved performance:
> 
> https://github.com/vinoski/otp/commit/a261aae36f617e39c5e53dc8a16fa186e4c5830c
> 
> Thanks again to Anthony and Richard for their excellent feedback.
> 
> --steve
> 
> 
> 
> On Wed, Oct 2, 2013 at 5:36 PM, Steve Vinoski <> wrote:
> 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.
> 
> Please refetch.
> 
> --steve
> 
> 
> On Wed, Oct 2, 2013 at 3:02 AM, Steve Vinoski <> wrote:
> I've added a new commit to this branch that addresses the concerns Anthony raised. Please refetch.
> 
> --steve
> 
> 
> On Mon, Sep 30, 2013 at 5:32 AM, Steve Vinoski <> wrote:
> Great feedback, Anthony -- thanks very much. Clearly there are more backward compatibility issues I need to address.
> 
> --steve
> 
> 
> On Mon, Sep 30, 2013 at 4:00 AM, Anthony Ramine <> wrote:
> Hello Steve,
> 
> Great patch, I added a few comments about some edge cases.
> 
> Regards,
> 
> Le 30 sept. 2013 à 09:38, Steve Vinoski a écrit :
> 
> > 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.
> >
> > --steve
> > _______________________________________________
> > erlang-patches mailing list
> > 
> > http://erlang.org/mailman/listinfo/erlang-patches
> 
> --
> Anthony Ramine
> 
> 
> 
> 
> 

-- 
Anthony Ramine



More information about the erlang-patches mailing list