delphi - mexico - Problema de velocidad del generador de chatarra

delphi technologies

Question

Estoy buscando en la generación de un archivo (750 MB) lleno de bytes aleatorios. El código que estoy usando en un hilo separado se ve así:

Asigné un búfer de ese tamaño ya que escribir en el disco consume más tiempo:

function Generate(buf:Pointer):DWORD;stdcall;
var
i:DWORD;
begin
      for i := 0 to keysize -1 do
            PByte(DWORD(buf) + i)^ := Random(256);
      Result:=0;
end;

El problema es que lleva años hasta que el proceso se completa. ¿Alguna idea para un método más rápido? Intentaré implementarlo en ensamblaje si no hay otra alternativa.

Answer 1

Además de hacer su propia función aleatoria () y / o utilizar CPU adicionales, para un bucle, un enfoque rápido es:

procedure Generate(p: pointer; size: integer);
type
  TCardinalArray = array[0..0] of cardinal;
  PCardinalArray = ^TCardinalArray;

var
  i: integer;

begin
  i := (size div 4) - 1;
  while i >= 0 do
  begin
    PCardinalArray(p)[i] := Random(MaxInt) * 2;
    Dec(i);
  end;
end;

Dado que no hay necesidad de incrementar el puntero y el índice de bucle se compara con una operación TEST.

Unit6.pas.46: i := (size div 4) - 1;
0045209C 8BD9             mov ebx,ecx
0045209E 85DB             test ebx,ebx
004520A0 7903             jns $004520a5
004520A2 83C303           add ebx,$03
004520A5 C1FB02           sar ebx,$02
004520A8 4B               dec ebx
Unit6.pas.47: while i >= 0 do
004520A9 85DB             test ebx,ebx
004520AB 7C14             jl $004520c1
Unit6.pas.49: PCardinalArray(p)[i] := Random(MaxInt) * 2;
004520AD B8FFFFFF7F       mov eax,$7fffffff
004520B2 E8C50EFBFF       call Random
004520B7 03C0             add eax,eax
004520B9 89049E           mov [esi+ebx*4],eax
Unit6.pas.50: Dec(i);
004520BC 4B               dec ebx
Unit6.pas.47: while i >= 0 do
004520BD 85DB             test ebx,ebx
004520BF 7DEC             jnl $004520ad

Por supuesto que no hay gran diferencia, pero es algo ...

Answer 2

Como la función Random no tiene una buena distribución, puedes reducir tu código en casi un factor de cuatro con lo siguiente:

function Generate(buf: Pointer): DWORD; stdcall;
var
  i: DWORD;
  p: PInteger;
begin
  p := buf;
  for i := 0 to (keysize div 4) - 1 do begin
    p^ := Random(MaxInt);
    Inc(p);
  end;
  Result := 0;
end;

Actualización: el código anterior necesita aproximadamente 650 ms en mi sistema, mientras que el código original necesita aproximadamente 3 segundos.

Answer 3

El problema es que Random() tiene una entropía limitada. Y si genera 750MiB de datos, obtendrá solo una de las 2^31 cadenas diferentes posibles (ya que ese es el período del RNG), no 2^(750*1024*1024*8) , como sería el caso Si el generador fuera perfecto. Esta es una gran disparidad.

En resumen, si usa Random (), sus datos no son aleatorios en absoluto. Cualquiera podría adivinar los 750MiB de datos de una muestra / pieza del archivo de 4MB.

Tienes que hacerlo de otra manera. Si tiene una máquina linux, ejecute este comando desde su programa:

dd if=/dev/urandom of=file.img bs=1M count=750

Termina en menos de medio minuto en mi vieja laptop.

Answer 4

Esto sonó como un buen problema de práctica, así que seguí adelante e implementé una solución paralela. Utiliza un poco más de 3 segundos para generar un archivo de 750 MB y utiliza más del 90% de CPU durante su trabajo. (El disco SSD también ayuda. Se necesitaron 3,5 segundos para generar el archivo en un par de discos RAID0 y 4 segundos para generar un archivo en un disco más lento de 512 GB).

Todo el código reutilizado está disponible con la licencia de OpenBSD (que es casi "use como desee"): DSiWin32 , GpStuff , GpRandomGen , Otl * .

