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