CS巴别塔

面试宝典1：程序性能优化

Posted in Uncategorized by Kenny Yuan on 2010/04/29

开场白：最近公司招人，接触了一批形形色色的工程师，但感觉绝大多数人基础都很差，在某次TL的讨论之后，就想到了写一个《面试宝典》系列。

卷首语：这个《面试宝典》名字是我一贯的标题党风格，其实在内容上都是很简单、很基础的——都是那种“不知道这些就别出来混”的知识点。所以，高手/牛人可以到此打住了——端咖啡——送客~~~

作/译序：此文可能会持续更新直到补充得比较完整为止，有什么要补充的欢迎留言

基础原则之万能利器：Profiling

如何测量距离？——直尺/游标卡尺/卷尺/etc
如何测量电压？——电压表/万用表
如何测量时间？——钟表/秒表
如何测量温度？——温度计
如何测量质量？——天平/台秤/etc
如何测量程序性能？——Profiler !

是的，Profiler就是这么一件又基础又重要的工具（小标题里的“万能”当然是标题党了，千万别真的相信）。要回答“程序为什么慢/什么地方慢/到底有多慢”等问题，离不开Profiler，就像测量长度离不开尺子一样。 (嗯，那位要测地月距离的，别抬杠了，请移步回你的实验室吧，我知道你是rocket scientist，高科技呢:)

可以使用软件Profiler，也可以使用硬件来做Profiling（DSO/Logic Analyzer/Hybrid DSO/Timer），在什么都没有的情况下，至少也可以输出Log或者用其它方式来达到Profiling的目的。
一般来说，测量工具对被测目标应该没有影响（或者极小），但是软件的Profiler却对被测目标有一定程度的影响——以此为代价，换来的是方便和廉价（免费）。

在系统外部对性能进行测试，也是一种测量性能的方式，只不过它所测量的粒度很大，不能用于分析源码，只能用于比较不同源码的优劣。

如何进行性能优化？

基本原则

原则：使用Profiler来找出最影响性能的那些程序，重点优化它们
分类：基本知识
提示：时刻记心间

原则：无论尝试了何种优化，都要使用profiler来测量这种优化
分类：基本知识
提示：时刻记心间

原则：一九原则
分类：基本知识
提示：运行中的软件有一种典型情况：10%的程序占了90%的运行时间，优化的重点是这10%的程序（10%和90%为约数）。应当使用Profiler来找出它们，改进它们并继续用Profiler测量改进的效果——在没有明显的性能热点的时候，就要考虑换一种思路进行优化了：比如使用“硬件优化”（参见下文）。在切换了设计和体系结构后，之前做的profiling也有可能会失效，要重新进行测量，每一种判断和决策必须得到证据的支持。

原则：Amdahl定律
分类：基本知识
提示：活学活用Amdahl思想（原本此定律是讲并行计算的）——在知道了“要优化的部分”占“整体”的比例之后，对于此次优化来说，最高可能的加速比也就可以计算出来了。所以不能过多期望，要多多开辟新战场。

原则：benchmark是个宝
分类：基本知识
提示：从来就没有可以代表所有程序的“典型程序”，所以要想在各种情况下均取得较好的性能，就需要使用benchmark方式对性能进行测量。

硬件优化

原则：使用更快的设备/通讯协议
分类：硬件优化
提示：有时候需要尝试跳出软件优化的框框来想问题
范例：使用SSD代替机械硬盘，在IO速率上你能提高2－5倍（在无RAID的情况下），在寻道时间上你能提高4个数量级（WOW!）

原则：对硬件友好
分类：硬件优化
范例：利用SIMD指令（如视频编码器）；对Cache友好（数据Cache和指令Cache）；对流水线友好（比如threaded code，削减分枝预测失误。注意这里的thread不是“线程”，是“线索化”）；使用硬盘的外圈以达到更大的速度；

原则：利用硬件加速
分类：硬件优化
范例：使用D3D/OpenGL（哪怕是2D图形），使用GPU计算（如FFT），使用DMA不使用PIO，使用ASIC代替CPU进行专用计算（如常见的视频编解码专用芯片，还有加解密芯片），使用DSP对高负载数据进行处理（或预处理）

设计优化

原则：使用分布式计算
分类：设计优化
范例：使用HardoopHadoop；使用Memcached

原则：改进业务逻辑
分类：设计优化
范例：Google Chrome会扫描鼠标指针所在的位置，取得鼠标指针下的URL，然后去解析这些URL中的domain name（于是OS的DNS cache得到了warmup）；对于某个name A，一组相关的names也会被送去解析（比如上次打开name A中的页面时，用到了其它的name B, C, D，那么这次也把name B, C, D送去解析）

