[erlang-bugs] Bug in gb_trees ? Integer key not found.

[Matthias Lang]

On Monday, May 09, Ulf Wiger wrote:
> 
> On 9 May 2011, at 22:01, PAILLEAU Eric wrote:
> 
> >> T=gb_trees:from_orddict([{10,a1},{15,a2},{5,a3},{7,a4}]).
> > {4,{5,a3,{15,a2,{10,a1,nil,nil},nil},{7,a4,nil,nil}}}
> > 
> >> gb_trees:lookup(10,T).
> > none

> The argument is not an orddict.

The above was the important part of your mail, but this made me wonder:

> The reason for the function is speed, obviously, and verifying that
> the list is in fact ordered would defeat the speed advantage.

Checking that the input is ordered should be cheap since you have to
traverse the whole input anyway. Here's gb_trees:from_orddict:

  from_orddict(L) ->
    S = length(L),
    {S, balance_list(L, S)}.

replacing the length() call with one which also checks input ordering
is easy, so I did that. I measured a 5% slowdown on long (1M)
lists. I'd live with that, but maybe not everyone would.

I then took a look at "who uses gb_trees:from_orddict anyway?". In
OTP, it's mostly the beam compiler itself. This code pops up a few
times:

  gb_trees:from_orddict(lists:sort(L))

It feels like there's a function missing in gb_trees, one which inserts a
list of tuples which aren't sorted (but do have unique keys).

Matt