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.