16 replies to this topic

[Delphius]

Buenas,

 

He estado trabajando en mis bibliotecas, y mientras seguía avanzando sobre mis algoritmos llegué a material que ofrece el MIT que a mi ver le terminaría poniendo la cereza al postre.

A los algoritmos ya los tengo estudiado y estoy en proceso de portarlo a mi querido Lazarus.

 

Mi duda ahora se debe a que el material de estudio, y que ya había visto de otras fuentes de consulta y en bibliotecas libres aprovechan y recomiendan mucho el uso de punteros y la aritmética. Y si bien le voy entiendiendo hay cosillas que se me escapan un poco. Miedo a los punteros le estoy perdiendo gracias a Dios.

 

Hasta donde yo tengo entendido podemos reservar memoria con AllocMem() y obtener el puntero a ese bloque. Este bloque de memoria lo podríamos usar como vector, matriz, etc.

Suponiendo que queremos trabajar con tipo double, podríamos hacer algo como esto:

delphi

procedure TForm1.Button1Click(Sender: TObject);
var Matrix: PDouble;
begin
  Matrix := AllocMem(ROWS*COLS*SizeOf(Double));
  // operamos
  FreeMem(Matrix);
end;

En el código se aprecia que se reservan los bytes necesarios para la cantidad requerida y adecuada para el tipo. Para ser exactos: ROWS*COLS*8 bytes

 

Ahora bien, mi primera duda es cómo se debiera de ubicarse en cada "celda" de 8 bytes. ¿Es válido esto?

delphi

procedure TForm1.Button1Click(Sender: TObject);
var Matrix: PDouble;
    i, Size: integer;
begin
  //reservamos
  Size := ROWS * COLS;
  Matrix := AllocMem(Size * SizeOf(Double));
  // operamos
  for i := 0 to Size - 1 do
  Matrix[i] := random;
  // liberamos
  FreeMem(Matrix);
end;

¿O debe hacerse así?

delphi

procedure TForm1.Button1Click(Sender: TObject);
var Matrix: PDouble;
    i, Size: integer;
begin
  //reservamos
  Size := ROWS * COLS;
  Matrix := AllocMem(Size * SizeOf(Double));
  // operamos
  for i := 0 to Size - 1 do
  (Matrix + i)^ := random;
  // liberamos
  FreeMem(Matrix);
end;

¿O es lo mismo?

 

Esto lo pregunto tras leer este hilo en el foro de Lazarus. No me queda bien claro.

 

Relacionada con esta duda, me asalta otra. Esta aritmética de punteros tiene sentido mientras la memoria reservada sea contínua, al menos así es como lo tengo entendido. Y lo que leí en unos comentarios en una biblioteca llama mrMath me deja un poco intranquilo:

delphi

function MtxAlloc( NumBytes : TASMNativeInt ) : Pointer;
begin
     assert(NumBytes and $7 = 0, 'Numbytes not multiple of 8');
 
     Result := nil;
     if NumBytes <= 0 then
        exit;
 
     // align to next multiple of 16 bytes
     if NumBytes and $F <> 0 then
        NumBytes := NumBytes and $FFFFFFF0 + 16;
 
     Result := GetMemory(NumBytes);
     if Assigned(Result) then
     begin
          // normally getMemory should return aligned bytes ->
          // but just in case:
          if (TASMNativeUInt( Result ) and $F) <> 0 then
          begin
               PDouble(Result)^ := 0;
               inc(PByte(Result), 8);
               memInitfunc(Result, NumBytes - 8, 0);
               dec(PByte(Result), 8);
          end
          else
              memInitFunc(Result, NumBytes, 0);
     end;
end;

Ahi tiene anotado: que normalmente GetMemory devuelve bytes alineados. La ayuda no dice nada del tema:

 

GetMemory allocates a memory block.

GetMemory allocates a block of the given Size on the heap, and returns the address of this memory. The bytes of the allocated buffer are not set to zero. To dispose of the buffer, use FreeMemory. If there is not enough memory available to allocate the block, an EOutOfMemory exception is raised.

If the memory needs to be zero-initialized, you can use AllocMem.

 Note: GetMemory is the C++ compatible version of GetMem.

 

La llamada de AllocMem del código inicial que expuse, y que corresponde a Lazarus, no es más que una envoltura la llamada a GetMem. Así lo deja expreso su documentación:

 

 

Allocate and clear memory.

Declaration

Source position: heaph.inc line 93

function AllocMem(

  Size: PtrUInt

):pointer;

Description

AllocMem calls getmem GetMem, and clears the allocated memory, i.e. the allocated memory is filled with Size zero bytes.

 

Esto dice GetMem:

 

 

procedure Getmem(

 

  out p: pointer;

  Size: PtrUInt

);

function GetMem(

  size: PtrUInt

):pointer;

Description

Getmem reserves Size bytes memory on the heap, and returns a pointer to this memory in p. What happens if no more memory is available, depends on the value of the variable ReturnNilIfGrowHeapfails: if the variable is True then Nil is returned. If the variable is False, a run-time error is generated. The default value is False, so by default an error is generated.

 

