Ejercicios Resueltos: Memoria Dinámica

::::{exercise} Ejercicio 1c.7 - Matriz Contígua con Puntero a Array
:label: ej-memoria-puntero-array

Implementá funciones para crear y manipular una matriz dinámica contigua usando
un puntero plano (`int *`):

````{code-block} c
:linenos:
// Crear matriz de N filas y M columnas (contígua en memoria)
int *crear_matriz_contigua(size_t filas, size_t columnas);

// Llenar la matriz con un patrón: matriz[i * columnas + j] = i * columnas + j
void llenar_matriz(int *matriz, size_t filas, size_t columnas);

// Imprimir la matriz
void imprimir_matriz_contigua(const int *matriz, size_t filas, size_t columnas);

// Transponer la matriz in-place (solo para matrices cuadradas)
void transponer_cuadrada(int *matriz, size_t n);

<!-- {exercise} Ejercicio 1c.7 - Matriz Contígua con Puntero a Array -->

::::{solution} ej-memoria-puntero-array
:class: dropdown

````{code-block} c
:linenos:
#include <stdio.h>
#include <stdlib.h>

/**
 * Crea una matriz dinámica contigua usando un puntero plano.
 * @param filas Número de filas.
 * @param columnas Número de columnas.
 * @returns Un puntero plano que apunta a la matriz, o NULL si hay error.
 */
int *crear_matriz_contigua(size_t filas, size_t columnas)
{
    // Asignar memoria contígua para todos los elementos (filas * columnas)
    int *matriz = malloc(filas * columnas * sizeof(*matriz));

    if (matriz == NULL)
    {
        return NULL;
    }

    // Inicializar a cero
    for (size_t i = 0; i < filas * columnas; i++)
    {
        matriz[i] = 0;
    }

    return matriz;
}

/**
 * Llena la matriz con el patrón: matriz[i * columnas + j] = i * columnas + j
 * @param matriz Puntero a la matriz (no debe ser NULL).
 * @param filas Número de filas.
 * @param columnas Número de columnas.
 */
void llenar_matriz(int *matriz, size_t filas, size_t columnas)
{
    if (matriz == NULL)
    {
        return;
    }

    for (size_t i = 0; i < filas; i++)
    {
        for (size_t j = 0; j < columnas; j++)
        {
            matriz[i * columnas + j] = (int)(i * columnas + j);
        }
    }
}

/**
 * Imprime la matriz.
 * @param matriz Puntero a la matriz (no debe ser NULL).
 * @param filas Número de filas.
 * @param columnas Número de columnas.
 */
void imprimir_matriz_contigua(const int *matriz, size_t filas, size_t columnas)
{
    if (matriz == NULL)
    {
        return;
    }

    for (size_t i = 0; i < filas; i++)
    {
        for (size_t j = 0; j < columnas; j++)
        {
            printf("%4d ", matriz[i * columnas + j]);
        }
        printf("\n");
    }
}

/**
 * Transpone una matriz cuadrada in-place.
 * @param matriz Puntero a la matriz cuadrada (no debe ser NULL).
 * @param n Tamaño de la matriz (n×n).
 */
void transponer_cuadrada(int *matriz, size_t n)
{
    if (matriz == NULL)
    {
        return;
    }

    // Intercambiar matriz[i * n + j] con matriz[j * n + i]
    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = i + 1; j < n; j++)
        {
            int temp = matriz[i * n + j];
            matriz[i * n + j] = matriz[j * n + i];
            matriz[j * n + i] = temp;
        }
    }
}

