[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20151220214318.GO23362@port70.net>
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.
