From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/8987 Path: news.gmane.org!not-for-mail From: Szabolcs Nagy Newsgroups: gmane.linux.lib.musl.general Subject: Re: Re: AVL tree: storing balances instead of heights Date: Sun, 20 Dec 2015 22:43:19 +0100 Message-ID: <20151220214318.GO23362@port70.net> References: <20151207130344.GZ23362@port70.net> <20151207144621.GA23362@port70.net> <20151210121449.GC23362@port70.net> <20151210134349.GF23362@port70.net> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="tT3UgwmDxwvOMqfu" X-Trace: ger.gmane.org 1450647818 13367 80.91.229.3 (20 Dec 2015 21:43:38 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 20 Dec 2015 21:43:38 +0000 (UTC) To: musl@lists.openwall.com, Ed Schouten Original-X-From: musl-return-9000-gllmg-musl=m.gmane.org@lists.openwall.com Sun Dec 20 22:43:37 2015 Return-path: Envelope-to: gllmg-musl@m.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by plane.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1aAllR-0004Iu-Fp for gllmg-musl@m.gmane.org; Sun, 20 Dec 2015 22:43:37 +0100 Original-Received: (qmail 15605 invoked by uid 550); 20 Dec 2015 21:43:34 -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 15587 invoked from network); 20 Dec 2015 21:43:33 -0000 Mail-Followup-To: musl@lists.openwall.com, Ed Schouten Content-Disposition: inline In-Reply-To: <20151210134349.GF23362@port70.net> User-Agent: Mutt/1.5.24 (2015-08-30) Xref: news.gmane.org gmane.linux.lib.musl.general:8987 Archived-At: --tT3UgwmDxwvOMqfu Content-Type: text/plain; charset=us-ascii Content-Disposition: inline * 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. --tT3UgwmDxwvOMqfu Content-Type: text/x-csrc; charset=us-ascii Content-Disposition: attachment; filename="tsearch_small.c" #include #include struct node { const void *key; void *a[2]; int h; }; static int height(struct node *n) { return n ? n->h : 0; } static struct node *rot(struct node *x, int dir) { struct node *y = x->a[!dir]; struct node *z = y->a[dir]; int hz = height(z); if (hz > height(y->a[!dir])) { // x // dir / \ !dir z // A y / \ // / \ --> x y // z D /| |\ // / \ A B C D // B C x->a[!dir] = z->a[dir]; y->a[dir] = z->a[!dir]; z->a[dir] = x; z->a[!dir] = y; x->h = hz; y->h = hz; z->h = hz+1; } else { // x y // / \ / \ // A y --> x D // / \ / \ // z D A z x->a[!dir] = z; y->a[dir] = x; x->h = hz+1; y->h = hz+2; z = y; } return z; } static struct node *balance(struct node *n) { int h0 = height(n->a[0]); int h1 = height(n->a[1]); if (h0-h1+1u < 3) { n->h = h0>h1 ? h0+1 : h1+1; return n; } return rot(n, h0>h1); } static struct node *remove_rightmost(struct node *n, const void **pkey) { if (!n->a[1]) { struct node *left = n->a[0]; *pkey = n->key; free(n); return left; } n->a[1] = remove_rightmost(n->a[1], pkey); return balance(n); } static struct node *remove(const void *key, void **p, int (*cmp)(const void *, const void *), struct node *parent) { struct node *n = *p; if (!n) return 0; int c = cmp(key, n->key); if (!c) { if (n->a[0]) { n->a[0] = remove_rightmost(n->a[0], &n->key); *p = balance(n); } else { *p = n->a[1]; free(n); } return parent; } parent = remove(key, &n->a[c>0], cmp, n); if (parent) *p = balance(n); return parent; } void *tdelete(const void *restrict key, void **restrict rootp, int(*cmp)(const void *, const void *)) { if (!rootp) return 0; /* last argument is arbitrary non-null pointer which is returned when the root node is deleted */ return remove(key, rootp, cmp, *rootp); } static struct node *insert(const void *key, void **p, int (*cmp)(const void *, const void *), struct node **found) { struct node *n = *p; struct node *r; if (!n) { n = malloc(sizeof *n); if (n) { n->key = key; n->a[0] = n->a[1] = 0; n->h = 1; } *p = n; *found = n; return n; } int c = cmp(key, n->key); if (!c) { *found = n; return 0; } r = insert(key, &n->a[c>0], cmp, found); if (r) *p = balance(n); return r; } void *tsearch(const void *key, void **rootp, int (*cmp)(const void *, const void *)) { if (!rootp) return 0; struct node *found; insert(key, rootp, cmp, &found); return found; } static struct node *find(const void *key, struct node *n, int (*cmp)(const void *, const void *)) { if (!n) return 0; int c = cmp(key, n->key); if (!c) return n; return find(key, n->a[c>0], cmp); } void *tfind(const void *key, void *const *rootp, int(*cmp)(const void *, const void *)) { if (!rootp) return 0; return find(key, *rootp, cmp); } static void walk(const struct node *r, void (*action)(const void *, VISIT, int), int d) { if (!r) return; if (r->h == 1) action(r, leaf, d); else { action(r, preorder, d); walk(r->a[0], action, d+1); action(r, postorder, d); walk(r->a[1], action, d+1); action(r, endorder, d); } } void twalk(const void *root, void (*action)(const void *, VISIT, int)) { walk(root, action, 0); } --tT3UgwmDxwvOMqfu Content-Type: text/x-csrc; charset=us-ascii Content-Disposition: attachment; filename="tsearch_fast.c" #include #include #define MAXH (sizeof(void*)*8*3/2) struct node { const void *key; void *a[2]; int h; }; static int height(struct node *n) { return n ? n->h : 0; } static struct node *rot(struct node *x, int dir) { struct node *y = x->a[!dir]; struct node *z = y->a[dir]; int hz = height(z); if (hz > height(y->a[!dir])) { // x // dir / \ !dir z // A y / \ // / \ --> x y // z D /| |\ // / \ A B C D // B C x->a[!dir] = z->a[dir]; y->a[dir] = z->a[!dir]; z->a[dir] = x; z->a[!dir] = y; x->h = hz; y->h = hz; z->h = hz+1; } else { // x y // / \ / \ // A y --> x D // / \ / \ // z D A z x->a[!dir] = z; y->a[dir] = x; x->h = hz+1; y->h = hz+2; z = y; } return z; } void *tsearch(const void *key, void **rootp, int (*compar)(const void *, const void *)) { if (!rootp) return 0; void **a[MAXH]; struct node *n = *rootp; struct node *r; int h, i=0; a[i++] = rootp; for (;;) { if (!n) break; int c = compar(key, n->key); if (!c) return n; a[i++] = &n->a[c>0]; n = n->a[c>0]; } r = malloc(sizeof *r); if (!r) return 0; r->key = key; r->a[0] = r->a[1] = 0; r->h = h = 1; *a[--i] = r; while (i) { n = *a[--i]; if (n->h > h) break; n->h = ++h; for (int d=0; d<2; d++) if (h-2 > height(n->a[d])) { *a[i] = rot(n,d); return r; } } return r; } void *tdelete(const void *restrict key, void **restrict rootp, int(*compar)(const void *, const void *)) { if (!rootp) return 0; void **a[MAXH]; struct node *n = *rootp; struct node *parent; struct node *child; int h, i=0; a[i++] = rootp; a[i++] = rootp; for (;;) { if (!n) return 0; int c = compar(key, n->key); if (!c) break; a[i++] = &n->a[c>0]; n = n->a[c>0]; } parent = *a[i-2]; if (n->a[0]) { struct node *found = n; for (a[i++]=&n->a[0], n=n->a[0]; n->a[1]; a[i++]=&n->a[1], n=n->a[1]); found->key = n->key; child = n->a[0]; } else { child = n->a[1]; } free(n); *a[--i] = child; h = height(child); while (--i) { int d, hd; h++; n = *a[i]; hd = height(n->a[d=0]); if (h > hd) hd = height(n->a[d=1]); if (h < hd) { *a[i] = n = rot(n,!d); h = hd; if (h < n->h) break; } else if (h == hd) { break; } else { n->h = h; } } return parent; } void *tfind(const void *key, void *const *rootp, int(*compar)(const void *, const void *)) { if (!rootp) return 0; struct node *n = *rootp; for (;;) { if (!n) break; int c = compar(key, n->key); if (c < 0) n = n->a[0]; else if (c > 0) n = n->a[1]; else break; } return n; } static void walk(const struct node *r, void (*action)(const void *, VISIT, int), int d) { if (r == 0) return; if (r->h == 1) action(r, leaf, d); else { action(r, preorder, d); walk(r->a[0], action, d+1); action(r, postorder, d); walk(r->a[1], action, d+1); action(r, endorder, d); } } void twalk(const void *root, void (*action)(const void *, VISIT, int)) { walk(root, action, 0); } --tT3UgwmDxwvOMqfu--