uses
  DSiWin32,
  GpStuff,
  GpRandomGen,
  OtlCommon,
  OtlCollections,
  OtlParallel;

{$R *.dfm}

procedure FillBuffer(buf: pointer; bufSize: integer; randomGen: TGpRandom);
var
  buf64: PInt64;
  buf8 : PByte;
  i    : integer;
  rnd  : int64;
begin
  buf64 := buf;
  for i := 1 to bufSize div SizeOf(int64) do begin
    buf64^ := randomGen.Rnd64;
    Inc(buf64);
  end;
  rnd := randomGen.Rnd64;
  buf8 := PByte(buf64);
  for i := 1 to bufSize mod SizeOf(int64) do begin
    buf8^ := rnd AND $FF;
    rnd := rnd SHR 8;
    Inc(buf8);
  end;
end; { FillBuffer }

procedure CreateRandomFile(fileSize: integer; output: TStream);
const
  CBlockSize = 1 * 1024 * 1024 {1 MB};
var
  buffer        : TOmniValue;
  lastBufferSize: integer;
  memStr        : TMemoryStream;
  numBuffers    : integer;
  outQueue      : IOmniBlockingCollection;
begin
  outQueue := TOmniBlockingCollection.Create;
  numBuffers := (fileSize - 1) div CBlockSize + 1;
  lastBufferSize := (fileSize - 1) mod CBlockSize + 1;
  Parallel.ForEach(1, numBuffers).NoWait
    .NumTasks(Environment.Process.Affinity.Count)
    .OnStop(
      procedure
      begin
        outQueue.CompleteAdding;
      end)
    .Initialize(
      procedure(var taskState: TOmniValue)
      begin
        taskState := TGpRandom.Create;
      end)
    .Finalize(
      procedure(const taskState: TOmniValue)
      begin
        taskState.AsObject.Free;
      end)
    .Execute(
      procedure(const value: integer; var taskState: TOmniValue)
      var
        buffer      : TMemoryStream;
        bytesToWrite: integer;
      begin
        if value = numBuffers then
          bytesToWrite := lastBufferSize
        else
          bytesToWrite := CBlockSize;
        buffer := TMemoryStream.Create;
        buffer.Size := bytesToWrite;
        FillBuffer(buffer.Memory, bytesToWrite, taskState.AsObject as TGpRandom);
        outQueue.Add(buffer);
      end);
  for buffer in outQueue do begin
    memStr := buffer.AsObject as TMemoryStream;
    output.CopyFrom(memStr, 0);
    FreeAndNil(memStr);
  end;
end;

procedure TForm43.btnRandomClick(Sender: TObject);
var
  fileStr: TFileStream;
  time   : int64;
begin
  time := DSiTimeGetTime64;
  try
    fileStr := TFileStream.Create(''e:/0/random.dat'', fmCreate);
    try
      CreateRandomFile(750*1024*1024, fileStr);
    finally FreeAndNil(fileStr); end;
  finally Caption := Format(''Completed in %d ms'', [DSiElapsedTime64(time)]); end;
end;

EDITAR: El uso de ForEach en este caso no fue una solución realmente elegante, por lo que mejoré OmniThreadLibrary con Parallel.ParallelTask ​​y con un mejor IOmniCounter. Usando la versión 993 (o más reciente) de la SVN , puede resolver este problema de múltiples productores y consumidores únicos de la siguiente manera.

procedure CreateRandomFile(fileSize: integer; output: TStream);
const
  CBlockSize = 1 * 1024 * 1024 {1 MB};
var
  buffer   : TOmniValue;
  memStr   : TMemoryStream;
  outQueue : IOmniBlockingCollection;
  unwritten: IOmniCounter;
begin
  outQueue := TOmniBlockingCollection.Create;
  unwritten := CreateCounter(fileSize);
  Parallel.ParallelTask.NoWait
    .NumTasks(Environment.Process.Affinity.Count)
    .OnStop(Parallel.CompleteQueue(outQueue))
    .Execute(
      procedure
      var
        buffer      : TMemoryStream;
        bytesToWrite: integer;
        randomGen   : TGpRandom;
      begin
        randomGen := TGpRandom.Create;
        try
          while unwritten.Take(CBlockSize, bytesToWrite) do begin
            buffer := TMemoryStream.Create;
            buffer.Size := bytesToWrite;
            FillBuffer(buffer.Memory, bytesToWrite, randomGen);
            outQueue.Add(buffer);
          end;
        finally FreeAndNil(randomGen); end;
      end
    );
  for buffer in outQueue do begin
    memStr := buffer.AsObject as TMemoryStream;
    output.CopyFrom(memStr, 0);
    FreeAndNil(memStr);
  end;