原则：批量操作
分类：设计优化
备注：可以是业务逻辑优化，也可以去尝试利用底层提供的批操作机制（如writev）。批操作之后是否真的在性能上有提高，需要实测数据的支持。

原则：减少用户空间/内核空间的切换和数据交换
分类：设计优化
范例：例如在设计时就考虑去使用futex和zero-copy之类的技术，在特定场合下“有奇效”（嗯，前面这句话好有卖大力丸的感觉……）

原则：对输入进行缓存
分类：设计优化，缓存
范例：依靠CPU Cache/阵列Cache/磁盘Cache/磁盘/操作系统Cache/程序管理的Cache/专用Cache服务器等，对输入进行缓存，以加快速度

原则：对中间结果进行缓存
分类：设计优化，缓存
范例：预装载/索引/suffix tree

原则：对输出进行缓存
分类：设计优化，缓存
范例：使用buffer批量输出（匹配软件计算速度和设备的速度）

原则：空间换时间
分类：设计优化

原则：使用内存池
分类：设计优化，内存
提示：可以用类似slab的方式来优化可预期的内存使用

原则：使用更好/更合适的GC算法
分类：设计优化，内存

原则：控制内存交换
分类：设计优化，内存

原则：吸收掉不必要的界面更新
分类：设计优化，GUI

原则：只重绘更新的区域
分类：设计优化，GUI

原则：对可视化的结果进行缓存
分类：设计优化，GUI
备注：中间结果缓存的一个特例

原则：parallelism–利用多CPU/多核心
分类：设计优化，并行

原则：利用并发(concurrency)
分类：设计优化，并行
提示：在单CPU上跑并发也能提高性能
范例：线程池

原则：选取合适的锁类型
分类：设计优化，并行，锁
范例：使用Futex/读写锁/seq锁/RCU

原则：使用消息
分类：设计优化，并行，锁
备注：可以减少共享数据和锁

原则：使用异步模型
分类：设计优化，并行，锁
范例：使用epoll/kqueue等；nginx

原则：消除锁
分类：设计优化，并行，锁
提示：试用无锁的算法/数据结构（如Ring Buffer）/算法

原则：使用FP Paradigm
分类：设计优化，并行
提示：彪悍的FP不需要提示

算法优化

（其实算法往往是包含在设计中的）

原则：使用更优的算法，减小算法的阶
分类：算法优化
范例：使用BM/Sunday算法代替BF算法

原则：减小算法的常量（BigOO）
分类：算法优化
范例：使用sentry来编写double link list

原则：处理好Big Omega和BigO，使算法在“最坏的时候也不要太坏”
分类：算法优化
范例：quick sort，避免O(N*N)的情况

原则：使用更优的数据结构
分类：算法优化
范例：AVL Tree–>Hash Table–>Ternary Search Tree
备注：其实有些重复，主要是为了区分狭义的“算法”和“数据结构”

原则：寻找并行化算法
分类：算法优化
备注：和前面的parallelism有些重复，这个更多的是指可并行的算法而不是其它意义上的并行

小技巧

原则：编译器优化
分类：小技巧
范例：使用Intel的编译器，使用Intel的性能库IPP
备注：注意Proebsting定律

原则：树递归–>尾递归
分类：小技巧
备注：在许多语言中，尾递归是不需要栈的，自动转换成迭代了（例如在erlang中用尾递归实现无限循环）

原则：少用小技巧，以免妨碍大粒度上的性能优化
分类：小技巧
提示：主要是指那些影响并行计算的小技巧，或者那些没有使用profiler进行测量就草率进行的盲目优化

原则：远离“神话”
分类：小技巧
提示：有些流传的关于优化的神化不足信，“是骡子是马拉出来骝骝”，一切在profiler下见真章
范例：比如“大块内存分配非常慢”的神话（甚至有过一个人估计数量级的时候说：分配10M内存至少要1秒钟），比如“虚函数导致效率低”的神话，比如“解释运行比编译慢”的神话，等等

原则：使用Lazy Evaluation
分类：小技巧

原则：避免大对象复制
分类：小技巧
范例：RVO/RVal Ref

原则：预译码/编译成本地代码
分类：小技巧，解释器和VM
范例：PYC/HipHop

原则：混合使用各有优势的语言
分类：小技巧
范例：C里使用汇编；Python里使用C模块；

原则：使用二进制优化器
分类：小技巧
范例：JIT就是最出名的一种二进制优化；Win32SDK的BitBlt()函数也是；

……

重温：无论尝试了何种优化，都要使用profiler来测量这种优化
分类：红宝书
提示：时刻记心间

