New Balanced Search Tree Implementation

New Balanced Search Tree Implementation

[Benjamin Purcell]

I have written a binary search tree C library for Plan 9.  It contains
implementations of both left leaning red-black trees and AVL trees.
In short, you create an AVL tree with

Bsttree *t = bstcreate(AVL, cmp);

and an LLRB tree with

Bsttree *t = bstcreate(LLRB, cmp);

Cmp is a comparison function.  All other implementation details are
hidden from the user.

I intend to replace libavl with this library for the following reasons
(details can be found below):

1. You get a choice of BST with a single API.
2. The AVL implementation is much faster.
3. The AVL implementation is smaller and less complicated.
4. The API is easier to use.

Item 1. is self-explanatory.

Item 2.
Measurements of the new AVL implementation against the old one shows
that on average:
Insertion is 21.9% faster.
Deletion is 23.9% faster.
Lookup is 14.95% faster.
10 trials were conducted on random keys.  Sequential keys show similar
results.

Item 3.
As for code size, the new AVL implementation plus walk code -- which
is shared with the LLRB tree -- comes to 362 source lines of idiomatic
C. The old AVL implementation 436 lines.  The old implementation also
contains more functions, and calls many of them unnecessarily.
Despite the fact that it has more functions, the individual functions
themselves are more complicated.

Item 4.
The AVL implementation's api has the following signatures expressed as
abstract types:

Avl *(*)(Avltree*, Avl*);
Avl *(*)(Avltree*, Avl*, int);
Avl *(*)(Avlwalk*);
Avltree *(*)(int(*)(Avl*, Avl*));
Avlwalk *(*)(Avltree*);
void (*)(Avltree*, Avl*, Avl**);
void (*)(Avlwalk*);

Duplicate signatures have been removed in the above.  The new bst
implementation has the following de-duped signatures:

Bst *(*)(Bsttree*);
Bsttree *(*)(int, int(*cmp)(Bst*, Bst*));
Channel *(*)(Bsttree*, Bst*, Bst*, int);

but maintains the same functionality.  Which API would you rather use?

The code can be found at the following locations:

/n/contrib/spew/libbst
https://bitbucket.org/spewspews/libbst
https://github.com/spewspews/libbst

A full man page is include and various tests are included in src/tests
including measurements of AVL vs. LLRB, and the new AVL implementation
against the old.

If there are no objections I would like to remove libavl and add
libbst instead.  Libavl has no usages in the source tree.  If anyone tries
to compile a libavl program then tough.  There will be a better
implementation available and we can always keep it available in
contrib or extra.

Spew

Re: [9front] New Balanced Search Tree Implementation

[Mehmet Erol Sanliturk]

