我意识到这是一个愚蠢的问题,因为缺乏一个更好的术语。我只是在寻找任何有关提高此代码效率的外部想法,因为它会严重阻碍系统(它必须执行此功能)并且我的想法很少。
它正在做什么加载两个图像容器(imgRGB用于全彩色img和imgBW用于b&w图像)逐个像素的图像存储在“unsigned char * pImage”中。
imgRGB和imgBW都是用于根据需要访问各个像素的容器。
// input is in the form of an unsigned char
// unsigned char *pImage
for (int y=0; y < 640; y++) {
for (int x=0; x < 480; x++) {
imgRGB[y][x].blue = *pImage;
pImage++;
imgRGB[y][x].green = *pImage;
imgBW[y][x] = *pImage;
pImage++;
imgRGB[y][x].red = *pImage;
pImage++;
}
}
就像我说的那样,我只是在寻找有关更好的内存管理和/或复制的新输入和想法。有时候我会看到自己的代码,以至于我得到隧道视觉......有点心理障碍。如果有人想要/需要更多信息,请务必告诉我。
我认为数组访问(他们是真正的数组访问还是operator []?)会杀了你。每一个代表一个乘法。
基本上,你想要这样的东西:
for (int y=0; y < height; y++) {
unsigned char *destBgr = imgRgb.GetScanline(y); // inline methods are better
unsigned char *destBW = imgBW.GetScanline(y);
for (int x=0; x < width; x++) {
*destBgr++ = *pImage++;
*destBW++ = *destBgr++ = *pImage++; // do this in one shot - don't double deref
*destBgr++ = *pImage++;
}
}
这将在每条扫描线上进行两次乘法运算。您的代码每个PIXEL执行4次乘法。
如果可能的话,将其修复到更高的水平,然后进行钻头或指令!
imgBW
课程。imgRGB
中存储数据,您可以从输入数据中一次复制三元组。更好的是,您可以复制整个内容,甚至只是存储引用(这也使之前的建议变得容易)。如果你不控制这里所有的实现,你可能会被卡住,然后:
您似乎将每个像素定义为某种结构或对象。使用基本类型(比方说,int)可能会更快。正如其他人所提到的,编译器很可能使用指针增量来优化数组访问。如果编译不能为您执行此操作,则可以在使用array [] []时自行执行此操作以避免乘法运算。
由于每个像素只需要3个字节,因此可以将一个像素打包成一个int。通过这样做,您可以一次复制3个字节而不是逐个字节。唯一棘手的事情是当你想要读取像素的各个颜色分量时,你需要一些掩码和移位。这可能会比使用int节省的开销更多。
或者,您可以分别为3个颜色组件使用3个int数组。但是,您需要更多存储空间。
这是一个非常小的,非常简单的优化:
你反复提到imageRGB [y] [x],并且可能需要在每一步重新计算。
相反,计算一次,看看是否有所改善:
Pixel* apixel;
for (int y=0; y < 640; y++) {
for (int x=0; x < 480; x++) {
apixel = &imgRGB[y][x];
apixel->blue = *pImage;
pImage++;
apixel->green = *pImage;
imgBW[y][x] = *pImage;
pImage++;
apixel->red = *pImage;
pImage++;
}
}
如果pImage已完全在内存中,为什么需要按摩数据呢?我的意思是如果它已经是伪RGB格式,为什么你不能只编写一些内联例程/宏可以按需吐出值而不是复制它?
如果重新排列像素数据对于以后的操作很重要,请考虑块操作和/或缓存线优化。
显而易见的问题是,您是否需要首先复制数据?你不能只定义访问器函数来从原始输入数组中提取任何给定像素的R,G和B值吗?
如果图像数据是瞬态的,那么您必须保留它的副本,您可以在不重新格式化的情况下制作它的原始副本,并再次定义访问器以索引到其上的每个像素/通道。
假设您提供的副本是必要的,将循环展开几次可能会有所帮助。
我认为最好的方法是将循环展开足够多次以确保每次迭代处理一个可被4字节整除的数据块(因此在每次迭代中,循环可以简单地读取少量的整数,而不是大量的chars)当然这要求你在写入时屏蔽这些int的位,但这是一个快速操作,最重要的是,它是在寄存器中完成的,而不会增加内存子系统或CPU缓存的负担:
// First, we need to treat the input image as an array of ints. This is a bit nasty and technically unportable, but you get the idea)
unsigned int* img = reinterpret_cast<unsigned int*>(pImage);
for (int y = 0; y < 640; ++y)
{
for (int x = 0; x < 480; x += 4)
{
// At the start of each iteration, read 3 ints. That's 12 bytes, enough to write exactly 4 pixels.
unsigned int i0 = *img;
unsigned int i1 = *(img+1);
unsigned int i2 = *(img+2);
img += 3;
// This probably won't make a difference, but keeping a reference to the found pixel saves some typing, and it may assist the compiler in avoiding aliasing.
ImgRGB& pix0 = imgRGB[y][x];
pix0.blue = i0 & 0xff;
pix0.green = (i0 >> 8) & 0xff;
pix0.red = (i0 >> 16) & 0xff;
imgBW[y][x] = (i0 >> 8) & 0xff;
ImgRGB& pix1 = imgRGB[y][x+1];
pix1.blue = (i0 >> 24) & 0xff;
pix1.green = i1 & 0xff;
pix1.red = (i0 >> 8) & 0xff;
imgBW[y][x+1] = i1 & 0xff;
ImgRGB& pix2 = imgRGB[y][x+2];
pix2.blue = (i1 >> 16) & 0xff;
pix2.green = (i1 >> 24) & 0xff;
pix2.red = i2 & 0xff;
imgBW[y][x+2] = (i1 >> 24) & 0xff;
ImgRGB& pix3 = imgRGB[y][x+3];
pix3.blue = (i2 >> 8) & 0xff;
pix3.green = (i2 >> 16) & 0xff;
pix3.red = (i2 >> 24) & 0xff;
imgBW[y][x+3] = (i2 >> 16) & 0xff;
}
}
你最好还是填写一个临时的ImgRGB值,然后立刻将整个结构写入内存,这意味着第一个块看起来就像这样:(当然下面的块类似)
ImgRGB& pix0 = imgRGB[y][x];
ImgRGB tmpPix0;
tmpPix0.blue = i0 & 0xff;
tmpPix0.green = (i0 >> 8) & 0xff;
tmpPix0.red = (i0 >> 16) & 0xff;
imgBW[y][x] = (i0 >> 8) & 0xff;
pix0 = tmpPix0;
根据编译器的聪明程度,这可能会大大减少所需的读取次数。假设原始代码是天真编译的(这可能不太可能,但将作为一个例子),这将使您从每个像素3次读取和4次写入(读取RGB通道,并写入RGB + BW)到每次3/4读取像素和2写。 (一个写入RGB结构,一个写入BW值)
您还可以在单个int中累积4个写入BW图像的写入,然后一次性写入,如下所示:
bw |= (i0 >> 8) & 0xff;
bw |= (i1 & 0xff) << 8;
bw |= ((i1 >> 24) & 0xff) << 16;
bw |= ((i2 >> 16) & 0xff) << 24;
*(imgBW + y*480+x/4) = bw; // Assuming you can treat imgBW as an array of integers
这将减少每像素1.25的写入次数(每个RGB结构1个,每4个BW值1个)
同样,好处可能会小得多(甚至不存在),但它可能值得一试。
更进一步,使用SSE指令可以毫不费力地完成同样的操作,允许您每次迭代处理4倍的值。 (假设你在x86上运行)
当然,这里一个重要的免责声明是上述不可移植。 reinterpret_cast可能是一个学术点(它很可能无论如何都有效,特别是如果你能确保原始数组在32位边界上对齐,这通常适用于所有平台上的大量分配)更大的问题是,苦涩取决于CPU的字节顺序。
但实际上,这应该适用于x86。并且只需稍加改动,它也适用于大端机器。 (当然,我的代码中的任何错误都是模数。我没有测试过,甚至没有编译过任何错误;))
但无论你如何解决它,你都会看到最大限度地提高速度,最大限度地减少读写次数,并尽量在CPU的寄存器中累积尽可能多的数据。尽可能读取大块中的所有内容,例如整数,在寄存器中重新排序(将其累积为多个整数,或将其写入RGB结构的临时实例),然后将这些组合值写入内存。
根据您对低级优化的了解程度,您可能会感到惊讶,但临时变量很好,而直接内存到内存访问可能很慢(例如,您的指针解除引用直接分配到数组中)。这样做的问题是你可能获得了比必要更多的内存访问,并且编译器更难以保证不会出现别名,因此它可能无法重新排序或组合内存访问。你通常最好尽可能早地编写(循环的顶部),尽可能多地在临时文件中执行(因为编译器可以将所有内容保存在寄存器中),然后在最后编写所有内容。这也为编译器提供了尽可能多的余地来等待最初的慢速读取。
最后,将第四个虚拟值添加到RGB结构(因此它的总大小为32位)很可能也会有很大的帮助(因为编写这样的结构是一个32位写入,这比一个更简单,更有效。目前的24位)
在决定展开循环的程度时(每次迭代可以执行上述两次或更多次),请记住CPU有多少个寄存器。由于存在大量内存访问,因此扩散到缓存中可能会对您造成伤害,但另一方面,考虑到可用的寄存器数量,请尽可能多地展开(上面使用3个寄存器来保存输入数据,以及一个可以累积BW值。可能需要一两个来计算必要的地址,所以在x86上,上面加倍可能会推动它(总共有8个寄存器,其中一些具有特殊含义)。另一方面,现代CPU通过在幕后使用更多的寄存器来做很多事情以补偿寄存器压力,因此进一步展开可能仍然是总体性能获胜。
一如既往,衡量措施措施。在你测试它之前,不可能说出什么是快速的,什么是不可能的。
要记住的另一个一般要点是数据依赖性很差。只要您只处理整数值,这仍然不是什么大问题,但它仍然会禁止指令重新排序和超标量执行。在上面,我试图尽可能缩短依赖链。不是不断地递增相同的指针(这意味着每个增量依赖于前一个增量),向同一个基地址添加不同的偏移意味着每个地址都可以独立计算,再次为编译器提供更多的自由来重新排序和重新安排说明。
在这样的情况下我喜欢做的是进入调试器并逐步完成反汇编以查看它实际上在做什么(或让编译器生成汇编列表)。这可以为您提供很多关于效率低下的线索。他们往往不在你想的地方!
通过实施上述Assaf和David Lee建议的更改,您可以获得前后指令计数。这真的有助于我优化紧密的内环。
您可以使用下标运算符[] []优化掉一些指针算法,并使用迭代器(即推进指针)。
内存带宽是你的瓶颈。将所有数据传输到系统存储器和从系统存储器传输所需的理论最小时间。我写了一个小测试来比较OP的版本和一些简单的汇编程序,看看编译器有多好。我正在使用具有默认释放模式设置的VS2005。这是代码:
#include <windows.h>
#include <iostream>
using namespace std;
const int
c_width = 640,
c_height = 480;
typedef struct _RGBData
{
unsigned char
r,
g,
b;
// I'm assuming there's no padding byte here
} RGBData;
// similar to the code given
void SimpleTest
(
unsigned char *src,
RGBData *rgb,
unsigned char *bw
)
{
for (int y = 0 ; y < c_height ; ++y)
{
for (int x = 0 ; x < c_width ; ++x)
{
rgb [x + y * c_width].b = *src;
src++;
rgb [x + y * c_width].g = *src;
bw [x + y * c_width] = *src;
src++;
rgb [x + y * c_width].r = *src;
src++;
}
}
}
// the assembler version
void ASM
(
unsigned char *src,
RGBData *rgb,
unsigned char *bw
)
{
const int
count = 3 * c_width * c_height / 12;
_asm
{
push ebp
mov esi,src
mov edi,bw
mov ecx,count
mov ebp,rgb
l1:
mov eax,[esi]
mov ebx,[esi+4]
mov edx,[esi+8]
mov [ebp],eax
shl eax,16
mov [ebp+4],ebx
rol ebx,16
mov [ebp+8],edx
shr edx,24
and eax,0xff000000
and ebx,0x00ffff00
and edx,0x000000ff
or eax,ebx
or eax,edx
add esi,12
bswap eax
add ebp,12
stosd
loop l1
pop ebp
}
}
// timing framework
LONGLONG TimeFunction
(
void (*function) (unsigned char *src, RGBData *rgb, unsigned char *bw),
char *description,
unsigned char *src,
RGBData *rgb,
unsigned char *bw
)
{
LARGE_INTEGER
start,
end;
cout << "Testing '" << description << "'...";
memset (rgb, 0, sizeof *rgb * c_width * c_height);
memset (bw, 0, c_width * c_height);
QueryPerformanceCounter (&start);
function (src, rgb, bw);
QueryPerformanceCounter (&end);
bool
ok = true;
unsigned char
*bw_check = bw,
i = 0;
RGBData
*rgb_check = rgb;
for (int count = 0 ; count < c_width * c_height ; ++count)
{
if (bw_check [count] != i || rgb_check [count].r != i || rgb_check [count].g != i || rgb_check [count].b != i)
{
ok = false;
break;
}
++i;
}
cout << (end.QuadPart - start.QuadPart) << (ok ? " OK" : " Failed") << endl;
return end.QuadPart - start.QuadPart;
}
int main
(
int argc,
char *argv []
)
{
unsigned char
*source_data = new unsigned char [c_width * c_height * 3];
RGBData
*rgb = new RGBData [c_width * c_height];
unsigned char
*bw = new unsigned char [c_width * c_height];
int
v = 0;
for (unsigned char *dest = source_data ; dest < &source_data [c_width * c_height * 3] ; ++dest)
{
*dest = v++ / 3;
}
LONGLONG
totals [2] = {0, 0};
for (int i = 0 ; i < 10 ; ++i)
{
cout << "Iteration: " << i << endl;
totals [0] += TimeFunction (SimpleTest, "Initial Copy", source_data, rgb, bw);
totals [1] += TimeFunction ( ASM, " ASM Copy", source_data, rgb, bw);
}
LARGE_INTEGER
freq;
QueryPerformanceFrequency (&freq);
freq.QuadPart /= 100000;
cout << totals [0] / freq.QuadPart << "ns" << endl;
cout << totals [1] / freq.QuadPart << "ns" << endl;
delete [] bw;
delete [] rgb;
delete [] source_data;
return 0;
}
并且C和汇编程序I之间的比率约为2.5:1,即C是汇编程序版本的2.5倍。
我刚刚注意到原始数据是以BGR顺序排列的。如果副本交换了B和R组件,那么它确实使汇编代码更复杂一些。但它也会使C代码更复杂。
理想情况下,您需要确定理论上的最短时间,并将其与您实际获得的时间进行比较。要做到这一点,您需要知道内存频率和内存类型以及CPU MMU的工作方式。
您可以尝试使用简单的强制转换来获取RGB数据,然后重新计算灰度数据:
#pragma pack(1)
typedef unsigned char bw_t;
typedef struct {
unsigned char blue;
unsigned char green;
unsigned char red;
} rgb_t;
#pragma pack(pop)
rgb_t *imageRGB = (rgb_t*)pImage;
bw_t *imageBW = (bw_t*)calloc(640*480, sizeof(bw_t));
// RGB(X,Y) = imageRGB[Y*480 + X]
// BW(X,Y) = imageBW[Y*480 + X]
for (int y = 0; y < 640; ++y)
{
// try and pull some larger number of bytes from pImage (24 is arbitrary)
// 24 / sizeof(rgb_t) = 8
for (int x = 0; x < 480; x += 24)
{
imageBW[y*480 + x ] = GRAYSCALE(imageRGB[y*480 + x ]);
imageBW[y*480 + x + 1] = GRAYSCALE(imageRGB[y*480 + x + 1]);
imageBW[y*480 + x + 2] = GRAYSCALE(imageRGB[y*480 + x + 2]);
imageBW[y*480 + x + 3] = GRAYSCALE(imageRGB[y*480 + x + 3]);
imageBW[y*480 + x + 4] = GRAYSCALE(imageRGB[y*480 + x + 4]);
imageBW[y*480 + x + 5] = GRAYSCALE(imageRGB[y*480 + x + 5]);
imageBW[y*480 + x + 6] = GRAYSCALE(imageRGB[y*480 + x + 6]);
imageBW[y*480 + x + 7] = GRAYSCALE(imageRGB[y*480 + x + 7]);
}
}
您可以采取几个步骤。结果在这个答案结束时。
首先,使用指针。
const unsigned char *pImage;
RGB *rgbOut = imgRGB;
unsigned char *bwOut = imgBW;
for (int y=0; y < 640; ++y) {
for (int x=0; x < 480; ++x) {
rgbOut->blue = *pImage;
++pImage;
unsigned char tmp = *pImage; // Save to reduce amount of reads.
rgbOut->green = tmp;
*bwOut = tmp;
++pImage;
rgbOut->red = *pImage;
++pImage;
++rgbOut;
++bwOut;
}
}
如果imgRGB
和imgBW
被宣布为:
unsigned char imgBW[480][640];
RGB imgRGB[480][640];
您可以组合两个循环:
const unsigned char *pImage;
RGB *rgbOut = imgRGB;
unsigned char *bwOut = imgBW;
for (int i=0; i < 640 * 480; ++i) {
rgbOut->blue = *pImage;
++pImage;
unsigned char tmp = *pImage; // Save to reduce amount of reads.
rgbOut->green = tmp;
*bwOut = tmp;
++pImage;
rgbOut->red = *pImage;
++pImage;
++rgbOut;
++bwOut;
}
您可以利用单词读取比四个char读取更快的事实。我们将为此使用辅助宏。请注意,此示例假定使用little-endian目标系统。
const unsigned char *pImage;
RGB *rgbOut = imgRGB;
unsigned char *bwOut = imgBW;
const uint32_t *curPixelGroup = pImage;
for (int i=0; i < 640 * 480; ++i) {
uint64_t pixels = 0;
#define WRITE_PIXEL \
rgbOut->blue = pixels; \
pixels >>= 8; \
\
rgbOut->green = pixels; \
*bwOut = pixels; \
pixels >>= 8; \
\
rgbOut->red = pixels; \
pixels >>= 8; \
\
++rgbOut; \
++bwOut;
#define READ_PIXEL(shift) \
pixels |= (*curPixelGroup++) << (shift * 8);
READ_PIXEL(0); WRITE_PIXEL;
READ_PIXEL(1); WRITE_PIXEL;
READ_PIXEL(2); WRITE_PIXEL;
READ_PIXEL(3); WRITE_PIXEL;
/* Remaining */ WRITE_PIXEL;
#undef COPY_PIXELS
}
(你的编译器可能会在第一个or
中优化冗余的READ_PIXEL
操作。它也会优化移位,移除冗余的<< 0
。)
如果RGB
的结构是这样的:
struct RGB {
unsigned char blue, green, red;
};
您可以进一步优化,直接复制到结构,而不是通过其成员(red
,green
,blue
)。这可以使用匿名结构(或转换,但这使得代码更麻烦,可能更容易出错)来完成。 (同样,这取决于小端系统等等):
union RGB {
struct {
unsigned char blue, green, red;
};
uint32_t rgb:24; // Make sure it's a bitfield, otherwise the union will strech and ruin the ++ operator.
};
const unsigned char *pImage;
RGB *rgbOut = imgRGB;
unsigned char *bwOut = imgBW;
const uint32_t *curPixelGroup = pImage;
for (int i=0; i < 640 * 480; ++i) {
uint64_t pixels = 0;
#define WRITE_PIXEL \
rgbOut->rgb = pixels; \
pixels >>= 8; \
\
*bwOut = pixels; \
pixels >>= 16; \
\
++rgbOut; \
++bwOut;
#define READ_PIXEL(shift) \
pixels |= (*curPixelGroup++) << (shift * 8);
READ_PIXEL(0); WRITE_PIXEL;
READ_PIXEL(1); WRITE_PIXEL;
READ_PIXEL(2); WRITE_PIXEL;
READ_PIXEL(3); WRITE_PIXEL;
/* Remaining */ WRITE_PIXEL;
#undef COPY_PIXELS
}
您可以像读取(使用单词而不是24位)一样优化写入像素。事实上,这是一个非常好的主意,并将成为优化的下一步。但是,编码太累了。 =]
当然,您可以用汇编语言编写例程。然而,这使它不像现在那样便携。
我现在假设以下内容,所以如果我的假设是错误的,请告诉我:
a)imgRGB是该类型的结构
struct ImgRGB
{
unsigned char blue;
unsigned char green;
unsigned char red;
};
或至少类似的东西。
b)imgBW看起来像这样:
struct ImgBW
{
unsigned char BW;
};
c)代码是单线程的
假设上述情况,我发现您的代码有几个问题:
for (int y=0; y blue = *pImage;
...
}
}
总而言之,您只需要使您的循环适合您的底层硬件,因此对于特定的优化技术,您可能必须了解您的硬件运行良好以及它的功能是什么。
确保将pImage,imgRGB和imgBW标记为__restrict。使用SSE并一次执行16个字节。
实际上,从你在那里做的事情看起来你可以使用一个简单的memcpy()将pImage复制到imgRGB(因为imgRGB是行主格式,显然与pImage的顺序相同)。您可以通过使用一系列SSE swizzle和store ops填写imgBW来打包绿色值,但这可能很麻烦,因为您需要一次处理(3 * 16 =)48个字节。
当你开始这个时,你确定pImage和你的输出数组都是dcache吗?尝试使用预取提示提前获取128个字节并进行测量以查看是否可以改善效果。
编辑如果您不在x86上,请将“SSE”替换为适合您硬件的SIMD指令集。 (那是VMX,Altivec,SPU,VLIW,HLSL等)