digitalmars.D.learn - Red-Black tree storing color without additional memory requirements
- simendsjo (14/14) Nov 20 2013 Wikipedia states that the color bit can be stored without taking
- bearophile (5/6) Nov 20 2013 If the tree manages its memory manually, using C heap memory,
- safety0ff (5/7) Nov 20 2013 Since the GC supports interior pointers, I think you can justify
- bearophile (5/11) Nov 20 2013 From:
- Ellery Newcomer (2/13) Nov 20 2013 ha. I did this with steve's rb tree. hasn't bit me yet.
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
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
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
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.htmlDo not take advantage of alignment of pointers to store bit flags in the low order bits:Bye, bearophile
Nov 20 2013
On 11/20/2013 06:50 AM, bearophile wrote:safety0ff:ha. I did this with steve's rb tree. hasn't bit me yet.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.htmlDo not take advantage of alignment of pointers to store bit flags in the low order bits:Bye, bearophile
Nov 20 2013