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