AVL tree

classic Classic list List threaded Threaded
16 messages Options
Reply | Threaded
Open this post in threaded view
|

AVL tree

Michael Pounov-2
Add AVL tree implementation and merge few RB tree related macros.

If you have comments or any claims, please send me feedback
and I will fix them.

--

M.Punov
---------------------
AITNET - Sofia/Bulgaria -
Software & Network Solutions
(+359) 888 73 73 58;(+359) 2 402 4000

[demime 1.01d removed an attachment of type text/x-chdr which had a name of tree.h]

Reply | Threaded
Open this post in threaded view
|

Re: AVL tree

Thordur Bjornsson-2
On Thu, May 19, 2011 at 07:52:44PM +0300, Michael Pounov wrote:
> Add AVL tree implementation and merge few RB tree related macros.
>
> If you have comments or any claims, please send me feedback
> and I will fix them.
cool. but tech@ removes attachments, send your diffs inline.

I'm assuming you implemented this as a macro a la RB/SPAY in
tree.h;

That being said, there is already an AVL tree implementation
floating around, that's "not macros".

I've been beating on it (with some of the RB trees diffs we
have in the kernel switched over) for some time, and hopefully
it will be committable soon.


I think I'm not alone when I say that usage of yet another
macro tree is not welcome, at least not in the kernel.

ciao!
thib

Reply | Threaded
Open this post in threaded view
|

Re: AVL tree

Owain Ainsworth-2
In reply to this post by Michael Pounov-2
On Thu, May 19, 2011 at 07:52:44PM +0300, Michael Pounov wrote:
> Add AVL tree implementation and merge few RB tree related macros.
>
> If you have comments or any claims, please send me feedback
> and I will fix them.

First of all, before we get anto any technical discussion etc. please
provide the patch inline in the mail. OpenBSD lists othe than ports@
strip MIME attachments. (This is mentioned on OpenBSD.org/mail.html).

> [demime 1.01d removed an attachment of type text/x-chdr which had a name of tree.h]
>

Cheers,

-0-
--
The porcupine with the sharpest quills gets stuck on a tree more often.

Reply | Threaded
Open this post in threaded view
|

Re: AVL tree

Mike Belopuhov
In reply to this post by Thordur Bjornsson-2
On Thu, May 19, 2011 at 7:12 PM, Thordur Bjornsson <[hidden email]> wrote:

> On Thu, May 19, 2011 at 07:52:44PM +0300, Michael Pounov wrote:
>> Add AVL tree implementation and merge few RB tree related macros.
>>
>> If you have comments or any claims, please send me feedback
>> and I will fix them.
> cool. but tech@ removes attachments, send your diffs inline.
>
> I'm assuming you implemented this as a macro a la RB/SPAY in
> tree.h;
>
> That being said, there is already an AVL tree implementation
> floating around, that's "not macros".
>
> I've been beating on it (with some of the RB trees diffs we
> have in the kernel switched over) for some time, and hopefully
> it will be committable soon.
>

what do you need it for? it's pretty much the same as r/b tree.
do you think that lookup speed up is considerable?
same questions apply to Michael.

>
> I think I'm not alone when I say that usage of yet another
> macro tree is not welcome, at least not in the kernel.
>
> ciao!
> thib

Reply | Threaded
Open this post in threaded view
|

Re: AVL tree

Michael Pounov-2
Not see differences in results with performance from RB tree vs AVL,
 but right solution for problems when we have choice between algorithms.

On Thu, 19 May 2011 19:21:21 +0200
Mike Belopuhov <[hidden email]> wrote:

> On Thu, May 19, 2011 at 7:12 PM, Thordur Bjornsson <[hidden email]> wrote:
> > On Thu, May 19, 2011 at 07:52:44PM +0300, Michael Pounov wrote:
> >> Add AVL tree implementation and merge few RB tree related macros.
> >>
> >> If you have comments or any claims, please send me feedback
> >> and I will fix them.
> > cool. but tech@ removes attachments, send your diffs inline.
> >
> > I'm assuming you implemented this as a macro a la RB/SPAY in
> > tree.h;
> >
> > That being said, there is already an AVL tree implementation
> > floating around, that's "not macros".
> >
> > I've been beating on it (with some of the RB trees diffs we
> > have in the kernel switched over) for some time, and hopefully
> > it will be committable soon.
> >
>
> what do you need it for? it's pretty much the same as r/b tree.
> do you think that lookup speed up is considerable?
> same questions apply to Michael.
>
> >
> > I think I'm not alone when I say that usage of yet another
> > macro tree is not welcome, at least not in the kernel.
> >
> > ciao!
> > thib
> >


--

