借助C++进行Windows开发：探索高性能算法

借助C++进行Windows开发：探索高性能算法2010-04-16 MSDN / Kenny Kerr在并发空间中，诸如协调、异步行为、响应性和可伸缩性等问题会成为关注的焦点。这些都是开发人员在设计应用程序时必须考虑的一些比较深奥的主题。但是，也许是由于缺乏经验或缺乏合适的性能工具，一些同样重要的主题却常常被忽略。高性能算法就是其中一例。

在企业级别，开发人员会仔细斟酌分布式文件系统和缓存、群集、消息队列和数据库等问题。但是如果最核心的算法和数据结构效率低下，考虑这些又有什么用呢？

算法效率并不像您认为的那样简单。单处理器上设计良好的算法通常可以胜过多处理器上的低效实现。但是现在，当多处理器已经可用时，设计良好的算法还要显示出可衡量的可伸缩性和效率。由于会使问题变得更为复杂，因此针对单处理器进行优化的算法通常很难并行执行，而效率略低的算法通常可以在多处理器环境中发挥更好的性能。

为了说明这一点，我将使用 Visual C++ 展示一个非常简单的算法的开发过程，但实际上它不简单，即使乍看起来像是如此。下面是我们需要实现的一些内容：

void MakeGrayscale（BYTE* bitmap,
          const int width,
          const int height,
          const int stride）;

位图参数，指向一幅 32 位/像素的图像。再次重申，这是本文的重点。跨距的绝对值，指示内存中一行像素到下一行像素的字节数。每行的末尾可能存在填充内容。跨距的符号，指示这些行在内存中是自上而下（正跨距）还是自下而上（负跨距）。

让我们首先确定着手点。我们可以使用下面的结构来表示内存中的像素：

typedef unsigned char BYTE; // from windef.h
struct Pixel
{
  BYTE Blue;
  BYTE Green;
  BYTE Red;
  BYTE Alpha;
};

通过快速的 Web 搜索，我们确定对于一个给定颜色的像素可通过混合 30% 的红色、59% 的绿色和 11% 的蓝色来获得合理的灰度值。下面是将一个像素转换为灰度级的简单函数：

void MakeGrayscale（Pixel& pixel）
{
  const BYTE scale = static_cast<BYTE>（0.30 * pixel.Red +
                     0.59 * pixel.Green +
                     0.11 * pixel.Blue）;
  pixel.Red = scale;
  pixel.Green = scale;
  pixel.Blue = scale;
}

要计算位图内某个特定像素的字节偏移，可计算其水平位置与像素大小的乘积以及其垂直位置与跨距的乘积，然后将这些值相加：

offset = x * sizeof（Pixel） + y * stride

那么，该如何实现 MakeGrayscale 函数呢？如果您跳过这部分而不做其他考虑，您可能会写出类似于图 1 所示的算法行。乍一看这似乎是合理的，采用这样的方法，似乎可以很好地对小位图进行处理。但对于较大的位图会怎样呢？对 20,000 * 20,000 像素的位图又会如何？

图 1 低效的单线程算法

void MakeGrayscale（BYTE* bitmap,
          const int width,
          const int height,
          const int stride）
{
  for （int x = 0; x < width; ++x）
  for （int y = 0; y < height; ++y）
  {
    const int offset = x * sizeof（Pixel） + y * stride;
    Pixel& pixel = *reinterpret_cast<Pixel*>（bitmap + offset）;
    MakeGrayscale（pixel）;
  }
}

我恰好有一个配有四核 Intel Xeon X3210 处理器的 Dell PowerEdge。这种机器的时钟速度为 2.13GHz，前端总线为 1066MHz，二级缓存为 8MB，此外还具有其他各种超炫的功能。不可否认，它并不是最新的 Intel Xeon 处理器，但它确实值得称道。它由 64 位版本的 Windows Server 2008 驱动，非常适合做性能测试。

有了这些支持，我对宽度为 20,000 像素且高度也为 20,000 像素的位图运行了图 1 所示的算法。平均来说，它在 46 秒钟内进行了 10 余次迭代。不可否认，这张位图相当大，约占 1.5GB 的空间。但是这真的是问题所在吗？我的服务器有 4GB 内存，因此不需要分页磁盘。但图 2 显示了大家都非常熟悉的处理器使用率视图。

图 2 低效单线程算法的处理器使用率