2012.10 颜然/韩富晟 yanran.hfs@taobao.com @韩富晟 如何赢一个机械键盘 2012.10 颜然/韩富晟 yanran.hfs@taobao.com @韩富晟
题纲 什么样的比赛 解决问题的步骤 影响程序性能的因素 优化实践
什么样的比赛 排序267751个单词 单词存储在文件中,每行一个单词 运行结果输出到文件中 不限制运行环境 不限制语言 以运行时间短作为获胜标准
解决问题的步骤 从文件读取数据 切分单词 排序 合并单词 输出结果到文件
影响程序性能的因素 影响程序性能的因素: 选择好的算法 利用多核并发处理 让程序与机器架构更友好
排序算法的选择 考虑时间复杂度和能否多线程化 思考:多种算法的组合 数据结构 时间复杂度 多线程化 Quicksort O(NlogN) 是 Merge sort Heapsort 否 Bubble sort O(N^2) Bucket sort O(N + K)* * K是元素的长度
并发 CPU核数越来越多
并发 尽可能将所有步骤并行化,充分利用CPU的计算资源 注意阿姆达定律所给的启示 一端单核运行1分钟的程序,有30秒可以被并行优化,另外30秒不能并行优化,那么并行优化的极限,运行时间也不能小于30秒
认识CPU Cache CPU与内存之间巨大的速度鸿沟 访问内存有时间上和空间上的局部性 一些数据 Cache Line Size: 64Bytes L1 Cache Lentency: ~1ns Memory Lentency: 60~100ns
认识CPU Pipeline Branch Predication 一条指令分成多个步骤执行 CPU内部指令级别的并行 不确定的分支,虚函数等损伤性能 一次分支预测误判: 5ns
优化程序性能的步骤 正确地测量程序的性能是最基础,同时也是最容易被忽视的步骤 设计测试场景(排除环境干扰,固化测试场景) 测量优化前程序的性能 优化ing 测量优化后程序的性能
排序程序并行化 … 并行化 从文件读取数据 切分单词 排序 合并单词 输出结果到文件 从文件读取数据 切分单词 快速排序 输出结果到文件 若干次归并排序* 合并单词 * 并行化
排序程序耗时分布
数据结构的优化 267751个单词里最长的16个字符 两个8字节的整形可以存下 极大的提高比较操作的性能:最重要的优化之一
数据结构的优化
数据结构的优化-计算长度 这个算法的优点和缺点?
归并排序的优化 不使用通用的算法,针对两路归并做优化,减少比较次数
颜然/韩富晟 yanran.hfs@taobao.com @韩富晟 谢谢