（2010年10月29日更新）

鸣谢：感谢Guancheng指出问题

参见：性能优化的方法和技巧（这是一个文章系列）

Tagged with: ,

9 comments

如何在午休时间写一个QT程序以便能够挣到同事的五毛

Posted in Uncategorized by Kenny Yuan on 2010/04/28
作者的话：本文有两个目的：1、Zhuangbility；2、教你如何变成五毛；3、展示QT的生产力。
译者的话：本文并非虚构，是真实发生过的——如有雷同你肯定认识我，欢迎到我座位这边来喝可乐（你一定知道这个典故的）

在30分钟内用QT写一个抓屏程序

（注：Qt这个词应该读成Cute，而不是Queue-Tee）


※ ※ ※ ※
叮咚、叮咚、叮咚——00:29:59
叮咚、叮咚、叮咚——00:29:58
叮咚、叮咚、叮咚——00:29:57
※ ※ ※ ※

此截图程序可以实现以下功能：

+跨平台运行
+可以截取全屏幕或者其中一部分
+鼠标选中的区域为高亮，未选中的区域亮度减半
+截屏后可以反复选择，直至满意为止
+保存文件到桌面并退出
+复制图像到剪切板并退出


※ ※ ※ ※
叮咚、叮咚、叮咚——00:25:59
叮咚、叮咚、叮咚——00:25:58
叮咚、叮咚、叮咚——00:25:57
※ ※ ※ ※

整个程序主要有三个关键点：（1）抓屏到内存；（2）随着鼠标选取，加亮显示内存中的图片；（3）将图片的一部分保存到剪切板或者文件。
在QT中，这三个问题很好解决，问题（1）可以直接调用QT函数：

    QPixmap px = QPixmap::grabWindow(QApplication::desktop()->winId())

※ ※ ※ ※
叮咚、叮咚、叮咚——00:24:59
叮咚、叮咚、叮咚——00:24:58
叮咚、叮咚、叮咚——00:24:57
※ ※ ※ ※

问题（2）也不难，只需要提前做一点点工作，在抓图后保存两个图片，一个是正常的，另一个是变暗之后的：


    screen_ = px.toImage();
将刚刚截屏得到的图像转换成设备无关的内存表示
    darkScreen_ = screen_;
在内存中对RGB减半处理，使图像变暗，先计算每行的字节数：
    int bytesPerLine = darkScreen_.width() * darkScreen_.depth() / 8;
然后处理每个行
    for ( int i = 0 ; i < darkScreen_.height() ; ++ i )
    {
        uchar* lineBuf = darkScreen_.scanLine(i);
scanLine函数可以取得指定行的起始指针，不必再自己计算了。取得行指针后对每像素RGB值进行操作
        for ( int x = 0 ; x < bytesPerLine ; ++ x )
            lineBuf[x] /= 2;
    }
在这里没有尝试加速图片变暗的过程，效率问题最后再综合考虑。

※ ※ ※ ※
叮咚、叮咚、叮咚——00:22:59
叮咚、叮咚、叮咚——00:22:58
叮咚、叮咚、叮咚——00:22:57
※ ※ ※ ※
有了这两张图片，就可以进行绘图了：

void Widget::paintEvent(QPaintEvent *)
{
声明绘图对象，目标为窗口
    QPainter painter(this);
全屏绘制暗图像：
    painter.drawImage(0, 0, darkScreen_);
在选定的区域绘制亮图像：
    painter.drawImage(currentRect_, screen_, currentRect_, Qt::AutoColor);
}

currentRect_是在鼠标事件中保存的当前选择区域，它的计算也很简单，在鼠标的移动消息处理器中：


void Widget::mouseMoveEvent(QMouseEvent * e)
{
    if ( dragging_ )
        end_ = e->globalPos();
保存旧区域，用于后面的区域合并
    QRect oldRect = currentRect_;
设置新区域
    currentRect_.setTopLeft(start_);
    currentRect_.setBottomRight(end_);
调用normalized函数解决负宽度或者负高度问题
    currentRect_ = currentRect_.normalized();
QRect::united()函数用来求两个rect合并后的rect，可以省去许多手工计算。
且QT的repaint()函数也不需要关心背景擦除问题，QT4以上都是自动double buffer
    repaint(oldRect.united(currentRect_));
}

至此，问题（2）处理完毕。


※ ※ ※ ※
叮咚、叮咚、叮咚——00:18:59
叮咚、叮咚、叮咚——00:18:58
叮咚、叮咚、叮咚——00:18:57
※ ※ ※ ※

为处理问题（3），需要得到指定图像的指定区域，并且一个图像对象来表示。将这个功能编写成以下辅助函数：


