Colecciones Sin Asignación de Memoria

Imagina que tienes un método que recopila datos mediante la creación de una Lista temporal, calcula estadísticas a partir de estos datos y luego destruye la lista. Este método se invoca con frecuencia, lo que provoca numerosas asignaciones y liberaciones de memoria, además de aumentar la fragmentación de memoria. Además, toda esta gestión de memoria requiere tiempo y puede afectar el rendimiento.

Para estos escenarios, podrías querer mantener todos los datos en la pila (stack) y evitar completamente las asignaciones de memoria. A continuación, te mostraremos varias formas de lograr esto.

Incluso si estos casos de uso no se aplican a ti, es probable que encuentres este artículo interesante, ya que utiliza algunos conceptos interesantes y funcionalidades del lenguaje Delphi.

Pila vs Montículo, Tipos de Valor vs Tipos de Referencia

Primero, repasemos algunos términos. Es posible que ya conozcas todo lo que se incluye en esta sección, pero repasemos los conceptos de todos modos.

La memoria interna tiene dos tipos principales: la pila y el montículo (heap). La pila se utiliza para almacenar variables locales de métodos y posiblemente otros datos (como las direcciones de retorno en muchas plataformas). El montículo almacena memoria asignada dinámicamente, incluyendo cadenas, arrays dinámicos y objetos.

Cuando conoces estos tipos de memoria, es probable que en el mismo párrafo o capítulo leas sobre tipos de valor y tipos de referencia, ya que ambos están relacionados. Los tipos de valor almacenan directamente un valor en la ubicación de memoria, mientras que los tipos de referencia almacenan un puntero que apunta a un valor ubicado en otro lugar (usualmente, aunque no necesariamente, en el montículo). Ejemplos de tipos de valor son los enteros, números de punto flotante, booleanos, enumeraciones, caracteres, registros y arrays estáticos. Ejemplos de tipos de referencia son las cadenas, objetos, interfaces de objeto, arrays dinámicos y punteros.

Existe controversia sobre la diferencia entre clases y objetos, a veces se usan indistintamente. Personalmente considero que son diferentes: una clase describe un contrato (campos, métodos, propiedades y eventos), mientras que un objeto es una instancia específica de una clase.

Solo los tipos de valor pueden almacenarse en la pila. Cuando declaras un tipo de referencia en la pila, solo se almacena su valor de puntero; el valor real se asigna en el montículo (si no es nil).``

procedure PilaVsMonticulo;
var
  Numero: Integer;
  Lista: TLista<Integer>;
begin
  Numero := 42;
  Lista := TLista<Integer>.Crear;
  Lista.Agregar(42);
  Lista.Agregar(100);
end;

Esto resulta en el siguiente diseño de memoria (las ubicaciones de memoria son solo de referencia):

Como puedes ver, al crear un TLista y agregar al menos dos elementos, se asignan dos bloques de memoria en el montículo: uno para almacenar los datos de la instancia de la lista (Elementos, Conteo y algunos otros campos) y otro para almacenar los elementos en un array dinámico. En este ejemplo, el array dinámico puede contener 4 elementos, de los cuales 2 están en uso. El array dinámico crecerá según sea necesario para acomodar nuevos elementos.

Colecciones Basadas en la Pila

Es posible que encuentres situaciones donde estas asignaciones de memoria en el montículo no son ideales. Pueden aumentar la fragmentación de memoria, lo que lleva a un mayor uso de memoria. Además, asignar y liberar memoria dinámica no es una operación económica, y crear listas temporales varias veces por segundo puede afectar el rendimiento. Por otro lado, la "asignación" de memoria en la pila suele ser una operación de costo cero. Generalmente solo implica ajustar el puntero de la pila al inicio del método, algo que el compilador hace en la mayoría de los casos.

Si puedes crear completamenet una colección en la pila (es decir, tanto las propiedades de la colección Conteo como los elementos reales deberían existir en la pila), puedes resolver estos problemas. De hecho, es probable que ya hayas usado este tipo de colecciones:

procedure ArrayEstatico;
var
  Elementos: array [0..9] de Integer;
  Conteo: Integer;
begin
  ...
end;

Los arrays estáticos locales son esencialmente colecciones basadas en la pila, aunque no son colecciones amigables para el usuario. Para hacer que este array se parezca más a una lista, podemos envolverlo en un registro.

Una Lista Simple Basada en la Pila

Una implementación simple podría ser la siguiente:

