From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/76 Path: news.gmane.org!not-for-mail From: Szabolcs Nagy Newsgroups: gmane.linux.lib.musl.general Subject: Re: Completeness status of musl Date: Sun, 26 Jun 2011 12:30:58 +0200 Message-ID: <20110626103057.GW27421@port70.net> References: <20110528234156.GA277@brightrain.aerifal.cx> <4DE271F8.8030107@int3.at> <4DE277DF.3020605@int3.at> <4DE28333.9040900@int3.at> <20110529180854.GC6142@port70.net> <20110530103009.GE6142@port70.net> <20110530154741.GB277@brightrain.aerifal.cx> <20110530172735.GF6142@port70.net> <20110608235810.GJ191@brightrain.aerifal.cx> <20110625183106.GV27421@port70.net> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="n8884J15jRwcBTvu" X-Trace: dough.gmane.org 1309084278 32572 80.91.229.12 (26 Jun 2011 10:31:18 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Sun, 26 Jun 2011 10:31:18 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-160-gllmg-musl=m.gmane.org@lists.openwall.com Sun Jun 26 12:31:15 2011 Return-path: Envelope-to: gllmg-musl@lo.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by lo.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1QamcS-0001n1-QY for gllmg-musl@lo.gmane.org; Sun, 26 Jun 2011 12:31:13 +0200 Original-Received: (qmail 5978 invoked by uid 550); 26 Jun 2011 10:31:11 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: Original-Received: (qmail 5968 invoked from network); 26 Jun 2011 10:31:10 -0000 Content-Disposition: inline In-Reply-To: <20110625183106.GV27421@port70.net> User-Agent: Mutt/1.5.20 (2009-06-14) Xref: news.gmane.org gmane.linux.lib.musl.general:76 Archived-At: --n8884J15jRwcBTvu Content-Type: text/plain; charset=us-ascii Content-Disposition: inline * Szabolcs Nagy [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 #include #include #include static void *root; static int cmp(const void *a, const void *b) { return strcmp(a, b); } static char *sdup(char *s) { size_t n = strlen(s)+1; return memcpy(malloc(n), s, n); } static int add(char *s) { char **r = tsearch(s, &root, cmp); if (*r == s) { /* only do the string copy if s is a new string */ *r = sdup(s); return 1; } return 0; } static int getword(char *s) { int c; for (;;) { c = getchar(); if (c == EOF) return 0; if (!(c == ' ' || c == '\n' || c == '\r' || c == '\t')) break; } for (;;) { *s++ = c; c = getchar(); if (c == EOF || c == ' ' || c == '\n' || c == '\r' || c == '\t') break; } *s = 0; return 1; } int main(void) { char buf[4096]; int c = 0; while (getword(buf)) c += add(buf); printf("%d\n", c); return 0; } --n8884J15jRwcBTvu Content-Type: text/x-csrc; charset=us-ascii Content-Disposition: attachment; filename="words-hsearch.c" #include #include #include #include static char *sdup(char *s) { size_t n = strlen(s)+1; return memcpy(malloc(n), s, n); } static int add(char *s) { ENTRY *e; e = hsearch((ENTRY){.key = s}, ENTER); if (e->key == s) { /* only do the string copy if s is a new string */ e->key = sdup(s); return 1; } return 0; } static int getword(char *s) { int c; for (;;) { c = getchar(); if (c == EOF) return 0; if (!(c == ' ' || c == '\n' || c == '\r' || c == '\t')) break; } for (;;) { *s++ = c; c = getchar(); if (c == EOF || c == ' ' || c == '\n' || c == '\r' || c == '\t') break; } *s = 0; return 1; } int main(void) { char buf[4096]; int c = 0; /* start with a small table so resize is tested */ hcreate(64); while (getword(buf)) c += add(buf); // hdestroy(); printf("%d\n", c); return 0; } --n8884J15jRwcBTvu--