delphi - vectorial - rotación de mapas de bits. En codigo

mapa de bits ventajas y desventajas

Question

¿Hay una forma más rápida de rotar un mapa de bits grande en 90 o 270 grados que simplemente hacer un ciclo anidado con coordenadas invertidas?

Los mapas de bits son 8bpp y típicamente 2048 * 2400 * 8bpp

Actualmente hago esto simplemente copiando con argumento de inversión, más o menos (pseudo código:

for x = 0 to 2048-1
for y = 0 to 2048-1
dest[x][y]=src[y][x];

(En realidad lo hago con punteros, para un poco más de velocidad, pero eso es más o menos la misma magnitud)

GDI es bastante lento con imágenes grandes, y los tiempos de carga / almacenamiento de GPU para texturas (tarjetas GF7) son de la misma magnitud que el tiempo de CPU actual.

¿Alguna sugerencia, punteros? Un algoritmo en el lugar sería incluso mejor, pero la velocidad es más importante que estar en el lugar.

Target es Delphi, pero es más una pregunta algorítmica. La vectorización de SSE (2) no es un problema, es un problema lo suficientemente grande como para codificarlo en ensamblador

Seguimiento a la respuesta de Nils

• Imagen 2048x2700 -> 2700x2048
• Compiler Turbo Explorer 2006 con optimización en.
• Windows: esquema de energía establecido en "Siempre encendido". ( importante !!!! )
• Máquina: Core2 6600 (2.4 GHz)

tiempo con la rutina anterior: 32 ms (paso 1)

tiempo con pasos 8: 12ms

tiempo con pasos de 16: 10ms

tiempo con pasos de 32+: 9ms

Mientras tanto, también probé en un Athlon 64 X2 (5200+ iirc), y la velocidad fue un poco más que un factor cuatro (80 a 19 ms).

La velocidad vale la pena, gracias. Tal vez durante los meses de verano me torture con una versión SSE (2). Sin embargo, ya pensé en cómo abordar eso, y creo que me quedaré sin registros SSE2 para una implementación directa:

for n:=0 to 7 do
begin
load r0, <source+n*rowsize>
shift byte from r0 into r1
shift byte from r0 into r2
..
shift byte from r0 into r8
end;
store r1, <target>
store r2, <target+1*<rowsize>
..
store r8, <target+7*<rowsize> 

Entonces 8x8 necesita 9 registros, pero SSE de 32 bits solo tiene 8. De todos modos, eso es algo para los meses de verano :-)

Tenga en cuenta que lo del puntero es algo que hago por instinto, pero podría ser que en realidad tiene algo que ver, si sus dimensiones no están codificadas, el compilador no puede convertir el mul en un cambio. Mientras que los muls an sich son baratos hoy en día, también generan más presión de registro afaik.

El código (validado al restar el resultado de la implementación "naieve" rotate1):