type
  TListaPila<T: registro> = record
  private type
    Puntero = ^T;
  private
    FDatos: array [0..255] de Byte;
    FCapacidad: Integer;
    FConteo: Integer;
    function ObtenerElemento(const AIndice: Integer): T;
  public
    procedure Inicializar;
    procedure Limpiar;
    procedure Agregar(const AElemento: T);
 
    property Conteo: Integer read FConteo;
    property Elementos[const AIndice: Integer]: T read ObtenerElemento; default;
  end;

Puedes encontrar una versión mejor documentada de este código (y de todos los demás códigos de este artículo) en el repositorio JustAddCode en GitHub, en el directorio AllocationFreeCollections.

Es posible que el nombre TListaPila te resulte un poco confuso. Aquí, la palabra "pila" no se refiere a una estructura de datos similar a una pila, sino al hecho de que la lista debe existir en la memoria de pila. Si fueras a crear una colección similar a una pila que exista en la memoria de pila, podrías llamarla TPilaPila.

Hay varios puntos a tener en cuenta:

  • He elegido crear una lista genérica. Hoy en día, rara vez se necesitan listas no genéricas.
  • El parámetro de tipo T tiene una restricción de registro. Esto significa que la lista solo puede almacenar tipos de valor (por ahora). Esto simplifica en cierta medida la implementación de la lista.
  • La declaración anidada type Puntero = ^T; podría ser nueva para ti. Declara un tipo de puntero al tipo de elemento de la lista. Esto es útil en la implementación para acceder a los elementos de la lista.
  • La lista almacena sus elementos en un array estático de 256 bytes, lo que significa que siempre consume 256 bytes de memoria (de pila), sin importar el tipo T. Por lo tanto, si se usa para crear una lista de enteros, la lista puede contener hasta 64 elementos (ya que un entero tiene un tamaño de 4 bytes).
  • Debes llamar al método Inicializar para inicializar o crear la lista. Este método actúa como un constructor. Como los registros no pueden tener constructores sin parámetros (al menos en las versiones actuales de Delphi), elegí agregar un método Inicializar. También podrías elegir devolver un método estático de la lista (como class function Crear: TListaPila<T>; static;), pero devolver un registro grande desde una función no es eficiente.
  • Aunque puedes declarar un campo TListaPila en un objeto, esto no es el propósito de esta lista y solo desperdicia memoria. Este tipo está diseñado para declararse solo como variable local en un método.

La implementación es bastante simple. El método Inicializar simplemente calcula el número de elementos que puede contener la colección y establece el campo FConteo en 0 (ya que cuando se declara en la pila, los campos del registro no se inicializan en 0).

procedure TListaPila<T>.Inicializar;
begin
  if EsTipoGestionado(T) then
    raise EOperacionInvalida.Create(
      'Una colección basada en pila no puede contener tipos gestionados');
 
  FCapacidad := SizeOf(FDatos) div SizeOf(T);
  FConteo := 0;
end;

También verifica si el parámetro de tipo T es un tipo gestionado, y si es así, lanza una excepción. Esto merece alguna explicación. Aunque el parámetro de tipo T tiene una restricción de registro, esto no significa que T no pueda contener tipos gestionados. Por ejemplo, la restricción de registro impide que Delphi compile:

var
  Lista: TListaPila<Cadena>;

pero no impide compilar esto:

type
  ContenedorCadena = record
    Valor: Cadena;
  end;
var
  Lista: TListaPila<ContenedorCadena>;

Cuando el parámetro de tipo T es un tipo de referencia o gestionado, necesitamos algo de código adicional para evitar fugas de memoria. Hablaremos de esto más adelante y por ahora simplemente no lo permitimos.

Agregar un elemento funciona de la siguiente manera:

procedure TListaPila<T>.Agregar(const AElemento: T);
var
  Destino: Puntero;
begin
  if (FConteo >= FCapacidad) then
    raise EOperacionInvalida.Create('La lista está llena');
 
  Destino := @FDatos[FConteo * SizeOf(T)];
  Destino^ := AElemento;
  Inc(FConteo);
end;

Como esta lista tiene una capacidad fija, necesitamos lanzar una excepción cuando la lista esté llena. Veremos una alternativa más adelante.

Dado que el campo FDatos es solo un array de bytes, necesitamos un truco para colocar elementos de tipo T en este array. Aquí es donde entra en juego la declaración type Puntero = ^T;. Calculamos el desplazamiento en el array FDatos y asignamos su dirección a una variable de tipo Puntero. Luego podemos desreferenciar esta variable para asignar el valor. La recuperación de elementos funciona de manera similar:

