Re: AVL tree
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.
Re: AVL tree
On May 19, 2011, at 1:21 PM, Mike Belopuhov m...@crypt.org.ru wrote: On Thu, May 19, 2011 at 7:12 PM, Thordur Bjornsson t...@openbsd.org 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.
Re: AVL tree
I test this implementation with 1000 entry inserted by random() ;) average seek time with random search of 1 is from 2 to 3 seconds On Fri, 20 May 2011 04:04:07 +0200 Ariane van der Steldt ari...@stack.nl 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 mi...@aitbg.com 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
Re: AVL tree
On Fri, May 20, 2011 at 4:04 AM, Ariane van der Steldt ari...@stack.nl 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
Re: AVL tree
On Fri, 20 May 2011 05:01:41 +0200
Ariane van der Steldt ari...@stack.nl wrote:
On Thu, May 19, 2011 at 08:28:09PM +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.
Inline patch::
--- /usr/src/sys/sys/tree.h Mon Mar 2 11:42:55 2009
+++ tree.h Thu May 19 20:16:36 2011
@@ -730,9 +730,367 @@
(x) != NULL; \
(x) = name##_RB_NEXT(x))
+#define RB_FOREACH_FROM(x, name, y)
\
This macro modifies parameter y, which I do not expect from using it.
Please keep y its original value. Also, I want to be able to use an
rvalue for y.
+ for ((x) = (y); \
+ ((x) != NULL) ((y) = name##_RB_NEXT(x), (x) != NULL);\
+(x) = (y))
+
+#define RB_FOREACH_SAFE(x, name, head, y) \
(Again, don't modify the value of y.)
+ for ((x) = RB_MIN(name, head); \
+ ((x) != NULL) ((y) = name##_RB_NEXT(x), (x) != NULL);\
+(x) = (y))
+
Is there a specific reason your wrote the above 2 macros? The pattern
where the for loop is written out is quite common and well understood by
developers.
#define RB_FOREACH_REVERSE(x, name, head) \
for ((x) = RB_MAX(name, head); \
(x) != NULL; \
(x) = name##_RB_PREV(x))
+
+#define RB_FOREACH_REVERSE_FROM(x, name, y)
\
+ for ((x) = (y); \
+ ((x) != NULL) ((y) = name##_RB_PREV(x), (x) != NULL);\
+(x) = (y))
+
+#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
+ for ((x) = RB_MAX(name, head); \
+ ((x) != NULL) ((y) = name##_RB_PREV(x), (x) != NULL);\
+(x) = (y))
+
+/* Macros that define a avl tree */
+#define AVL_MAX_HEIGHT 42
No. Trees do not have a max height. On a modern amd64, I can
create code which will be able to fit more than 2 ** 42 items in the
tree (provided I had the physmem in my machine).
+#define AVL_HEAD(name, type)
\
+struct name {
\
+ struct type *avlh_root; /* root of the tree */ \
+ int avlh_height;\
+ long avlh_count;\
This tree implementation use height for ancestors temporary array
because we have not a pointer to the parent.
You may use all memory when set new height 2**height = all stored elements in
tree!
:)
size_t, not long. KR guarantee it'll fit for every future version C.
Why is there a count? For most trees in the system, we don't care how
large they are. And we don't care for the height either.
+}
+
+#define AVL_INITIALIZER(root)
\
+ { NULL, 0, 0 }
+
+#define AVL_INIT(root, height) do {
\
+ (root)-avlh_root = NULL; \
+ (root)-avlh_height = !height ? AVL_MAX_HEIGHT : height;\
height? This is not the current height of the tree... Don't like it; if
the items in the tree are constrained in some way, other code will have
dealt with it.
+ (root)-avlh_count = 0; \
+} while (0)
+
+#define AVL_ENTRY(type)
\
+struct { \
+ struct type *avle_left; /* left element */ \
+ struct type *avle_right;/* right element */ \
+ int avle_height;/* node color */\
Comment copy-pasted from RB tree.
+}
+
+#define AVL_LEFT(elm, field) (elm)-field.avle_left
+#define AVL_RIGHT(elm, field) (elm)-field.avle_right
+#define AVL_HEIGHT(elm, field) (elm)-field.avle_height
+#define AVL_ROOT(head) (head)-avlh_root
+#define AVL_EMPTY(head)(AVL_ROOT(head) == NULL)
+#define AVL_ROOT_HEIGHT(head) (head)-avlh_height
How about this instead: (AVL_EMPTY(head) ? 0 : AVL_HEIGHT(AVL_ROOT(head)))
+#define AVL_ROOT_COUNT(head) (head)-avlh_count
+
+/* Generates prototypes and inline functions */
+#defineAVL_PROTOTYPE(name, type, field, cmp)
\
+ AVL_PROTOTYPE_INTERNAL(name, type, field, cmp,)
+#defineAVL_PROTOTYPE_STATIC
Re: AVL tree
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 ari...@stack.nl 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
AVL tree
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]
Re: AVL tree
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
Re: AVL tree
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.
Re: AVL tree
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. Include patch file -- 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-diff which had a name of tree.patch]
Re: AVL tree
On Thu, May 19, 2011 at 7:12 PM, Thordur Bjornsson t...@openbsd.org 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
Re: AVL tree
On Thu, May 19, 2011 at 08:16:22PM +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. Include patch file -- 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-diff which had a name of tree.patch] Still attached via mime. put the patch text inline in the mail message please. -0- -- Do what comes naturally now. Seethe and fume and throw a tantrum.
Re: AVL tree
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 m...@crypt.org.ru wrote: On Thu, May 19, 2011 at 7:12 PM, Thordur Bjornsson t...@openbsd.org 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
Re: AVL tree
On Thu, May 19, 2011 at 07:21:21PM +0200, Mike Belopuhov wrote: On Thu, May 19, 2011 at 7:12 PM, Thordur Bjornsson t...@openbsd.org 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.
Re: AVL tree
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.
Inline patch::
--- /usr/src/sys/sys/tree.h Mon Mar 2 11:42:55 2009
+++ tree.h Thu May 19 20:16:36 2011
@@ -730,9 +730,367 @@
(x) != NULL; \
(x) = name##_RB_NEXT(x))
+#define RB_FOREACH_FROM(x, name, y)\
+ for ((x) = (y); \
+ ((x) != NULL) ((y) = name##_RB_NEXT(x), (x) != NULL);\
+(x) = (y))
+
+#define RB_FOREACH_SAFE(x, name, head, y) \
+ for ((x) = RB_MIN(name, head); \
+ ((x) != NULL) ((y) = name##_RB_NEXT(x), (x) != NULL);\
+(x) = (y))
+
#define RB_FOREACH_REVERSE(x, name, head) \
for ((x) = RB_MAX(name, head); \
(x) != NULL; \
(x) = name##_RB_PREV(x))
+
+#define RB_FOREACH_REVERSE_FROM(x, name, y)\
+ for ((x) = (y); \
+ ((x) != NULL) ((y) = name##_RB_PREV(x), (x) != NULL);\
+(x) = (y))
+
+#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
+ for ((x) = RB_MAX(name, head); \
+ ((x) != NULL) ((y) = name##_RB_PREV(x), (x) != NULL);\
+(x) = (y))
+
+/* Macros that define a avl tree */
+#define AVL_MAX_HEIGHT 42
+#define AVL_HEAD(name, type) \
+struct name { \
+ struct type *avlh_root; /* root of the tree */ \
+ int avlh_height;\
+ long avlh_count;\
+}
+
+#define AVL_INITIALIZER(root) \
+ { NULL, 0, 0 }
+
+#define AVL_INIT(root, height) do {\
+ (root)-avlh_root = NULL; \
+ (root)-avlh_height = !height ? AVL_MAX_HEIGHT : height;\
+ (root)-avlh_count = 0; \
+} while (0)
+
+#define AVL_ENTRY(type)
\
+struct { \
+ struct type *avle_left; /* left element */ \
+ struct type *avle_right;/* right element */ \
+ int avle_height;/* node color */\
+}
+
+#define AVL_LEFT(elm, field) (elm)-field.avle_left
+#define AVL_RIGHT(elm, field) (elm)-field.avle_right
+#define AVL_HEIGHT(elm, field) (elm)-field.avle_height
+#define AVL_ROOT(head) (head)-avlh_root
+#define AVL_EMPTY(head)(AVL_ROOT(head) == NULL)
+#define AVL_ROOT_HEIGHT(head) (head)-avlh_height
+#define AVL_ROOT_COUNT(head) (head)-avlh_count
+
+/* Generates prototypes and inline functions */
+#defineAVL_PROTOTYPE(name, type, field, cmp)
\
+ AVL_PROTOTYPE_INTERNAL(name, type, field, cmp,)
+#defineAVL_PROTOTYPE_STATIC(name, type, field, cmp)
\
+ AVL_PROTOTYPE_INTERNAL(name, type, field, cmp,
__attribute__((__unused__)) static)
+#define AVL_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
+attr struct type *name##_AVL_REMOVE(struct name *, struct type *); \
+attr struct type *name##_AVL_INSERT(struct name *, struct type *); \
+attr struct type *name##_AVL_FIND(struct name *, struct type *); \
+attr struct type *name##_AVL_NFIND(struct name *, struct type *); \
+attr struct type *name##_AVL_NEXT(struct name *, struct type *); \
+attr struct type *name##_AVL_PREV(struct name *, struct type *); \
+attr struct type *name##_AVL_MIN(struct name *); \
+attr struct type *name##_AVL_MAX(struct name *);
+
+#define AVL_ROTATE_LEFT(parent, elm, type, field) do {
\
+ struct type *_rl = AVL_LEFT(elm, field);
\
+ struct type *_rr = AVL_RIGHT(elm, field);
\
+ int _l = !_rl ? 0 : AVL_HEIGHT(_rl, field);
\
+
\
+ if (_rr AVL_HEIGHT(_rr, field) = _l) {
\
+ AVL_RIGHT(*parent, field) = _rl
Re: AVL tree
AVL implementation consume less memory from RB tree implementation On Thu, 19 May 2011 19:33:22 +0200 Mike Belopuhov m...@crypt.org.ru wrote: On Thu, May 19, 2011 at 7:25 PM, Michael Pounov mi...@aitbg.com 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
Re: AVL tree
On Thu, May 19, 2011 at 05:27:01PM +, 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 t...@openbsd.org 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
Re: AVL tree
On Thu, May 19, 2011 at 07:33:22PM +0200, Mike Belopuhov wrote: On Thu, May 19, 2011 at 7:25 PM, Michael Pounov mi...@aitbg.com 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
