[go-nuts] Sorted Set

[Jonathan Wills]

I needed a sorted set, so I made a B-tree.  I also wanted the type-safety of generics, so I used gotgo (Thanks David Roundy).  When/if generics are added to go I will probably generify this, but for now I just wanted to make it available to anyone that needed something like this.  The code could be cleaner and faster, but it works.  It is available at git://github.com/runningwild/go-btree.git.

The BTree class (compiled for type T) is created like this:

tree := NewTree(func (a,b T) bool { return a < b })

and it conforms to the SortedSet interface:

Front() T

Insert(T) bool

Remove(T) bool

Contains(T) bool

Len() int

Data() <-chan T

Just to see how it stacks up against stl, here is a quick comparison I did vs. stl's set class, all times are in seconds.

Stl's set<int>, compiled using -O3

1.073: 1000000 Unique Inserts

0.970: 1000000 Repeated Inserts

0.827: 500000 Unique Deletes

0.528: 500000 Repeated Deletes

0.893: 1000000 Queries

my BTree (int), compiled using 6g (had trouble getting gccgo to compile otherwise I would have tried that too)

1.063: 1000000 Unique Inserts

0.910: 1000000 Repeated Inserts

1.272: 500000 Unique Deletes

1.076: 500000 Repeated Deletes

0.447: 1000000 Queries

On smaller input sets stl wins on all of those benchmarks, but I was pretty happy with this.  It's also worth noting that (at least for a set of ints) the btree takes up about 40% less memory.

[Andrew Gerrand]

Interesting benchmarks! Nice to see Go winning some of them =)

[Paolo 'Blaisorblade' Giarrusso]

On 14 Mag, 00:50, Andrew Gerrand <a...@golang.org> wrote:
> Interesting benchmarks! Nice to see Go winning some of them =)
>

Thanks for providing this.

I think STL uses a RB-tree, which is "equivalent" to a BTree with node
size varying between 2 and 4 (see Sedgewick - a red node joins black
nodes into a 2-3-4 tree node). Although the delete implementation is
not equivalent in the two algorithms.

Can you benchmark the BTree against itself with node size varying
between 2 and 4? A cross-language and cross-algorithm comparison is
quite difficult to analyze. I think your BTree may be faster here
because it has more spatial locality than binary trees (beyond a
smaller tree depth). And surely that's why it's more compact.
I wonder about the slower delete performance - is this expected from
the algorithm?
Bye

[Jonathan Wills]

Thanks for providing this.

I think STL uses a RB-tree, which is "equivalent" to a BTree with node
size varying between 2 and 4 (see Sedgewick - a red node joins black
nodes into a 2-3-4 tree node). Although the delete implementation is
not equivalent in the two algorithms.

The red-black tree that stl uses has one key per node and up to two children per node.  This has the benefit that iterators in the tree are never invalidated by inserts and deletes, except a delete of a node that an iterator is pointing at.  My implementation actually assumes an even number of keys per node, so I can't even emulate this.  This restriction is probably unnecessary, but I would have to tweak a few things to make it work.

 

Can you benchmark the BTree against itself with node size varying
between 2 and 4? A cross-language and cross-algorithm comparison is
quite difficult to analyze. I think your BTree may be faster here
because it has more spatial locality than binary trees (beyond a
smaller tree depth). And surely that's why it's more compact.
I wonder about the slower delete performance - is this expected from
the algorithm?
Bye

The comparison was just to show that there was a sorted set in go (6g) that was in the same ballpark as one in c++ (g++ -O3).  The locality that BTrees offer is certainly where the extra speed comes from, and the slow deletes is certainly because of my implementation.  I haven't implemented a BTree before and I tried to use wikipedia as a guide, which was a mistake (because it's not entirely correct).  I also tried to avoid storing a parent pointer in each node because I could do all the balancing I needed without them, but I realize now that was a bad idea.  In the end what I came up with was probably sub-par, but functional and not too bad, which is why I posted it.

Here are the benchmarks for different numbers of keys per node, again for a BTree of ints.

(seconds)                 1-2    2-4    4-8    8-16   16-32  32-64  64-128 128-256

1000000  Unique Inserts   4.587  3.784  1.818  1.227  0.987  0.900  0.848  0.889    

1000000  Repeated Insert  3.427  3.089  1.325  1.023  0.848  0.787  0.698  0.706    

 500000  Unique Delete    4.200  2.277  1.816  1.414  1.246  1.123  1.036  1.076    

 500000  Repeated Deletes 3.816  1.901  1.506  1.229  1.038  0.962  0.845  0.855    

1000000  Queries          0.716  0.623  0.550  0.515  0.463  0.458  0.408  0.414    

(ms)

10000  Unique Inserts    28.339 13.345  7.523  6.516  5.656  5.546  5.102  5.313    

10000  Repeated Inserts  16.056  4.675  4.126  3.976  3.737  3.701  3.262  3.297    

 5000  Unique Deletes    14.844 12.128 10.002  9.566  8.771  8.580  7.961  8.274    

 5000  Repeated Deletes  10.676  8.937  8.655  8.234  7.393  7.694  6.720  7.019    

10000  Queries           4.111   3.687  3.417  3.295  2.835  2.920  2.550  2.583    

I repeated this for smaller sizes and the optimum maximum number of keys per node was always either 64 or 128, even for much smaller benchmarks.

[Sergejs Melderis]

As an exercise I implemented RB-tree.
Here is the source code http://github.com/serega/go-rbtree

I tested it with the same Jonathan's benchmark.
Here are the results on my machine:

