Red-Black tree storing color without additional memory requirements
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?
Re: Red-Black tree storing color without additional memory requirements
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
Re: Red-Black tree storing color without additional memory requirements
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.
Re: Red-Black tree storing color without additional memory requirements
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
Re: Red-Black tree storing color without additional memory requirements
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.
