This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH v2] Reduce memory size of tsearch red-black tree.
- From: Mark Wielaard <mark at klomp dot org>
- To: libc-alpha at sourceware dot org
- Cc: Adhemerval Zanella <adhemerval dot zanella at linaro dot org>, Florian Weimer <fweimer at redhat dot com>
- Date: Tue, 23 Aug 2016 13:23:39 +0200
- Subject: Re: [PATCH v2] Reduce memory size of tsearch red-black tree.
- Authentication-results: sourceware.org; auth=none
- References: <1471446714-950-1-git-send-email-mark@klomp.org>
On Wed, 2016-08-17 at 17:11 +0200, Mark Wielaard wrote:
> A tsearch red-black tree node contains 3 pointers (key, left, right)
> and 1 bit to hold the red-black flag. When allocating new nodes
> this 1 bit is expanded to a full word. Causing the overhead per node
> to be 3 times the key size.
>
> We can reduce this overhead to just 2 times the key size.
> malloc returns naturally aligned memory. All nodes are internally
> allocated with malloc and the left/right node pointers are used
> as implementation details. So we can use the low bits of the
> left/right node pointers to store extra information.
>
> Replace all direct accesses of the struct node_t node pointers and
> red-black value with defines that take care of the red-black flag in
> the low bit of the (left) node pointer. This reduces the size of the
> nodes on 32-bit systems from 16 to 12 bytes and on 64-bit systems
> from 32 to 24 bytes.
>
> Also fix a call to CHECK_TREE so the code can be build (and tested)
> with DEBUGGING defined again.
>
> V2 changes:
>
> - Add assert after malloc to catch any odd pointers from bad
> interposed mallocs.
> - Rename implementation flag to USE_MALLOC_LOW_BIT.
>
> ChangeLog:
>
> * misc/tsearch.c (struct node_t): Reduce to 3 pointers if
> USE_MALLOC_LOW_BIT. Define pointer/value accessors.
> (check_tree_recurse): Use newly defined accessors.
> (check_tree): Likewise.
> (maybe_split_for_insert): Likewise.
> (__tfind): Likewise.
> (__tdelete): Likewise.
> (trecurse): Likewise.
> (tdestroy_recurse): Likewise.
> (__tsearch): Likewise. And assert malloc alignment.
> (__twalk): Cast root to node in case CHECK_TREE is defined.
Ping. OK to commit?
Thanks,
Mark