Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sun, 20 Dec 2015 22:43:19 +0100
From: Szabolcs Nagy <>
To:, Ed Schouten <>
Subject: Re: Re: AVL tree: storing balances instead of heights

* Szabolcs Nagy <> [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.