M.Punov
---------------------
AITNET - Sofia/Bulgaria -
Software & Network Solutions
(+359) 888 73 73 58;(+359) 2 402 4000

Reply | Threaded
Open this post in threaded view
|

Re: AVL tree

Thordur Bjornsson-2
In reply to this post by Mike Belopuhov
On Thu, May 19, 2011 at 07:21:21PM +0200, Mike Belopuhov wrote:

> On Thu, May 19, 2011 at 7:12 PM, Thordur Bjornsson <[hidden email]> wrote:
> > On Thu, May 19, 2011 at 07:52:44PM +0300, Michael Pounov wrote:
> >> Add AVL tree implementation and merge few RB tree related macros.
> >>
> >> If you have comments or any claims, please send me feedback
> >> and I will fix them.
> > cool. but tech@ removes attachments, send your diffs inline.
> >
> > I'm assuming you implemented this as a macro a la RB/SPAY in
> > tree.h;
> >
> > That being said, there is already an AVL tree implementation
> > floating around, that's "not macros".
> >
> > I've been beating on it (with some of the RB trees diffs we
> > have in the kernel switched over) for some time, and hopefully
> > it will be committable soon.
> >
>
> what do you need it for? it's pretty much the same as r/b tree.
> do you think that lookup speed up is considerable?
> same questions apply to Michael.

It's not the same as an r/b tree.

The main reason for it is to cut down on the code bloat that
the tree.h macros introduce.

Also, my (limited though, have not done proper networking checks)
show no performance difference.

Reply | Threaded
Open this post in threaded view
|

Re: AVL tree

Mike Belopuhov
In reply to this post by Michael Pounov-2
On Thu, May 19, 2011 at 7:25 PM, Michael Pounov <[hidden email]> wrote:
> Not see differences in results with performance from RB tree vs AVL,
>  but right solution for problems when we have choice between algorithms.
>

if you don't see any difference then what's the point in having them
both available?  how are you supposed to choose between them?

Reply | Threaded
Open this post in threaded view
|

Re: AVL tree

Michael Pounov-2
AVL implementation consume less memory from RB tree implementation

On Thu, 19 May 2011 19:33:22 +0200
Mike Belopuhov <[hidden email]> wrote:

> On Thu, May 19, 2011 at 7:25 PM, Michael Pounov <[hidden email]> wrote:
> > Not see differences in results with performance from RB tree vs AVL,
> >  but right solution for problems when we have choice between algorithms.
> >
>
> if you don't see any difference then what's the point in having them
> both available?  how are you supposed to choose between them?


--

M.Punov
---------------------
AITNET - Sofia/Bulgaria -
Software & Network Solutions
(+359) 888 73 73 58;(+359) 2 402 4000

Reply | Threaded
Open this post in threaded view
|

Re: AVL tree

Owain Ainsworth-2
In reply to this post by Thordur Bjornsson-2
On Thu, May 19, 2011 at 05:27:01PM +0000, Thordur Bjornsson wrote:

> On Thu, May 19, 2011 at 07:21:21PM +0200, Mike Belopuhov wrote:
> > On Thu, May 19, 2011 at 7:12 PM, Thordur Bjornsson <[hidden email]> wrote:
> > > On Thu, May 19, 2011 at 07:52:44PM +0300, Michael Pounov wrote:
> > >> Add AVL tree implementation and merge few RB tree related macros.
> > >>
> > >> If you have comments or any claims, please send me feedback
> > >> and I will fix them.
> > > cool. but tech@ removes attachments, send your diffs inline.
> > >
> > > I'm assuming you implemented this as a macro a la RB/SPAY in
> > > tree.h;
> > >
> > > That being said, there is already an AVL tree implementation
> > > floating around, that's "not macros".
> > >
> > > I've been beating on it (with some of the RB trees diffs we
> > > have in the kernel switched over) for some time, and hopefully
> > > it will be committable soon.
> > >
> >
> > what do you need it for? it's pretty much the same as r/b tree.
> > do you think that lookup speed up is considerable?
> > same questions apply to Michael.
>
> It's not the same as an r/b tree.
>
> The main reason for it is to cut down on the code bloat that
> the tree.h macros introduce.
>
> Also, my (limited though, have not done proper networking checks)
> show no performance difference.

The networking code is where the performance differences tend to show up

the theory is still that gcc manages to inline the comparators

-0-
--
Some programming languages manage to absorb change, but withstand
progress.
                -- Epigrams in Programming, ACM SIGPLAN Sept. 1982

Reply | Threaded
Open this post in threaded view
|

Re: AVL tree

Ariane van der Steldt
In reply to this post by Mike Belopuhov
On Thu, May 19, 2011 at 07:33:22PM +0200, Mike Belopuhov wrote:
> On Thu, May 19, 2011 at 7:25 PM, Michael Pounov <[hidden email]> wrote:
> > Not see differences in results with performance from RB tree vs AVL,

