[erlang-patches] improved orddict performance

[Steve Vinoski]

On Fri, Oct 4, 2013 at 6:23 AM, Anthony Ramine <n.oxyde@REDACTED> wrote:

> 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?
>

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.

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.


> 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]).
>

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.

--steve




> 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 <vinoski@REDACTED> 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 <vinoski@REDACTED> 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 <vinoski@REDACTED> 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 <n.oxyde@REDACTED>
> 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
> > > erlang-patches@REDACTED
> > > http://erlang.org/mailman/listinfo/erlang-patches
> >
> > --
> > Anthony Ramine
> >
> >
> >
> >
> >
>
> --
> Anthony Ramine
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-patches/attachments/20131004/e8c38394/attachment.htm>