int main()
{
    size_t n = 4;  // Matriz 4×4

    // Crear matriz contígua
    int *matriz = crear_matriz_contigua(n, n);

    if (matriz == NULL)
    {
        fprintf(stderr, "Error: No se pudo crear la matriz.\n");
        return 1;
    }

    // Llenar con patrón
    llenar_matriz(matriz, n, n);

    printf("Matriz original %zu×%zu:\n", n, n);
    imprimir_matriz_contigua(matriz, n, n);

    // Transponer
    transponer_cuadrada(matriz, n);

    printf("\nMatriz transpuesta:\n");
    imprimir_matriz_contigua(matriz, n, n);

    // Verificar la transposición
    printf("\nVerificación:\n");
    printf("Elemento [0][1] (era 1, ahora debe ser 4): %d\n", matriz[0 * n + 1]);
    printf("Elemento [1][0] (era 4, ahora debe ser 1): %d\n", mocesar_heap()
{
    int *datos = malloc(1000 * sizeof(int));  // Llamada a función

    if (datos == NULL) return;

    // Posiblemente más cache misses:
    for (int i = 0; i < 1000; i++)
    {
        datos[i] = i * 2;  // Menos predecible para el hardware
    }

    free(datos);  // Otra llamada a función
}

````
<!-- {code-block} c -->

En un benchmark real, la versión stack podría ser 2-5 veces más rápida,
especialmente para arreglos pequeños que caben completamente en caché.

:::{note} Optimización

Práctica Comprender el caché te permite optimizar código:

````{code-block} c
:linenos:
// Malo: Recorrer matriz por columnas (pobre localidad)
for (int j = 0; j < cols; j++)
    for (int i = 0; i < rows; i++)
        matriz[i][j] = 0;  // Saltos grandes en memoria

// Bueno: Recorrer por filas (buena localidad)
for (int i = 0; i < rows; i++)
    for (int j = 0; j < cols; j++)
        matriz[i][j] = 0;  // Acceso secuencial

````
<!-- {code-block} c -->

La segunda versión puede ser 10-50 veces más rápida para matrices grandes,
simplemente porque usa mejor el caché.

-   **[*plus ultra*]:** Validar punteros `NULL` recibidos como parámetro para
    evitar fallos de segmentación.
-   **[*plus ultra*]:** Implementar una versión utilizando aritmética de
    punteros en lugar de indexación directa.

:::
<!-- {note} Optimización -->

(memoria-fragmentacion)=
### Fragmentación de Memoria

La fragmentación es un fenómeno que ocurre cuando el heap contiene bloques
libres pequeños dispersos que no pueden satisfacer solicitudes de memoria más
grandes, incluso si la suma total de memoria libre sería suficiente.

Imaginá que tenés un estante con espacios libres dispersos de diferentes
tamaños. Aunque la suma total de espacio libre sea grande, si necesitás colocar
un libro grande y solo tenés espacios pequeños separados, no podrás hacerlo. Lo
mismo ocurre con la memoria.

**Fragmentación Externa:** Espacios libres entre bloques asignados que son
demasiado pequeños para ser útiles individualmente. Ocurre cuando asignás y
liberás bloques de memoria de diferentes tamaños en un orden arbitrario, dejando
"huecos" entre bloques ocupados.

**Ejemplo conceptual:**

:::{figure} ../../apunte/bloque_2_memoria/5/fragmentacion_externa.svg
:name: fig-fragmentacion-externa
:width: 100%

Proceso de fragmentación externa: se asignan tres bloques (A, B, C), luego se
libera B dejando un hueco. Ahora hay dos bloques libres separados, pero ninguno
puede satisfacer una solicitud del tamaño de A+B.

:::
<!-- {figure} ../../apunte/bloque_4_dinamica_indireccion/1/fragmentacion_externa.svg -->

Ahora hay dos bloques libres, pero si necesitás un bloque del tamaño de A+B, no
podés usar el espacio libre entre A y C.

**Fragmentación Interna:** Desperdicio de memoria dentro de un bloque asignado
cuando se solicita menos de lo que el sistema asigna. Algunos sistemas asignan
memoria en múltiplos de cierto tamaño (por ejemplo, bloques de 16 bytes),
entonces si pedís 10 bytes, te dan 16 y los 6 extra se desperdician.

**Cómo minimizar la fragmentación:**

- Liberá memoria en el orden inverso al que la asignaste cuando sea posible.
- Usá tamaños consistentes para asignaciones frecuentes.
- Considerá usar memory pools para objetos de tamaño fijo (tema avanzado).

(memoria-alineacion)=
### Alineación de Memoria

La alineación de memoria es un concepto fundamental que afecta tanto el
rendimiento como la corrección de los programas. Comprender por qué existe y
cómo funciona te permite escribir código más eficiente.

**¿Qué es la alineación?**

Un dato está **alineado** cuando su dirección de memoria es un múltiplo de su
tamaño. Por ejemplo:

- Un `char` (1 byte) puede estar en cualquier dirección.
- Un `short` (2 bytes) debería estar en direcciones múltiplo de 2.
- Un `int` (4 bytes) debería estar en direcciones múltiplo de 4.
- Un `double` (8 bytes) debería estar en direcciones múltiplo de 8.

:::{figure} ../../apunte/bloque_2_memoria/5/memory_alignment.svg
:name: fig-memory-alignment
:width: 100%

Comparación entre memoria bien alineada (donde cada int comienza en un múltiplo
de 4) y mal alineada (causando penalización de rendimiento). El acceso alineado
requiere una sola lectura del CPU, mientras que el desalineado requiere
múltiples lecturas y manipulación de bits.

:::
<!-- {figure} ../../apunte/bloque_4_dinamica_indireccion/1/memory_alignment.svg -->

**¿Por qué importa la alineación?**

Los procesadores modernos leen memoria en bloques (palabras) de tamaño fijo,
típicamente 4 u 8 bytes a la vez. Si un dato no está alineado:

1. **Penalización de rendimiento:** El CPU debe hacer múltiples lecturas y
   combinarlas con operaciones de bits. Una lectura alineada toma 1 operación,
   mientras que una desalineada puede tomar 2 operaciones más manipulación
   adicional (2-3x más lento).

2. **En algunas arquitecturas, causa errores:** ARM en modo estricto y algunos
   procesadores RISC generan excepciones de alineación.

3. **Operaciones atómicas:** Muchas instrucciones atómicas (necesarias para
   multithreading) requieren alineación natural.

**Alineación en estructuras:**

El compilador inserta "padding" (bytes de relleno) para mantener la alineación:

````{code-block} c
:linenos:
struct ejemplo {
    char a;      // 1 byte
    // 3 bytes de padding insertados automáticamente
    int b;       // 4 bytes (debe estar en múltiplo de 4)
    char c;      // 1 byte
    // 3 bytes de padding al final para el arreglo
};

// sizeof(struct ejemplo) = 12, no 6

````
<!-- {code-block} c -->

**Visualización:**

:::{figure} ../../apunte/bloque_2_memoria/5/struct_padding.svg
:name: fig-struct-padding
:width: 100%

Comparación entre una estructura sin padding (incorrecta con desalineación) y
con padding (correcta con alineación apropiada). El compilador inserta bytes de
relleno para mantener la alineación de los campos.

:::
<!-- {figure} ../../apunte/bloque_4_dinamica_indireccion/1/struct_padding.svg -->

**Optimizar estructuras:**

Podés minimizar el padding ordenando los campos de mayor a menor:

````{code-block} c
:linenos:
// Desperdicia espacio (16 bytes):
struct ineficiente {
    char a;      // 1 byte
    int b;       // 4 bytes (+ 3 padding antes)
    char c;      // 1 byte (+ 3 padding después)
};

// Más eficiente (8 bytes):
struct eficiente {
    int b;       // 4 bytes
    char a;      // 1 byte
    char c;      // 1 byte
    // 2 bytes padding al final (menos que antes)
};

````
<!-- {code-block} c -->

**Verificar alineación:**

````{code-block} c
:linenos:
#include <stdio.h>
#include <stddef.h>

struct prueba {
    char a;
    int b;
    char c;
};

int main()
{
    printf("Tamaño de struct: %zu\n", sizeof(struct prueba));
    printf("Offset de 'a': %zu\n", offsetof(struct prueba, a));
    printf("Offset de 'b': %zu\n", offsetof(struct prueba, b));
    printf("Offset de 'c': %zu\n", offsetof(struct prueba, c));

    return 0;
}

````
<!-- {code-block} c -->

**malloc y alineación:**

Las funciones de asignación de memoria (`malloc` y `calloc`) garantizan que la
memoria devuelta está adecuadamente alineada para cualquier tipo de dato
estándar. Típicamente retornan direcciones alineadas a 8 o 16 bytes, lo cual
satisface los requisitos de todos los tipos básicos.

````{code-block} c
:linenos:
int *p = malloc(sizeof(int));
// p está garantizado como alineado para 'int'

struct grande {
    double d;  // Necesita alineación de 8 bytes
    long l;
};
struct grande *s = malloc(sizeof(*s));
// s está garantizado como alineado para todos los campos

````
<!-- {code-block} c -->

:::{note} Packed Structures

Podés forzar al compilador a no insertar padding usando atributos específicos
del compilador:

````{code-block} c
:linenos:
struct __attribute__((packed)) sin_padding {
    char a;
    int b;      // Puede estar desalineado
    char c;
};
// sizeof = 6, pero acceso más lento a 'b'

````
<!-- {code-block} c -->

Esto es útil para formatos de archivos binarios o protocolos de red, pero reduce
el rendimiento. Usalo solo cuando la compatibilidad binaria es más importante
que la velocidad.

:::
<!-- {note} Packed Structures -->

(memoria-valgrind)=

### Herramientas de Depuración: Valgrind

Valgrind es una herramienta fundamental para detectar errores de memoria en
programas C y C++. Funciona ejecutando tu programa en un entorno virtualizado
donde puede monitorear cada acceso a memoria y operación de
asignación/liberación.

**Tipos de errores que detecta:**

- **Fugas de memoria (memory leaks):** Bloques de memoria asignados que nunca
  fueron liberados.
- **Accesos a memoria no inicializada:** Leer valores de memoria que nunca
  fueron escritos.
- **Accesos fuera de límites:** Leer o escribir más allá de los límites de un
  bloque asignado.
- **Dobles liberaciones:** Intentar liberar el mismo bloque dos veces.
- **Uso de memoria después de `free`:** Acceder a memoria que ya fue liberada.
- **Desajustes entre asignación y liberación:** Por ejemplo, asignar con
  `malloc` y liberar con `delete` (en C++).

**Uso básico:**

```` bash
# Compilar con símbolos de depuración
gcc -g -o programa programa.c

# Ejecutar con Valgrind
valgrind --leak-check=full --show-leak-kinds=all ./programa
````
<!-- bash -->

**Opciones útiles:**

- `--leak-check=full`: Muestra detalles completos de las fugas de memoria.
- `--show-leak-kinds=all`: Muestra todos los tipos de fugas.
- `--track-origins=yes`: Rastrea el origen de valores no inicializados (más
  lento pero útil).
- `--verbose`: Muestra información adicional de depuración.

**Interpretando la salida:**

Cuando Valgrind detecta un error, muestra:

- El tipo de error
- La ubicación en el código (archivo y línea)
- El stack trace (secuencia de llamadas que llevó al error)
- Para fugas de memoria: dónde se asignó el bloque que no fue liberado

**Ejemplo de salida:**

````
==12345== Invalid write of size 4
==12345==    at 0x108A: main (programa.c:15)
==12345==  Address 0x522d068 is 0 bytes after a block of size 40 alloc'd
````

Esto indica que se intentó escribir 4 bytes fuera de un bloque de 40 bytes
asignado, en la línea 15 del archivo `programa.c`.

:::{important} Desarrollo Profesional

En un entorno profesional, es inaceptable entregar código con errores de
memoria. El uso de herramientas como Valgrind durante el desarrollo no es
opcional, es una práctica estándar de la industria. Acostumbrate a ejecutar
Valgrind regularmente durante el desarrollo, no solo cuando sospechás que hay un
problema.

:::
<!-- {important} Desarrollo Profesional -->

La segunda versión puede ser 10-100 veces más rápida.

**2. La localidad de acceso importa enormemente:**

````{code-block} c
:linenos:
// Malo: Acceso aleatorio (muchos cache misses)
for (int i = 0; i < n; i++)
{
    int idx = random_index();
    data[idx] = process(data[idx]);  // Impredecible para el caché
}

// Bueno: Acceso secuencial (cache hits)
for (int i = 0; i < n; i++)
{
    data[i] = process(data[i]);  // Predecible, alta localidad
}

````
<!-- {code-block} c -->

**3. El tamaño de la estructura de datos importa:**

````{code-block} c
:linenos:
// Si tu estructura cabe en caché L1 (32 KB):
struct pequena datos[1000];  // 4 KB total, cabe en L1
// Acceso muy rápido, todo en caché

// Si excede la caché L3 (8 MB):
struct grande datos[1000000];  // 100 MB, no cabe
// Muchos accesos a RAM, más lento

````
<!-- {code-block} c -->

**4. El costo de la indirección:**

````{code-block} c
:linenos:
// Un nivel de indirección:
int *ptr = malloc(sizeof(int));
*ptr = 42;  // Lee ptr, luego lee *ptr (2 accesos potenciales a RAM)

// Dos niveles de indirección:
int **ptr2 = malloc(sizeof(int *));
*ptr2 = malloc(sizeof(int));
**ptr2 = 42;  // Lee ptr2, luego *ptr2, luego **ptr2 (3 accesos)

// Directo (sin indirección):
int valor = 42;  // Puede estar en registro, cero accesos a memoria

````
<!-- {code-block} c -->

**Ejemplo cuantitativo:**

Considerá procesar un millón de elementos:

````{code-block} c
:linenos:
// Opción A: Arreglo continuo (stack o heap)
int arreglo[1000000];
for (int i = 0; i < 1000000; i++)
{
    arreglo[i] = i * 2;
}
// Costo: ~1 millón de escrituras secuenciales
// Cache: Muy efectivo (prefetching automático)
// Tiempo: ~1-2 ms en un CPU moderno

// Opción B: Lista enlazada (heap)
struct nodo *lista = crear_lista(1000000);
struct nodo *actual = lista;
int i = 0;
while (actual != NULL)
{
    actual->valor = i * 2;
    actual = actual->siguiente;  // Sigue puntero (indirección)
    i++;
}
// Costo: ~1 millón de escrituras + 1 millón de lecturas de punteros
// Cache: Malo (los nodos están dispersos)
// Tiempo: ~5-20 ms (3-10x más lento)

````
<!-- {code-block} c -->

**Estrategias de optimización basadas en el modelo de costos:**

1. **Minimizá asignaciones dinámicas:** Usá stack cuando sea posible, o pooling
   de memoria.

2. **Maximizá localidad:** Mantené datos relacionados físicamente juntos.

3. **Reducí indirección:** Preferí arreglos sobre listas enlazadas cuando el
   acceso aleatorio es importante.

4. **Batch operations:** Procesá múltiples elementos antes de saltar a otra
   región de memoria.

5. **Considerá el cache line size:** Operá en bloques de ~64 bytes cuando sea
   posible.

:::{important} Profiling sobre Intuición

Aunque este modelo proporciona intuición valiosa, siempre **medí** antes de
optimizar. Usa herramientas de profiling como `perf`, `gprof`, o `Valgrind
--tool=cachegrind` para identificar cuellos de botella reales. La optimización
prematura basada en intuición puede hacer el código más complejo sin beneficios
reales.

:::
<!-- {important} Profiling sobre Intuición -->