const stepsize = 32;
procedure rotatealign(Source: tbw8image; Target:tbw8image);
var stepsx,stepsy,restx,resty : Integer;
RowPitchSource, RowPitchTarget : Integer;
pSource, pTarget,ps1,ps2 : pchar;
x,y,i,j: integer;
rpstep : integer;
begin
RowPitchSource := source.RowPitch; // bytes to jump to next line. Can be negative (includes alignment)
RowPitchTarget := target.RowPitch; rpstep:=RowPitchTarget*stepsize;
stepsx:=source.ImageWidth div stepsize;
stepsy:=source.ImageHeight div stepsize;
// check if mod 16=0 here for both dimensions, if so -> SSE2.
for y := 0 to stepsy - 1 do
begin
psource:=source.GetImagePointer(0,y*stepsize); // gets pointer to pixel x,y
ptarget:=Target.GetImagePointer(target.imagewidth-(y+1)*stepsize,0);
for x := 0 to stepsx - 1 do
begin
for i := 0 to stepsize - 1 do
begin
ps1:=@psource[rowpitchsource*i]; // ( 0,i)
ps2:=@ptarget[stepsize-1-i]; // (maxx-i,0);
for j := 0 to stepsize - 1 do
begin
ps2[0]:=ps1[j];
inc(ps2,RowPitchTarget);
end;
end;
inc(psource,stepsize);
inc(ptarget,rpstep);
end;
end;
// 3 more areas to do, with dimensions
// - stepsy*stepsize * restx // right most column of restx width
// - stepsx*stepsize * resty // bottom row with resty height
// - restx*resty // bottom-right rectangle.
restx:=source.ImageWidth mod stepsize; // typically zero because width is
// typically 1024 or 2048
resty:=source.Imageheight mod stepsize;
if restx>0 then
begin
// one loop less, since we know this fits in one line of "blocks"
psource:=source.GetImagePointer(source.ImageWidth-restx,0); // gets pointer to pixel x,y
ptarget:=Target.GetImagePointer(Target.imagewidth-stepsize,Target.imageheight-restx);
for y := 0 to stepsy - 1 do
begin
for i := 0 to stepsize - 1 do
begin
ps1:=@psource[rowpitchsource*i]; // ( 0,i)
ps2:=@ptarget[stepsize-1-i]; // (maxx-i,0);
for j := 0 to restx - 1 do
begin
ps2[0]:=ps1[j];
inc(ps2,RowPitchTarget);
end;
end;
inc(psource,stepsize*RowPitchSource);
dec(ptarget,stepsize);
end;
end;
if resty>0 then
begin
// one loop less, since we know this fits in one line of "blocks"
psource:=source.GetImagePointer(0,source.ImageHeight-resty); // gets pointer to pixel x,y
ptarget:=Target.GetImagePointer(0,0);
for x := 0 to stepsx - 1 do
begin
for i := 0 to resty- 1 do
begin
ps1:=@psource[rowpitchsource*i]; // ( 0,i)
ps2:=@ptarget[resty-1-i]; // (maxx-i,0);
for j := 0 to stepsize - 1 do
begin
ps2[0]:=ps1[j];
inc(ps2,RowPitchTarget);
end;
end;
inc(psource,stepsize);
inc(ptarget,rpstep);
end;
end;
if (resty>0) and (restx>0) then
begin
// another loop less, since only one block
psource:=source.GetImagePointer(source.ImageWidth-restx,source.ImageHeight-resty); // gets pointer to pixel x,y
ptarget:=Target.GetImagePointer(0,target.ImageHeight-restx);
for i := 0 to resty- 1 do
begin
ps1:=@psource[rowpitchsource*i]; // ( 0,i)
ps2:=@ptarget[resty-1-i]; // (maxx-i,0);
for j := 0 to restx - 1 do
begin
ps2[0]:=ps1[j];
inc(ps2,RowPitchTarget);
end;
end;
end;
end;

Actualización 2 genéricos

Traté de actualizar este código a una versión genérica en Delphi XE. Fallé debido al QC 99703, y la gente del foro ya ha confirmado que también existe en XE2. Por favor vota por ello :-)

Actualizar 3 genéricos funciona ahora en XE10

Answer 1

Es posible que pueda mejorarlo copiando en bloques alineados en caché en lugar de filas, ya que en el momento en que el paso de cualquiera de los dos discos fallará (dependiendo de si delphi es fila mayor o columna mayor).

Answer 2

Si la imagen no es cuadrada, no puedes hacerla en el lugar. Incluso si trabaja en imágenes cuadradas, la transformación no es propicia para el trabajo en el lugar.

Si quieres intentar hacer las cosas un poco más rápido, puedes intentar aprovechar las ventajas de la fila para que funcione, pero creo que lo mejor que puedes hacer es leer 4 bytes a la vez en un largo desde la fuente y luego, escríbelo en cuatro filas consecutivas en el dest. Eso debería reducir algunos de sus gastos generales, pero no esperaría más que una mejora del 5%.

Answer 3

Si puede usar C ++, es posible que desee ver Eigen .

Es una biblioteca de plantillas de C ++ que usa SSE (2 y posteriores) y conjuntos de instrucciones de AltiVec con elegante repliegue de código no vectorizado .

