[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20110626103057.GW27421@port70.net>
Date: Sun, 26 Jun 2011 12:30:58 +0200
From: Szabolcs Nagy <nsz@...t70.net>
To: musl@...ts.openwall.com
Subject: Re: Completeness status of musl
* Szabolcs Nagy <nsz@...t70.net> [2011-06-25 20:31:06 +0200]:
> tsearch:
> i provided two different implementations: plain binary
> tree (as used in bsd) and a self balancing avl tree
> (glibc seems to use rb-tree)
>
> the avl tree implementation uses recursive functions
> (max depth of an avl tree with 2^42 nodes is 60)
i was not sure about the performance of this
so i did some benchmarks now
it turns out my avl tree is a little bit faster at word
counting than glibc rb-tree
i had to change scanf("%s", buf) to custom getword(buf)
as musl scanf is slower than glibc's and it took
comparable amount of time to the actual tree operations
on a large text file (gcc info page ~ 30K different words)
musl vs glibc tsearch (best run out of several tries)
$ time ./words <gcc.info
30617
real 0m0.261s
user 0m0.240s
sys 0m0.020s
$ time ./words-gnu <gcc.info
30617
real 0m0.291s
user 0m0.284s
sys 0m0.008s
by comparision hsearch version gives
$ time ./words <gcc.info
30617
real 0m0.116s
user 0m0.100s
sys 0m0.016s
(i could not test the glibc version of
hsearch as it segfaults after a while
even when allocate memory for every string
so i think it's a glibc bug)
View attachment "words.c" of type "text/x-csrc" (869 bytes)
View attachment "words-hsearch.c" of type "text/x-csrc" (882 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.
