Necesidad de velocidad

Interactuar con el lenguaje C: structs

En el lenguaje C, un struct es un tipo compuesto, formado por distintos campos. Cada campo tiene su propio tipo y tamaño.

Por ejemplo, esto define un tipo formado por tres enteros, dos de 4 bytes y uno de 8 bytes:

struct example {
    int32_t first_four_byte_integer;
    uint32_t second_four_byte_integer;
    uint64_t eight_byte_integer;
};

Un struct también puede contener otros structs:

struct example_2 {
    struct example first;
    struct example second;
};

Si uno de los campos del struct es un array, todos los bytes asignados para el array forman parte del struct. Sin embargo, si el campo es solo un puntero al array, el array debe almacenarse en otro lugar:

struct with_array {
    char string[20];
};
// all 20 bytes of string are inside struct with_array

struct with_pointer {
    const char *string;
};
// only the 8-byte pointer to the string is inside struct with_pointer

Alineación

La alineación de un tipo es una potencia de dos no negativa (1, 2, 4, 8, ...) que representa un requisito sobre su dirección. Todo objeto de ese tipo debe ubicarse en una dirección que sea un múltiplo de su alineación.

Para un tipo primitivo, la alineación suele ser igual a su tamaño, así que, por ejemplo, un int32_t normalmente tiene una alineación de 4 bytes. Esto significa que int32_t debe asignarse en límites de 4 bytes.

Sin embargo, la alineación de un struct es la alineación máxima de cualquiera de sus campos. Así, por ejemplo, el struct example, definido anteriormente, tendría una alineación de 8 bytes, ya que esta es la alineación de uint64_t.

Si la alineación de un campo del struct es menor que la del struct, se pueden insertar bytes de relleno después de ese campo. Esto garantiza que los campos siguientes y el struct en su conjunto cumplan los requisitos de alineación. En la práctica, esto significa que, aunque esos bytes de relleno contribuyen al tamaño del struct, no se usan en el valor del struct:

struct example_3 {
    char one_byte; // alignment of 1
    int four_byte; // alignment of 4
};
// example_3 has alignment of 4 (the same as int)
// it occupies 8 bytes in space:
// 1 byte for field 'one_byte'
// 3 padding bytes (with undefined value)
// 4 bytes for field 'four_byte'

Ten en cuenta que, en el struct definido anteriormente, el campo 'one_byte' tiene alineación de 1 y puede colocarse en cualquier dirección. Como el campo 'four_byte' tiene alineación de 4, los campos del struct también deben respetar los límites de 4 bytes. Esto significa que debe haber un número de bytes que sea múltiplo de 4 entre dos campos cualesquiera del struct. Como 'one_byte' ocupa solo 1 byte, se insertan 3 bytes de relleno después de él para respetar este límite.

Los campos adyacentes se agrupan siempre que sea posible para minimizar el número de bytes de relleno necesarios:

struct two_padding {
    char one; // alignment of 1
    char two; // alignment of 1
    int three; // alignment of 4
};
// struct two_padding has alignment of 4 (the same as int)
// it occupies 8 bytes in space:
// 1 byte for field 'one'
// 1 byte for field 'two'
// 2 padding bytes
// 4 bytes for field 'three'

Esta agrupación también debe respetar la alineación de cada campo:

struct one_padding {
    char one; // alignment of 1
    int16_t two; // alignment of 2
    int three; // alignment of 4
};
// struct one_padding has alignment of 4 (the same as int)
// it occupies 8 bytes in space:
// 1 byte for field 'one'
// 1 padding byte
// 2 bytes for field 'two'
// 4 bytes for field 'three'
// Since 'two' has alignment of 2, it must be placed in a 2-byte boundary
// So, there must be 1 padding byte between 'one' and 'two'

Esto significa que cambiar el orden de los campos de un struct puede, en ocasiones, dar lugar a una diferencia en su tamaño:

struct example_4 {
    int64_t one;
    short two;
    int32_t three;
};
// example_4 has alignment of 8 (the same as int64_t)
// it occupies 16 bytes in space:
// 8 bytes for field 'one'
// 2 bytes for field 'two'
// 2 padding bytes
// 4 bytes for field 'three'
// two' and 'three' are adjacent and can be grouped to sum up 8 bytes with only 2 bytes of padding

