<xtree>: Consider encoding _Color and _Isnil in the least significant bits of a node pointer

[StephanTLavavej]

map and set nodes are currently represented with:

https://github.com/microsoft/STL/blob/58bb49d63d92e7a0346a05af29816aeea6b4cf0f/stl/inc/xtree#L321-L330

This consumes a surprising amount of space. At first glance, _Color and _Isnil consume a total of 2 bytes, but because the node contains pointers, they actually consume a total of 4 bytes (for 32-bit architectures) or 8 bytes (for 64-bit architectures), due to alignment.

We could potentially encode these bits into one of the pointers, saving a significant amount of space, at the cost of additional bit-masking logic. (There are also "fancy pointers" to consider, but we could enable such an optimization for raw pointers only.)

Also tracked by Microsoft-internal VSO-854783 / AB#854783.

vNext note: Resolving this issue will require breaking binary compatibility. We won't be able to accept pull requests for this issue until the vNext branch is available. See #169 for more information.

[Reza-Rajabi]

I would love to work on this. I know you mentioned that "Resolving this issue will require breaking binary compatibility.", I am kind of a first-time contributor, so apologies for asking: can I use a bit size variable for that like: unsigned int color : 1; so that I can send a pull request?

[StephanTLavavej]

Welcome!

Regarding binary compatibility and the "vNext note" above: the issue is that Microsoft has guaranteed that code compiled with VS 2015, VS 2017, and VS 2019 can be linked together (with some limitations). This makes customers' lives easier, but prevents us from changing certain things in the libraries. One of the things that we can't change is how data structures are represented. For example, if we tried to add an extra data member to an STL container, then code compiled before that change and code compiled after that change wouldn't properly work together. (One object file might push 12 bytes on the stack and another might pop 16 bytes off of the stack, if they can't agree on how big a vector<int> is, and then the program would crash horribly.) Eventually, we're going to work on a separate branch of the STL, not part of the VS 2019 update series, where we can change data structure representations, break binary compatibility, and fix long-standing bugs and performance issues. That branch is what we're calling "vNext". It's not yet ready, and we're several months away from starting it on GitHub, but it'll be coming along eventually.

This issue in _Tree_node is a data structure representation issue, because it affects how large associative container nodes are. Changing the size of those nodes is required to fix the issue, but it's also what breaks binary compatibility. So, as the "vNext note" above says, we will be unable to accept pull requests for this issue, until the vNext branch is ready. You can still investigate it if you like, and work on prototyping a fix, but we will be unable to merge such a fix into our master branch (which will become part of the next VS 2019 update).

Regarding your bitfield question - unfortunately, a bitfield like unsigned int color : 1; is insufficient to fix this issue. That would fix the problem if it were caused by _Color and _Isnil occupying separate bytes (being separate char variables). But here, the problem is that spending any space at all, even a single byte for up to 8 bits in a bitfield, will consume a pointer's worth of space (due to alignment and padding).

There's an undocumented and unsupported (but extremely useful) compiler option /d1reportSingleClassLayoutNAME that can be used to visualize this. Here's an example:

C:\Temp>type meow.cpp
struct ThreePointersOnly {
    int * a;
    int * b;
    int * c;
};

struct ThreePointersAndTwoChars {
    int * d;
    int * e;
    int * f;
    char color;
    char isnil;
};

struct ThreePointersAndBitfield {
    int * g;
    int * h;
    int * i;
    unsigned int color : 1;
    unsigned int isnil : 1;
};

C:\Temp>cl /EHsc /nologo /W4 /c /d1reportSingleClassLayoutThreePointersOnly meow.cpp
meow.cpp

class ThreePointersOnly size(24):
        +---
 0      | a
 8      | b
16      | c
        +---

C:\Temp>cl /EHsc /nologo /W4 /c /d1reportSingleClassLayoutThreePointersAndTwoChars meow.cpp
meow.cpp

class ThreePointersAndTwoChars  size(32):
        +---
 0      | d
 8      | e
16      | f
24      | color
25      | isnil
        | <alignment member> (size=6)
        +---

C:\Temp>cl /EHsc /nologo /W4 /c /d1reportSingleClassLayoutThreePointersAndBitfield meow.cpp
meow.cpp

class ThreePointersAndBitfield  size(32):
        +---
 0      | g
 8      | h
16      | i
24.     | color (bitstart=0,nbits=1)
24.     | isnil (bitstart=1,nbits=1)
        | <alignment member> (size=4)
        +---

So, to avoid wasting 4/8 bytes here, what's necessary is to pack these two bits inside one of the pointers, taking advantage of the fact that (due to pointer alignment) the least significant two bits of the pointer will be 0. This can be done with reinterpret_cast and bitwise operations, assuming that the _Nodeptr type is a raw pointer (of the form _Tree_node *). If _Nodeptr is a "fancy pointer" (a user-defined type imitating a pointer), then such casting has to be avoided with template metaprogramming.

This is a surprisingly complicated issue; I hope this explanation helps somewhat. If you're interested in contributing, I recommend looking at our other issues tagged enhancement but not tagged vNext. Here's a query: https://github.com/microsoft/STL/issues?q=is%3Aissue+is%3Aopen+label%3Aenhancement+-label%3AvNext+-label%3Ablocked

[miscco]

For reference there is a great talk by Chandler Carruth about the magic LLVM does with this technique.

If you are interested in a full-fledged "batteries included" implementation (which would not be necessary here) you can have a look at LLVMs PointerIntPair

@StephanTLavavej That is indeed an awesome little trick.

[Reza-Rajabi]

Thank you very much for the detail clarification. Definitely the explanation is helpful. I will look into the other issues to find something that is not in vNext.