As described in the Poptrie paper, direct mapping is implemented by substituting the first root node of the poptrie for a fully expanded array where each entry points to a node prefixed by its identifier. This is like a fully populated normal poptrie node, except that since it's known to be full there's no need to use the POPCOUNT to get the index, which allows the node to encode more than 6 bits without incurring in extra POPCOUNT (at most 64 bit) instructions. The original Poptrie used this first layer to encode 16 and 18 bits in their tests, which require 2^16 and 2^18 arrays.
- Should be parameterizable (generic? builder pattern?)
- Performance impact needs to be studied, since the extra space may negatively impact cache locality.
As described in the Poptrie paper, direct mapping is implemented by substituting the first root node of the poptrie for a fully expanded array where each entry points to a node prefixed by its identifier. This is like a fully populated normal poptrie node, except that since it's known to be full there's no need to use the
POPCOUNTto get the index, which allows the node to encode more than 6 bits without incurring in extraPOPCOUNT(at most 64 bit) instructions. The original Poptrie used this first layer to encode 16 and 18 bits in their tests, which require 2^16 and 2^18 arrays.