www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Red-Black tree storing color without additional memory requirements

reply "simendsjo" <simendsjo gmail.com> writes:
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?
Nov 20 2013
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
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
Nov 20 2013
prev sibling parent reply "safety0ff" <safety0ff.dev gmail.com> writes:
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.
Nov 20 2013
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
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
Nov 20 2013
parent Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
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.
Nov 20 2013