Date: Sun, 20 Dec 2015 22:43:19 +0100 From: Szabolcs Nagy <nsz@...t70.net> To: musl@...ts.openwall.com, Ed Schouten <ed@...i.nl> Subject: Re: Re: AVL tree: storing balances instead of heights * Szabolcs Nagy <nsz@...t70.net> [2015-12-10 14:43:50 +0100]: > > based on the updated stats the iterative bottom up > approach seems to be a good tradeoff, i wouldn't > try to reduce stack usage further by increasing the > code size. i tried the 'more clever' balancing approach but i could not make it small compared to the basic approach and i could not win by using height diff instead of height in the nodes. complete tsearch api implementation code size on x86_64 (pic and non-pic as well): tsearch_avl.o 958 tsearch_fast.o 934 tsearch_small.o 804 _avl is the current code, _small uses various tricks to make the code smaller (it is also a bit faster because of simpler balancing code) and _fast avoids the unnecessary balancing steps like cloud libc does. (_fast is non-recursive, bottom-up approach with fixed stack size and optimized for code size, the stack array could be a vla because the tree height is known, but the upper bound is not huge either). code size tricks: - left/right children are accessed with array indexing so symmetry can be exploited (one rotation function) - balancing/rotation use less unnecessary operations. - void* child pointers so the void** arguments can be used directly without making a copy on the stack. (this means a bit less type checking) - recursive functions use argument order such that minimal register shuffling is needed on most archs. i think for musl the small one is reasonable improvement. View attachment "tsearch_small.c" of type "text/x-csrc" (3414 bytes) View attachment "tsearch_fast.c" of type "text/x-csrc" (3167 bytes)
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.