end;

EDIT2: Una publicación de blog más larga sobre este problema: La vida después de 2.1: Producción de datos en paralelo (Introducción a la Tarea Paralela)

Answer 5

Excepto otros factores, los principales problemas de velocidad que veo con el código en la publicación original son:

1) Ejecución aleatoria para cada byte. Esta función cuenta para la mayoría del procesamiento. El procesamiento de cada cuatro bytes será ventajoso. 2) Minimizar los cálculos dentro del bucle. Establecería los límites del puntero y luego ejecutaría un bucle while (inc o dec por 4) hasta que la diferencia entre el límite superior y el límite inferior sea menor que 4, luego inc o dec por 1 el resto del camino. Probablemente no consideraría un bucle for en ningún momento de esto. 3) No correría esto contra una gran cantidad de datos: no haría 750 MB de una vez porque la degradación de la velocidad para manejar esa cantidad de datos tiende a superar cualquier mejora de rendimiento a través del código.

Muy poco probado, y probablemente mucho para mejorar, pero la idea básica que tuve aquí es:

function Generate(buf: Pointer): DWord; stdcall;
  var
    inbuf, uplimit: Cardinal;
  begin
    inbuf := Cardinal(buf);
    uplimit := inbuf + keysize - 1;
    while (uplimit - inbuf) >= 4 do
      begin
        PDWord(inbuf)^ := Random(MAXINT);
        inc(inbuf, 4);
      end;
    while inbuf <= uplimit do
      begin
        PByte(inbuf)^ := Random(256);
        inc(inbuf, 1);
      end;
    Result := 0;
  end;

Answer 6

No sé sobre Delphi, pero podría estar perdiendo el tiempo en la llamada Random(256) . ¿Por qué no codificas a mano algo pseudoaleatorio al efecto de

n = (n * 1103515245 + 12345) & 0xff;

Deje que n comience en alguna parte y use la recursión, como esta, para generar la siguiente n . No es realmente tan aleatorio, pero debería hacerlo para crear archivos aleatorios.

EDITAR algo de alimento para el pensamiento. Si está creando este archivo con la esperanza de que no sea fácilmente compresible, entonces el método descrito anteriormente no es tan bueno, debido a la parte & 0xff . Es mejor que hacer

n = (n * 1103515245 + 12345) & 0x7fffffff;

como 0x7fffffff = 2147483647 es un número primo. Y almacene el valor exacto mayor de n , y haga un n % 256 en la asignación. He tenido algunas buenas ejecuciones con esta elección de constantes, y la prefiero como fuente de entropía a la alternativa .NET incorporada, ya que es muchas veces más rápida y, de todos modos, rara vez se necesitan números pseudoaleatorios realmente aleatorios o mejores.

Answer 7

Puedes probar RandomRange(Low(Integer), High(Integer)) y ver si funciona. Esto generará 4 bytes de datos aleatorios a la vez (tenga en cuenta que está firmado y que supongo que el entero es de 4 bytes, pero The Integer type is an Integer whose size is not guaranteed (http: //www.delphibasics .co.uk / RTL.asp? Name = Integer).

Answer 8

    var
  F: TFileStream;
  I: Cardinal;
  index: integer;

  a: array[1..10240] of Cardinal;
  IndexA: integer;

  T1: TDateTime;
begin
  T1 := Now;

  F := TFileStream.Create( ''D:/filler.fil'', fmCreate);
  try
    for index := 1 to (650 * MByte) div (sizeof( A)) do begin

      for indexA := 1 to 10240 do begin
        a[ IndexA] := Random( 4294967295    );
      end;
      F.WriteBuffer( A, SizeOf( A));
    end;
  finally
    F.Free;
  end;

  ShowMessage( SecondsBetween( T1, Now));
end;

Funciona en 3 ~ 4 segundos en una unidad SSD. Mucho más fácil.