function TListaPila<T>.ObtenerElemento(const AIndice: Integer): T;
var
  Elemento: Puntero;
begin
  if (AIndice < 0) or (AIndice >= FConteo) then
    raise EArgumentoFueraDeRango.Create('El índice de la lista está fuera de rango');
 
  Elemento := @FDatos[AIndice * SizeOf(T)];
  Resultado := Elemento^;
end;

Puedes usar esta lista basada en la pila de la siguiente manera (consulta el ejemplo E01ListaPilaSimple en el repositorio):

procedure EjemploListaPilaSimple;
var
  Lista: TListaPila<Integer>;
  Error: Booleano;
  I: Integer;
begin
  Lista.Inicializar;
 
  { TListaPila<Integer> puede contener hasta 256 bytes de datos. Un Integer
    tiene un tamaño de 4 bytes, lo que significa que la lista puede contener hasta 64 enteros. }
  for I := 0 to 63 do
    Lista.Agregar(I);
 
  { Agregar el elemento 64 debería lanzar una excepción. }
  Error := Falso;
  try
    Lista.Agregar(0);
  except
    Error := Verdadero;
  end;
  Assert(Error);
 
  { Verificar contenidos }
  Assert(Lista.Conteo = 64);
  for I := 0 to Lista.Conteo - 1 do
    Assert(Lista[I] = I);
end;

Lista de Pila con Tamaño Configurable

Es posible que 256 bytes de almacenamiento te parezcan demasiado poco o demasiado. Sería bueno si este tamaño fuera configurable. Si Delphi fuera más como C++, podríamos usar un parámetro de plantilla como este:

type
  TListaPila<T: registro; N: Integer> = record
  private
    FDatos: array [0..N - 1] de Byte;
  end;
 
var
  Lista: TListaPila<Double, 1024>;

Pero Delphi no es C++, y los genéricos no son plantillas. Entonces, ¿cómo podemos lograr algo similar? Podemos usar otro parámetro de tipo en lugar de un parámetro de plantilla, cuyo único propósito es proporcionar almacenamiento para los elementos de la lista:

type
  TListaPila<T: registro; TTamano: registro> = record
  private
    FDatos: TTamano;
    ...

Luego podemos declarar una lista de pila que almacene 1024 bytes de la siguiente manera:

type
  T1024Bytes = record Datos: array [0..1023] de Byte end;
 
var
  Lista: TListaPila<Double, T1024Bytes>;

Su uso es el mismo que la lista de tamaño fijo que se describió anteriormente. Puedes encontrar esta versión en el ejemplo E02ListaPilaConTamano en el código base.

Ten en cuenta que el tipo T1024Bytes contiene un array estático dentro del registro. Dado que TTamano está restringido a registro, el array en sí no puede usarse como tipo, por lo que necesitamos encapsularlo en un registro.

La implementación de este registro es muy similar al anterior. Como FDatos ya no es un array estático, necesitamos un código diferente para calcular la dirección de los elementos:

procedure TListaPila<T, TTamano>.Agregar(const AElemento: T);
var
  Destino: Puntero;
begin
  if (FConteo >= FCapacidad) then
    raise EOperacionInvalida.Create('La lista está llena');
 
  Destino := @FDatos;
  Inc(Destino, FConteo);
  Destino^ := AElemento;
 
  Inc(FConteo);
end;

Dado que Puntero es un tipo de puntero, podemos usar la lógica de punteros simple. Primero configuramos Destino para que apunte a la dirección del primer elemento del array, luego lo incrementamos con el FConteo actual. Como referencia, aquí hay dos alternativas para realizar el mismo cálculo:

{$POINTERMATH ON}
Destino := P(@FDatos) + FConteo;

Esto agrega directamente el contador a la dirección, sin necesidad de una declaración Inc separada. Pero requiere convertir P y habilitar la directiva POINTERMATH.

Otra forma es realizar todo el cálculo manualmente:

Elemento := P(IntPtr(@FDatos) + (FConteo * SizeOf(T)));

En Delphi, primero necesitamos convertir la dirección a un tipo entero,最好是类型 IntPtr para ser compatible en todas las plataformas. Después de eso, necesitamos incrementar el valor usando el contador multiplicado por el tamaño del tipo de elemento de la lista. Finalmente, necesitamos hacer typecast de todo a P. Esta es una forma más compleja de lograr lo mismo, pero es la forma en que el compilador convierte las dos primeras versiones detrás de escenas. Así que es bueno saber qué está sucediendo.

