Barrapunto

Sí, más o menos. Lo de usar índices en lugar de punteros es muy importante para evitar desaprovechar la cache de datos, pues puede provocar que el programa se ralentize un orden de magnitud a base de fallos de cache. En el caso de CPUs de 64 bits, los punteros para manejo de estructuras de datos complejas, son directamente inviables.

Normalmente se tiende a rizar un poco el rizo en el uso de índices. En el caso concreto de un árbol (ya sea binario, enario, B, etc.), se puede usar la propia topología del árbol a modo de contador implícito, necesitando menos bits para direccionar más nodos.

Ejemplo incompleto, para que se vea la idea:

enum eNodeConfig
{

NC_RefTypeBits = 2,
NC_SubContextBits = 16,
NC_IndexBits = 14,
NC_SubContextMask = (1<<NC_SubContextBits)-1,
NC_IndexMask = (1<<NC_IndexBits)-1,

};

struct NodeGlobalRef // sizeof(NodeGlobalRef) = 4 bytes (32 bits)
{

unsigned char type : NC_RefTypeBits; // S-simple, M-multiplexed, T-look-up-table
unsigned short subcontext : NC_SubContextBits ;
unsigned short index : NC_IndexBits;

};
struct NodeLocalRef // sizeof(NodeLocalRef) = 2 (16 bits)
{

unsigned char type : NC_RefTypeBits ; // S-simple, M-multiplexed, T-look-up-table
unsigned short index : NC_IndexBits;

};
struct NodeM_Local // sizeof(NodeM_Local) = 16 (256 bits)
{ // 16 * 16 bits = 64 bytes

enum eNodeM_Cfg // Para dimensionar este nodo de múltiples referencias, en C++ se podría usar un template en lugar del enum.
{

NC_MaxRefs = 16

};

NodeLocalRef nodes[NC_MaxRefs];

// ... añadir elementos de control para el árbol, etc.

};

//...

Se puede observar que sólo he puesto 14 bits para direccionamiento, se correspondería con el bloque de reserva de memoria, i.e., se haría una reserva de memoria por cada 2^14 nodos direccionables (16384). En el caso de grafos la gestión de la localidad es algo más complicada que en el caso de los árboles, pues la localidad tendría que gestionarse de manera explícita en la estructura de datos (imagina como si se tratase de un sistema solar, tendrías los nodos cercanos unidos por referencias locales, y los saltos interplanetarios, mediante referencias globales).

Corrección (tenía la prueba en otro fichero y no había sincronizado con el post, había metido la pata con el campo de bits):


struct NodeGlobalRef // sizeof(NodeGlobalRef) = 4 bytes (32 bits)
{

unsigned int type : NC_RefTypeBits; // S-simple, M-multiplexed, T-look-up-table
unsigned int subcontext : NC_SubContextBits ;
unsigned int index : NC_IndexBits;

};
struct NodeLocalRef // sizeof(NodeLocalRef) = 2 (16 bits)
{

unsigned short type : NC_RefTypeBits ; // S-simple, M-multiplexed, T-look-up-table
unsigned short index : NC_IndexBits;

};

Otra corrección:

struct NodeM_Local // sizeof(NodeM_Local) = 32 (256 bits)
{

enum eNodeM_Cfg // Para dimensionar este nodo de múltiples referencias, en C++ se podría usar un template en lugar del enum.
{

NC_MaxRefs = 16

};

NodeLocalRef nodes[NC_MaxRefs];

// ... añadir elementos de control para el árbol, etc.

};

Otra corrección:

Quise decir:

En el caso de procesos de 64 bits (puesto que hay sistemas operativos que con determinadas arquitecturas pueden operar con procesos de 32 bits bajo un SO de 64 bits, p.e. Linux para x86-64 y PPC64, o Windows y x86-64).

Muchísimas gracias por el adelanto. Estaré atento a tu bitácora ;-)