Ahora bien, podemos usar directamente la llamada MAlloc de la librería Cmem, ya que en última todo se delega a esta, y que no es más de lo mismo que vinimos usando: es un wrapper a la biblioteca de C++. ¡Por lo que todo termina en roma!

 

 

Declaration

Source position: cmem.pp line 51

function Malloc(

  Size: ptruint

):Pointer;

Arguments

Size

  

Requested size for the new memory block.

Function result

A pointer to the newly allocated memory block

Description

Malloc is the external declaration of the C librarys malloc call. It accepts a size parameter, and returns a pointer to a memory block of the requested size or Nil if no more memory could be allocated.

 

El asunto es que no veo en ninguna parte de la doc, de delphi como de Lazarus, que se aclare el punto si efectivamente hay vía segura de que la memoria estará alineada y continua. O si existe posibilidad de que no.

 

¿Alguno sabría aclararme estas dudas?

 

Saludos,

[escafandra]

Lazarus tiene una artimética de punteros más parecida a C que a Delphi. En Delphi podemos hacer esto sin problemas:

delphi

var
  Matrix: PAnsiChar;
begin
  .....
  (Matrix + i)^ := 'a';

El tamaño de AnsiChar es 1, pero no sirve si hacemos lo mismo con el tipo PBYTE aunque BYTE tenga el mismo tamaño, es decir, 1.

Sin embargo cuando incrementamos un puntero, la aritmética es correcta, es decir si el tamaño del tipo es 4 e incrementamos en 1 el puntero, se incrementa en 4. De forma que siempre me he preguntado porqué Delphi no deja sumar un entero a un puntero para tener una expresión como esta:

delphi

var
  Matrix: PDouble;
begin
  .....
  (Matrix + i)^ := 1.2;

Esa expresión es válida para C (su equivalente en sintaxis) y Lazarus. En C sería algo como esto:

cpp

