Re: [PATCH v2] Reduce memory size of tsearch red-black tree.

[Adhemerval Zanella <adhemerval dot zanella at linaro dot org>]

On 23/08/2016 08:23, Mark Wielaard wrote:
> 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

I think it addressed both Florian runtime assert and the macro define 
name. I would prefer to just remove the old implementation since now the
optimized one is the default but I think we can remove it a future
cleanup.  LGMT.