Lista con Tipos Gestionados

Pero, ¿qué quieres si necesitas una lista de cadenas u objetos? La restricción de registro del parámetro de tipo T actualmente no permite esto. Podemos eliminar esta restricción, pero debemos asegurarnos de gestionar los tipos gestionados en la lista. El ejemplo E03ListaPilaConTiposGestionados muestra cómo hacerlo.

Primero, el campo FDatos cuando se declara la lista en la pila generalmente contiene datos aleatorios. Si interpretamos estos datos como elementos de tipo gestionado, esto probablemente provocará violaciones de acceso, ya que Delphi intentará actualizar el recuento de referencias de una cadena (u otro tipo gestionado) usando una dirección aleatoria.

Por lo tanto, necesitamos inicializar explícitamente FDatos en el método Inicializar:

procedure TListaPila<T, TTamano>.Inicializar;
begin
  ...
  if EsTipoGestionado(T) then
    FillChar(FDatos, SizeOf(FDatos), 0);
end;

Ten en cuenta que esto solo es necesario cuando T es un tipo gestionado, verificado con EsTipoGestionado.

EsTipoGestionado es una función de "magia del compilador", lo que significa que la condición if se evalúa en tiempo de compilación, no en tiempo de ejecución. Por lo tanto, cuando se compila un TListaPila<Integer>, la verificación y la instrucción FillChar se eliminan completamente del código. Por otro lado, cuando se compila un TListaPila<Cadena>, la verificación if también se elimina del código, pero la instrucción FillChar permanece. Esta función mágica del compilador (y otras funciones mágicas como TieneReferenciaDebil y ObtenerTipo) pueden ser útiles para crear código que evita comprobaciones en tiempo de ejecución por razones de eficiencia.

Además, ahora necesitamos un método Finalizar (que debe llamarse en una sección finally) para liberar los elementos gestionados de la lista. Este método es equivalente a un destructor:

procedure TListaPila<T, TTamano>.Finalizar;
begin
  Limpiar;
end;
 
procedure TListaPila<T, TTamano>.Limpiar;
begin
  if EsTipoGestionado(T) then
  begin
    FinalizarArray(@FDatos, TypeInfo(T), FConteo);
    FillChar(FDatos, FConteo * SizeOf(T), 0);
  end;
  FConteo := 0;
end;

Utiliza la rutina FinalizarArray de la unidad System para decrementar el recuento de referencias de los elementos del array (dependiendo de su tipo). Sin esto, los elementos del array nunca se liberarían, lo que provocaría fugas de memoria.

Las demás partes del código permanecen igual. Es posible que te preguntes si esta parte del código aún funcionará correctamente:

var
  Destino: Puntero;
begin
  Destino := @FDatos;
  Inc(Destino, FConteo);
  Destino^ := AElemento;
end;

Porque Puntero podría ser un puntero a un tipo gestionado, es posible que te preguntes si este código omitirá cualquier recuento de referencias. No es el caso. Cuando Delphi compila este código para tipos gestionados, se asegurará de que la asignación Destino^ disminuya el recuento de referencias del elemento original (si existe) e incremente el recuento de referencias del nuevo elemento asignado.

Una Lista de Pila Creciente

Si sabes de antemano el número máximo de elementos que contendrá la lista, los ejemplos discutidos anteriormente pueden funcionar bien. Agregar más provocará una excepción. Pero si quieres aprovechar los beneficios de la pila pero aún así poder aumentar la colección cuando sea necesario, ¿qué puedes hacer?

Por lo tanto, para el último ejemplo, veremos cómo crear una lista que usa la pila para una cierta cantidad de elementos, pero que puede extenderse al montículo si es necesario. Esto puede ofrecer lo mejor de ambos mundos: si el número de elementos se mantiene bajo, se evita completamente el uso de memoria dinámica; pero si es necesario, aún puedes aumentar la colección sin problemas.

Puedes encontrar esta versión en el ejemplo E04ListaPilaCrecible en el repositorio. Esta versión no permite los tipos gestionados para sus elementos, por lo que podemos centrarnos en la parte "creciente".

type
  TListaPila<T: registro; TTamano: registro> = record
  private
    FDatosPila: TTamano;
    FCapacidadPila: Integer;
    FDatosMonticulo: Puntero;
    FCapacidadMonticulo: Integer;
    FConteo: Integer;
    ...