[-- Attachment #1: Type: text/plain, Size: 2900 bytes --]

On Sun, Dec 11, 2016 at 10:30 PM, Benjamin Purcell <benjapurcell@gmail.com>
wrote:

> I have written a binary search tree C library for Plan 9.  It contains
> implementations of both left leaning red-black trees and AVL trees.
> In short, you create an AVL tree with
>
> Bsttree *t = bstcreate(AVL, cmp);
>
> and an LLRB tree with
>
> Bsttree *t = bstcreate(LLRB, cmp);
>
> Cmp is a comparison function.  All other implementation details are
> hidden from the user.
>
> I intend to replace libavl with this library for the following reasons
> (details can be found below):
>
> 1. You get a choice of BST with a single API.
> 2. The AVL implementation is much faster.
> 3. The AVL implementation is smaller and less complicated.
> 4. The API is easier to use.
>
> Item 1. is self-explanatory.
>
> Item 2.
> Measurements of the new AVL implementation against the old one shows
> that on average:
> Insertion is 21.9% faster.
> Deletion is 23.9% faster.
> Lookup is 14.95% faster.
> 10 trials were conducted on random keys.  Sequential keys show similar
> results.
>
> Item 3.
> As for code size, the new AVL implementation plus walk code -- which
> is shared with the LLRB tree -- comes to 362 source lines of idiomatic
> C. The old AVL implementation 436 lines.  The old implementation also
> contains more functions, and calls many of them unnecessarily.
> Despite the fact that it has more functions, the individual functions
> themselves are more complicated.
>
> Item 4.
> The AVL implementation's api has the following signatures expressed as
> abstract types:
>
> Avl *(*)(Avltree*, Avl*);
> Avl *(*)(Avltree*, Avl*, int);
> Avl *(*)(Avlwalk*);
> Avltree *(*)(int(*)(Avl*, Avl*));
> Avlwalk *(*)(Avltree*);
> void (*)(Avltree*, Avl*, Avl**);
> void (*)(Avlwalk*);
>
> Duplicate signatures have been removed in the above.  The new bst
> implementation has the following de-duped signatures:
>
> Bst *(*)(Bsttree*);
> Bsttree *(*)(int, int(*cmp)(Bst*, Bst*));
> Channel *(*)(Bsttree*, Bst*, Bst*, int);
>
> but maintains the same functionality.  Which API would you rather use?
>
> The code can be found at the following locations:
>
> /n/contrib/spew/libbst
> https://bitbucket.org/spewspews/libbst
> https://github.com/spewspews/libbst
>
> A full man page is include and various tests are included in src/tests
> including measurements of AVL vs. LLRB, and the new AVL implementation
> against the old.
>
> If there are no objections I would like to remove libavl and add
> libbst instead.  Libavl has no usages in the source tree.  If anyone tries
> to compile a libavl program then tough.  There will be a better
> implementation available and we can always keep it available in
> contrib or extra.
>
> Spew
>




There is no license information file in

https://github.com/spewspews/libbst


means , it can not be used in any way  or manner .



Thank you very much .


Mehmet Erol Sanliturk

[-- Attachment #2: Type: text/html, Size: 3976 bytes --]

Re: [9front] New Balanced Search Tree Implementation

[Benjamin Purcell]

I'm giving it a lucent public license

On Mon, Dec 12, 2016 at 12:38 AM, Mehmet Erol Sanliturk
<m.e.sanliturk@gmail.com> wrote:
>
>
> On Sun, Dec 11, 2016 at 10:30 PM, Benjamin Purcell <benjapurcell@gmail.com>
> wrote:
>>
>> I have written a binary search tree C library for Plan 9.  It contains
>> implementations of both left leaning red-black trees and AVL trees.
>> In short, you create an AVL tree with
>>
>> Bsttree *t = bstcreate(AVL, cmp);
>>
>> and an LLRB tree with
>>
>> Bsttree *t = bstcreate(LLRB, cmp);
>>
>> Cmp is a comparison function.  All other implementation details are
>> hidden from the user.
>>
>> I intend to replace libavl with this library for the following reasons
>> (details can be found below):
>>
>> 1. You get a choice of BST with a single API.
>> 2. The AVL implementation is much faster.
>> 3. The AVL implementation is smaller and less complicated.
>> 4. The API is easier to use.
>>
>> Item 1. is self-explanatory.
>>
>> Item 2.
>> Measurements of the new AVL implementation against the old one shows
>> that on average:
>> Insertion is 21.9% faster.
>> Deletion is 23.9% faster.
>> Lookup is 14.95% faster.
>> 10 trials were conducted on random keys.  Sequential keys show similar
>> results.
>>
>> Item 3.
>> As for code size, the new AVL implementation plus walk code -- which
>> is shared with the LLRB tree -- comes to 362 source lines of idiomatic
>> C. The old AVL implementation 436 lines.  The old implementation also
>> contains more functions, and calls many of them unnecessarily.
>> Despite the fact that it has more functions, the individual functions
>> themselves are more complicated.
>>
>> Item 4.
>> The AVL implementation's api has the following signatures expressed as
>> abstract types:
>>
>> Avl *(*)(Avltree*, Avl*);
>> Avl *(*)(Avltree*, Avl*, int);
>> Avl *(*)(Avlwalk*);
>> Avltree *(*)(int(*)(Avl*, Avl*));
>> Avlwalk *(*)(Avltree*);
>> void (*)(Avltree*, Avl*, Avl**);
>> void (*)(Avlwalk*);
>>
>> Duplicate signatures have been removed in the above.  The new bst
>> implementation has the following de-duped signatures:
>>
>> Bst *(*)(Bsttree*);
>> Bsttree *(*)(int, int(*cmp)(Bst*, Bst*));
>> Channel *(*)(Bsttree*, Bst*, Bst*, int);
>>
>> but maintains the same functionality.  Which API would you rather use?
>>
>> The code can be found at the following locations:
>>
>> /n/contrib/spew/libbst
>> https://bitbucket.org/spewspews/libbst
>> https://github.com/spewspews/libbst
>>
>> A full man page is include and various tests are included in src/tests
>> including measurements of AVL vs. LLRB, and the new AVL implementation
>> against the old.
>>
>> If there are no objections I would like to remove libavl and add
>> libbst instead.  Libavl has no usages in the source tree.  If anyone tries
>> to compile a libavl program then tough.  There will be a better
>> implementation available and we can always keep it available in
>> contrib or extra.
>>
>> Spew
>
>
>
>
>
> There is no license information file in
>
> https://github.com/spewspews/libbst
>
>
> means , it can not be used in any way  or manner .
>
>
>
> Thank you very much .
>
>
> Mehmet Erol Sanliturk
>
>
>
>
>

Re: [9front] New Balanced Search Tree Implementation

[cinap_lenrek]

you'r exporting a bunch of symbols that should be static no?

also, its not true that libavl is unused. it is used in
venti/copy to keep track of already visited scores afaik.

--
cinap

Re: [9front] New Balanced Search Tree Implementation

[Steve Simon]

it would be interesting to try some timings on venti with the old and new libraries, just in case lib able is optimised for venti's use case.

-Steve


> On 12 Dec 2016, at 14:30, cinap_lenrek@felloff.net wrote:
> 
> you'r exporting a bunch of symbols that should be static no?
> 
> also, its not true that libavl is unused. it is used in
> venti/copy to keep track of already visited scores afaik.
> 
> --
> cinap

Re: [9front] New Balanced Search Tree Implementation

[Benjamin Purcell]

> it would be interesting to try some timings on venti with the old and new libraries, just in case lib able is optimised for venti's use case.

> also, its not true that libavl is unused. it is used in
> venti/copy to keep track of already visited scores afaik.

I have converted venti/copy.c to use libbst. It is available in the vc
repos and contrib. I don't have any venti setup so I would greatly
appreciate anyone who might want to test this. You can also try it
with LLRB but all of my tests have shown that LLRB is almost always
slower than AVL.

> you'r exporting a bunch of symbols that should be static no?

Those have been fixed, thank you for pointing that out.

spew

Re: [9front] New Balanced Search Tree Implementation

[cinap_lenrek]

> You can also try it with LLRB but all of my tests have shown that LLRB
> is almost always slower than AVL.

Then why even implement it then when its always slower than avl?
you could get rid of the indirection...

--
cinap

Re: [9front] New Balanced Search Tree Implementation

[cinap_lenrek]

another point about using enum constants to set the algorithm mode
has the disadvantage that you always have to link in all the implementations
even if you are not using them...

a better way would be to provide separate functions, that way if you
only use bstcreateavl(), you'll only link in the avl code... but you
can still have your common interface structure.

--
cinap

Re: [9front] New Balanced Search Tree Implementation

[Benjamin Purcell]

> Then why even implement it then when its always slower than avl?
> you could get rid of the indirection...

1. In the interest of keeping 9front in the tradition of not only an
OS we use but also an OS for research and learning, I think it's good
in its own right to have an implementation of another classic balanced
tree with interesting invariant properties.
2. RB trees are often touted as having better behavior than AVL trees
and especially in recent years there has been controversy over the
left leaning variant. Having comparable implementations of the two
trees together in one OS gives a living example of why AVL and only
AVL is the one true BST. This is In the same way that keeping acme and
sam around clearly shows that ED is the one true editor.

> another point about using enum constants to set the algorithm mode
> has the disadvantage that you always have to link in all the implementations
> even if you are not using them...
>
> a better way would be to provide separate functions, that way if you
> only use bstcreateavl(), you'll only link in the avl code... but you
> can still have your common interface structure.

That is a great point and I'll make that change soon.

> --
> cinap

Re: [9front] New Balanced Search Tree Implementation

[Benjamin Purcell]

> a better way would be to provide separate functions, that way if you
> only use bstcreateavl(), you'll only link in the avl code... but you
> can still have your common interface structure.

This is now done and the repos are updated. The venti code also has
been updated.

On Mon, Dec 12, 2016 at 11:18 AM, Benjamin Purcell
<benjapurcell@gmail.com> wrote:
>> Then why even implement it then when its always slower than avl?
>> you could get rid of the indirection...
>
> 1. In the interest of keeping 9front in the tradition of not only an
> OS we use but also an OS for research and learning, I think it's good
> in its own right to have an implementation of another classic balanced
> tree with interesting invariant properties.
> 2. RB trees are often touted as having better behavior than AVL trees
> and especially in recent years there has been controversy over the
> left leaning variant. Having comparable implementations of the two
> trees together in one OS gives a living example of why AVL and only
> AVL is the one true BST. This is In the same way that keeping acme and
> sam around clearly shows that ED is the one true editor.
>
>> another point about using enum constants to set the algorithm mode
>> has the disadvantage that you always have to link in all the implementations
>> even if you are not using them...
>>
>> a better way would be to provide separate functions, that way if you
>> only use bstcreateavl(), you'll only link in the avl code... but you
>> can still have your common interface structure.
>
> That is a great point and I'll make that change soon.
>
>> --
>> cinap