Re: Completeness status of musl

[Szabolcs Nagy <nsz@port70.net>]

[-- Attachment #1: Type: text/plain, Size: 1198 bytes --]

* Szabolcs Nagy <nsz@port70.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)

[-- Attachment #2: words.c --]
[-- Type: text/x-csrc, Size: 869 bytes --]

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <search.h>

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;
}

[-- Attachment #3: words-hsearch.c --]
[-- Type: text/x-csrc, Size: 881 bytes --]

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <search.h>

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;
}