Wikipedia states that the color bit can be stored without taking additional space: "In many cases the additional bit of information can be stored at no additional memory cost."

Looking at the Phobos implementation, it stores it as a regular byte: https://github.com/D-Programming-Language/phobos/blob/master/std/container.d#L4945

The only way I can see it storing a bit without taking additional space is by storing the color in the pointer to a node instead of in the node by using the tagged pointer trick: http://en.wikipedia.org/wiki/Pointer_tagging

But I would think this trick would break the GC, as well as making code less portable.

So.. Is the RBTree article a bit off here, or are there other techniques to reduce memory overhead?

simendsjo:

> But I would think this trick would break the GC,

If the tree manages its memory manually, using C heap memory, then the pointer tagging becomes possible.

Bye,
bearophile

On Wednesday, 20 November 2013 at 08:48:33 UTC, simendsjo wrote:
> But I would think this trick would break the GC, as well as making code less portable.

Since the GC supports interior pointers, I think you can justify using the least significant bits as long as the size and alignment of the pointed object guarantee that the pointer + tag will always lie inside the memory block.

safety0ff:

> Since the GC supports interior pointers, I think you can justify using the least significant bits as long as the size and alignment of the pointed object guarantee that the pointer + tag will always lie inside the memory block.

From:
http://dlang.org/garbage.html

> Do not take advantage of alignment of pointers to store bit flags in the low order bits:

Bye,
bearophile

On 11/20/2013 06:50 AM, bearophile wrote:
> safety0ff:
>
>> Since the GC supports interior pointers, I think you can justify using
>> the least significant bits as long as the size and alignment of the
>> pointed object guarantee that the pointer + tag will always lie inside
>> the memory block.
>
> From:
> http://dlang.org/garbage.html
>
>> Do not take advantage of alignment of pointers to store bit flags in
>> the low order bits:
>
> Bye,
> bearophile

ha. I did this with steve's rb tree. hasn't bit me yet.