{
  double *Matrix;
  .......
  *(Matrix + i) = 1.2;

La aritmética de punteros, se solapa con los índices de un array unidimensional de forma que en C las expresiones son equivalentes:

cpp

{
  double *Matrix;
  .......
  Matrix[i] = 1.2;
  *(Matrix + i) = 1.2;

Esto es así porque la representación en memoria del array es como la expresión con punteros, es decir, un array está representado por un puntero al primer elemento del array.

¿Pero que pasa con un array multidimensional? Pues que el asunto cambia un poco... o no. Un array multidimensional es un array de arrays, es decir es un array de punteros cada uno de los cuales representa otro array del tipo que definamos.

delphi

var
  Matrix: array of array of double; // es un array de arrays del tipo double

Recuerda este hilo donde tuvimos la oportunidad de implementar a bajo nivel estos temas, de forma que tus ejemplos sólo son válidos para un array unidimensional.

 

Sobre el tema de la continuidad de la memoria y/o su alineación, son cosas diferentes. Un puntero está alineado a un número cuando la dirección que define ese puntero, es múltiplo de dicho número. Las funciones de asignación de memoria devuelven montos de memoria continua, no tiene sentido otra cosa y fallan cuando no pueden asignar dicha memoria. La memoria deben darla alineada también, aunque el tipo de alineación puede depender de parámetros pasados al compilador, cuando éste los admite. La alineación es fundamental para el bloque de código, como es lógico que así sea.

 

Cuando declaramos un array dinámico y le asignamos un tamaño, no estamos haciendo más que pedir memoria al sistema que a bajo nivel será reservada con las funciones propias para ello, que en muy última instancia serán las que la API del S.O. en cuestión, establezca. Es de esperar que la memoria devuelta esté alineada pero en el caso de no estarlo no debería influir en la aritmética de punteros ya que esta siempre debería sumar al puntero el número multiplicado por el tamaño del tipo.

 

Nunca he tenido problemas con la alineación de un bloque de memoria salvo cuando desde una app compilada para 32bits quería ejecutar código de la API de 64bits, en ese caso he tenido asegurar la alineación de la pila a 8 ó 16bits. En el foro publiqué el caso.

 

 

Saludos.

[escafandra]

Recuerda este hilo donde tuvimos la oportunidad de implementar a bajo nivel estos temas, de forma que tus ejemplos sólo son válidos para un array unidimensional.

 

Quiero matizar la afirmación anterior. En el caso que definas un bloque de memoria estático de un tamaño fijo ROWS*COLS*SizeOf(Double) y que decidas la organización de memoria continua, de esas filas y columnas, puedes almacenar en este pseudoarray bidimensional todos tus datos y recuperarlos con aritmética de punteros, pero no con aritmética de arrays, es decir no podrás usar un doble índice si realizas un cast a un array de dos dimensiones puesto que internamente no lo es, no es un array de arrays, sino un array unidimensional en el que consideras que acabadas las filas comienza una nueva columna con más filas (o al revés, como dispongas).

 

 

Saludos.

[Delphius]

Muchas gracias amigo por tu explicación.

Ya voy entendiendo de a poco esto.

 

Lo que no se si estoy seguro de si entendí bien es si entonces da igual hacerlo por (puntero + indice)^ que puntero[indice] en Lazarus. Entiendo que comentaste que en C es válido, pero no estoy seguro si entendí bien si también lo es en Lazarus.

 

Como bien dices, al hacerlo ROWS*COLS*Size es una matriz dispuesta unidimensional. Y esto es para aprovechar y facilitar el indexado, velocidades y evita lidiar con punteros de punteros. Tal como debatimos en ese hilo.

 

Me quedo más tranquilo sobre el tema de la continuidad y alineación de la memoria. Esto también me ha preocupado debido a que los algoritmos que estoy por implementar son justamente del tipo cache-oblivious. Son algoritmos diseñados para reducir los errores de caché, y ya había leído algo sobre continuidad y he llegado a preocuparme de que pudiera afectar. Estos algoritmos asumen que la memoria es contínua.

 

Saludos,

[escafandra]

Lo que no se si estoy seguro de si entendí bien es si entonces da igual hacerlo por (puntero + indice)^ que puntero[indice] en Lazarus. Entiendo que comentaste que en C es válido, pero no estoy seguro si entendí bien si también lo es en Lazarus.

Ambas expresiones son válidas en Lazarus y en C. Aunque si configuraqmos el compilador de Lazarus para compatibilidad con Delphi, probablemente no permita esas expresiones, no lo he probado.

Saludos.

[Delphius]

Muchas gracias por la aclaración.

En la tarde hago mis pruebas del comportamiento. Anoche hice una prueba muy básica de algoritmo de recorrido y suma de elementos de un diseño basado en punteros contra uno de array unidimensional dinámico. ¡Curiosamente el ganador seguía siendo el array dinámico! Es cierto que no usé el mejor método para medir los tiempos, y debí usar QueryPerfomance.

La prueba de esta tarde será más real life y observaré el comportamiento no sólo en tiempos sino en uso de memoria y procesador.

Me cuesta creer que los arrays dinámicos aún en grandes dimensiones (he llegado a probar con una de 90mil elementos) le hayan ganado a los punteros por casi 3 segundos.

 

Saludos,

[Delphius]

He estado haciendo unas prueba que a mi ver ya debiera de ser significativa.

Un clásico algoritmo que se suele utilizar para comprobar la velocidad y uso de memoria para grandes dimensiones es la multiplicación de matrices. Así que lo implementé, aprovechando la técnica de tener un arreglo unidimensional y valiéndome de la maravillosa matemática ubicar los elementos adecuadamente.

 

Evalué la técnica de punteros, que puede verse en el post inicial de este hilo, contra el tradicional esquema de un arreglo dinámico (también llevado unidimensionalmente).

La prueba consistió en una multiplicación de matrices de (300 x 500) x (500 x 400) = (300 x 400). En promedio, el algoritmo basado en punteros se toma en mi "equipito" unos 300.000 microsegundos, y su mejor performance la tuvo en 291.000.

Por su parte la versión tradicional le aventajó, cuyo promedio fue de 290.000 y su mejor resultado en los 280.000.

 

Ambos algoritmos no consumen demasiado CPU, ni cosquillas le hacen. y el uso de memoria es indiferente, ni se aprecia ventaja de uno respecto a otro. Es de esperar puesto que ambos reservan y liberan la misma cantidad. No hay consumo adicional o secundario.

 

Me sigue sorprendiendo la ventaja del arreglo dinámico.    Aún cuando estoy usando Lazarus, que según algunos entendidos no es tan optimizado respecto a su contraparte Delphi.

Debe de haber alguna explicación, aunque mis conocimientos actualmente sobre el tema no me permiten ir hacia ello. O es que SetLength ha sido pensando y optimizado en cierta forma, que la técnica a punteros que estoy llevando a cabo no tiene.

 

Voy a hacer otra prueba, esta será un poco más dura... vamos a ponerle un cero más a las dimensiones   a ver si me sigue dando sorpresitas.

 

EDITO Y AGREGO:

Pues, como he dicho, le puse un cero más a las dimensiones: (3000 x 5000) x (5000 x 4000) = (3000 x 4000), cuyo total de memoria reservada entre las 3 estructuras asciende a un aproximado de 359 MB (redondeado para arriba).

Esta vez, se observa una merma de ventaja. Hice una sola corrida con ambos diseños, y obtuve:

Punteros: 839.720.025 micro-seg
Dinámico: 831.391.298 micro-seg

 

Son aproximadamente 8seg de diferencia. El consumo de CPU esta vez sube a un aproximado entre el 15% al 17%, al menos durante el 1er minuto de la prueba de los punteros... no he podido ver el consumo en la prueba de dinámicos puesto que tuve que dejar la máquina trabajando mientras salí de casa. Creería que el consumo sería bastante similar.

 

Mi pronostico es que a medida que aumente la dimensión, la memoria a reservar para ser más preciso, la diferencia entre ambas técnicas tienda a cero. Todavía no tengo una explicación razonable sobre el porque de la ventaja del arreglo dinámico, pero mi primera aproximación me lleva a pensar a que está relacionado con el uso de la memoria caché y el paso/intercambio entre éstas, al menos hasta el nivel 2: L2 <-> L1 <-> Caché Micro.

Mi prueba inicial antes de sumarle un cero a las dimensiones hacía un tamaño de memoria que fácilmente podría caber en la caché L1, mientras que estos 359 MB evidentemente deben ser llevados a L2. Cuanto más nos alejemos de la caché del micro más tiempo nos consume. Gracias a que en la prueba inicial toda la memoria reservada entraba en la L1 la info esta todo en línea y disponible. Al ir hacia el nivel L2, notamos que empiezan a aparecer saltos y una merma en general.

Ahora bien, esto explicaría parcialmente el tema. No termina de enfocar el porqué los arrays dinámicos son más rápidos... ¿será que emplean diferentes juegos de instrucciones del microprocesador y los arreglos dinámicos aprovechan alguno en particular que le permite sacar alguna ventaja?

 

Saludos,

[escafandra]

Todo depende del código usado y del compliado.  En C es más eficiente la aritmética de punteros que la indexaión.  Es decir:

cpp

// Más eficiente
for(puntero = pointer; *puntero; puntero++){
   ...
}
 
// Más lento:
for(int n = 0; puntero[n]; n++){
   ...
}

Habría que ver como compila Lazarus. En principio el uso de punteros con indexación no va a cambiar mucho al uso de un array pues en el fondo se van a tratar de forma muy similar. El cómo se reserva memoria y el tipo también repercutirá. Esto va a depender del S.O. y de la API usada. Grandes bloques pueden terminar precisando memoria virtual en disco lo que repercute de forma nefasta en el rendimiento de la app cuya memoria usada no es física.

 

Saludos. 

[Delphius]

Todo depende del código usado y del compliado.  En C es más eficiente la aritmética de punteros que la indexaión.  Es decir:

cpp

// Más eficiente
for(puntero = pointer; *puntero; puntero++){
   ...
}
 
// Más lento:
for(int n = 0; puntero[n]; n++){
   ...
}

Habría que ver como compila Lazarus. En principio el uso de punteros con indexación no va a cambiar mucho al uso de un array pues en el fondo se van a tratar de forma muy similar. El cómo se reserva memoria y el tipo también repercutirá. Esto va a depender del S.O. y de la API usada. Grandes bloques pueden terminar precisando memoria virtual en disco lo que repercute de forma nefasta en el rendimiento de la app cuya memoria usada no es física.

 

Saludos. 

 

He editado mi post anterior mientras respondiste.

Me dejas pensando un poco sobre el tema.

 

Es cierto que en parte depende de como es que compila Lazarus. Yo asumo que dentro de todo, mantiene una "igualdad de condiciones" en todo momento de la compilación. El código no tiene demasiada magia:

delphi

unit Unit1;
 
{$mode objfpc}{$H+}
 
interface
 
uses
  Classes, SysUtils, FileUtil, Forms, Controls, Graphics, Dialogs, StdCtrls, Math, Windows;
 
const
  UnMicro = 1000000;
 
  // A: 300 x 500 = 150.000 >> Size: 1,14 MB
  ROWS_A = 3000;
  COLS_A = 5000;
 
  // B: 500 x 400 = 200.000 >> Size: 1,53 MB
  ROWS_B = 5000;
  COLS_B = 4000;
 
  // C: 300 x 400 = 120.000 >> Size: 0,92 MB
  // Total: 3,59 MB
  posic = '(%d, %d) = %f';
 
  {Indice >> (i,j):
   DivMod(ix, Cols, i, j);
   i := i + 1;
   j := j + 1;
  }
 
 
type
 
  TMatrix = array of Double;
 
  { TForm1 }
 
  TForm1 = class(TForm)
    Button1: TButton;
    Button2: TButton;
    Button3: TButton;
    Button4: TButton;
    Memo1: TMemo;
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
    procedure Button3Click(Sender: TObject);
    procedure Button4Click(Sender: TObject);
    procedure FormCreate(Sender: TObject);
  private
    FFrecuency: Int64;
    FCounterIni: Int64;
    FCounterEnd: Int64;
 
    FTimeIni: TDateTime;
    FTimeEnd: TDateTime;
    procedure StartOperation(Operation: string);
    procedure FinishOperation(Operation: string; TimeIni, TimeEnd: TDateTime; CounterIni, CounterEnd: Int64);
    procedure RestartClock;
  public
 
  end;
 
var
  Form1: TForm1;
 
implementation
 
{$R *.lfm}
 
{ TForm1 }
 
procedure TForm1.Button1Click(Sender: TObject);
var MA, MB, MC: PDouble;
    Size, ix: Integer;
begin
  // Armar A
  StartOperation('Inicialización A');
  Size := ROWS_A * COLS_A;
  FTimeIni := Now;
  QueryPerformanceCounter(FCounterIni);
 
  MA := AllocMem(Size * SizeOf(PDouble));
  for ix := 0 to Size - 1 do
    (MA + ix)^ := ix + 1;
 
  FTimeEnd := Now;
  QueryPerformanceCounter(FCounterEnd);
  FinishOperation('Finalizando A',FTimeIni, FTimeEnd, FCounterIni, FCounterEnd);
 
  // Armar B
  StartOperation('Inicialización B');
  Size := ROWS_B * COLS_B;
  FTimeIni := Now;
  QueryPerformanceCounter(FCounterIni);
 
  MB := AllocMem(Size * SizeOf(PDouble));
  for ix := 0 to Size - 1 do
    (MB + ix)^ := ix + 1;
 
  FTimeEnd := Now;
  QueryPerformanceCounter(FCounterEnd);
  FinishOperation('Finalizando B',FTimeIni, FTimeEnd, FCounterIni, FCounterEnd);
 
  // Armar C
  StartOperation('Inicialización C');
  Size := ROWS_A * COLS_B;
  FTimeIni := Now;
  QueryPerformanceCounter(FCounterIni);
 
  MC := AllocMem(Size * SizeOf(PDouble));
  for ix := 0 to Size - 1 do
    (MB + ix)^ := ix + 1;
 
  FTimeEnd := Now;
  QueryPerformanceCounter(FCounterEnd);
  FinishOperation('Finalizando C',FTimeIni, FTimeEnd, FCounterIni, FCounterEnd);
 
  FreeMem(MA);
  FreeMem(MB);
  FreeMem(MC);
 
  if MA = nil
     then Memo1.Lines.Add('MA es nil')
     else Memo1.Lines.Add('MA a pesar de ser liberado no es nil');
  if MB = nil
     then Memo1.Lines.Add('MB es nil')
     else Memo1.Lines.Add('MB a pesar de ser liberado no es nil');
  if MC = nil
     then Memo1.Lines.Add('MC es nil')
     else Memo1.Lines.Add('MC a pesar de ser liberado no es nil');
end;
 
procedure TForm1.Button2Click(Sender: TObject);
begin
  Memo1.Clear;
end;
 
procedure TForm1.Button3Click(Sender: TObject);
var MA, MB, MC, PA, PB, PC: PDouble;
    Size, IxA, IxB, IxC, i, j, k: Integer;
    val: Double;
begin
  // Armar A
  StartOperation('Inicialización A');
  Size := ROWS_A * COLS_A;
  FTimeIni := Now;
  QueryPerformanceCounter(FCounterIni);
 
  MA := AllocMem(Size * SizeOf(PDouble));
  for ixA := 0 to Size - 1 do
    (MA + ixA)^ := ixA + 1;
 
  FTimeEnd := Now;
  QueryPerformanceCounter(FCounterEnd);
  FinishOperation('Finalizando A',FTimeIni, FTimeEnd, FCounterIni, FCounterEnd);
 
  // Armar B
  StartOperation('Inicialización B');
  Size := ROWS_B * COLS_B;
  FTimeIni := Now;
  QueryPerformanceCounter(FCounterIni);
 
  MB := AllocMem(Size * SizeOf(PDouble));
  for ixB := 0 to Size - 1 do
    (MB + ixB)^ := ixB + 1;
 
  FTimeEnd := Now;
  QueryPerformanceCounter(FCounterEnd);
  FinishOperation('Finalizando B',FTimeIni, FTimeEnd, FCounterIni, FCounterEnd);
 
  // Armar C
  StartOperation('Rservando C');
  Size := ROWS_A * COLS_B;
  FTimeIni := Now;
  QueryPerformanceCounter(FCounterIni);
 
  MC := AllocMem(Size * SizeOf(PDouble));
 
  FTimeEnd := Now;
  QueryPerformanceCounter(FCounterEnd);
  FinishOperation('Fin. Reserva:  C',FTimeIni, FTimeEnd, FCounterIni, FCounterEnd);
 
  // Calcular Multiplicación
  PA := MA;
  PB := MB;
  PC := MC;
  StartOperation('Multiplicando');
  FTimeIni := Now;
  QueryPerformanceCounter(FCounterIni);
 
  for i := 0 to ROWS_A - 1 do
  begin
    for j := 0 to COLS_B - 1 do
    begin
      val := 0.0;
      for k := 0 to COLS_A - 1 do
      begin
        // calcular indices
        IxA := (i * COLS_A) + k;
        IxB := (k * COLS_B) + j;
        IxC := (i * COLS_B) + j;
        // operamos
        val := Val + Double((PA + IxA)^) * Double((PB + IxB)^);
      end;
      // nos ubicamos en el indice de C correspondiente
      (PC + IxC)^ := Val;
    end;
  end;
 
  FTimeEnd := Now;
  QueryPerformanceCounter(FCounterEnd);
  FinishOperation('Fin. Multiplicación', FTimeIni, FTimeEnd, FCounterIni, FCounterEnd);
 
  PA := nil;
  PB := nil;
  PC := nil;
 
  FreeMem(MA, ROWS_A * COLS_A * SizeOf(PDouble));
  FreeMem(MB, ROWS_B * COLS_B * SizeOf(PDouble));
  FreeMem(MC, ROWS_A * COLS_B * SizeOf(PDouble));
 
  if MA = nil
     then Memo1.Lines.Add('MA es nil')
     else Memo1.Lines.Add('MA a pesar de ser liberado no es nil');
  if MB = nil
     then Memo1.Lines.Add('MB es nil')
     else Memo1.Lines.Add('MB a pesar de ser liberado no es nil');
  if MC = nil
     then Memo1.Lines.Add('MC es nil')
     else Memo1.Lines.Add('MC a pesar de ser liberado no es nil');
end;
 
procedure TForm1.Button4Click(Sender: TObject);
var MA, MB, MC: TMatrix;
    Size, IxA, IxB, IxC, i, j, k: Integer;
    val: Double;
begin
  // Armar A
  StartOperation('Inicialización A');
  Size := ROWS_A * COLS_A;
  FTimeIni := Now;
  QueryPerformanceCounter(FCounterIni);
 
  SetLength(MA, Size);
  for IxA := 0 to Size - 1 do
    MA[IxA] := IxA + 1;
 
  FTimeEnd := Now;
  QueryPerformanceCounter(FCounterEnd);
  FinishOperation('Finalizando A',FTimeIni, FTimeEnd, FCounterIni, FCounterEnd);
 
  // Armar B
  StartOperation('Inicialización B');
  Size := ROWS_B * COLS_B;
  FTimeIni := Now;
  QueryPerformanceCounter(FCounterIni);
 
  SetLength(MB, Size);
  for IxB := 0 to Size - 1 do
    MB[IxB] := IxB + 1;
 
  FTimeEnd := Now;
  QueryPerformanceCounter(FCounterEnd);
  FinishOperation('Finalizando B',FTimeIni, FTimeEnd, FCounterIni, FCounterEnd);
 
  // Armar C
  StartOperation('Rservando C');
  Size := ROWS_A * COLS_B;
  FTimeIni := Now;
  QueryPerformanceCounter(FCounterIni);
 
  SetLength(MC, Size);
 
  FTimeEnd := Now;
  QueryPerformanceCounter(FCounterEnd);
  FinishOperation('Fin. Reserva:  C',FTimeIni, FTimeEnd, FCounterIni, FCounterEnd);
 
  // Calcular Multiplicación
  StartOperation('Multiplicando');
  FTimeIni := Now;
  QueryPerformanceCounter(FCounterIni);
 
  for i := 0 to ROWS_A - 1 do
  begin
    for j := 0 to COLS_B - 1 do
    begin
      val := 0.0;
      for k := 0 to COLS_A - 1 do
      begin
        // calcular indices
        IxA := (i * COLS_A) + k;
        IxB := (k * COLS_B) + j;
        IxC := (i * COLS_B) + j;
        // operamos
        val := Val + (MA[IxA] * MB[IxB]);
      end;
      // nos ubicamos en el indice de C correspondiente
      MC[IxC] := Val;
    end;
  end;
 
  FTimeEnd := Now;
  QueryPerformanceCounter(FCounterEnd);
  FinishOperation('Fin. Multiplicación', FTimeIni, FTimeEnd, FCounterIni, FCounterEnd);
 
  SetLength(MA, 0);
  SetLength(MB, 0);
  SetLength(MC, 0);
  //MA := nil;
  //MB := nil;
  //MC := nil;
 
  if MA = nil
     then Memo1.Lines.Add('MA es nil')
     else Memo1.Lines.Add('MA a pesar de ser liberado no es nil');
  if MB = nil
     then Memo1.Lines.Add('MB es nil')
     else Memo1.Lines.Add('MB a pesar de ser liberado no es nil');
  if MC = nil
     then Memo1.Lines.Add('MC es nil')
     else Memo1.Lines.Add('MC a pesar de ser liberado no es nil');
end;
 
procedure TForm1.FormCreate(Sender: TObject);
begin
  DecimalSeparator := ',';
  ThousandSeparator := '.';
  QueryPerformanceFrequency(FFrecuency);
end;
 
procedure TForm1.StartOperation(Operation: string);
begin
  Memo1.Lines.Add(Operation);
  Memo1.Lines.Add('...');
end;
 
procedure TForm1.FinishOperation(Operation: string; TimeIni,
  TimeEnd: TDateTime; CounterIni, CounterEnd: Int64);
var Diff: Int64;
begin
  Diff := (CounterEnd - CounterIni) * UnMicro Div FFrecuency;
 
  Memo1.Lines.Add(Operation);
  Memo1.Lines.Add(' *Inicio: ' + FormatDateTime('hh:nn:ss.zzz',FTimeIni));
  Memo1.Lines.Add(' *Fin: ' + FormatDateTime('hh:nn:ss.zzz',FTimeEnd));
  Memo1.Lines.Add(' *Counter: ' + FormatFloat('0,.000', Diff) + ' microseg');
  Memo1.Lines.Add('');
end;
 
procedure TForm1.RestartClock;
begin
  QueryPerformanceFrequency(FFrecuency);
  FCounterIni := 0;
  FCounterEnd := 0;
end;
 
end.

Son 4 botones y un memo. El botón 1 era para probar reserva e inicialización solamente. El 2, para limpiar el memo y el 3ro y 4to implementan los algoritmos de prueba de multiplicación con el método de punteros y arreglos dinámicos respectivamente.

Puedes ver que hago uso de AllocMem y FreeMem al momento de trabjar con punteros, mientras que para el arreglo dinámico uso SetLength.

 

Yo estuve pensando que no debería cambiar mucho, puesto que como dices, en última "por debajo" ambas técnicas deberían trabajar de forma similar. Pero mi prueba me hace pensar que la hipótesis no es del todo cierta (al menos no en todo momento).

 

Voy a darle una mirada al código de SetLength(), a ver si se me escapa algo...

 

Saludos,

[escafandra]

¿Por qué realizas este cast?

delphi

val := Val + Double((PA + IxA)^) * Double((PB + IxB)^);

¿Probaste a localizar memoria con VirtualAlloc?

Saludos.

[Delphius]

¿Por qué realizas este cast?

delphi

val := Val + Double((PA + IxA)^) * Double((PB + IxB)^);

¿Probaste a localizar memoria con VirtualAlloc?

Saludos.

 

Ha decir verdad, puse el cast por seguridad para asegurarme de que se interprete el contenido como double. Dudé si era necesario o no, pero ante la duda preferí dejarlo. No creo que afectase demasiado este cast.

No, no he realizado la prueba con VirtualAlloc para no depender demasiado de la API de Windows. Si bien he usado las API QueryPerformanceFrequency y QueryPerformanceCounter para medir los tiempos, la intención es hacer código final (este es código prototipo y a modo de prueba de concepto) que no dependa del SO.

 

Se que esto implica que puede existir la posibilidad de que en otros SO los resultados varíen... y quien sabe... a lo mejor hiciera que la técnica basada en punteros se comporte mejor que la de arreglos dinámicos.

 

Se que tanto por AllocMem como GetMem se pasa por el Manejador de Memoria que tiene Lazarus. Tengo entendido que esto es para que el manejador intermedie entre la aplicación y las efectivas llamadas correspondiente al SO.

Hasta donde recuerdo que está documentado, SetLength() también pasa por el manejador de memoria.

 

Saludos,

[Delphius]

Acabo de hacer una prueba sin el cast, y si bien compila en tiempo de ejecución obtengo un error por parte de GDB. Esto termina de confirmarme mi sospecha, es necesario el cast a Double.

 

EDITO:

Pues, no, fue una pifia de mi parte. Me había equivocado en las dimensiones. Había alterado al doble de la prueba adicional para que demorara mucho y se me fue un cero de más.

 

Saludos,

[escafandra]

Acabo de hacer una prueba sin el cast, y si bien compila en tiempo de ejecución obtengo un error por parte de GDB. Esto termina de confirmarme mi sospecha, es necesario el cast a Double.

 

EDITO:

Pues, no, fue una pifia de mi parte. Me había equivocado en las dimensiones. Había alterado al doble de la prueba adicional para que demorara mucho y se me fue un cero de más.

 

Saludos,

Efectivamente, si los punteros son del tipo PDouble, no es necesario el cast.

 

Puedes  hacer una prueba para independizar el efecto de SetLength y es mezclar las técnicas:

delphi

var
  MA: TMatrix; //array of double
  PMA: PDouble;
  i: integer;
begin
  SetLength(MA, 1000);
  PMA:= @MA[0];
  for i:= 0 to 1000 do
    (PMA + i)^:= i;
.....
end;

Es decir, usas SetLength para localizar memoria del array que luego manejas con punteros simplemente localizando el puntero del primer elemento del array. Multiplica tus matrices a ver que pasa. el resultado no dependerá de la técnica usada para localizar memoria y será exclusivo del manejo de punteros y del compilador de Lazarus.

 

Saludos.

[Delphius]

Efectivamente, si los punteros son del tipo PDouble, no es necesario el cast.

 

Puedes  hacer una prueba para independizar el efecto de SetLength y es mezclar las técnicas:

delphi

var
  MA: TMatrix; //array of double
  PMA: PDouble;
  i: integer;
begin
  SetLength(MA, 1000);
  PMA:= @MA[0];
  for i:= 0 to 1000 do
    (PMA + i)^:= i;
.....
end;

Es decir, usas SetLength para localizar memoria del array que luego manejas con punteros simplemente localizando el puntero del primer elemento del array. Multiplica tus matrices a ver que pasa. el resultado no dependerá de la técnica usada para localizar memoria y será exclusivo del manejo de punteros y del compilador de Lazarus.

 

Saludos.

 

Si no me termina ganando el sueño (son las 8pm acá) al que vengo dando pelea desde esta mañana, en dos horas hago la prueba; sino las hago mañana por la tarde. Sabía que se puede "mezclar" ambos conceptos. Aunque no me animé a jugar con esa mezcla sin estar seguro.

Si esta alternativa tiene mejores performance que el enfoque tradicional y promete, la usaré para mis siguientes proyectos.

 

Lo que tengo que estudiar bien, es la posibilidad de copiar velozmente estas estructuras. Había visto código que se valían de Move(), aunque nunca hice esa prueba. O si es válida para enfoques "mixtos". Y se que también está disponible Copy(), que funciona con arrays dinámicos y te devuelve uno con la copia, aunque la idea de que Copia := Copy(Original) para arrays dinámicos no me suena del todo feliz... que una función regrese estructuras de datos es legal, aunque yo tengo la postura de que deben evitarse por el tipo de cohesión estructural. Me suenan más acordes la postura de Copy(Original, Copia).

 

Saludos,

[Delphius]

Se que he dejado este hilo medio inconcluso.

Después de un buen número de pruebas, he visto que la versión tradicional (Array dinámicos y el uso de SetLength) ha sido la que mejor se ha desempeñado.

Incluso he probado la última alternativa (la que podría llamarse "mixta") que me ha sugerido el maestro escafandra y para mi sorpresa es ligeramente la de peor desempeño.

 

He consultado en el foro de Lazarus el porque de esto y no obtuve alguna respuesta que me sepa orientar. Lo que si se me ha aconsejado es que si la idea es ganar más velocidad aún el próximo gran paso es acudir a LAPACK, y/o BLAS mediante OpenBLAS.

LAPACK como seguramente sabrán algunos, está escrito en FORTRAN y no es tan sencillo invocarlo o usar LAPACK desde Delphi y/o Lazarus. Primero hay que generar una dll con los headers y para ello hay que usar CMake, y disponer del compilador gcc de fortran, y otras cosas más que no recuerdo ahorita... y todo es un dolor de huevo.

 

Lo he intentado, y no hubo caso. No ha sido posible, hasta el momento con la versión LAPACK 3.7, generarlo. CMake da algunas advertencias y errores en los makelists.

 

Y me parece que no vale la pena esfuerzo adicional en llegar a ese nivel. Por ahora me quedo en el uso de los dinámicos, y seguiré usando esa "magia del compilador" mientras no necesite de más power.

Me queda en el tintero, porque no descarto en absoluto, darle una buena mirada a las fuentes de LAPACK. Hoy es un estándar, tiene años de estudio y puede que aprenda mucho y extraiga más de una lección para expandir mis bibliotecas algebraicas y científicas. No se si como para generar un fork, pero no estará demás contar con esa experiencia portada en Object Pascal.

 

Saludos,

[escafandra]

Me llaman la atención tus resultados lo que me hace pensar que el tratamiento intermedio del compilador tiene mucho que ver en ellos y que está bien optimizado para el uso de arrays de la forma tradicional. En definitiva se trata de que el código haga su trabajo de la forma más eficiente posible. Si en Lazarus la aritmética de punteros de comporta según tus mediciones, quizás convenga migrarla a los arrays tradicionales. Ese truco lo he usado en delphi ya que tiene una la aritmética de punteros muy pobre. El truco se basa en definir un puntero a un tipo array para luego realizar un cast desde un puntero a ese tipo, usándolo como un array normal, con lo que obviamos la aritmética de punteros. En el foro hay bastantes ejemplos en los que uso este truco.

 

 

Saludos.

[Delphius]

Me llaman la atención tus resultados lo que me hace pensar que el tratamiento intermedio del compilador tiene mucho que ver en ellos y que está bien optimizado para el uso de arrays de la forma tradicional. En definitiva se trata de que el código haga su trabajo de la forma más eficiente posible. Si en Lazarus la aritmética de punteros de comporta según tus mediciones, quizás convenga migrarla a los arrays tradicionales. Ese truco lo he usado en delphi ya que tiene una la aritmética de punteros muy pobre. El truco se basa en definir un puntero a un tipo array para luego realizar un cast desde un puntero a ese tipo, usándolo como un array normal, con lo que obviamos la aritmética de punteros. En el foro hay bastantes ejemplos en los que uso este truco.

 

 

Saludos.

 

Yo también lo he visto en algunos que otros lados.

La unidad MrMath, escrita originariamente para Delphi y que supuestamente, (no lo he probado) recientemente tiene soporte para FreePascal, hace uso de esta técnica.

Declara sus arrays dinámicos, pero accede a éstos, mediante un PDouble.

Quise estudiar esta unidad, que parece tener ciertos adeptos, pero es un mar de llamadas sobrecargadas que te marea y llega a nivel asm. Esto me inclinó a estudiar por ejemplo Alglib. Y... ¿sabes que usa Alglib? ¡El más puro enfoque tradicional! que de paso toma algunos conceptos e ideas de BLAS y LAPACK.

 

Es posible que en Delphi sea necesario trucos así, pero por mis pruebas en Lazarus y hasta con la configuración de optimización en level 1 (-O1) la versión tradicional gana (en 0 no he probado la verdad). He probado con -O2 y sigue en la misma tendencia. Admito que no he probado con ir más... quizá ahí está mi error. Desconozco si con -O3 o -O4 vea algunos cambios, pero hay que usar con cuidado estos dos últimos niveles. El propio form de configuración tiene un label que dice que la compilación es más lenta... y que el nivel 4 hay que usar con cuidado.

 

Saludos,