static QImage clipImage(const QImage& srcImage, QRect rect)
{
    QImage image(rect.size(), QImage::Format_RGB32);
    const QImage* target = &srcImage;
    QImage targetImg;
    if ( srcImage.depth() != 32 )
    {
        targetImg = srcImage.convertToFormat(QImage::Format_RGB32);
        target = &targetImg;
    }
    int bytesPerPixel = image.depth() / 8;
    for ( int i = 0 ; i < image.height() ; ++ i )
    {
        uchar * line = image.scanLine(i);
        const uchar * srcLine = target->scanLine(rect.top() + i);
        memcpy(line,
               srcLine + rect.left() * bytesPerPixel,
               rect.width() * bytesPerPixel);
    }
    return image;
}
这个函数有点长，但思路却很简单：
1、先创建一个小图像，宽高与选区相同
2、取得源图像的数据，复制到小图像中
3、返回小图像

有了这个辅助函数之后，想保存文件，就可以这样写：


QImage img(clipImage(screen_, currentRect_));
img.save(pathName, "png");
想把图片放到剪切板的话，可以这样写：

QApplication::clipboard()->clear();
QApplication::clipboard()->setImage(clipImage(screen_, currentRect_), QClipboard::Clipboard);
QImage(QApplication::clipboard()->image(QClipboard::Clipboard)); // Retrieve data from clipboard to make it owns the data

※ ※ ※ ※
叮咚、叮咚、叮咚——00:10:59
叮咚、叮咚、叮咚——00:10:58
叮咚、叮咚、叮咚——00:10:57
※ ※ ※ ※

再往下就是处理一些鼠标和键盘事件，比如在双击时复制到剪切板并退出，在按Ctrl+S时保存到文件并退出，按ESC时直接退出，等等

最终完成，编译，修改typo并运行，发现速度还可以，故取消profiling和性能调优计划，直接和DLL一起打包。至此任务完成，领取五毛工资。


※ ※ ※ ※
叮咚、叮咚、叮咚——00:00:09
叮咚、叮咚、叮咚——00:00:08
叮咚、叮咚、叮咚——00:00:07
叮咚、叮咚、叮咚
叮咚、叮咚、叮咚——00:00:05
叮咚、叮咚、叮咚
叮咚、叮咚、叮咚——00:00:03
叮咚、叮咚、叮咚——00:00:02
叮咚、叮咚、叮咚——00:00:01
叮咚、叮咚、叮咚——00:00:00

(EOF)
Tagged with: , ,

1 comment

SEMAT – 软件工程方法和理论

Posted in Uncategorized by Kenny Yuan on 2010/04/07

无责翻译：SEMAT – 软件工程方法和理论（终于醒悟了？想起来理论的缺失了？）


在当今这个摩登时代，非常幼齿的实践方法几乎埋葬了“软件工程”，特别突出地，有下列问题：
* 本来应该是德国式的严谨工程纪律，结果搞成了法国式的时尚随意流行
* 没有坚实的、被最广大人民群众接受的理论基础（就是说现在还是不明真相？）
* 实践方法千万种，其实没有多少能让人搞明白的差别，但却被人搞得和iPad一样大（蘑菇处处有啊——每个人的心中都有一颗大蘑菇）
* 没有可信的实验进行评估和验证（证伪原则！召唤软件工程行业的波普尔）
* 学院派搞理论的玩儿一套，工业界搞实践的玩儿另外一套，完全割裂开来了。（本来理论界应该是工业界的“大后方”才对）

我们吐血推荐去建立这样的“软件工程”：建立在坚实的理论基础之上的，有真正管用的原则的，有最好实践的：
* 由人人承认的要素构成它的核心，对特殊用途也可以扩展（一个中心，一个基本点）
* 应对处理两种问题：技术和人员（其实领导搞破坏比小兵要厉害多了，应该写上这一条）
* 工业界，学术界，研究者，用户都支持（千秋万代，一统江湖）
* 需求和技术变换不影响它的本质层面，只需要改动一下外表，不伤筋动骨（九头鸟，百足虫）

P.S. 圆扩号中的是我写的评论，原文请见（http://www.semat.org/bin/view）。在这里多说一句：其实，只要脑子不笨的人，都能明白这里面的道道儿；但是换了一批“大师”来搞这个东西，估计效果会不一样吧？ 当然，我过去碰到的那种不敢大声说“影帝是裸体的”人也不少，不过这种人还是容易被“大师”忽悠的，嘿嘿……

P.P.S. 这个东西从图老师的TWITTER看到的——感谢国家！

Tagged with: , ,

1 comment

Follow

Get every new post delivered to your Inbox.