Re: Re: AVL tree: storing balances instead of heights

[Ed Schouten <ed@nuxi.nl>]

Hi Szabolcs,

2015-12-10 13:14 GMT+01:00 Szabolcs Nagy <nsz@port70.net>:
> can you add code size column as well?
> (sum of size of x86_64 pic .text+.data+.bss)

I've added text sizes for all of the functions, building them using
these compilers:

GCC: (Ubuntu 5.2.1-22ubuntu2) 5.2.1 20151010
Clang: 3.7.0-2ubuntu1 (tags/RELEASE_370/final) (based on LLVM 3.7.0)

None of the functions use any data/bss, so I've only added the text
sizes. As some implementations have some code reuse between tsearch()
and tdelete(), I've done both separate and combined builds of these
two functions.

The sizes of the glibc implementation is an estimate, as I didn't
build that one manually.

> i assume freebsd does not balance the tree so it timeouts
> (which also shows why this api is not useful in practice)

Exactly.

> glibc uses red-black trees which do less balancing operations
> so insert/delete may be faster, but lookup is slightly slower.
> (but it seems it does more comparisions and that can be slow)

Yes. Comparisons are rather expensive (one callback per comparison),
so we'd better optimize for a tree that is as flat as possible.

> i assume the musl code there already has the tdelete balancing
> patch applied and it is compiled with -Os.

It was the latest version in Git, using -O2.

> performance also depends on the allocator since insert/delete
> has to malloc/free (yet another issue with the api) musl's
> allocator is i think still better for realtime systems than
> the jemalloc used in cloudlibc, but it will have worse average
> performance in benchmarks like this.

Yes. All of the tests were run on Linux, using glibc. Only the
tsearch()/tdelete() implementations are different between tests. They
all use glibc's standard malloc().

-- 
Ed Schouten <ed@nuxi.nl>
Nuxi, 's-Hertogenbosch, the Netherlands
KvK-nr.: 62051717