Ahora, cuando agreguemos un elemento, verificamos si aún cabe en la pila, y si no, aumentaremos la colección en el montículo:

procedure TListaPila<T, TTamano>.Agregar(const AElemento: T);
var
  Destino: Puntero;
  Indice: Integer;
begin
  if (FConteo < FCapacidadPila) then
    { Todavía podemos agregar este elemento a la memoria de pila. }
    Destino := @FDatosPila;
    Inc(Destino, FConteo);
  else
  begin
    { Necesitamos agregar este elemento a la memoria del montículo.
      Primero calculamos el índice en la memoria del montículo. }
    Indice := FConteo - FCapacidadPila;
 
    { Aumentamos la memoria del montículo si es necesario para acomodar el índice }
    if (Indice >= FCapacidadMonticulo) then
      Aumentar;
 
    Destino := FDatosMonticulo;
    Inc(Destino, Indice);
  end;
 
  Destino^ := AElemento;
  Inc(FConteo);
end;

El campo FDatosPila retendrá los primeros FCapacidadPila elementos. Cualquier otro elemento adicional se asignará en el montículo. El campo FDatosMonticulo es un puntero a un array que puede contener hasta FCapacidadMonticulo elementos. Cuando se alcanza esta capacidad, se aumenta este bloque de memoria:

{$IF (RTLVersion < 33)}
procedure TListaPila<T, TTamano>.Aumentar;
begin
  { Estrategia de crecimiento previa a Rio: duplicar el tamaño de la colección }
  if (FCapacidadMonticulo = 0) then
    FCapacidadMonticulo := 4
  else
    FCapacidadMonticulo := FCapacidadMonticulo * 2;
  ReallocMem(FDatosMonticulo, FCapacidadMonticulo * SizeOf(T));
end;
{$ELSE}
procedure TListaPila<T, TTamano>.Aumentar;
begin
  { Delphi Rio introdujo una estrategia de crecimiento configurable por el usuario }
  FCapacidadMonticulo := CrecerColeccion(FCapacidadMonticulo, FCapacidadMonticulo + 1);
  ReallocMem(FDatosMonticulo, FCapacidadMonticulo * SizeOf(T));
end;
{$ENDIF}

Aquí, aprovechamos la estrategia de crecimiento configurable por el usuario que introdujo Delphi Rio. Cuando se usan versiones más antiguas de Delphi, duplicamos el tamaño de la colección por defecto.

Al recuperar un elemento, también debemos verificar si está en la pila o en el montículo:

function TListaPila<T, TTamano>.ObtenerElemento(const AIndice: Integer): T;
var
  Elemento: Puntero;
begin
  if (AIndice < 0) or (AIndice >= FConteo) then
    raise EArgumentoFueraDeRango.Create('El índice de la lista está fuera de rango');
 
  if (AIndice < FCapacidadPila) then
  begin
    Elemento := @FDatosPila;
    Inc(Elemento, AIndice);
  end
  else
  begin
    Elemento := FDatosMonticulo;
    Inc(Elemento, AIndice - FCapacidadPila);
  end;
 
  Resultado := Elemento^;
end;

Finalmente, debemos asegurarnos de liberar cualquier dato asignado en el montículo en el método Finalizar.

Cuándo No Usar Colecciones de Pila

Las colecciones basadas en la pila ciertamente tienen sus usos, pero los beneficios dependen del caso específico. Si solo necesitas ocasionalmente una lista temporal, generalmente no tiene sentido usar una lista de pila, y deberías aprovechar la flexibilidad de las "normales" listas.

Además, las listas de pila ocupan memoria en la pila. Esto generalmente no es un problema, ya que todas las plataformas actuales ofrecen una pila bastante grande. Sin embargo, si usas una lista de pila en una rutina recursiva, en algún punto podrías encontrarte con un desbordamiento de pila. Por lo tanto, mi recomendación es mantener el tamaño de las listas de pila dentro de unos pocos KB. Si necesitas más, entonces la fragmentación de memoria y la velocidad probablemente no sean tu cuello de botella, y las listas normales son suficientes.

Así que como siempre, úsalas cuando sea apropiado, no solo porque puedes.

Si encuentros algún caso de uso interesante con colecciones basadas en pila, házmelo saber.

Etiquetas: Delphi Colecciones Gestión de memoria Memoria de pila programación genérica

Publicado el 6-11 01:01

Etiquetas populares

©2026 Friki Work