Which tree size did you use to test that? Which insert order (yes, this
is relevant: with the right ordering you can hit the worst or best case
of a tree algorithm). Did you test lookup time or update time or both
(combined or split)?

> >  but right solution for problems when we have choice between algorithms.
> >
>
> if you don't see any difference then what's the point in having them
> both available?

AVL trees have a difference of max 1 between the longest and shortest
path to a leaf, whereas RB-trees have at max the longest path be double
the length of the shortest path.
I.e. work case lookups require traversal of
    ln(size)/ln(2) elements for AVL trees,
2 * ln(size)/ln(2) elements for RB trees.

However, RB trees are slightly more efficient with insertion/removal.

The better balancing of AVL trees can make a big difference in lookup
time compared to RB trees, for trees containing millions of items.

> how are you supposed to choose between them?

Basically it's a trade off. Is lookup more important, or insert/remove?
And ofcourse, if you still don't know, just take what strikes your
fancy. :D

But I'm mostly interested because I tend to use trees left, right and
center and those macros lead to code bloat. If I can use a tree without
macros, I'm happy.
--
Ariane

Reply | Threaded
Open this post in threaded view
|

Re: AVL tree

Michael Pounov-2
I test this implementation with 10000000 entry inserted by random()
;)
average seek time with random search of 10000 is from 2 to 3 seconds

On Fri, 20 May 2011 04:04:07 +0200
Ariane van der Steldt <[hidden email]> wrote:

> On Thu, May 19, 2011 at 07:33:22PM +0200, Mike Belopuhov wrote:
> > On Thu, May 19, 2011 at 7:25 PM, Michael Pounov <[hidden email]> wrote:
> > > Not see differences in results with performance from RB tree vs AVL,
>
> Which tree size did you use to test that? Which insert order (yes, this
> is relevant: with the right ordering you can hit the worst or best case
> of a tree algorithm). Did you test lookup time or update time or both
> (combined or split)?
>
> > >  but right solution for problems when we have choice between algorithms.
> > >
> >
> > if you don't see any difference then what's the point in having them
> > both available?
>
> AVL trees have a difference of max 1 between the longest and shortest
> path to a leaf, whereas RB-trees have at max the longest path be double
> the length of the shortest path.
> I.e. work case lookups require traversal of
>     ln(size)/ln(2) elements for AVL trees,
> 2 * ln(size)/ln(2) elements for RB trees.
>
> However, RB trees are slightly more efficient with insertion/removal.
>
> The better balancing of AVL trees can make a big difference in lookup
> time compared to RB trees, for trees containing millions of items.
>
> > how are you supposed to choose between them?
>
> Basically it's a trade off. Is lookup more important, or insert/remove?
> And ofcourse, if you still don't know, just take what strikes your
> fancy. :D
>
> But I'm mostly interested because I tend to use trees left, right and
> center and those macros lead to code bloat. If I can use a tree without
> macros, I'm happy.
> --
> Ariane
>


--

M.Punov
---------------------
AITNET - Sofia/Bulgaria -
Software & Network Solutions
(+359) 888 73 73 58;(+359) 2 402 4000

Reply | Threaded
Open this post in threaded view
|

Re: AVL tree

Mike Belopuhov
In reply to this post by Ariane van der Steldt
On Fri, May 20, 2011 at 4:04 AM, Ariane van der Steldt <[hidden email]>
wrote:

>
> AVL trees have a difference of max 1 between the longest and shortest
> path to a leaf, whereas RB-trees have at max the longest path be double
> the length of the shortest path.
> I.e. work case lookups require traversal of
>    ln(size)/ln(2) elements for AVL trees,
> 2 * ln(size)/ln(2) elements for RB trees.
>
> However, RB trees are slightly more efficient with insertion/removal.
>
> The better balancing of AVL trees can make a big difference in lookup
> time compared to RB trees, for trees containing millions of items.
>
>> how are you supposed to choose between them?
>
> Basically it's a trade off. Is lookup more important, or insert/remove?
> And ofcourse, if you still don't know, just take what strikes your
> fancy. :D
>

i know about the difference of lookup and insert/remove speed, but
is there a significant difference in practice (in openbsd use cases)?

> But I'm mostly interested because I tend to use trees left, right and
> center and those macros lead to code bloat. If I can use a tree without
> macros, I'm happy.

so maybe it makes sense to have a non macro implementation in libkern
and use it in uvm or whenever needed?

> --
> Ariane

Reply | Threaded
Open this post in threaded view
|

Re: AVL tree

