旋转位图。 在代码中
有一个更快的方法来旋转一个大的位图90或270度，而不是简单地做一个嵌套循环与坐标倒置？
位图是8bpp，通常是2048 * 2400 * 8bpp
目前我通过简单地使用参数反转进行复制，粗略地（伪代码：
for x = 0 to 2048-1 for y = 0 to 2048-1 dest[x][y]=src[y][x]; （实际上我是用指针来做的，速度更快一些，但大致相同）
GDI对于大图像来说相当慢，并且纹理（GF7卡）的GPU加载/存储时间与当前CPU时间相同。
任何提示，指针？ 一个就地algorithm甚至会更好，但速度比就地更重要。
目标是delphi，但它更是一个algorithm问题。 上证所（2）vector化没有问题，这是一个足够大的问题，我编码在汇编
跟随Nils的答案
- 图片2048×2700 – > 2700×2048
- 编译Turbo Explorer 2006，并进行优化。
- Windows：电源scheme设置为“始终打开”。 （ 重要!!!! ）
- 机器：Core2 6600（2.4 GHz）
时间与旧例程：32毫秒（第1步）
时间步长8：12ms
时间步长16：10ms
时间步长32+：9ms
同时我也testing了Athlon 64 X2（5200 + iirc），而且速度稍微超过了四倍（80到19毫秒）。
加快是非常值得的，谢谢。 也许在夏天的几个月里，我会用SSE（2）版本来折磨自己。 但是我已经想过如何解决这个问题了，我想我会用完SSE2寄存器来实现一个直接的实现：
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>
所以8×8需要9个寄存器，但是32位SSE只有8个。反正那是夏天的一些事情:-)
请注意，指针是我本能的东西，但它可能是其中的一些东西，如果你的维度没有被硬编码，编译器就不能把mul变成一个转换。 而现在这个价格便宜，他们也产生了更多的注册压力afaik。
代码（通过从“naieve”rotate1实现中减去结果来validation）：
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;
更新2generics
我试图将这个代码更新到Delphi XE的generics版本。 我因为QC 99703而失败了，论坛的人已经证实它也存在于XE2中。 请投票支持:-)
更新3generics现在在XE10中工作
是的，有更快的方法来做到这一点。
你的简单循环花费大部分时间在caching未命中。 发生这种情况是因为您在紧密的环路中在非常不同的地方触摸了大量数据。 更糟的是：你的记忆位置恰恰是两个分开的力量。 这是caching执行最差的大小。
如果改善内存访问的局部性，则可以改进此旋转algorithm。
一个简单的方法是使用与整个位图相同的代码自行旋转每个8×8像素块，然后包装另一个循环，将图像旋转分割为8×8像素的块。
例如像这样（没有检查，并抱歉的C代码，我的Delphi技能不是最新的）：
// 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] } }
还有其他的方法。 你可以用Hilbert-Order或Morton-Order来处理数据。 这在理论上会更快一些，但代码会更复杂。
顺便说一句 – 既然你提到SSE是你的select。 请注意，您可以旋转SSE寄存器内的8×8字节块。 让它工作有点棘手，但看看SSEmatrix转置代码应该让你开始，因为它是同样的事情。
编辑：
刚刚检查：
对于8×8像素的块大小的代码运行约。 在我的机器上快了5倍。 以16×16的块大小运行速度快10倍。
似乎尝试不同的块大小是个好主意。
这是我用过的（非常简单的）testing程序：
#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); }
如果你可以使用C ++，那么你可能想看看Eigen 。
它是一个C ++模板库，使用SSE（2及更高版本）和AltiVec指令集，优雅地回退到非vector化代码 。
快速。 （见基准）。
expression式模板允许智能地删除临时对象，并启用惰性评估（如果适当的话） – Eigen会自动处理这种情况，并且在大多数情况下也会处理别名。
针对SSE（2和更高版本）和AltiVec指令集执行显式vector化，并优雅地回退到非vector化代码。 expression式模板允许在整个expression式中全局执行这些优化。
对于固定大小的对象，可以避免dynamic内存分配，并且在有意义时展开循环。
对于大型matrix，特别注意caching友好性。
您可以通过复制cachingalignment的块而不是行来改进它，因为此时src dest的步幅将会是未命中的（取决于delphi是行主还是列主）。
如果图像不是方形的，则不能在原地进行。 即使你用方形图像工作，这种转换也不利于就地工作。
如果你想尽量做更快的事情，你可以尝试利用行方式来使它工作，但我认为你所要做的最好的做法是一次从源头读取4个字节，然后将其写入dest中的四个连续行。 这应该减less一些你的开销，但我不希望有超过5％的改善。
