Primero, esta pregunta no es para aquellos que se ven a sí mismos como oficiales de la policía de C ++, ya que implica una seria flexión en C para recuperar un poco de memoria, así que lea esta pregunta con su sombrero de vigilante.

Tengo un programa con muchas cadenas asignadas con malloc donde la mayoría de ellas tienen 1 carácter de longitud. Una cadena que contiene 1 carácter ocupa aproximadamente ~ 32 bytes de memoria real, incluidos los descriptores, el tamaño del bloque, etc. Entonces, mi plan astuto es usar el puntero char * para almacenar un char o una cadena de esta manera:

char *sourceStringOrChar;

sourceStringOrChar = malloc(10);
//-- OR
sourceStringOrChar = (char *)'A';    //-- Note that its '' and not ""

if((intptr_t)sourceStringOrChar & (~0xFF))
    TRACE("%s\n", sourceStringOrChar);
else
    TRACE("%c\n", sourceStringOrChar);

Ya sé que malloc devuelve ENOMEM cuando no tiene memoria donde el valor real de esta constante es 12. Eso me da alguna esperanza de que haya una vacante en los resultados devueltos de malloc. Comencé a leer el código fuente de malloc para determinar si esto es posible, pero si alguien aquí tiene algún conocimiento sobre el extremo profundo de malloc podría salvarme un montón de tiempo.

Editar:

  • La pregunta, por supuesto, es si esto es posible.
  • Algunos de ustedes están preocupados por free / strlen, etc., pero tenga en cuenta que este es un código de ejemplo y puede manejarse de la misma manera que lo anterior con el

    if((intptr_t)sourceStringOrChar & (~0xFF))
    {
        strlen(sourceStringOrChar);
        free(sourceStringOrChar);
    }
    
  • Además, no iría por ese camino peligroso si no hubiera un gran problema de memoria

0
Moav 5 mar. 2017 a las 16:45

2 respuestas

La mejor respuesta

He estado trabajando un poco en el código de CLISP. Algo similar se hace allí para exprimir algunos valores inmediatos en un puntero (en lugar de asignar un objeto del montón de basura recolectada).

Sin embargo, en el caso de CLISP esto funciona porque sabemos el rango de direcciones que nuestro asignador podría devolver. Luego hay un bit que nunca podría ser establecido por una dirección válida, que si se establece indica que el "puntero" no es un puntero real sino datos (el carácter único o más) en su caso).

Por cierto: Usar un char * no es un buen plan, estás a medio camino de dispararte en el pie debido a un comportamiento indefinido o simplemente pasar accidentalmente ese "puntero" a, por ejemplo, strlen. Supongo que usar un union es un enfoque mucho mejor (aunque actualmente no tengo tiempo para verificar las reglas reales del estándar sobre si incluso está permitido usar una unión de esta manera). Aún más seguro es empacar un uintptr_t dentro de una estructura.

[..] pero si alguien aquí tiene algún conocimiento sobre el extremo profundo de malloc, podría ahorrarme mucho tiempo.

Eso no te va a comprar nada. Cambie el sistema operativo, la plataforma o simplemente la biblioteca estándar utilizada y todo podría ser diferente de lo que aprendió sobre la implementación de malloc que está viendo actualmente.

Un enfoque es utilizar su propio asignador, como se hace con CLISP, que está tomando memoria de algún grupo (por ejemplo, adquirido con mmap en Linux / BSD) que reside en alguna dirección predefinida.

Pero también puede usar malloc (o una función más adecuada, como C11 aligned_alloc o posix_memalign) para asigna memoria alineada para tus cadenas. Digamos que alineas cada cadena en una dirección par. De esa manera, cuando vea una dirección que tiene el conjunto de bits menos significativo, puede estar seguro de que no es realmente una dirección, sino datos inmediatos, es decir, la cadena en sí.

El uso de malloc solo para asignar 2 bytes de memoria alineada funciona así: Usted asigna 2 bytes adicionales. Si la dirección devuelta por malloc ya está correctamente alineada, entonces devuelve la siguiente dirección correctamente alineada (char_ptr + 2) y marca la celda directamente antes de esa dirección con algún valor que indica que la dirección original estaba alineada ( char_ptr[1] = '1'). Si, por otro lado, la dirección devuelta no está correctamente alineada, entonces devuelve el siguiente byte directamente (que está correctamente alineado; char_ptr + 1) y marca la celda directamente antes de esa dirección (por lo tanto, la primera; {{ X5}}).

Al liberar, mire la celda directamente antes de la dirección que se pasó, contiene la marca que le indica qué dirección necesita free.

En codigo:

#define IS_ALIGNED_2BYTE(value) (((uintptr_t)(value) & 0x01) == 0)

/// Allocate a memory region of the specified size at an even (2 byte
/// aligned) address.
///
/// \param[in] size Required size of the memory region.
/// \return Pointer to the memory, or NULL on failure.
inline static void * allocate_2byte_aligned(size_t size) {
#ifdef HAVE_ALIGNED_ALLOC
  return aligned_alloc(2, size);
#elif defined(HAVE_POSIX_MEMALIGN)
  void * ptr;
  if (posix_memalign(&ptr, sizeof(void *), size) == 0) {
    assert(IS_ALIGNED_2BYTE(ptr)); // Paranoia due to uncertainty
                                   // about alignment parameter to
                                   // posix_memalign.
    return ptr;
  } else {
    return NULL;
  }
#else
  char * const memory = malloc(size + 2);
  if (! memory) {
    return NULL;
  }
  if (IS_ALIGNED_2BYTE(memory)) {
    // memory is correctly aligned, but to distinguish from originally
    // not aligned addresses when freeing we need to have at least one
    // byte. Thus we return the next correctly aligned address and
    // leave a note in the byte directly preceeding that address.
    memory[1] = '1';
    return &(memory[2]);
  } else {
    // memory is not correctly aligned. Leave a note in the first byte
    // about this for freeing later and return the next (and correctly
    // aligned) address.
    memory[0] = '0';
    return &(memory[1]);
  }
#endif
}