struct example_5 {
    int16_t one;
    int64_t two;
    unsigned int three;
};
// example_5 also has alignment of 8 (the same as int64_t)
// however, it occupies 24 bytes in space:
// 2 bytes for field 'one'
// 6 bytes for padding
// 8 bytes for field 'two'
// 4 bytes for field 'three'
// 4 padding bytes
// 'one' can't be grouped with 'two' because their sum would be higher than the struct's alignment
// 'two' and 'three' also can't be grouped, for the same reason
// so padding bytes must be inserted in full after each field with less than 8 bytes in alignment

Ten en cuenta que la alineación de un array es la misma que la alineación de su tipo subyacente:

struct array_example {
    char string[10]; // alignment of 1
};
// array_example has alignment of 1 (it can be placed at any address)
// it occupies 10 bytes in space, one for each char in 'string'

Los elementos de un array pueden agruparse de la misma forma que si no formaran parte de un array:

struct group_array {
    int16_t arr[3];
    int8_t one_byte;
    int32_t four_byte;
};
// group_array has alignment of 4 because this is the alignment of 'four_byte'
// it occupies 12 bytes in space:
// 4 bytes for arr[0] and arr[1]
// 2 bytes for arr[2]
// 1 byte for 'one_byte'
// 1 padding byte (arr[2] is grouped with 'one_byte')
// 4 bytes for 'four_byte'

Es importante tener en cuenta los posibles bytes de relleno cada vez que se accede a un struct en ensamblador.

Convención de llamada

En general, los valores se pasan a las funciones y se devuelven desde ellas como cabría esperar:

• Los valores enteros, incluidas las direcciones de memoria y los enums, se pasan en registros de propósito general (GPR).
• Los valores de coma flotante se pasan en registros xmm.

Sin embargo, los structs son un caso especial. Como regla general, todos los campos de un struct ocupan espacio adyacente en memoria y deben colocarse en un solo registro siempre que sea posible:

struct single_type {
    int16_t first;
    int16_t second;
    int16_t third;
    int16_t fourth;
};
// this struct occupies 8 bytes
// it is entirely passed in the same GPR register:
// the field 'first' is passed on the lowest 2 bytes
// each subsequent field is passed in the following 2 bytes

Si un struct tiene campos con valores enteros y también campos con valores de coma flotante, cada 8 bytes consecutivos del struct deben clasificarse por separado:

struct mixed_types {
    double first;
    int second;
    int third;
};
// this struct occupies 16 bytes
// the field 'first' is passed in the first 8 bytes of a xmm register
// the fields 'second' and 'third' are passed in the same GPR register:
// the field 'second' is passed on the lowest 4 bytes
// the field 'third' is passed in the next 4 bytes

En caso de que haya enteros y valores de coma flotante en los mismos 8 bytes, el tipo es entero y los 8 bytes completos (incluido el valor de coma flotante) se colocan en un GPR:

struct mixed_types {
    int32_t integer;
    float floating_point;
};
// this struct occupies 8 bytes
// it is entirely passed in the same GPR register:
// the field 'integer' is passed on the lowest 4 bytes
// the field 'floating_point' is passed on the next 4 bytes

Sin embargo, los structs con un tamaño superior a 16 bytes normalmente se colocan en memoria, independientemente del tipo de cada 8 bytes:

struct big_struct {
    uint8_t first;
    double second;
    int64_t third;
};
// this struct occupies 24 bytes, including 7 padding bytes between 'first' and 'second'
// it is entirely passed in memory

Cuando se pasa un struct como argumento a una función, este usa tantos registros como sea necesario. Si se coloca en memoria, se usa la pila en su lugar.

Se aplican reglas similares a los structs devueltos por una función. Normalmente se devuelven primero en rax y rdx (si son de valor entero) o en xmm0 y xmm1 (si son de valor de coma flotante). Sin embargo, si se colocan en memoria, quien llama debe reservar espacio para él y pasar la dirección de esta ubicación de memoria como primer argumento implícito a la función (en rdi). Después, la función almacena el struct en ese espacio y devuelve su dirección en rax.