RB-tree(int)
Using input size 1000000 and averaged over 10 runs.
1.275: 1000000 Unique Inserts
0.686: 1000000 Repeated Inserts
0.493: 500000 Unique Deletes
0.353: 500000 Repeated Deletes
0.250: 1000000 Queries

Jonothan's BTree(int)
Using input size 1000000 and averaged over 10 runs.
0.860: 1000000 Unique Inserts
0.709: 1000000 Repeated Inserts
1.074: 500000 Unique Deletes
0.915: 500000 Repeated Deletes
0.395: 1000000 Queries

Stl's set<int>
Using input size 1000000 and averaged over 10 runs.
0.859: 1000000 Unique Inserts
0.793: 1000000 Repeated Inserts
0.711: 500000 Unique Deletes
0.422: 500000 Repeated Deletes
0.697: 1000000 Queries

The inserts in RB-tree are slower, but the queries are faster then in both BTree and stl set.
Query and insert operations is the same algorithm, except that insert operation
allocates new nodes, and does the red-black tree dancing. So, I guess, the allocation
of new nodes slows down the insert operation.

Sergey.

[Peter Williams]

Have you tried Sedgewick's Left Leaning Red Black Trees

<http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf>

which is his latest contribution to the topic? Their implementation is
a good deal simpler than the older models. It would be interesting to
see how it compares with the above trees.

Peter

[Serge Hulne]

- Very impressive !

- Can be handy to store and retrieve efficiently objects of any type
which simply satisfy a given interface.

- It would be interresting to have a hash_map which works on the same
principle: Store objects of any type which satisfy a given interface,
in that case: objects which can be tied to a : hash ( *T) () int
method (I found one on Github, but the performance was not optimized,
according to its author, it was just an academic exercice).

- The motivation being that, for large sets of data sets, hasmaps
perform faster that Trees, (since they do not involve so many
comparisons).

Serge.

[roger peppe]

On 19 June 2010 02:44, Peter Williams <pwil...@gmail.com> wrote:
> <http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf>
>
> which is his latest contribution to the topic?  Their implementation is a
> good deal simpler than the older models.  It would be interesting to see how
> it compares with the above trees.

it looks plausible, but the algorithm described in the paper
is very buggy. i kinda got it to work eventually, but
it's not obvious, and i'm not sure it was really right.

[Marcin 'Qrczak' Kowalczyk]

2010/6/19 roger peppe <rogp...@gmail.com>:

I don't remember any bugs (except that fixUp() is not defined
explicitly, you have to infer it from the text and other code). I've
implemented LLRB, in the bottom-up 2-3 flavor (not in Go).

Here is Sedgewick's presentation which helps:
<http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf>

--
Marcin Kowalczyk

[roger peppe]

it's a couple of years ago now, and i can't remember
the details, but i mentioned a few on this page:
http://www.reddit.com/r/programming/comments/69tpu/robert_sedgwicks_left_leaning_redblack_trees

to be fair, i did get another version in actual code form,
but i seem to remember that wasn't quite right either.

i'll have a rummage around and see if i can find
the test cases that broke it.

but this is veering off topic, i'm afraid.

[Eric Eisner]

Jumping on the bandwagon, I implemented skip lists.
Source available at http://bitbucket.org/ede/go-skiplist

Using the same set of benchmarks against the original btree, inserts
are a lot slower, deletes are a lot faster, queries a bit faster. As a
testament to the quality of the rand package, inserts only get a
little bit faster when the PRNG isn't called.

skiplist.go
Using input size 100000 and averaged over 5 runs.
0.615: 100000 Unique Inserts
0.803: 100000 Repeated Inserts
0.168: 50000 Unique Deletes
0.148: 50000 Repeated Deletes
0.134: 100000 Queries

btree.go
Using input size 100000 and averaged over 5 runs.
0.282: 100000 Unique Inserts
0.540: 100000 Repeated Inserts
0.424: 50000 Unique Deletes
0.364: 50000 Repeated Deletes
0.166: 100000 Queries

-Eric

On Jun 18, 6:13 pm, Sergejs Melderis <sergey.melde...@gmail.com>

wrote:
> As an exercise I implementedRB-tree.

> Here is the source codehttp://github.com/serega/go-rbtree

>
> I tested it with the same Jonathan's benchmark.
> Here are the results on my machine:
>
> RB-tree(int)
> Using input size 1000000 and averaged over 10 runs.
> 1.275:  1000000 Unique Inserts
> 0.686:  1000000 Repeated Inserts
> 0.493:  500000  Unique Deletes
> 0.353:  500000  Repeated Deletes
> 0.250:  1000000 Queries
>
> Jonothan's BTree(int)
> Using input size 1000000 and averaged over 10 runs.
> 0.860:  1000000 Unique Inserts
> 0.709:  1000000 Repeated Inserts
> 1.074:  500000  Unique Deletes
> 0.915:  500000  Repeated Deletes
> 0.395:  1000000 Queries
>
> Stl's set<int>
> Using input size 1000000 and averaged over 10 runs.
> 0.859:  1000000 Unique Inserts
> 0.793:  1000000 Repeated Inserts
> 0.711:  500000  Unique Deletes
> 0.422:  500000  Repeated Deletes
> 0.697:  1000000 Queries
>

> The inserts inRB-treeare slower, but the queries are faster then in both BTree and stl set.

> Query and insert operations is the same algorithm, except that insert operation

> allocates new nodes, and does the red-blacktreedancing. So, I guess, the allocation