/// Free memory previously allocated with allocate_2byte_aligned.
///
/// \param[in] ptr Pointer to the 2 byte aligned memory region.
inline static void free_2byte_aligned(void * ptr) {
  assert(IS_ALIGNED_2BYTE(ptr));
#if defined(HAVE_ALIGNED_ALLOC) || defined(HAVE_POSIX_MEMALIGN)
  free(ptr);
#else
  char const * const memory = ptr;
  void const * original_address;
  if (memory[-1] == '0') {
    // malloc returned an address that was not aligned when allocating
    // this memory block. Thus we left one byte unused and returned
    // the address of memory[1]. Now we need to undo this addition.
    original_address = &(memory[-1]);
  } else {
    // malloc returned an address that was aligned. We left two bytes
    // unused and need to undo that now.
    assert(memory[-1] == '1');
    original_address = &(memory[-2]);
  }
  free((void *) original_address);
#endif
}

Crear y destruir estructuras de "puntero-o-datos-inmediatos" es entonces sencillo:

typedef struct its_structure {
  uintptr_t data; ///< Either a pointer to the C string, or the actual
                  ///< string, together with a bit to indicate which
                  ///< of those it is.
} its;

its its_alloc(size_t size) {
  if (size < sizeof(uintptr_t)) {
    its const immediate_string = {.data = 0x01};
    return immediate_string;
  } else {
    void * const memory = allocate_2byte_aligned(size);
    assert(IS_ALIGNED_2BYTE(memory));
    its const allocated_string = {
      .data = memory ? (uintptr_t) memory : (0x01 | 0x02) /* Invalid string */};
    return allocated_string;
  }
}

void its_free(its string) {
  if (IS_ALIGNED_2BYTE(string.data)) {
    free_2byte_aligned((void *) string.data);
  } // else immediate, thus no action neccessary
}

El código anterior es en realidad de una pequeña biblioteca que escribí para probar / escribir esta respuesta. Si lo desea, puede usarlo / mejorarlo.

0
Community 23 may. 2017 a las 12:02

Si realmente tiene "muchas muchas cadenas" que tienen un solo carácter, entonces al menos uno de los siguientes debe ser verdadero:

  1. Tus personajes tienen más de ocho bits de largo

  2. Podría beneficiarse enormemente "interning" sus cadenas para que no cree más de una copia de la misma cadena.

Si sus cadenas son inmutables (o puede hacer arreglos para que no se muten en su lugar), entonces el # 2 es una opción muy atractiva. En el caso de que el n. ° 1 sea falso y solo tenga 255 posibles cadenas de un carácter, puede internar simplemente indexando en una tabla preconstruida de 510 bytes (caracteres individuales alternos y NUL). La estrategia de internamiento más general requiere una tabla hash o algo así, y hay más trabajo (pero potencialmente extremadamente valioso).

Si sus "caracteres" son en realidad secuencias de bytes cortas pero no se repiten con frecuencia, entonces es posible que desee implementar un esquema de asignación de grupo simple. Esto será más fácil / más efectivo si no hay mucha "rotación" en sus cadenas; es decir, con frecuencia no asigna e inmediatamente libera la cadena.

Un esquema simple de asignación de grupo de cadenas es elegir un límite y asignar todas las cadenas de ese tamaño secuencialmente en bloques que sean lo suficientemente grandes como para contener muchas cadenas cortas. Los tamaños dependerán de su aplicación precisa, pero he tenido éxito con un modelo en el que las cadenas "cortas" tienen un máximo de 31 bytes y el tamaño del fragmento es exactamente 4096 bytes siempre asignados en un límite de 4096 bytes (usando { {X0}}, por ejemplo). El asignador de agrupación mantiene un único fragmento, al que agrega cadenas recién asignadas. También mantiene una lista de fragmentos asignados, cada uno con un recuento de cadenas activas. pool_malloc(n) difiere a malloc(n) si la cadena es más larga que el límite; de lo contrario, coloca la nueva cadena al final del fragmento actualmente activo después de asignar primero un nuevo fragmento si el fragmento actual está lleno. pool_free(s) comprueba si s es lo suficientemente corto como para caber en un fragmento. Si no, solo llama a free(), y si es así, encuentra el fragmento en la lista de fragmentos activos y disminuye su recuento de cadenas activo. (Es fácil encontrar el fragmento debido al hecho de que los fragmentos están todos alineados en 4k.) Hay muchas variaciones sobre este tema: puede colocar los metadatos en el fragmento en lugar de mantener metadatos externos; simplemente no puede liberar cadenas cortas hasta que se desasigne todo el grupo (lo que ahorra mucho tiempo a expensas del uso de memoria adicional si hay muchas liberaciones); puede hacer trozos de cadenas de longitud fija, lo que facilita la liberación inmediata de una cadena (pero requiere que mantenga algún tipo de estructura de lista libre).

Estas dos estrategias se pueden usar en combinación; eso es particularmente efectivo si puede permitirse liberar toda la tabla interna / grupo de memoria en una sola operación, lo que a menudo es posible. (Véase, por ejemplo, el enfoque Apache Portable Runtime para la asignación de memoria).

0
rici 5 mar. 2017 a las 16:44