Ariane van der Steldt
On Fri, May 20, 2011 at 11:23:47AM +0200, Mike Belopuhov wrote:

> On Fri, May 20, 2011 at 4:04 AM, Ariane van der Steldt <[hidden email]> wrote:
> > AVL trees have a difference of max 1 between the longest and shortest
> > path to a leaf, whereas RB-trees have at max the longest path be double
> > the length of the shortest path.
> > I.e. work case lookups require traversal of
> > ? ?ln(size)/ln(2) elements for AVL trees,
> > 2 * ln(size)/ln(2) elements for RB trees.
> >
> > However, RB trees are slightly more efficient with insertion/removal.
> >
> > The better balancing of AVL trees can make a big difference in lookup
> > time compared to RB trees, for trees containing millions of items.
> >
> >> how are you supposed to choose between them?
> >
> > Basically it's a trade off. Is lookup more important, or insert/remove?
> > And ofcourse, if you still don't know, just take what strikes your
> > fancy. :D
> >
>
> i know about the difference of lookup and insert/remove speed, but
> is there a significant difference in practice (in openbsd use cases)?

I suspect that the PF state table is mostly lookups, therefor AVL would
improve performance there. That said without having looked at the code
though.

For UVMs allocators, the case is harder to pin, since they use a lot of
lookup and traversal (where AVL may benefit) while also requiring a lot
of modifications (where RB may be better). The choice is a lot harder to
pin down.

This is without taking cache coherency on multiple CPUs into account,
which may change the picture again (a write/rotate would lead to cache
invalidation on all other cpus).

> > But I'm mostly interested because I tend to use trees left, right and
> > center and those macros lead to code bloat. If I can use a tree without
> > macros, I'm happy.
>
> so maybe it makes sense to have a non macro implementation in libkern
> and use it in uvm or whenever needed?

Or just in sys/kern.
--
Ariane

Reply | Threaded
Open this post in threaded view
|

Re: AVL tree

Ted Unangst-2
In reply to this post by Mike Belopuhov
On May 19, 2011, at 1:21 PM, Mike Belopuhov <[hidden email]> wrote:

> On Thu, May 19, 2011 at 7:12 PM, Thordur Bjornsson <[hidden email]>
wrote:

>> On Thu, May 19, 2011 at 07:52:44PM +0300, Michael Pounov wrote:
>>> Add AVL tree implementation and merge few RB tree related macros.
>>>
>>> If you have comments or any claims, please send me feedback
>>> and I will fix them.
>> cool. but tech@ removes attachments, send your diffs inline.
>>
>> I'm assuming you implemented this as a macro a la RB/SPAY in
>> tree.h;
>>
>> That being said, there is already an AVL tree implementation
>> floating around, that's "not macros".
>>
>> I've been beating on it (with some of the RB trees diffs we
>> have in the kernel switched over) for some time, and hopefully
>> it will be committable soon.
>>
>
> what do you need it for? it's pretty much the same as r/b tree.
> do you think that lookup speed up is considerable?
> same questions apply to Michael.
>>
>>

I wrote an AVL implementation because I needed a slightly different lookup
function at the time. Also I don't like the tree macros interface, straight C
is much nicer.

The choice of AVL over RB was just because I found the algorithm easier. I see
no need to have both trees with the same interface.

Reply | Threaded
Open this post in threaded view
|

Re: AVL tree

Stuart Henderson
In reply to this post by Ariane van der Steldt
On 2011/05/21 00:19, Ariane van der Steldt wrote:
> I suspect that the PF state table is mostly lookups, therefor AVL would
> improve performance there. That said without having looked at the code
> though.

Lots of writes too, but in normal conditions the majority are to
existing states rather than insert/delete. However (and this is
usually the time when performance really matters) when under
attack you might have a huge number of states to insert.

Reply | Threaded
Open this post in threaded view
|

Re: AVL tree

Otto Moerbeek
On Mon, May 23, 2011 at 02:05:53PM +0100, Stuart Henderson wrote:

> On 2011/05/21 00:19, Ariane van der Steldt wrote:
> > I suspect that the PF state table is mostly lookups, therefor AVL would
> > improve performance there. That said without having looked at the code
> > though.
>
> Lots of writes too, but in normal conditions the majority are to
> existing states rather than insert/delete. However (and this is
> usually the time when performance really matters) when under
> attack you might have a huge number of states to insert.

Write to existing states are not important as long as they do not
change the key (and they do not, is my understanding). But that latter
point you mention could be major consideration. The more localized
updates of R&B trees cause less cache trashing as well.

I always liked R&B trees and their approach of keeping things
reasoanbly well-balanced.

As to a macro based implementation versus a function bad one, that is
a different matter, imo. Both trees can be implemented either way.

        -Otto