Rápido. (Ver punto de referencia).
Las plantillas de expresión permiten eliminar temporalmente los temporales y habilitar la evaluación diferida, cuando sea apropiado: Eigen se encarga de esto automáticamente y maneja el alias también en la mayoría de los casos.
La vectorización explícita se realiza para los conjuntos de instrucciones SSE (2 y posteriores) y AltiVec, con elegante repliegue a código no vectorizado. Las plantillas de expresión permiten realizar estas optimizaciones globalmente para expresiones completas.
Con los objetos de tamaño fijo, se evita la asignación dinámica de memoria y los bucles se desenrollan cuando tiene sentido.
Para matrices grandes, se presta especial atención a la conservación de la memoria caché.

Answer 4

Sí, hay formas más rápidas de hacer esto.

Su bucle simple pasa la mayor parte del tiempo en fallas de caché. Esto sucede porque tocas muchos datos en lugares muy diferentes en un círculo cerrado. Peor aún: sus ubicaciones de memoria son exactamente una potencia de dos aparte. Ese es un tamaño donde la memoria caché funciona peor.

Puede mejorar este algoritmo de rotación si mejora la localidad de sus accesos de memoria.

Una forma sencilla de hacer esto sería rotar cada bloque de 8x8 píxeles por sí mismo utilizando el mismo código que ha utilizado para todo su mapa de bits, y ajustar otro ciclo que divide la rotación de la imagen en fragmentos de 8x8 píxeles cada uno.

Por ejemplo, algo como esto (no verificado, y lo siento por el código C. Mis habilidades Delphi no están actualizadas):

 // this is the outer-loop that breaks your image rotation
// into chunks of 8x8 pixels each:
for (int block_x = 0; block_x < 2048; block_x+=8)
{
for (int block_y = 0; blocky_y < 2048; block_y+=8)
{
// this is the inner-loop that processes a block
// of 8x8 pixels.
for (int x= 0; x<8; x++)
for (int y=0; y<8; y++)
dest[x+block_x][y+block_y] = src[y+block_y][x+block_x]
}
} 

También hay otras formas. Puede procesar los datos en Hilbert-Order o Morton-Order. Eso sería en teoría incluso un poco más rápido, pero el código será mucho más complejo.

Por cierto, ya que has mencionado que SSE es una opción para ti. Tenga en cuenta que puede rotar un bloque de 8x8 bytes dentro de los registros SSE. Es un poco complicado hacerlo funcionar, pero al mirar el código de transposición de matriz SSE debería comenzar porque es lo mismo.

EDITAR:

Acabo de revisarlo:

Con un tamaño de bloque de 8x8 píxeles, el código se ejecuta ca. 5 veces más rápido en mi máquina. Con un tamaño de bloque de 16x16, corre 10 veces más rápido.

Parece que es una buena idea experimentar con diferentes tamaños de bloques.

Aquí está el (muy simple) programa de prueba que he usado:

#include <stdio.h>
#include <windows.h>
char temp1[2048*2048];
char temp2[2048*2048];
void rotate1 (void)
{
int x,y;
for (y=0; y<2048; y++)
for (x=0; x<2048; x++)
temp2[2048*y+x] = temp1[2048*x+y];
}
void rotate2 (void)
{
int x,y;
int bx, by;
for (by=0; by<2048; by+=8)
for (bx=0; bx<2048; bx+=8)
for (y=0; y<8; y++)
for (x=0; x<8; x++)
temp2[2048*(y+by)+x+bx] = temp1[2048*(x+bx)+y+by];
}
void rotate3 (void)
{
int x,y;
int bx, by;
for (by=0; by<2048; by+=16)
for (bx=0; bx<2048; bx+=16)
for (y=0; y<16; y++)
for (x=0; x<16; x++)
temp2[2048*(y+by)+x+bx] = temp1[2048*(x+bx)+y+by];
}
int main (int argc, char **args)
{
int i, t1;
t1 = GetTickCount();
for (i=0; i<20; i++) rotate1();
printf ("%d/n", GetTickCount()-t1);
t1 = GetTickCount();
for (i=0; i<20; i++) rotate2();
printf ("%d/n", GetTickCount()-t1);
t1 = GetTickCount();
for (i=0; i<20; i++) rotate3();
printf ("%d/n", GetTickCount()-t1);
}