为 了 衡 量 一 个 算 法 时 间 效 率 上 的 优 劣, 计 算 机 科 学 中 引 入 了 时 间 复 杂 度 的 概 念 回 忆 我 们 习 惯 使 用 的 大 O 表 示 法, 我 们 说 一 个 算 法 运 行 时 间 的 界 是 O(f(n)), 所 表 示 的 意 义 是, 假

Transcription

1 论 程 序 底 层 优 化 的 一 些 方 法 与 技 巧 成 都 七 中 骆 可 强 摘 要 : 本 文 以 优 化 程 序 运 行 的 时 间 效 率 为 目 地, 从 编 译 器 汇 编 代 码 CPU 特 性 等 较 为 底 层 的 概 念 着 眼, 对 程 序 优 化 进 行 了 全 方 位 的 探 讨, 总 结 了 在 优 化 中 实 用 的 思 想 原 则 方 法 和 技 巧, 并 对 它 们 在 竞 赛 中 的 应 用 价 值 做 出 了 一 些 尝 试 关 键 字 : 优 化 CPU 汇 编 语 言 编 译 器 序 言 引 例 CPU 指 令 的 运 行 效 率 数 值 运 算 的 优 化 除 法 乘 法 高 精 度 运 算 CPU 优 化 特 性 高 速 缓 存 分 支 预 测 乱 序 执 行 位 运 算 技 巧 高 维 数 组 使 用 的 注 意 事 项 应 用 举 例 总 结 参 考 文 献 特 别 感 谢 目 录 序 言 第 1 页 第 3 页 第 12 页 第 13 页 第 13 页 第 18 页 第 20 页 第 20 页 第 21 页 第 25 页 第 27 页 第 29 页 第 31 页 第 34 页 第 35 页 第 36 页 第 37 页 信 息 学 奥 林 匹 克 竞 赛 (Olympiad in Informatics) 是 研 究 怎 样 编 写 计 算 机 程 序 来 解 决 特 定 问 题 的 竞 赛 考 察 的 关 键 点, 在 于 怎 样 利 用 有 限 的 系 统 资 源 (CPU 时 间 片 与 系 统 内 存 ) 来 求 解 规 模 庞 大 的 数 学 模 型 在 正 确 这 一 前 提 下, 效 率 自 然 是 考 虑 问 题 的 第 一 要 素 效 率, 分 为 时 间 效 率 与 空 间 效 率, 如 何 对 时 间 效 率 进 行 优 化 是 本 文 将 要 研 究 的 主 题 算 法 是 决 定 时 间 效 率 的 关 键 优 化 程 序 的 时 间 效 率, 简 单 地 讲, 就 是 用 尽 一 切 手 段, 在 保 证 正 确 的 前 提 下 让 程 序 的 运 行 时 间 更 短 那 么, 有 些 什 么 手 段 呢? 最 重 要 的 自 然 是 : 使 用 尽 可 能 高 效 的 算 法 算 法 (Algorithm), 是 一 系 列 解 决 问 题 的 机 械 步 骤, 它 采 用 明 确 定 义 的 语 义, 描 述 了 求 解 特 定 数 学 模 型 的 一 般 方 法 算 法 的 好 坏, 直 接 决 定 了 程 序 的 运 行 效 率 采 用 低 效 的 算 法 或 高 效 的 算 法, 其 差 别 就 好 像 选 择 走 路 或 是 坐 飞 机, 完 全 不 在 一 个 数 量 级 时 间 复 杂 度 的 概 念 及 其 局 限 性 第 1 页

2 为 了 衡 量 一 个 算 法 时 间 效 率 上 的 优 劣, 计 算 机 科 学 中 引 入 了 时 间 复 杂 度 的 概 念 回 忆 我 们 习 惯 使 用 的 大 O 表 示 法, 我 们 说 一 个 算 法 运 行 时 间 的 界 是 O(f(n)), 所 表 示 的 意 义 是, 假 设 这 个 算 法 的 实 际 运 行 时 间 关 于 输 入 规 模 n 的 函 数 是 T(n), 那 么 存 在 正 常 数 n0 c, 使 得 对 于 n n0, 有 0 T(n) c f(n) 有 了 这 样 一 个 上 界, 我 们 就 能 知 道 T(n) 的 增 长 速 度, 从 而 能 够 大 致 判 断 对 于 给 定 的 n, 我 们 的 算 法 能 不 能 在 一 个 合 理 的 时 间 内 出 解 然 而 另 一 方 面 不 可 否 认 的 是, 这 样 一 个 工 具 是 极 其 粗 略 的 我 们 注 意 到 刚 才 的 定 义 式 中 存 在 一 个 常 数 c, 它 在 渐 进 意 义 上 是 无 关 紧 要 的, 但 回 到 现 实 世 界 中, 它 却 不 可 忽 视 同 样 是 O(n) 阶 的 算 法, 有 些 可 以 快 到 只 消 耗 2 n 个 CPU 时 钟 周 期, 而 另 一 些 甚 至 需 要 1000 n 个 时 钟 周 期 还 要 多 就 好 像 同 样 是 乘 坐 飞 机, 也 有 快 慢 的 极 大 差 别 使 用 相 同 时 间 复 杂 度 的 算 法, 因 为 这 个 常 数 c 的 不 同, 实 际 运 行 所 需 要 的 时 间, 也 可 能 有 天 壤 之 别 算 法 并 不 是 时 间 效 率 的 全 部 那 么, 这 个 常 数 受 哪 些 因 素 的 影 响 呢? 无 疑, 它 同 样 受 制 于 算 法 : 不 同 的 算 法, 可 能 有 着 相 同 的 复 杂 度, 但 是 实 际 效 果 截 然 不 同 相 同 的 算 法, 可 能 有 着 不 同 的 实 现 方 式, 一 些 逻 辑 上 的 简 化 也 能 大 大 降 低 运 行 所 需 花 费 的 时 间 那 么, 算 法 就 是 程 序 运 行 效 率 的 全 部 了 么? 答 案 是 否 定 的, 有 些 东 西 是 隐 藏 在 逻 辑 层 面 之 下 的, 它 们 同 样 显 著 地 影 响 着 程 序 的 运 行 效 率, 而 我 们 却 很 难 看 到 举 例 来 说, 你 能 想 象 当 我 们 在 C 语 言 中 书 写 a/=7 这 一 语 句 时, 实 际 上 处 理 器 并 没 有 做 缓 慢 的 除 法, 而 使 用 了 乘 法 和 位 移 取 而 代 之 么? 因 为 这 样, 我 喜 欢 把 大 O 定 义 式 中 的 常 数 c 一 分 为 二 的 来 看 待 :c=c1 c2,c1 代 表 逻 辑 层 面 ( 算 法 ) 的 消 耗, 而 c2 表 示 每 一 句 程 序 语 句 在 底 层 运 行 的 消 耗, 那 么 程 序 的 实 际 运 行 时 间, 约 为 c2 [c1 f(n)], 方 括 号 中 的 部 分 c1 f(n) 就 完 全 由 算 法 来 决 定, 而 c2 则 取 决 于 程 序 的 底 层 实 现 前 者 固 然 重 要, 后 者 也 同 样 不 可 忽 视 本 文 将 要 研 究 的, 就 是 怎 样 在 程 序 运 行 的 底 层 对 细 节 做 出 优 化, 以 提 升 程 序 的 运 行 效 率 为 什 么 要 学 习 底 层 优 化 在 OI 竞 赛 中, 算 法 是 考 察 的 重 点 底 层 实 现 看 起 来 并 不 重 要, 确 实 提 升 空 间 也 相 对 较 小, 但 当 我 们 设 计 的 算 法 有 一 些 先 天 缺 陷 时, 或 许 对 底 层 做 细 致 的 优 化 能 对 我 们 有 很 大 的 帮 助, 在 后 文 中 会 展 示 一 些 实 际 的 例 子 在 竞 赛 之 外, 学 习 底 层 的 东 西, 能 让 我 们 更 深 入 地 认 识 眼 前 的 机 器, 即 使 在 使 用 高 级 语 言 书 写 程 序 时, 脑 海 中 也 会 自 然 投 射 出 底 层 发 生 的 事 情, 从 而 能 够 写 出 质 量 更 高 的 代 码 在 这 篇 论 文 前 期 准 备 实 验 研 究 总 结 规 律 到 最 终 成 文 的 过 程 中, 我 学 到 了 太 多 的 东 西, 这 些 东 西 在 我 们 平 时 为 OI 竞 赛 编 程 的 过 程 中 是 很 难 看 到 的, 而 我 也 相 信, 这 些 东 西 在 为 大 家 所 广 泛 认 识 之 后, 同 样 能 够 服 务 于 竞 赛, 实 际 地 提 升 成 绩 说 了 这 么 多, 或 许 是 该 展 现 一 个 实 例 的 时 候 了 下 面 我 们 从 一 个 极 其 简 化 的 编 程 任 务 入 手, 来 看 看 什 么 是 底 层 优 化, 有 些 什 么 样 的 工 具, 能 做 到 什 么 程 度 第 2 页

3 平 台 简 介 条 件 所 限, 本 文 中 的 所 有 研 究 编 码 测 量 工 作 均 在 一 台 Thinkpad X61 笔 记 本 上 进 行, 下 面 简 要 给 出 工 作 平 台 上 硬 件 和 软 件 与 优 化 工 作 相 关 的 规 格 参 数 : CPU: Intel Core 2 Duo CPU 1.80GHz Cache: L1-64KB L2-2MB 主 存 : SODIMM Synchronous 667 MHz 1GB 2 操 作 系 统 : Ubuntu Intrepid Ibex 内 核 版 本 : Linux generic 编 译 器 版 本 : gcc 汇 编 器 版 本 : GNU assembler 连 接 器 版 本 : GNU ld 当 然, 一 种 优 化 方 法 的 实 际 效 果, 和 平 台 规 格 密 切 相 关 如 果 只 在 一 种 平 台 ( 主 要 指 CPU) 进 行 测 试 就 妄 下 结 论, 是 不 负 责 任 的 为 此, 我 也 将 文 中 所 涉 及 的 程 序 在 不 同 的 平 台 下 进 行 了 广 泛 的 测 试, 跨 越 了 不 同 的 操 作 系 统 (windows 与 linux) 和 不 同 厂 家 生 产 的 CPU(intel 与 AMD) 测 量 结 果 的 绝 对 值 自 然 千 差 万 别, 但 采 取 不 同 优 化 方 式 所 取 得 的 效 果 基 本 上 是 一 致 的, 这 得 益 于 现 代 CPU 都 采 用 了 一 套 相 似 的 内 部 架 构 与 优 化 引 擎, 为 开 发 人 员 提 供 了 方 便 不 过 另 一 方 面, 也 要 求 我 们 在 学 习 CPU 开 发 时 应 以 把 握 大 原 则 为 重 点, 而 不 要 钻 牛 角 尖 如 果 沉 溺 于 为 某 种 特 定 的 CPU 内 部 特 性 做 古 怪 的 优 化, 会 导 致 在 不 同 的 CPU 上 运 行 效 果 天 差 地 别, 这 样 的 优 化 是 没 有 价 值 的 遗 憾 的 是, 后 文 将 提 及 的 SIMD 系 列 优 化 方 法, 在 AMD 生 产 的 芯 片 上, 虽 然 可 以 兼 容, 但 是 优 化 效 果 并 不 突 出, 值 得 大 家 留 意 让 我 们 先 来 看 一 个 非 常 简 单 的 例 子 : 引 例 假 设 我 们 被 要 求 编 写 这 样 一 个 函 数, 接 受 一 个 指 向 32 位 正 整 数 数 组 头 部 的 指 针, 以 及 数 组 的 长 度, 要 求 函 数 返 回 这 些 整 数 中 的 最 大 值 在 C 语 言 中, 函 数 头 应 该 是 这 样 : int get_max(int* a,int l); 朴 素 的 实 现 若 要 在 算 法 层 面 研 究 这 个 问 题 几 乎 没 有 任 何 价 值, 进 行 一 遍 线 性 的 扫 描 即 可 得 到 O(n) 级 别 的 算 法, 另 外 由 于 数 组 中 的 每 一 个 元 素 必 须 被 访 问 到 才 能 保 证 出 解 正 确, 所 以 算 法 的 复 杂 度 下 界 也 是 O(n) 我 们 可 以 立 即 写 出 下 面 这 个 C 语 言 程 序 : // 最 初 版 程 序 int get_max(int* a,int l){ int mx=0,i; for(i=0;i<l;i++){ if(a[i]>mx)mx=a[i]; return mx; 第 3 页

4 编 译 说 明 众 所 周 知, 现 代 编 译 器 已 经 不 再 局 限 于 简 单 地 把 一 句 句 高 级 语 言 翻 译 为 对 应 的 汇 编 语 言, 而 能 够 智 能 地 完 成 许 多 以 前 只 有 人 手 工 才 能 完 成 的 优 化, 特 别 是 各 个 编 译 器 提 供 的 高 级 优 化 选 项, 更 是 常 常 能 够 提 供 接 近 人 类 手 工 优 化 的 效 率 但 是, 在 我 们 OI 竞 赛 的 评 测 中, 这 些 优 化 选 项 是 不 会 被 开 启 的 所 以, 本 文 中 所 有 程 序 的 编 译, 都 没 有 打 开 优 化 选 项 诚 然, 打 开 这 些 优 化 选 项, 本 文 中 介 绍 的 各 种 人 工 优 化 的 效 果 可 能 会 打 些 折 扣, 但 我 仍 然 觉 得 这 样 做 是 合 理 的, 一 来 更 贴 近 比 赛 中 使 用 的 评 测 环 境, 二 来 既 然 是 在 研 究 优 化, 我 们 自 然 应 该 亲 自 去 探 究 其 中 的 方 法 和 原 理, 而 不 应 该 让 别 人 的 程 序 来 代 劳, 否 则 可 能 永 远 也 不 会 清 楚 其 中 的 奥 妙 为 此, 本 文 中 所 有 的 程 序 均 使 用 竞 赛 时 的 编 译 选 项 进 行 编 译 并 测 量 效 果, 对 于 c 语 言 程 序, 编 译 命 令 为 : gcc a.c -o a 这 个 程 序 显 然 能 够 正 确 地 完 成 所 要 求 的 任 务, 而 且, 算 法 的 复 杂 度 也 达 到 了 理 论 下 界 效 率 怎 么 样 呢? 让 我 们 来 检 验 一 下 程 序 运 行 的 速 度 我 在 测 试 平 台 将 此 函 数 应 用 于 一 个 存 有 个 整 数 的 数 组, 连 续 运 行 100 次 并 求 平 均 占 用 的 时 钟 周 期 数 测 量 值 为 个 周 期 处 理 一 个 数 平 均 就 占 用 了 7~8 个 时 钟 周 期, 结 果 不 令 人 满 意 关 于 文 中 程 序 所 使 用 的 计 时 方 法 为 了 测 试 程 序 的 运 行 效 率, 需 要 一 种 测 量 时 间 的 工 具, 有 许 多 不 同 的 库 函 数, 操 作 系 统 api, 命 令 行 工 具 可 以 进 行 时 间 测 量, 本 文 主 要 使 用 IA32 处 理 器 提 供 的 rdtsc 指 令 来 获 取 程 序 运 行 消 耗 的 时 钟 周 期, 此 方 法 精 确 度 较 高, 缺 点 在 于 无 法 排 除 掉 程 序 运 行 过 程 中 操 作 系 统 和 后 台 运 行 程 序 所 占 用 的 时 钟 周 期, 结 合 linux 系 统 命 令 time 一 起 使 用 可 以 弥 补 这 一 缺 憾. 下 面 是 本 文 所 有 程 序 都 会 用 到 的 计 时 函 数 的 C 代 码 : #define ull unsigned long long ull get_clock(){ ull ret; asm volatile ("rdtsc\n\t":"=a"(ret):); return ret; 第 一 次 优 化 开 始 着 手 寻 找 程 序 可 优 化 之 处, 首 先 发 现 'a[i]' 被 提 及 了 两 次, 重 复 计 算 地 址 在 这 个 小 循 环 中 的 开 销 也 是 不 可 忽 略 的, 那 么 第 一 版 的 优 化 我 们 尝 试 来 进 行 普 通 的 循 环 和 寻 址 的 优 化 : 第 4 页

5 // 第 一 次 优 化 int get_max(int* a,int l){ int mx=0,*ed=a+l; while(a!=ed){ if(*a>mx)mx=*a; a++; return mx; 测 试 一 下 运 行 时 间, 平 均 占 用 时 钟 周 期 测 量 值 为 : , 处 理 一 个 数 平 均 下 降 了 一 个 时 钟 周 期, 比 第 一 版 程 序 在 时 间 效 率 上 优 化 了 12% 来 回 顾 一 下 这 次 优 化, 他 解 决 了 在 初 版 程 序 代 码 中 出 现 的 重 复 寻 址 的 问 题, 而 获 得 了 期 望 中 效 率 的 提 升, 从 本 质 上 说 仍 然 属 于 逻 辑 层 面 的 优 化 这 次 优 化 是 在 C 语 言 层 面 编 写, 也 能 够 在 C 语 言 层 面 进 行 解 释 的 第 二 次 优 化 继 续 前 面 的 思 路, 很 难 再 想 出 什 么 有 效 的 优 化 了, 这 就 是 我 们 的 终 点 吗? 其 实 游 戏 才 刚 刚 开 始, 下 面 给 出 第 二 个 优 化 : // 第 二 次 优 化 int get_max(int* a,int l){ assert(l%8==0); #define D(x) mx##x=0 int D(0),D(1),D(2),D(3), D(4),D(5),D(6),D(7),*ed=a+l; #define CMP(x) if(*(a+x)>mx##x)mx##x=*(a+x); while(a!=ed){ CMP(0);CMP(1); CMP(2);CMP(3); CMP(4);CMP(5); CMP(6);CMP(7); a+=8; #define CC(x1,x2) if(mx##x1>mx##x2)mx##x2=mx##x1; CC(1,0);CC(3,2); CC(5,4);CC(7,6); CC(2,0);CC(6,4); CC(4,0); return mx0; 这 个 程 序 使 用 了 许 多 宏 定 义, 可 读 性 较 差 不 过 思 路 非 常 简 单 : 将 原 来 单 线 的 求 最 大 值 进 程 分 为 八 路, 最 后 再 来 汇 总 总 的 最 大 值 要 说 明 一 点 的 是, 正 如 程 序 第 一 行 的 assert 所 显 示, 这 个 函 数 只 能 在 l 是 8 的 倍 数 的 情 况 下 工 作, 要 让 它 可 以 对 任 何 l 工 作 很 容 易, 不 第 5 页

6 过 那 不 是 我 们 关 注 的 重 点, 为 了 让 代 码 简 短 一 些, 略 去 不 表 这 个 程 序 的 效 率 怎 样 呢? 同 样 平 台 下 的 测 量 值 为 : , 比 最 初 版 本 优 化 了 54% 是 什 么 让 这 个 程 序 拥 有 了 如 此 大 的 效 率 提 升? 难 道 是 指 针 a 的 递 增 次 数 只 有 原 来 1/8 导 致 的? 从 C 语 言 的 层 面 来 看, 只 有 这 一 个 解 释 但 这 是 说 不 通 的, 因 为 相 比 循 环 体 里 面 的 语 句, 这 一 个 递 增 显 得 无 足 轻 重, 至 少 不 会 带 来 这 么 大 的 效 率 改 善 而 除 了 这 里, 从 C 代 码 上 看 和 第 二 个 程 序 又 没 有 本 质 上 的 区 别 难 道 计 算 机 程 序 的 运 行 是 完 全 不 可 预 测 和 理 解 的 吗? 深 入 汇 编 语 言 让 我 们 来 回 顾 一 下 C 语 言 编 写 的 程 序 是 怎 样 运 行 的 吧, 首 先 编 译 器 (compiler) 将 C 代 码 编 译 为 汇 编 语 言 (assembly language) 代 码, 再 经 过 汇 编, 连 接 等 一 系 列 步 骤 转 化 为 可 执 行 文 件 这 里 最 关 键 的 一 部, 自 然 在 编 译 环 节, 因 为 一 旦 代 码 编 译 为 机 器 指 令 后, 在 CPU 中 执 行 它 的 方 式 就 已 经 确 定 了 编 译 的 质 量, 也 直 接 决 定 了 程 序 运 行 的 效 率 如 果 仅 仅 把 目 光 集 中 在 C 代 码 的 层 次, 而 完 全 不 在 汇 编 语 言 层 面 进 行 思 考, 优 化 的 过 程 就 像 被 蒙 住 了 眼 睛 既 不 可 能 真 正 看 清 程 序 运 行 效 率 的 本 质, 也 不 能 进 一 步 进 行 更 强 的 优 化 对 第 二 次 优 化 的 程 序 进 行 编 译, 得 到 相 应 的 汇 编 代 码, 经 过 查 看, 发 现 除 了 循 环 变 量 的 累 加 之 外, 其 他 语 句 对 应 的 汇 编 代 码 的 面 目 并 无 甚 差 别, 仅 仅 是 简 单 的 重 复 并 列 起 来 但 确 实 获 得 了 极 大 的 效 率 提 升, 要 完 整 的 解 释 这 个 问 题, 会 提 及 处 理 器 中 的 各 种 优 化 机 制 : 乱 序 执 行 流 水 线 机 制 指 令 预 取 分 支 预 测 寄 存 器 重 命 名 高 速 缓 存, 这 些 主 题 都 将 在 后 文 中 作 研 究 简 单 的 讲, 在 最 初 两 个 程 序 中, 每 次 计 算 新 的 mx 都 会 依 赖 于 上 一 步 的 计 算 结 果, 相 关 的 计 算 指 令 也 必 须 依 次 运 行, 而 将 求 值 过 程 分 为 多 路 处 理,mx0,mx1 等 变 量 的 相 关 指 令 之 间 互 相 没 有 关 联, 让 处 理 器 有 更 大 的 机 会 将 他 们 并 发 过 于 底 层 的 细 节 固 然 不 容 易 完 全 掌 控, 但 是 遵 循 一 些 基 本 的 原 则, 总 有 机 会 使 处 理 器 为 我 们 作 出 优 化 第 三 次 优 化 既 然 已 经 深 入 到 了 汇 编 语 言 的 层 次, 那 不 如 直 接 用 汇 编 语 言 来 编 写 这 个 函 数 汇 编 语 言 的 利 与 弊 在 CPU 中 重 要 的 概 念 如 寄 存 器 (register) 状 态 标 志 (status flag) 指 令 (instruction) 等, 在 高 级 语 言 中 全 部 被 隐 藏, 取 而 代 之 的 是, 高 级 语 言 过 于 依 赖 内 存 变 量 这 一 概 念, 而 读 写 内 存, 是 处 理 器 最 低 效 的 操 作 之 一 而 且 高 级 语 言 过 于 丰 富 的 语 义 也 造 成 了 翻 译 过 程 自 然 出 现 极 大 浪 费 这 一 切, 让 我 们 在 C 语 言 层 面 作 优 化, 就 像 带 着 脚 镣 跳 舞, 一 旦 使 用 起 汇 编 语 言, 这 一 切 就 豁 然 开 朗 了, 我 们 不 再 被 内 存 变 量 与 高 级 语 句 所 束 缚, 可 以 直 接 操 纵 最 底 层 的 部 件, 更 有 额 外 的 丰 富 指 令 可 供 使 用 可 以 说, 使 用 汇 编 语 言 是 获 得 极 致 效 率 的 基 础 汇 编 语 言 既 然 如 此 之 好, 那 我 们 为 什 么 不 用 汇 编 语 言 来 编 写 所 有 的 程 序 呢 这 主 要 是 因 为 汇 编 语 言 编 码 成 本 太 高, 要 用 来 编 写 大 型 程 序 虽 并 非 完 全 不 可 能, 也 是 极 其 困 难 的, 实 际 的 程 序 中 并 非 所 有 地 方 都 需 要 如 此 极 致 的 效 率, 而 真 正 需 要 的 是 正 确 地 设 计 代 码 架 构 并 编 写 程 序 逻 辑, 要 用 汇 编 语 言 来 做 这 些, 就 好 像 用 小 颗 粒 的 颜 料 逐 点 绘 制 一 副 油 画, 是 很 难 把 握 成 品 的 全 貌 的 另 一 方 面, 汇 编 语 言 编 写 的 程 序 会 有 较 强 的 平 台 依 赖 性, 可 移 植 性 很 差, 也 使 它 被 拒 于 应 用 程 序 开 发 的 门 外, 而 高 级 语 言 ( 如 C 语 言 ) 被 发 明 出 来 较 好 地 解 决 了 这 些 缺 陷 那 么 汇 编 语 言 又 一 钱 不 值 了 吗? 当 然 也 不 是, 就 算 在 现 今 的 实 际 程 序 开 发 过 程 中, 程 序 员 们 仍 然 使 用 汇 编 语 言 来 编 写 程 序 中 的 效 率 瓶 颈 部 分, 而 程 序 的 主 要 部 分 使 用 高 级 语 言 来 第 6 页

7 编 写 要 实 现 这 一 点, 最 简 便 的 方 法 是 使 用 编 译 器 各 自 提 供 的 内 嵌 汇 编 机 制 使 我 们 可 以 直 接 在 C 代 码 中 书 写 汇 编 代 码, 并 且 可 以 通 过 C 编 译 器 的 编 译 这 样 做 还 有 一 个 最 直 接 的 好 处 : 在 竞 赛 中, 我 们 可 以 直 接 提 交 这 样 的 程 序 并 通 过 编 译 声 明 本 文 并 非 以 讲 授 汇 编 语 言 与 计 算 机 体 系 结 构 为 目 的, 所 以 在 这 里 假 设 读 者 对 这 两 者 有 最 基 本 的 了 解, 否 则 阅 读 会 有 较 大 障 碍 使 用 内 嵌 汇 编 进 行 优 化 下 面 正 式 开 始 转 向 汇 编 语 言 进 行 优 化, 本 文 中 的 程 序 均 使 用 gcc 内 嵌 汇 编, 采 用 AT&T 格 式 的 汇 编 语 法, 后 面 不 再 做 说 明 首 先, 我 们 直 接 朴 素 地 将 原 始 意 图 使 用 汇 编 语 言 实 现 一 遍, 得 到 如 下 代 码 : // 第 三 次 优 化 int get_max(int* a,int l){ int ret; asm volatile ( "movl $0, %%eax\n\t" ".p2align 4,,15\n" "LP1:\n\t" "cmpl -4(%1,%2,4), %%eax\n\t" "jge ED\n\t" "movl -4(%1,%2,4), %%eax\n" "ED:\n\t" //"loop LP1\n\t" "decl %2\n\t" "jnz LP1\n\t" "movl %%eax, %0\n\t" :"=m"(ret) :"r"(a),"c"(l) :"%eax"); return ret; 这 个 程 序 的 效 率 如 何 呢? 测 量 结 果 为 : 平 均 个 时 钟 周 期 处 理 一 个 数 据 平 均 只 需 要 2 个 时 钟 周 期 了, 相 比 最 初 的 程 序, 优 化 了 72%, 结 果 十 分 令 人 满 意 打 量 一 下 这 个 程 序, 核 心 循 环 中, 有 5 条 指 令, 其 中 甚 至 有 两 条 是 条 件 分 支 指 令, 还 有 两 条 需 要 访 问 内 存, 而 且 使 用 了 最 复 杂 的 sib 寻 址 方 式 感 觉 起 来, 平 均 2 个 时 钟 周 期, 是 没 有 道 理 的, 其 实 这 主 要 得 益 于 现 代 CPU 各 种 强 大 的 优 化 机 制 : 高 速 数 据 cache 使 两 次 访 问 同 一 内 存 如 同 访 问 寄 存 器 一 般 迅 速, 第 一 个 条 件 跳 转 大 部 分 时 间 不 会 成 立, 而 相 反 第 二 个 跳 转 总 会 成 立, 这 让 CPU 的 分 支 预 测 发 挥 到 极 致 而 强 大 的 乱 序 执 行 引 擎 使 得 循 环 中 的 这 些 小 指 令 得 以 以 接 近 双 倍 的 时 间 运 行 ( 以 上 提 到 的 这 些 名 词 在 后 文 都 会 有 详 细 的 介 绍 ) 现 代 CPU 的 优 化 如 此 强 大, 是 否 我 们 可 以 胡 乱 书 写 汇 编 代 码 了 呢? 绝 对 不 是 优 化 中 的 一 些 小 插 曲 第 7 页

8 注 意 到 在 上 面 的 程 序 中, 有 一 行 注 释 掉 的 loop 指 令, 如 果 没 有 经 验, 或 许 会 想, 使 用 loop 指 令, 指 令 码 体 积 更 小, 而 且 使 用 复 杂 指 令, 一 次 性 指 示 CPU 完 成 更 复 杂 的 工 作, 应 该 具 有 更 高 的 效 率 那 么 我 们 使 用 loop 指 令 取 代 递 减 与 跳 转 指 令 试 一 试, 结 果 令 人 大 跌 眼 镜 : 平 均 耗 费 个 时 钟 周 期, 整 整 慢 了 一 倍 还 多 RISC 与 CISC 要 解 释 这 个 问 题, 不 得 不 提 到 RISC 与 CISC 架 构 CISC 全 称 为 Complex Instruction Set Computer, 即 复 杂 指 令 系 统 计 算 机, 它 从 计 算 机 诞 生 之 初 一 直 沿 用 至 今, 他 的 指 令 集 极 其 庞 大, 功 能 繁 杂, 导 致 制 作 工 艺 复 杂, 成 本 高 昂, 而 且 速 度 缓 慢 看 看 我 们 现 在 使 用 的 intel pentium 处 理 器 就 知 道 了, 虽 然 看 似 其 中 有 很 多 一 次 性 完 成 复 杂 工 作 的 指 令, 事 实 上 还 是 在 CPU 内 部 被 翻 译 成 多 条 微 指 令, 才 能 真 正 在 cpu 上 运 行 这 个 过 程 本 身 造 成 的 性 能 损 耗 可 想 而 知, 虽 然 处 理 器 厂 商 采 用 了 各 种 强 大 的 办 法 来 试 图 优 化 这 一 过 程, 也 不 能 弥 补 设 计 上 先 天 的 劣 势 后 来 工 程 师 们 发 现, 事 实 上 人 们 所 使 用 的 80% 的 指 令 都 处 于 20% 的 指 令 集 中, 于 是 设 计 了 理 念 完 全 不 同 的 RISC( 精 简 指 令 集 计 算 机 ) 通 过 采 用 一 个 较 小 但 功 能 完 备 的 指 令 集, 大 大 简 化 处 理 器 的 设 计 RISC 中 不 再 需 要 微 指 令 的 概 念, 而 直 接 硬 件 执 行 指 令 码, 在 一 个 时 钟 周 期 执 行 一 条 指 令, 性 能 极 高 且 容 易 控 制 到 今 天, 只 有 intel,amd 等 少 数 厂 家 还 在 生 产 CISC 芯 片 虽 然 RISC 有 如 此 多 的 优 势, 但 不 可 回 避 的 是, 我 们 的 普 通 桌 面 应 用 已 经 使 用 CISC 架 构 许 多 年, 对 以 前 软 件 的 兼 容 性 不 能 放 弃 为 了 兼 顾 性 能 与 兼 容 性, 处 理 器 厂 商 使 用 了 折 中 的 方 案 : 处 理 器 的 外 层 继 续 兼 容 老 式 的 x86 指 令 集, 而 内 核 尽 量 向 RISC 靠 拢 : 使 用 一 套 类 似 RISC 的 微 指 令 集, 内 部 采 用 128 个 物 理 寄 存 器, 在 外 层 通 过 微 指 令 解 码 器,RAT(Register Alias Table) 等 把 对 外 部 指 令 映 射 到 RISC 核 心 上 去 除 此 之 外, 处 理 器 厂 商 继 续 大 力 优 化 指 令 集 中 类 RISC 的 那 一 部 分, 使 他 们 在 流 水 线 上 能 有 最 好 的 表 现, 而 对 于 某 些 复 杂 指 令, 在 很 早 以 前 就 已 经 被 处 理 器 厂 商 放 弃,cmps cmov lea 等 复 合 指 令 不 再 具 备 速 度 优 势,loop 当 然 也 是 其 中 一 员 所 以, 我 们 应 该 了 解 现 今 做 汇 编 优 化, 应 该 尽 量 使 用 最 基 本 的 那 一 个 指 令 子 集,CPU 会 帮 助 我 们 尽 量 高 效 地 运 行 当 然 也 有 例 外, 那 就 是 各 cpu 厂 商 都 投 入 大 量 精 力 研 发 的 SMID 指 令 集, 这 在 后 面 会 提 到 回 到 我 们 的 程 序,loop 指 令 低 效 的 问 题 已 经 有 了 解 答 同 理, 如 果 试 图 用 cmov 指 令 优 化 掉 条 件 跳 转, 结 果 同 样 会 令 人 失 望 第 四 次 优 化 完 成 了 这 个 朴 素 的 汇 编 优 化, 下 一 步 又 怎 么 做 呢? 容 易 想 到 : 降 低 程 序 上 下 文 依 赖 性! 在 前 面 的 第 二 次 优 化 中, 这 种 方 法 起 到 了 非 常 好 的 效 果, 那 我 们 就 在 汇 编 语 言 中 如 法 炮 制 一 次 : 第 8 页

9 // 第 四 次 优 化 int get_max(int* a,int l){ assert(l%2==0); int ret; asm volatile ( "movl $0, %%eax\n\t" "movl $0, %%edx\n\t" ".p2align 4,,15\n" "LP2:\n\t" "cmpl (%1), %%eax\n\t" "jge ED2\n\t" "movl (%1), %%eax\n" "ED2:\n\t" "cmpl 4(%1), %%edx\n\t" "jge ED3\n\t" "movl 4(%1), %%edx\n" "ED3:\n\t" "addl $8, %1\n\t" "subl $2, %2\n\t" "jnz LP2\n\t" "cmpl %%edx, %%eax\n\t" "cmovll %%edx, %%eax\n\t" "movl %%eax, %0\n\t" :"=m"(ret) :"r"(a),"r"(l) :"%eax","%edx"); return ret; 我 们 期 待 着 它 能 起 到 第 二 个 优 化 一 般 神 奇 的 效 果, 运 行 程 序, 测 量 结 果 为 个 时 钟 周 期 确 实 取 得 了 优 化, 但 效 果 不 明 显 立 即 想 到, 是 不 是 应 该 展 开 更 多 的 次 数 呢? 我 试 着 进 行 4 次 展 开, 用 上 了 全 部 的 通 用 寄 存 器, 结 果 再 次 令 人 大 跌 眼 镜 : 速 度 竟 然 比 没 有 展 开 时 还 要 慢 其 实 仔 细 观 察 这 个 程 序 和 前 面 第 二 次 优 化 程 序 的 汇 编 代 码, 不 难 发 现 第 二 次 优 化 由 于 是 编 译 器 生 成 代 码, 冗 余 的 小 操 作 很 多, 乱 序 执 行 有 非 常 大 的 优 化 空 间 但 是 到 了 这 个 程 序, 代 码 已 经 十 分 精 简, 在 每 次 循 环 体 第 一 句 mov 指 令 cache miss( 后 文 会 讲 解 ) 时, 后 面 并 没 有 指 令 可 以 提 前 来 执 行 所 以 优 化 的 这 点 时 间, 本 质 上 仅 仅 是 循 环 展 开 所 得 如 果 再 进 一 步 试 图 采 用 所 有 寄 存 器 参 与 来 进 行 4 路 求 值, 一 来 很 不 利 于 RAT 工 作, 另 一 方 面 过 多 的 条 件 跳 转 指 令 也 让 处 理 器 吃 不 消 我 们 再 一 次 看 到, 优 化 工 作 不 是 想 当 然 的, 如 果 不 充 分 了 解 处 理 器 的 特 性, 仅 仅 凭 想 象 来 做 优 化, 不 会 取 得 什 么 效 果, 甚 至 适 得 其 反 第 五 次 优 化 已 经 做 到 了 这 个 程 度, 考 察 程 序 各 处 似 乎 都 无 利 可 图 了, 优 化 再 次 陷 入 了 僵 局 要 想 再 取 得 优 化, 必 须 再 打 开 思 维 才 行 这 里 要 提 到 的, 是 所 谓 的 单 指 令 多 数 据 (SIMD) 的 方 法 第 9 页

10 什 么 是 SIMD? 让 我 们 回 归 程 序 优 化 的 本 原 : 优 化, 自 然 是 为 了 让 程 序 运 行 效 率 更 高, 而 程 序 运 行 时,%90 的 时 间 都 在 运 行 10% 的 代 码, 这 些 代 码 自 然 就 是 循 环 我 们 只 用 找 出 程 序 的 瓶 颈 部 分, 在 最 耗 时 的 循 环 中 取 得 微 弱 的 优 化, 也 胜 过 在 外 层 决 定 性 的 巨 大 优 化 而 这 些 循 环 是 在 做 什 么 呢, 许 多 时 候, 他 们 是 在 遍 历 并 处 理 大 块 的 数 据 处 理 器 厂 商 发 现 了 这 一 点, 开 发 了 SIMD 指 令 集 来 专 门 帮 助 更 高 效 地 处 理 大 量 数 据 我 们 刚 才 有 提 到, 不 应 该 使 用 过 于 复 杂 的 指 令, 用 经 过 充 分 优 化 的 更 适 应 流 水 线 的 简 单 指 令 对 程 序 运 行 效 率 更 有 益 处,SIMD 的 理 念 看 上 去 不 是 和 这 个 原 则 背 道 而 驰 么? 其 实 不 然, 打 个 比 方, 我 们 有 三 条 基 本 指 令, 洗 苹 果, 削 苹 果, 切 苹 果, 为 了 更 高 效 地 完 成 任 务, 我 们 把 他 整 合 成 一 条 复 杂 指 令 : 处 理 苹 果 这 对 更 高 效 地 完 成 任 务 有 帮 助 吗? 一 点 也 没 有, 因 为 接 受 命 令 者 首 先 要 先 回 忆, 处 理 苹 果 这 一 条 指 令 意 味 着 什 么, 然 后 再 按 部 就 班 地 进 行 洗 削 切 三 个 过 程, 不 但 执 行 任 务 的 时 间 没 有 减 少, 反 而 还 多 出 了 分 解 复 杂 命 令 的 过 程, 如 果 说 这 一 个 整 合 有 帮 助 的 话, 那 就 在 于 创 建 了 一 条 更 简 短 的 指 令 表 达 丰 富 的 含 义 使 用 那 些 单 指 令 多 任 务 的 复 杂 语 句, 就 好 比 上 面 一 个 过 程, 对 时 间 效 率 优 化 毫 无 益 处 但 是, 单 指 令 多 数 据 就 不 一 样 了, 再 设 想 一 下, 假 如 我 们 时 常 需 要 处 理 一 大 堆 苹 果, 我 们 可 以 创 建 一 个 叫 一 刀 切 两 个 苹 果 的 指 令, 那 么 在 切 的 阶 段, 必 然 就 能 更 高 效 地 完 成 任 务, 为 什 么 不 创 建 一 刀 切 100 个 苹 果 的 指 令 呢? 因 为 我 们 的 刀, 让 我 们 一 次 切 不 了 这 么 多 处 理 器 就 是 我 们 的 刀, 数 据 就 是 苹 果, 创 建 一 次 处 理 多 个 数 据 的 指 令, 可 以 减 少 发 号 施 令 所 用 的 时 间, 而 让 处 理 器 专 注 于 十 分 高 效 地 完 成 数 据 处 理 任 务 同 样, 处 理 器 处 理 数 据 的 能 力 也 是 有 限 的, 一 次 能 处 理 多 少 数 据, 受 制 于 处 理 器 内 部 寄 存 器 的 大 小 intel 在 Pentium MMX 处 理 器 中 发 布 了 MMX 指 令 集, 它 借 用 FPU 中 的 八 个 80 位 浮 点 寄 存 器, 一 次 只 能 同 时 处 理 8 字 节 数 据 在 Pentium 2 又 发 布 了 SSE 指 令 集, 加 入 8 个 独 立 的 128 位 寄 存 器, 此 后 又 发 布 了 SSE2,3,4, 不 断 加 入 新 的 SIMD 指 令, 使 程 序 员 可 以 极 其 高 效 地 完 成 打 包 整 数 浮 点 数 的 处 理, 在 科 学 计 算 信 号 处 理 3D 游 戏 中 都 有 着 广 泛 的 应 用, 而 AMD 也 一 直 紧 跟 intel 的 脚 步, 现 在 新 一 代 的 AMD 处 理 器 均 能 支 持 到 SSE3 指 令 集 下 面 我 们 就 来 尝 试 将 SIMD 用 在 这 个 程 序 的 优 化 中 : 第 10 页

11 // 第 五 次 优 化 int get_max(int* a,int l){ assert(l%4==0); assert(sse2); int ret,tmp[4]; asm volatile ( "\txorps %%xmm0, %%xmm0\n" "LP3:\n" "\tmovdqa %%xmm0, %%xmm1\n" "\tpcmpgtd (%1), %%xmm1\n" "\tandps %%xmm1, %%xmm0\n" "\tandnps (%1), %%xmm1\n" "\torps %%xmm1, %%xmm0\n" "\taddl $16, %1\n" "\tsubl $4, %2\n" "\tjnz LP3\n" "\tmovdqu %%xmm0, (%3)\n" "\tmovl (%3), %%eax\n" "\tcmpl 4(%3), %%eax\n" "\tcmovll 4(%3), %%eax\n" "\tcmpl 8(%3), %%eax\n" "\tcmovll 8(%3), %%eax\n" "\tcmpl 12(%3), %%eax\n" "\tcmovll 12(%3), %%eax\n" "\tmovl %%eax, %0\n" :"=m"(ret) :"r"(a),"r"(l),"r"(tmp) :"%eax"); return ret; 用 SSE 指 令 集 来 处 理 这 个 问 题 的 方 式 有 些 间 接, 大 体 思 路 仍 然 是 多 路 求 值, 不 过 这 次 的 这 四 路 局 部 最 大 值, 打 包 保 存 在 xmm0 寄 存 器 中 为 了 把 内 存 中 的 四 个 连 续 值 与 xmm0 取 较 大 值, 需 要 先 使 用 sse 比 较 指 令 获 得 一 个 掩 码, 再 通 过 位 运 算 进 行 结 合, 这 也 是 sse 处 理 数 据 的 常 见 方 式 值 得 注 意 的 是, 这 里 使 用 了 整 整 5 条 sse 指 令, 这 么 复 杂 的 过 程, 真 的 能 有 优 化 的 效 果 么? 运 行 程 序, 这 次 的 平 均 时 钟 周 期 为 , 还 真 有 一 定 的 优 化 效 果 看 来, 处 理 器 厂 商 确 实 也 在 simd 指 令 优 化 上 下 了 大 力 气 到 了 这 里, 我 们 的 程 序 仅 仅 需 要 最 初 版 程 序 1/5 的 时 间 了, 处 理 一 个 数 据 仅 仅 需 要 1.5 个 时 钟 周 期, 效 率 是 十 分 惊 人 的 第 六 次 优 化 优 化 就 到 此 为 止 了 吗? 当 然 没 有, 有 句 话 说 得 好 : 程 序 的 优 化 是 无 止 境 的 我 相 信 一 定 还 存 在 更 加 优 秀 的 方 式 解 决 这 个 问 题, 只 是 我 才 疏 学 浅, 暂 时 还 无 法 企 及 不 过 另 一 方 面, cpu 厂 商 同 时 也 在 不 断 地 努 力, 给 我 们 提 供 更 加 强 大 的 工 具 就 这 个 问 题, 在 intel 近 年 发 第 11 页

12 布 的 45 纳 米 Penryn 处 理 器 中, 支 持 了 SSE4 指 令 集, 其 中 有 一 条 pmaxsd 指 令, 可 直 接 取 代 前 面 的 位 运 算 步 骤, 那 么 可 以 写 出 这 样 一 个 程 序 : // 第 六 次 优 化 int get_max(int* a,int l){ assert(l%4==0); assert(sse4); int ret,tmp[4]; asm volatile ( "\txorps %%xmm0, %%xmm0\n" "LP4:\n" "\tpmaxsd (%1), %%xmm0\n" "\taddl $16, %1\n" "\tsubl $4, %2\n" "\tjnz LP4\n" "\tmovdqu %%xmm0, (%3)\n" "\tmovl (%3), %%eax\n" "\tcmpl 4(%3), %%eax\n" "\tcmovll 4(%3), %%eax\n" "\tcmpl 8(%3), %%eax\n" "\tcmovll 8(%3), %%eax\n" "\tcmpl 12(%3), %%eax\n" "\tcmovll 12(%3), %%eax\n" "\tmovl %%eax, %0\n" :"=m"(ret) :"r"(a),"r"(l),"r"(tmp) :"%eax"); return ret; 这 个 程 序 在 我 的 处 理 器 上 尚 无 法 运 行, 故 无 法 测 量 其 优 化 效 果, 不 过 我 估 计, 在 未 来 支 持 SSE4 的 处 理 器 上, 这 个 程 序 可 以 跑 到 处 理 每 个 数 据 一 个 时 钟 周 期 的 极 致 这 个 程 序 的 优 化 就 做 到 这 里 了, 确 实, 这 个 例 子 显 得 过 于 简 单 而 没 有 实 用 性, 但 它 所 折 射 出 来 的 一 些 思 想 和 方 法 是 共 通 的, 后 文 将 分 别 具 体 讨 论 各 种 方 法 与 技 巧, 它 们 将 为 我 们 的 优 化 实 战 提 供 详 细 的 参 考 关 于 各 CPU 指 令 的 运 行 效 率 在 后 文 的 内 容 中 我 们 时 常 要 与 CPU 指 令 打 交 道, 要 做 出 有 效 的 优 化, 对 这 些 指 令 的 效 率 有 基 本 的 了 解 是 前 提 因 此 在 开 始 之 前, 我 们 先 来 研 究 一 下 这 些 指 令 运 行 的 快 慢 在 CISC 架 构 处 理 器 上, 一 条 特 定 的 指 令 具 体 要 占 用 多 少 个 时 钟 周 期 是 很 难 有 一 个 确 切 的 答 案 的 因 为 这 条 指 令 不 是 独 立 存 在 于 此 的, 在 实 际 的 运 行 中, 它 的 微 指 令 可 能 会 被 打 散 并 和 其 它 指 令 并 发 执 行, 这 样 就 不 再 具 有 一 个 完 整 且 独 立 的 运 行 周 期 另 一 方 面, 指 令 本 第 12 页

13 身 和 指 令 所 使 用 的 数 据 是 否 cache, 是 否 对 齐, 对 效 率 也 有 着 致 命 的 影 响 总 的 来 说, 一 条 指 令 的 运 行 效 率, 和 代 码 中 的 上 下 文 环 境 有 着 密 不 可 分 的 联 系 这 当 然 不 是 说 我 们 就 不 需 要 关 心 各 种 指 令 的 快 慢 了, 例 如 一 条 除 法 指 令 无 论 在 什 么 情 况 下 也 是 会 比 一 条 加 法 指 令 要 慢 的, 对 指 令 集 中 各 条 指 令 的 效 率 有 个 大 致 的 了 解, 是 正 确 地 书 写 汇 编 代 码 的 基 础, 甚 至 对 于 编 写 高 级 语 言 代 码 也 很 有 好 处 诚 然 intel 官 方 的 开 发 手 册 上 有 提 供 各 条 指 令 平 均 占 用 时 钟 周 期 数 的 一 个 参 考 数 值, 不 过 我 还 是 更 喜 欢 在 自 己 的 平 台 上 进 行 实 际 测 量, 印 象 也 会 更 深 刻 一 些 我 的 测 量 方 式 是, 将 待 测 指 令 放 在 一 个 有 意 义 的 上 下 文 环 境 中, 在 指 令 的 两 测 各 插 入 一 条 cpuid 指 令 以 将 被 测 指 令 隔 离 开 来, 并 循 环 次, 测 量 消 耗 的 时 钟 周 期, 再 将 被 测 指 令 抽 去, 再 次 循 环 同 样 的 次 数 并 测 量, 两 者 相 减 并 除 以 循 环 次 数, 就 得 到 了 一 个 近 似 的 时 钟 周 期 数 当 然, 这 样 的 测 量 有 许 多 可 能 导 致 误 差 之 处, 不 过 没 有 关 系, 因 为 我 们 关 注 的 重 点 并 不 是 它 实 际 需 要 占 用 时 钟 周 期 数 的 绝 对 数 值, 这 个 数 值 在 不 同 的 cpu 上 是 有 差 异 的, 但 了 解 一 个 大 体 的 情 况 始 终 是 有 意 义 的 下 面 给 出 我 所 测 量 的 一 些 结 果, 它 们 将 会 在 后 文 的 论 证 中 被 引 用 指 令 名 称 操 作 数 类 型 平 均 时 钟 周 期 数 add r32/r32 1 shr imm8/r32 1 bsr r32/r32 1 mul r32 2 div r32 21 fadd r 3 fdiv r 35 fsqrt n/a 60 padd xmm/xmm 1 关 于 数 值 运 算 的 优 化 一. 除 法 在 现 代 cpu 中, 乘 法 指 令 的 速 度 基 本 已 经 被 优 化 到 足 够 快 了, 但 除 法 指 令, 由 于 其 逻 辑 的 过 于 复 杂, 一 直 以 来 都 需 要 消 耗 庞 大 数 目 的 时 钟 周 期, 比 其 它 简 单 指 令 要 慢 上 数 十 倍 从 前 文 中 所 做 的 测 量 就 可 以 看 出, 即 使 使 用 20 条 位 移 指 令, 如 果 能 取 代 一 条 除 法 指 令 的 话, 也 是 十 分 值 得 的 可 是 只 要 稍 加 思 考 就 会 想 到, 假 如 存 在 一 种 通 用 的 除 法 算 法, 其 效 率 能 够 比 CPU 内 部 硬 件 实 现 的 除 法 指 令 还 要 高 的 话,CPU 厂 商 一 定 会 使 用 这 种 算 法 来 重 写 除 法 电 路 也 就 是 说, 对 于 一 次 普 遍 性 的 除 法 任 务, 固 然 div 指 令 较 为 缓 慢, 但 是 也 没 有 什 么 可 优 化 的 余 地 从 逻 辑 上 讲 是 这 样, 事 实 也 就 是 这 样 消 除 除 法 当 然, 这 并 不 意 味 着 对 于 除 法 我 们 就 束 手 无 策 了 在 各 种 特 殊 的 场 合, 时 常 有 专 门 的 方 法 可 以 进 行 一 些 针 对 性 的 优 化 最 简 单 有 效 的 一 个 方 法 无 疑 就 是 : 避 免 使 用 除 法, 这 时 常 需 要 在 逻 辑 上 进 行 一 些 调 整, 例 如 最 简 单 的 一 句 条 件 判 断 语 句 : if(a/b<c), 我 们 可 以 将 其 转 换 为 if(a<b*c), 要 注 意 这 并 不 总 是 成 立, 要 考 虑 到 乘 法 可 能 溢 出 还 有 b 为 负 数 时 不 等 式 需 要 变 号 等 问 题 在 实 际 的 算 法 设 计 中, 有 时 也 有 机 会 进 行 一 些 类 似 的 变 换, 不 过 需 要 非 常 小 心 第 13 页

14 减 少 取 模 运 算 在 竞 赛 题 目 中, 我 们 时 常 需 要 解 决 这 样 的 问 题 : 要 求 对 某 种 对 象 进 行 计 数, 不 过 由 于 数 目 太 大, 仅 仅 需 要 我 们 给 出 最 后 答 案 mod M 的 值 即 可 在 这 类 问 题 的 算 法 设 计 中, 滥 用 %M 操 作 对 效 率 的 影 响 可 能 是 致 命 的, 而 取 模 操 作, 在 计 算 机 底 层 和 除 法 操 作 是 同 一 条 指 令 所 完 成, 速 度 极 其 缓 慢, 应 该 尽 可 能 消 除 这 个 工 作 有 时 只 是 举 手 之 劳, 例 如 对 于 一 个 可 能 为 负 的 整 数 a 进 行 取 模, 惯 常 的 写 法 是 (a%m+m)%m, 之 所 以 有 两 次 mod, 是 为 了 解 决 底 层 除 法 指 令 规 定 余 数 的 符 号 和 被 除 数 相 同 的 问 题, 但 是 第 二 次 mod 是 相 当 浪 费 的, 一 个 简 单 的 if 就 可 以 解 决 这 个 问 题 : inline int mod(int a){a%=m;if(a<0)a+=m;return a;; 又 比 如 说, 在 许 多 线 性 递 推 的 模 型 中, 将 其 抽 象 为 矩 阵 乘 积 的 形 式 可 以 高 效 地 解 决 在 求 矩 阵 乘 积 的 内 层 循 环 中, 频 繁 地 调 用 除 法 指 令 会 使 程 序 运 行 效 率 不 堪 忍 受 为 了 解 决 这 个 问 题, 可 以 在 计 算 结 果 中 某 个 元 素 的 值 时 先 不 进 行 取 模, 仅 仅 简 单 地 进 行 乘 法 和 累 加, 在 计 算 完 后 再 来 取 模 实 践 表 明, 此 方 法 可 以 极 大 的 提 高 程 序 的 运 行 效 率 减 少 浮 点 除 法 如 果 把 浮 点 数 也 加 入 进 来 考 虑, 那 优 化 的 方 法 就 更 加 灵 活 多 样 一 方 面 浮 点 数 的 各 种 运 算 之 间 的 速 度 差 距 更 为 悬 殊, 除 法 指 令 更 是 慢 到 难 以 忍 受 ; 而 另 一 方 面, 浮 点 数 模 拟 的 是 数 学 中 实 数 的 概 念, 运 算 规 律 为 我 们 所 熟 悉, 不 需 要 像 对 待 整 数 运 算 一 样 去 推 导 数 论 方 面 的 结 论 例 如, 在 浮 点 数 中, 我 们 可 以 认 为 a b 等 价 于 a (1 b), 而 在 整 数 运 算 中 是 不 行 的 相 比 在 整 数 领 域, 对 于 浮 点 我 们 可 以 更 加 不 遗 余 力 地 将 除 法 指 令 替 换 为 多 条 更 加 快 速 的 指 令 : 最 简 单 的 例 子 是, 如 果 需 要 多 次 进 行 除 以 b 的 操 作, 我 们 事 先 计 算 b 的 倒 数 再 来 进 行 乘 法 是 很 划 算 的 如 果 要 计 算 a b+c d, 我 们 可 以 先 通 分 变 为 (a d+c b) (b d) 再 进 行 计 算, 虽 然 多 了 3 次 乘 法, 但 是 消 除 了 一 次 除 法, 仍 然 是 值 得 的 对 此 我 进 行 了 实 际 的 测 量, 用 通 分 与 不 通 分 的 方 式 分 别 计 算 次, 在 我 的 机 器 上, 通 分 的 方 法, 整 整 快 了 一 倍 还 要 多 这 种 优 化 甚 至 可 以 扩 展 到 不 相 关 的 代 数 式 上, 例 如 我 们 需 要 计 算 : x=a/b; y=c/d; z=e/f; 我 们 可 以 写 为 : t=1/(b*d*f); x=a*d*f*t; y=c*b*f*t; z=e*b*d*t; 在 我 的 机 器 上, 第 二 段 代 码 占 用 的 时 间, 仅 仅 是 第 一 段 的 1/3! 至 此 我 们 已 经 能 够 看 出, 浮 点 数 乘 法 指 令 在 除 法 的 面 前, 几 乎 是 可 以 忽 略 不 计 的 其 实 不 仅 仅 是 乘 除 法, 浮 点 指 令 集 中 不 同 指 令 的 效 率 差 距 拉 得 很 开, 这 给 了 我 们 的 优 化 无 限 的 可 能 就 曾 经 有 人 自 己 实 现 了 一 个 非 常 高 效 的 基 于 牛 顿 迭 代 的 开 根 算 法, 比 FPU 内 部 硬 件 实 现 的 还 整 整 快 了 6 倍 不 过, 这 些 技 巧 更 像 是 某 种 智 力 游 戏, 就 不 再 在 这 里 展 开 讨 论 了, 我 们 只 需 要 对 各 种 浮 点 指 令 的 速 度 有 一 个 大 致 的 了 解, 在 编 码 时 再 即 兴 发 挥 即 可 不 过 凡 事 不 能 过 度, 如 果 需 要 使 用 过 多 的 简 单 指 令 来 取 代 复 杂 指 令, 不 但 效 率 是 否 能 有 优 化 值 得 商 榷, 还 会 显 著 地 导 致 代 码 易 错, 难 第 14 页

15 于 调 试 和 维 护, 在 精 度 方 面 的 损 失, 也 不 可 忽 略 特 殊 除 法 运 算 的 加 速 上 面 讨 论 的 技 巧, 主 要 的 思 想 都 是 通 过 避 开 除 法 或 者 减 少 除 法 指 令 的 数 量 来 进 行 优 化 那 当 我 们 必 须 直 面 一 条 除 法 指 令 时, 有 没 有 办 法 让 它 可 以 运 行 得 更 快 呢? 对 于 通 用 的 目 的, 可 以 说 是 没 有 但 我 们 程 序 中 对 除 法 的 使 用, 常 常 有 某 种 特 殊 性, 最 简 单 而 且 有 效 的 一 个 例 子 是 : 我 们 日 常 使 用 的 是 有 符 号 整 数, 但 是 在 进 行 除 法 时 操 作 数 常 常 可 以 保 证 都 是 非 负 的, 这 时 我 们 应 当 先 将 操 作 数 转 换 为 无 符 号 类 型 再 做 除 法 : a=(unsigned int)b/123; 无 符 号 类 型 的 除 法 比 有 符 号 类 型 进 行 得 更 快, 所 以 这 样 确 实 可 以 起 到 优 化 作 用 关 于 其 它 的 技 巧, 我 选 择 了 除 以 二 的 方 幂 除 以 常 数 商 值 较 小 这 三 种 情 况 进 行 研 究 需 要 说 明 的 是, 我 们 这 里 所 涉 及 的, 全 部 都 是 整 数 除 法 要 手 动 实 现 浮 点 除 法, 过 于 复 杂 也 没 有 多 少 提 升 空 间, 不 做 讨 论 除 以 二 的 方 幂 首 先 要 讲 的 是 除 以 二 的 方 幂, 这 个 技 巧 已 经 为 大 家 所 熟 知 : 除 以 2 的 k 次 方, 等 价 于 将 被 除 数 向 右 算 术 位 移 k 位 在 CTSC2008 的 totem 一 题 中, 要 求 我 们 将 答 案 对 取 模, 而 这 个 数 字, 恰 好 就 是 2 24, 所 以 在 计 算 过 程 中 我 们 可 以 照 常 计 算 任 其 溢 出, 而 不 会 影 响 到 数 字 末 24 个 bit 的 值, 这 样 会 比 使 用 了 取 模 运 算 的 程 序 快 很 多 倍, 这 一 点 也 会 部 分 影 响 到 题 目 最 后 的 得 分 怎 样 找 到 位 串 中 1 的 位 置 不 过 我 在 这 里 主 要 想 讨 论 的 问 题 是, 给 出 一 个 数 b, 且 已 知 b=2 k, 我 们 怎 样 最 快 地 得 到 那 个 k 值 既 然 b=2 k, 那 么 在 b 的 二 进 制 表 示 中, 一 定 是 有 且 只 有 一 个 1 的, 我 们 只 要 找 到 这 个 1 的 位 置, 就 得 到 了 k 线 性 地 位 扫 描 固 然 可 行, 但 是 速 度 无 法 忍 受, 使 用 对 数 函 数 虽 然 是 理 论 O(1), 但 显 然 不 切 实 际 还 有 一 种 容 易 想 到 的 方 法 是 将 b 进 行 截 断, 然 后 构 造 一 张 查 找 表, 从 高 到 低 对 每 段 判 断 是 否 为 0, 如 果 不 为 0 就 在 查 找 表 中 得 到 1 的 位 置 这 种 方 法 在 只 分 为 2 段 时 相 当 高 效, 可 是 需 要 一 张 64KB 的 查 找 表, 虽 然 在 今 天 的 计 算 机 中 64KB 可 以 忽 略 不 计, 但 此 方 法 终 归 不 够 优 美 我 首 先 给 出 我 所 想 到 的 在 C 语 言 下 最 好 的 方 法 : char tb[32]={31,0,27,1,28,18,23,2, 29,21,19,12,24,9,14,3, 30,26,17,22,20,11,8,13, 25,16,10,7,15,6,5,4; //x 需 要 为 unsigned int #define LOG(x) tb[((x)* )>>27] 一 看 便 知, 我 是 构 造 了 一 张 无 冲 突 无 浪 费 哈 希 表 来 做 查 询 它 是 怎 样 构 造 出 来 的 呢? 当 2 k 乘 以 一 个 数 时, 其 实 就 是 将 这 个 数 左 移 k 位, 利 用 这 一 点, 我 构 造 出 来 一 个 数 T, 使 得 对 T 分 别 左 位 移 0~31 位 时, 结 果 的 高 5 位 会 取 遍 0~31 的 所 有 数 相 信 说 到 这 里, 大 家 都 会 想 起 那 个 基 于 欧 拉 回 路 的 经 典 算 法, 这 里 不 再 赘 述 第 15 页

16 CPU 的 位 扫 描 指 令 但 是 前 面 所 说 的 这 些 方 法, 都 不 是 我 想 讲 的 重 点 换 个 角 度 思 考, 处 理 器 能 够 在 一 个 时 钟 周 期 内 完 成 add,mov 等 指 令, 这 些 指 令 都 需 要 访 问 全 部 的 32 个 bit, 按 理 来 说, 处 理 器 要 想 快 速 得 到 一 个 1 的 位 置, 是 非 常 容 易 的, 幸 运 地 是,IA-32 处 理 器 确 实 也 提 供 了 这 样 的 功 能, 被 称 为 位 扫 描 (bit scan), 位 扫 描 指 令 分 为 bsf(bit scan forward) 和 bsr(bit scan reversed), 前 者 从 最 低 位 向 最 高 位 进 行 扫 描 直 到 找 到 第 一 个 1 为 止, 而 后 者 相 反 有 了 bsr 指 令, 我 们 就 可 以 轻 松 快 速 地 完 成 刚 才 的 任 务 : inline unsigned int LOG2(unsigned int x){ unsigned int ret; asm volatile ("bsrl %1, %%eax":"=a"(ret):"m"(x)); return ret; 无 疑 LOG2 可 以 比 LOG 宏 更 快 速 的 运 行, 但 优 势 决 不 仅 仅 在 于 速 度 刚 才 的 那 个 LOG 宏 其 实 并 不 能 真 正 计 算 对 数, 而 只 能 处 理 x 为 2 k 的 情 况, 但 是 LOG2 就 不 同 了 由 于 使 用 了 bsr 指 令, 它 在 找 到 最 高 位 的 1 时 就 会 停 止, 所 以 其 返 回 值, 确 实 就 是 log2(x) 取 整 后 的 值 如 果 你 有 一 定 算 法 编 程 经 验, 马 上 就 会 发 现 这 个 函 数 是 多 么 的 有 用, 我 们 求 RMQ 所 用 的 ST 表 求 LCA 所 用 的 log 在 线 算 法 以 及 许 多 按 位 二 分 的 算 法, 都 需 要 使 用 这 样 一 个 功 能, 而 刚 才 实 现 的 LOG2 函 数, 速 度 达 到 极 致, 又 不 需 要 多 余 的 空 间 占 用, 堪 称 完 美 这 里 多 提 一 句 bsf 指 令, 这 条 指 令 和 bsr 相 反, 是 从 低 位 往 高 位 扫 描 找 第 一 个 1, 这 首 先 让 人 联 想 到 树 状 数 组 中 使 用 的 LOWBIT 函 数, 不 过 使 用 bsf 和 shl 实 现 LOWBIT, 并 不 见 得 会 比 x&-x 来 得 快 我 认 为 bsf 指 令 最 大 的 用 处 在 于, 可 以 用 来 得 到 一 个 二 进 制 数 末 尾 有 多 少 个 0, 并 且 一 次 性 除 去 这 些 0, 在 Miller Rubbin 二 进 制 gcd 等 算 法 中, 都 能 发 挥 极 大 的 作 用 编 译 器 对 除 以 常 数 的 优 化 接 下 来 讨 论 除 以 常 数 的 优 化, 在 浮 点 领 域, 要 计 算 除 以 常 数 b 的 商 是 很 容 易 的, 因 为 只 要 事 先 计 算 出 常 数 br=1 b, 那 么 除 以 b 就 是 乘 以 br 到 了 整 数 领 域, 此 方 法 显 然 就 不 再 适 用 了, 不 过 首 先 会 想 到 的 是, 能 不 能 采 用 类 似 的 方 法, 因 为 虽 然 在 整 数 域,1 b 的 值 并 不 存 在, 但 不 要 忘 记 一 件 事 : 计 算 机 中 的 数 域 并 不 是 真 正 的 整 数 域, 而 是 模 2 32 的 剩 余 系, 因 此, 看 起 来 我 们 只 需 找 到 一 个 数 t, 使 得 t b 1(mod 2 32 ) 就 可 以 了, 然 后 除 以 b 就 可 以 转 化 为 乘 以 t 了 真 的 是 这 样 吗? 首 先 一 点,t 并 不 一 定 是 找 得 到 的, 如 果 熟 悉 基 本 的 数 论 定 理, 容 易 推 出 当 b 为 奇 数 时, 一 定 找 得 到 这 个 t, 当 b 为 偶 数 时, 一 定 找 不 到, 证 明 很 简 单, 不 再 赘 述 于 是 就 能 想 到 一 个 改 进 方 法, 基 于 这 样 两 个 事 实 : 除 以 2 的 方 幂 可 以 用 位 运 算 快 速 进 行 ;a (b1 b2) =a b1 b2 第 一 个 结 论 前 文 已 经 说 过, 这 里 简 要 证 明 一 下 第 二 个 结 论 : a (b1 b2)=d d (b1 b2)+q=a (d,q 为 非 负 整 数,0 q<b1 b2) a b1=d1 d1 b1+q1=a (d1,q1 为 非 负 整 数,0 q1<b1) d1 b2=d2 d2 b2+q2=d1 (d2,q2 为 非 负 整 数,0 q2<b2) 联 立 三 式 (d2 b2+q2) b1+q1=d (b1 b2)+q d2 (b1 b2)+(q2 b1+q1)=d (b1 b2)+q 0 q2 b1+q1 (b2-1) b1+(b1-1)=b2 b1-1 第 16 页

17 0 q b2 b1-1 且 q (q2 b1+q1)(mod b1 b2) q=q2 b1+q1 d=d2 a (b1 b2)=a b1 b2 有 了 这 个 结 论, 我 们 就 可 以 把 b 分 为 两 部 分, 令 b=b1 b2, 且 b1=2 k,b2 为 奇 数, 则 计 算 a b 可 以 先 将 a 右 移 k 位 得 到 a b1=d1, 再 计 算 d1 b2, 由 于 此 时 b2 已 是 奇 数, 则 可 以 使 用 刚 才 的 算 法 问 题 就 这 样 解 决 了 吗? 其 实 这 个 算 法 中 有 个 漏 洞, 在 a b=c 的 时 候, 两 边 同 乘 以 t(t b 1(mod 2 32 )), 的 确 可 以 得 到 a=c t, 但 是 别 忘 了 我 们 常 常 需 要 计 算 的 是 带 余 除 法, 也 就 是 说 a b+q=c(0 q<b), 这 时 再 将 两 边 同 乘 t, 得 到 a+q t=c t,q 的 值 我 们 不 知 道, 也 没 有 办 法 绕 过 除 法 求 得, 也 就 没 法 得 到 a 的 值 了 但 无 论 如 何 我 们 已 经 得 到 了 一 个 可 以 在 b a 时 计 算 a b 的 快 速 常 数 除 法 了 现 在 我 们 主 要 的 困 难 在 于, 整 数 除 法 的 定 义 式 中 有 两 个 未 知 数 a( 商 ) 和 q( 余 数 ), 虽 然 我 们 只 想 要 知 道 商, 但 是 无 论 如 何 恒 等 变 形, 都 难 以 摆 脱 q 那 么 这 样 的 算 法 真 正 存 在 吗? 这 时 编 译 器 是 我 们 最 好 的 老 师, 我 使 用 gcc -O2 编 译 如 下 的 C 代 码 : #include<stdio.h> int main(){ unsigned int a; scanf("%u",&a); a/=7; printf("%u",a); return 0; 查 看 编 译 器 生 成 的 汇 编 代 码, 可 以 看 到 a/=7 一 句 被 如 此 编 译 : movl -8(%ebp), %ecx movl $ , %edx movl %ecx, %eax mull %edx subl %edx, %ecx shrl %ecx addl %ecx, %edx shrl $2, %edx movl %edx, -8(%ebp) -8(%ebp) 是 堆 栈 上 储 存 变 量 a 的 位 置 从 这 段 代 码 我 们 可 以 看 到, 编 译 器 确 实 仅 仅 使 用 了 add,sub,shr,mul 指 令 就 完 成 了 除 法 的 工 作, 那 么 它 是 怎 么 做 到 的 呢? 让 我 们 从 那 个 奇 怪 的 数 字 入 手, 这 个 数 字 是 什 么 呢? 受 我 们 前 一 个 方 法 的 启 发, 将 它 和 7 相 乘, 并 查 看 它 的 二 进 制 表 示 发 现 它 恰 好 是 令 t= , 我 们 将 它 乘 入 整 除 的 定 义 式 : a 7+q=c a 7 t+q t=c t a ( )+q t=c t c t=2 32 a+(3 a+q t) 第 17 页

18 两 边 同 时 加 上 2 32 c c t+2 32 c=2 32 a+2 32 (a 7+q)+(3 a+q t) c t+2 32 c=2 35 a+(2 32 q+3 a+q t) 令 C=c t+2 32 c,a=2 35 a,q=(2 32 q+3 a+q t) 我 们 假 设 a 和 q 均 取 可 能 得 到 的 最 大 值, 即 a=(2 32-1) 7= ,q=6 计 算 得 Q 的 最 大 值 为 , 其 二 进 制 表 示 只 有 35 位 而 A=2 35 a, 其 低 35 位 均 为 0,36 位 开 始 为 商 的 二 进 制 表 示 故 只 要 计 算 出 C, 将 其 右 移 35 位,Q 中 混 乱 且 无 法 预 测 的 结 果 全 部 会 被 屏 蔽 掉, 而 a 的 正 确 值 就 得 到 了 编 译 器 对 这 个 算 法 的 实 现 也 是 十 分 精 巧 的, 本 来 C 的 最 大 值 甚 至 会 超 过 64 位 整 数 ( 仅 超 出 一 位 ), 但 可 以 看 到 gcc 仅 用 几 条 简 单 的 32 位 指 令 就 完 成 了 任 务 其 中 有 一 个 小 技 巧 值 得 一 提, 例 如 我 们 想 计 算 a 和 b 的 平 均 数, 可 以 写 成 (a+b)/2, 但 是 a+b 如 果 超 出 了 当 前 可 容 纳 数 据 范 围, 进 位 会 被 舍 弃, 除 以 2 的 答 案 也 就 不 再 正 确 了, 正 确 的 写 法 是 (a-b)/2+b, 这 个 式 子 可 以 对 所 有 的 a,b 正 确 工 作 上 面 的 汇 编 代 码 中 就 使 用 了 这 个 技 巧 来 处 理 可 能 爆 掉 的 1 个 bit 总 结 一 下 这 个 算 法, 它 的 巧 妙 之 处 在 于 突 破 了 恒 等 变 形 的 枷 锁, 式 子 变 得 混 乱 无 关 紧 要, 最 后 都 会 被 一 起 丢 弃, 只 剩 下 我 们 想 要 的 东 西 上 面 展 示 的 这 一 种 方 法 是 编 译 器 使 用 的 几 种 方 法 中 最 为 复 杂 的 一 种, 编 译 器 会 根 据 常 数 的 性 质 来 选 择 不 同 的 算 法, 剩 下 几 种 情 况 都 更 加 简 单, 这 里 不 再 罗 列, 我 自 己 编 写 了 一 个 微 型 编 译 器, 可 以 将 a/=b(b 为 常 数 ) 编 译 为 优 化 后 的 指 令, 我 进 行 了 充 分 的 测 试, 对 于 所 有 输 入 我 的 程 序 均 能 与 gcc 产 生 一 致 的 结 果 除 常 数 的 优 化 是 如 此 有 用, 以 至 于 就 算 不 开 优 化 开 关,gcc 也 会 默 认 给 我 们 做 这 样 的 优 化, 那 学 习 它 的 原 理 有 何 用 处 呢? 其 实 它 可 以 扩 展 到 非 编 译 期 常 数 的 除 法, 意 思 是 说, 如 果 代 码 中 时 常 需 要 除 以 一 个 同 样 的 数 字, 但 这 个 数 字 是 在 编 译 期 无 法 确 定 的, 那 么 我 们 就 可 以 自 己 内 嵌 一 个 微 型 编 译 器, 将 优 化 后 的 代 码 编 译 为 机 器 码 存 在 内 存 中, 需 要 做 除 法 时 跳 转 过 去 执 行 即 可, 不 过 这 种 优 化 实 现 代 价 太 高, 远 远 超 出 了 竞 赛 的 适 用 范 围, 这 里 不 再 展 开 讨 论 了 用 减 法 取 代 除 法? 我 要 讲 的 第 三 点, 其 实 并 不 是 一 个 优 化 的 技 巧, 仅 仅 是 澄 清 一 个 误 会 我 在 ACM 选 手 的 代 码 中 看 到 过 一 个 gcd 程 序, 它 使 用 了 一 个 很 不 优 美 的 方 式 : 首 先 手 动 从 a 中 减 去 b 数 次, 如 果 已 经 成 功 取 模 就 可 以 直 接 递 归, 否 则 才 调 用 除 法 指 令 我 刚 看 到 时 也 深 以 为 然, 因 为 每 次 递 归 后 的 b 实 际 上 是 模 a 的 余 数, 将 其 看 成 是 均 匀 分 布 的 话,a b 的 期 望 值 应 该 非 常 小, 用 几 次 减 法 来 取 代 它, 想 来 应 该 会 非 常 高 效 可 是 我 自 己 实 现 了 代 码 进 行 测 量, 速 度 反 而 变 慢 了 一 倍, 我 继 续 采 用 更 加 强 力 的 汇 编 优 化, 把 简 单 的 连 续 减 法 也 换 成 了 模 拟 的 除 法, 效 率 仍 然 超 不 过 最 朴 素 的 实 现 经 过 了 很 多 的 实 验, 终 于 发 现 问 题 出 在 除 法 指 令 上 :CPU 的 除 法 指 令 效 率 并 不 稳 定, 在 a 和 b 非 常 接 近 时, 速 度 也 是 可 以 达 到 非 常 快 的 而 手 工 的 模 拟, 会 导 致 一 大 堆 的 条 件 跳 转, 使 CPU 不 能 顺 畅 地 执 行 代 码 这 个 例 子 再 一 次 告 诉 我 们 : 优 化 决 不 是 想 当 然 的, 不 成 熟 的 优 化 是 效 率 低 下 的 根 源, 只 有 具 备 丰 富 的 经 验, 扎 实 的 基 础 知 识, 实 证 的 精 神, 才 能 做 出 真 正 精 巧 的 优 化 二. 乘 法 相 比 除 法, 乘 法 的 可 研 究 之 处 就 少 了 许 多, 从 前 面 的 指 令 时 钟 周 期 表 中 我 们 可 以 看 出, 现 代 cpu 上 的 乘 法 指 令 已 经 足 够 快 速 了, 所 以 一 些 老 式 的 优 化 也 已 经 过 时 了 : 例 如 将 a 10 写 为 (a<<3)+(a<<1), 这 条 语 句 包 含 了 2 条 位 移 指 令 和 一 条 加 法 指 令, 还 隐 藏 有 一 些 不 可 避 第 18 页

19 免 的 mov 指 令, 其 速 度 已 经 比 不 上 直 接 让 cpu 做 乘 法 了 用 lea 指 令 优 化 常 数 乘 法 但 另 一 方 面,(a<<3)+(a<<1) 其 实 并 不 是 最 好 的 优 化, 让 我 们 来 看 看 gcc 是 怎 么 做 的 吧 : lea 指 令 本 身 是 一 条 用 来 寻 址 的 指 令, 不 过 被 编 程 人 员 广 泛 使 用 于 计 算 工 作, 其 格 式 是 lea offset(reg1,reg2,c),dest, 作 用 是 将 寄 存 器 reg1 中 的 值 加 上 寄 存 器 reg2 中 的 值 乘 以 c 的 乘 积, 再 加 上 常 量 偏 移 offset, 将 最 终 得 到 的 结 果 存 到 dest 中 c 是 一 个 常 数, 取 值 只 能 为 1,2,4,8 那 么 lea (%eax,%eax,4),%eax 的 意 义 就 是 :eax=eax+eax*4, 即 eax*=5 在 第 一 条 指 令 将 eax 乘 以 了 5 之 后, 再 自 加 一 次 得 到 eax*10, 这 样 简 单 的 两 条 指 令, 又 确 实 可 以 比 乘 法 跑 得 更 快 了 不 过 显 然 并 不 是 对 所 有 的 常 数 都 有 如 此 简 单 的 优 化 方 式, 当 我 输 入 a*14,gcc 就 只 好 老 老 实 实 地 调 用 imul 指 令 了 所 以 说 在 乘 以 常 数 这 个 方 面, 基 本 上 是 没 有 多 大 的 优 化 余 地 的, 除 非 是 乘 以 二 的 方 幂, 这 里 我 们 都 很 熟 悉 了 : 乘 以 2 k 等 价 于 将 被 乘 数 左 位 移 k 位 还 有 一 些 乘 数 很 小 的 情 况, 也 有 一 些 巧 妙 的 优 化, 这 里 展 示 几 段 gcc 编 译 出 的 代 码 : lea (%eax,%eax,4),%eax add %eax,%eax 乘 以 2: addl %eax,%eax 乘 以 9: leal (%eax,%eax,8),%eax 乘 以 13:leal (%eax,%eax,2),%edx leal (%eax,%edx,4),%edx 乘 以 17:movl %eax,%edx sall 4,%edx addl %edx,%eax 乘 以 68:movl %eax,%edx sall 6,%edx leal (%edx,%eax,4),%eax 优 化 mul_mod 函 数 关 于 乘 法 有 一 个 容 易 被 忽 略 的 事 实 是,mul 指 令 其 实 是 不 会 爆 掉 的, 它 将 两 个 32bit 整 数 相 乘, 结 果 保 存 为 一 个 64bit 整 数, 可 惜 高 级 语 言 隐 藏 了 这 一 事 实, 也 给 我 们 造 成 了 一 些 不 必 要 的 麻 烦, 我 们 竞 赛 中 最 常 遇 到 的 是, 题 目 要 求 我 们 将 答 案 对 某 个 常 数 取 模, 那 么 我 们 就 可 以 在 中 间 过 程 中 随 时 只 保 留 取 模 后 的 结 果, 但 在 计 算 的 中 间 过 程, 可 能 会 因 为 乘 法 而 溢 出, 无 法 得 到 正 确 的 答 案, 在 C 语 言 层 面 我 们 的 解 决 方 式 是, 利 用 编 译 器 提 供 的 扩 展 64 位 整 数 来 储 存 中 间 结 果, 就 像 这 样 : inline int mul_mod_slow(int a,int b){ return (long long)a*b%mo; 这 样 在 速 度 上 会 比 较 慢, 最 快 速 且 优 美 的 解 决 方 式 其 实 处 理 器 已 经 为 我 们 提 供 了 :mul 指 令 将 结 果 储 存 在 edx:eax 这 个 64 位 整 数 中, 而 div 指 令 同 样 从 edx:eax 中 获 取 被 除 数, 这 样 我 们 的 汇 编 代 码 将 会 非 常 简 便 : 第 19 页

20 #define MO inline int mul_mod(int a,int b){ int ret; asm volatile ("\tmull %%ebx\n\tdivl %%ecx\n" :"=d"(ret):"a"(a),"b"(b),"c"(mo)); return ret; 这 个 函 数 是 简 洁 而 且 高 效 的, 在 我 的 机 器 上,mul_mod 函 数 比 mul_mod_slow 函 数 快 了 一 倍 还 要 多 既 然 说 到 了 这 里, 就 再 顺 便 提 及 一 个 技 巧, 它 用 来 解 决 这 样 一 个 问 题, 如 果 要 求 我 们 模 的 常 数 是 一 个 64bit 整 数, 那 在 做 乘 法 时 就 没 有 扩 展 类 型 给 我 们 使 用 了, 这 时 看 上 去 必 须 要 我 们 手 动 编 写 高 精 度 整 数 运 算 的 代 码 了 幸 运 的 是, 有 一 个 巧 妙 的 方 法 可 以 简 单 解 决 这 个 问 题 : typedef long long ll; #define MOL LL inline ll mul_mod_ll(ll a,ll b){ ll d=(ll)floor(a*(double)b/mol+0.5); ll ret=a*b-d*mol; if(ret<0)ret+=mol; return ret; 首 先 它 使 用 浮 点 运 算 来 得 到 a*b/mol 的 值, 关 键 在 于 第 二 句, 显 然 a*b-d*mol 中 的 两 个 乘 法 都 是 可 能 会 溢 出 的, 不 过 没 关 系, 因 为 我 们 可 以 预 见 其 差 是 一 个 64bit 可 容 纳 的 正 整 数, 那 么 溢 出 部 分 的 差 仅 可 能 为 0 或 者 1, 最 后 一 句 符 号 的 特 判 用 来 处 理 溢 出 部 分 差 为 1 的 情 况 容 易 注 意 到, 我 们 计 算 a*b/mol 时 使 用 了 浮 点 运 算, 误 差 是 不 可 避 免 的, 故 建 议 不 要 对 太 大 的 MOL 使 用 这 个 算 法 ( 感 谢 crazyb0y 无 私 地 给 我 提 供 这 个 技 巧 ) 三. 高 精 度 运 算 在 我 看 来, 编 写 大 整 数 运 算 的 代 码 本 来 就 应 该 是 属 于 汇 编 语 言 的 工 作, 在 IA-32 指 令 集 中, 有 一 大 套 的 指 令 几 乎 就 是 为 了 大 整 数 运 算 而 存 在 的 在 汇 编 语 言 层 次, 我 们 可 以 采 用 2 32 进 制 来 存 储 整 数, 以 获 得 最 高 的 运 算 效 率 和 指 令 支 持, 其 速 度 是 非 常 惊 人 的 我 用 内 嵌 汇 编 实 现 了 这 样 一 套 函 数 库, 在 我 的 机 器 上, 它 比 我 们 传 统 使 用 的 方 法 要 快 上 数 倍 在 附 件 中 的 bigint.c 文 件 中 可 以 找 到 这 个 实 现 CPU 优 化 特 性 CPU 是 计 算 机 的 心 脏, 我 们 的 程 序 代 码 就 会 在 这 里 被 执 行, 所 以 要 研 究 优 化, 深 入 到 CPU 的 内 部 是 很 有 意 义 的 CPU 执 行 效 率 主 频 可 能 有 的 人 会 粗 浅 地 认 为,CPU 执 行 程 序 的 速 度, 主 要 是 由 CPU 的 主 频 所 决 定 的,CPU 第 20 页

21 的 主 频 代 表 CPU 在 一 秒 钟 内 可 以 运 行 多 少 个 时 钟 周 期 (clock cycles) 这 在 十 多 年 前 可 能 还 是 相 当 正 确 的, 那 时 CPU 的 主 频 提 升 很 快, 基 本 符 合 摩 尔 定 律 所 预 计 的, 十 多 个 月 就 能 够 提 升 一 倍, 所 以 可 以 寄 希 望 于 CPU 主 频 地 不 断 翻 倍 来 提 升 我 们 电 脑 的 性 能 但 是 近 几 年, 受 制 造 工 艺 和 功 耗 的 限 制,CPU 的 主 频 已 经 不 再 能 够 提 升 了, 那 么, 就 是 说 CPU 的 性 能 也 不 再 提 升 了 吗? 当 然 不 是, 想 想 8088 的 时 代, 那 时 执 行 一 条 简 单 的 16-bit 整 数 乘 法 指 令, 都 要 消 耗 掉 上 百 个 时 钟 周 期, 而 现 在 呢, 平 均 只 需 要 使 用 1~2 个 周 期 就 够 了, 之 所 以 能 有 这 样 的 飞 跃, 是 因 为 现 代 CPU 不 再 局 限 于 将 一 条 条 指 令 简 单 地 执 行, 而 引 入 了 许 多 复 杂 的 优 化 机 制 例 如 Intel Pentium 4 处 理 器 中 采 用 了 名 为 NetBurst 的 控 制 单 元 技 术, 它 内 部 集 合 了 各 种 高 效 的 优 化 策 略, 例 如 指 令 预 取 分 支 预 测 乱 序 执 行 等 等, 使 我 们 的 代 码 可 以 更 加 快 速 地 执 行 但 有 一 个 现 实 是, 特 定 的 优 化 技 术 对 不 同 形 式 的 代 码 的 优 化 效 果 是 不 同 的, 也 就 是 说, 我 们 想 实 现 同 样 一 个 功 能, 一 些 实 现 上 的 细 微 差 别, 可 能 在 底 层 会 影 响 到 cpu 的 优 化, 效 率 也 会 天 差 地 别 所 以, 如 果 我 们 能 够 对 CPU 所 使 用 的 优 化 技 术 有 所 了 解, 就 可 以 有 意 识 地 在 编 码 时 去 配 合 CPU 工 作, 而 达 到 更 高 的 效 率 接 下 来, 我 们 就 一 个 一 个 地 来 看 看 CPU 内 部 的 优 化 机 制, 它 是 什 么, 怎 么 工 作, 怎 样 去 配 合 它 注 : 这 一 部 分 本 来 理 应 完 全 在 汇 编 语 言 层 面 进 行 研 究, 可 以 讲 述 的 规 则 与 技 巧 也 太 多, 但 出 于 更 贴 合 我 们 竞 赛 的 一 些 考 虑, 我 大 量 删 减 了 这 一 部 分 的 篇 幅, 只 留 下 了 一 些 在 高 级 语 言 层 面 也 有 意 义 的 内 容 一.CPU 高 速 缓 存 机 制 内 存 的 访 问 是 缓 慢 的 我 们 使 用 高 级 语 言 编 写 程 序, 变 量 (variable) 是 一 个 非 常 重 要 且 常 用 的 概 念, 我 们 整 个 程 序 中 都 使 用 变 量 来 存 储 数 据, 保 存 程 序 运 行 状 态, 传 递 参 数, 在 汇 编 语 言 中 的 核 心 概 念 寄 存 器 到 了 高 级 语 言 中 已 经 被 隐 藏 掉 但 有 一 个 事 实 是, 变 量 是 储 存 在 内 存 中 的, 而 内 存 的 访 问 速 度 是 远 远 跟 不 上 CPU 的 运 行 速 度 的, 在 CPU 需 要 访 问 内 存 时, 它 需 要 停 下 来, 将 请 求 通 过 控 制 总 线 和 地 址 总 线 发 送 给 内 存, 然 后 等 待 着 内 存 把 数 据 准 备 好, 再 去 提 取 数 据 这 个 过 程 是 相 当 漫 长 的, 需 要 占 用 几 十 上 百 个 时 钟 周 期, 严 重 影 响 了 CPU 整 体 的 执 行 效 率, 现 代 CPU 从 两 个 角 度 来 解 决 了 这 个 问 题, 其 一 是 让 CPU 在 等 待 内 存 准 备 数 据 时 可 以 抽 身 去 做 后 面 的 事 情, 其 二 是 使 用 缓 存 (cache) 的 思 路 第 一 点 在 后 面 乱 序 执 行 部 分 会 讲 到, 现 在 我 们 来 研 究 CPU 的 缓 存 机 制 高 速 缓 存 的 工 作 原 理 缓 存 基 于 这 样 一 个 事 实, 我 们 的 程 序 总 是 倾 向 于 执 行 相 临 近 的 指 令 码, 并 使 用 相 临 近 的 内 存 数 据, 一 个 内 存 位 置 在 访 问 后 有 很 高 的 几 率 会 在 短 时 间 内 被 再 次 被 访 问 于 是 CPU 在 内 部 加 入 了 多 级 高 速 缓 存, 级 别 越 高, 离 CPU 越 近, 访 问 速 度 越 快, 但 相 应 的 造 价 也 越 高, 容 量 也 越 小 例 如 在 我 的 电 脑 上 有 两 级 缓 存, 一 级 缓 存 大 小 为 64KB, 二 级 为 2MB,CPU 访 问 一 级 缓 存 的 速 度 几 乎 可 以 看 作 是 在 访 问 寄 存 器 CPU 缓 存 具 体 是 怎 样 工 作 的 呢, 首 先, 当 一 个 变 量 需 要 被 加 载 到 缓 存 中 时, 并 非 简 单 地 将 这 个 单 一 的 内 存 位 置 加 载, 而 是 一 次 性 加 载 一 行, 在 我 电 脑 上 一 行 为 64 字 节, 也 就 是 说 地 址 的 低 6 位 不 同, 而 高 位 相 同 的 这 一 段 连 续 的 内 存 位 置 会 被 一 次 性 加 载 进 来 我 的 1 级 缓 存 大 小 为 64KB, 算 下 来 一 共 可 以 加 载 1024 个 不 同 的 行, 但 一 个 特 定 的 内 存 位 置 并 不 能 随 意 加 载 到 其 中 任 意 一 行, 而 只 能 加 载 到 它 所 在 的 组 (set) 中, 每 个 组 有 8 个 行, 那 么 就 有 =128 个 不 同 的 组,128=2 7, 于 是 就 通 过 地 址 的 6~12 位 来 决 定 当 前 行 该 加 载 到 哪 一 个 组 第 21 页

22 中, 如 果 当 前 组 中 已 经 加 载 满 了 8 个 行, 显 然 就 只 有 将 其 中 一 行 从 缓 存 中 删 除, 下 次 再 访 问 到 此 行 就 需 要 重 新 加 载 了 当 需 要 访 问 某 一 个 内 存 位 置 时,CPU 会 首 先 检 查 它 是 否 被 加 载 到 缓 存 中, 如 果 已 经 加 载, 就 直 接 在 缓 存 中 读 写 之, 这 称 之 为 缓 存 命 中 (hit), 仅 仅 需 要 相 当 少 的 延 迟 时 间 但 是 如 果 没 有 的 话, 就 需 要 重 新 从 内 存 中 进 行 加 载, 称 之 为 cache miss, 这 个 代 价 是 十 分 巨 大 的, 我 们 写 程 序 时 需 要 尽 可 能 地 去 避 免 它, 这 也 是 我 们 需 要 了 解 高 速 缓 存 工 作 机 制 的 原 因 实 验 观 察 高 速 缓 存 的 存 在 性 为 了 可 以 直 观 地 看 到 高 速 缓 存 的 存 在, 我 们 先 来 看 如 下 一 个 程 序 int sum=0; for(i=0;i<n;i++)sum+=a[i]; 这 个 程 序 简 单 地 将 a 数 组 的 所 有 元 素 求 和, 为 了 更 加 明 显 地 看 出 效 果, 这 里 使 用 了 -O2 进 行 编 译 N 的 值 为 , 运 行 十 次 并 测 量 其 占 用 的 时 钟 周 期 数, 以 下 是 测 量 结 果 TIME0: TIME1: TIME2: TIME3: TIME4: TIME5: TIME6: TIME7: TIME8: TIME9: 可 以 很 明 显 的 看 出, 第 一 次 求 和 占 用 的 时 间 是 后 面 的 十 倍 左 右 这 主 要 是 因 为 a 数 组 是 没 有 经 过 初 始 化 的, 所 以 整 个 都 不 在 缓 存 中, 使 得 第 一 次 遍 历 需 要 极 大 的 代 价, 所 以 说, 缓 存 是 切 实 存 在 而 且 不 可 忽 视 的 怎 样 使 高 速 缓 存 更 好 地 工 作 那 么, 我 们 该 怎 样 编 写 代 码 来 配 合 CPU 缓 存 的 工 作 呢? 站 在 高 级 语 言 的 层 面, 我 们 主 要 从 不 同 的 变 量 类 型 的 角 度 来 看 尽 量 使 用 局 部 变 量 最 重 要 且 有 用 的 一 点 就 是 : 尽 量 使 用 局 部 变 量 局 部 变 量 所 处 的 位 置 是 程 序 的 运 行 时 堆 栈, 这 里 的 数 据 访 问 非 常 频 繁, 且 数 据 很 集 中, 在 大 部 分 时 候, 堆 栈 顶 部 的 数 据 都 会 处 于 CPU 的 一 级 缓 存 中, 访 问 速 度 非 常 快 而 相 对 的, 全 局 变 量 需 要 使 用 一 个 32 位 的 地 址 来 进 行 寻 址, 使 得 指 令 码 非 常 长, 不 利 于 CPU 的 各 种 机 制 的 工 作, 而 且 缓 存 命 中 率 也 远 远 不 如 局 部 变 量 来 得 要 高 使 用 结 构 体 组 织 相 关 联 的 数 据 另 一 方 面, 尽 量 使 用 结 构 体 来 组 织 相 关 联 的 数 据, 例 如 : int x[maxn],y[maxn]; 第 22 页

23 在 普 遍 情 况 下 就 不 如 使 用 struct 的 效 率 来 得 高 : struct point{int x,y;; point p[maxn]; 道 理 也 很 简 单, 因 为 x 和 y 是 相 关 联 的 数 据, 所 以 可 以 期 望, 当 访 问 到 x 时, 我 们 一 般 马 上 还 会 同 时 用 到 y, 如 果 把 他 们 放 在 一 个 struct 中, 任 意 一 个 元 素 被 访 问 时, 整 个 结 构 都 会 进 入 缓 存, 速 度 会 很 快 数 据 的 对 齐 说 到 这 里, 很 容 易 发 现 数 据 对 齐 也 是 很 重 要 的, 假 设 我 们 的 point 数 据 类 型 在 内 存 中 的 放 置 跨 越 了 缓 存 行 的 边 界, 每 次 访 问 都 需 要 加 载 两 个 缓 存 行, 效 率 之 低 下 是 可 想 而 知 的 数 据 对 齐 的 一 般 原 则 是, 普 通 变 量 应 该 按 照 它 自 身 的 大 小 对 齐, 较 大 的 struct 应 该 按 照 一 个 2 的 方 幂 的 边 界 对 齐 C 语 言 标 准 中 并 没 有 提 供 对 于 对 齐 的 支 持, 但 是 各 个 编 译 器 都 有 提 供 自 己 的 语 法, 在 我 们 竞 赛 使 用 的 gcc 中, 要 求 编 译 器 辅 助 对 齐 的 格 式 是 : int array[1024] attribute ((aligned(64))); 联 合 数 据 类 型 C 语 言 中 还 有 提 供 一 种 叫 做 联 合 (union) 的 数 据 类 型, 往 往 被 人 们 所 忽 视 了, 其 实 它 也 有 一 定 的 实 用 价 值 union{ A a; B b; ; 在 上 述 代 码 中,a 和 b 是 不 同 的 数 据 类 型, 但 是 由 于 使 用 它 们 的 代 码 不 会 同 时 使 用 两 者, 所 以 可 以 让 他 们 的 内 存 位 置 相 重 叠 这 样 做 不 单 单 是 可 以 节 约 一 点 内 存, 而 且 使 用 完 a 再 来 使 用 b 时, 由 于 a b 的 内 存 位 置 相 同, 所 以 b 会 也 存 在 于 高 速 缓 存 中, 从 而 获 得 较 高 的 访 问 效 率 避 免 动 态 内 存 分 配 最 后 一 点, 动 态 内 存 分 配 是 应 该 尽 量 避 免 的, 虽 然 它 有 众 多 的 好 处, 但 是 不 可 回 避 的 是 其 极 低 的 效 率, 分 配 和 释 放 时 系 统 会 遍 历 一 个 内 存 块 链 表 进 行 查 找, 而 且 其 分 配 出 来 的 内 存 块 可 能 会 相 当 零 散, 不 利 于 CPU 缓 存 的 工 作, 如 果 在 程 序 中 大 量 使 用 动 态 内 存 分 配 来 分 配 和 释 放 小 型 对 象, 分 配 内 存 本 身 很 有 可 能 成 为 效 率 瓶 颈 但 在 竞 赛 中, 我 们 也 时 常 需 要 实 现 各 种 动 态 数 据 结 构 ( 例 如 二 叉 平 衡 树 ), 较 好 的 解 决 方 法 是 先 开 一 个 足 够 大 的 内 存 池, 以 后 需 要 分 配 节 点 就 手 动 从 内 存 池 中 取 出 另 外, 结 合 前 面 所 讲, 在 实 现 这 些 动 态 数 据 结 构 时, 使 用 struct 来 表 示 一 个 节 点 也 比 使 用 各 个 分 离 的 数 组 要 来 得 高 效 一 些 例 外 凡 事 并 非 绝 对, 我 们 在 编 写 程 序 时 还 时 常 需 要 开 一 些 尺 寸 很 大 的 数 组, 这 些 数 组 也 应 该 开 在 堆 栈 上 ( 局 部 变 量 ) 么? 当 然 不 是, 如 果 开 在 堆 栈 上, 不 但 很 容 易 造 成 堆 栈 空 间 溢 出, 而 且 如 果 堆 栈 指 针 esp 常 常 很 大 地 变 动, 会 使 得 堆 栈 顶 部 的 数 据 常 在 高 速 缓 存 中 这 一 优 势 荡 然 无 存, 对 效 率 有 害 无 益 另 外,gcc 支 持 运 行 时 提 供 局 部 数 组 尺 寸 的 功 能, 看 起 来 很 实 用, 第 23 页

24 但 实 际 上 完 全 不 建 议 使 用, 不 但 具 有 前 面 所 述 的 所 有 缺 点, 而 且 使 得 最 朴 素 的 堆 栈 操 作 也 变 得 很 复 杂, 效 率 会 大 大 受 到 影 响 代 码 缓 存 以 上 提 到 的 都 是 CPU 的 数 据 缓 存, 其 优 化 的 是 程 序 代 码 访 问 内 存 数 据 的 效 率, 不 过 不 要 忘 记 了, 程 序 代 码 本 身 也 是 存 储 在 内 存 中 的, 由 eip 指 针 所 指 涉, 每 当 需 要 执 行 一 条 指 令 时,CPU 会 取 出 eip 所 指 向 的 指 令, 解 码 并 执 行, 按 理 来 说, 这 里 访 问 内 存 的 频 率 比 代 码 本 身 访 问 数 据 的 频 率 还 要 高, 自 然 也 是 CPU 优 化 的 要 点, 而 优 化 的 方 式, 同 样 也 是 使 用 高 速 缓 存 CPU 的 代 码 缓 存 和 数 据 缓 存 工 作 方 式 基 本 一 致, 这 里 只 简 单 来 看 看 在 高 级 语 言 层 面 怎 样 去 配 合 代 码 缓 存 工 作 相 邻 放 置 相 关 代 码 第 一 个 原 则 是, 将 功 能 上 有 关 联 的 函 数 在 源 代 码 中 的 位 置 放 得 尽 量 地 近, 例 如 一 个 函 数 f 中 要 调 用 函 数 g, 就 可 以 将 f 的 源 代 码 和 g 的 源 代 码 相 邻 放 置, 这 样 在 第 一 次 执 行 f 函 数 时, 就 有 机 会 将 g 的 代 码 一 起 加 载 到 缓 存 中 类 似 地, 在 整 个 程 序 中 可 以 将 调 用 频 率 最 高 的 一 些 函 数 相 邻 放 置, 这 样 它 们 就 有 机 会 随 时 保 持 在 代 码 缓 存 中, 而 那 些 很 少 调 用 的 函 数, 可 以 放 得 远 一 点, 它 们 被 加 载 到 缓 存 中 只 是 浪 费 空 间 减 小 循 环 体 尺 寸 毫 无 疑 问, 程 序 中 的 时 间 瓶 颈 所 在 一 般 都 在 一 个 循 环 中, 但 要 注 意, 真 正 占 用 时 间 的 一 般 是 循 环 体, 而 不 是 循 环 语 句 本 身 循 环 体 需 要 被 反 复 地 执 行, 第 一 次 进 入 循 环 体 时, 循 环 体 代 码 不 可 避 免 地 会 被 从 内 存 加 载 到 代 码 缓 存 中, 但 是 到 第 二 次 进 入 循 环 体 时, 我 们 期 望 这 时 循 环 体 的 代 码 仍 然 在 代 码 缓 存 中, 如 果 每 次 循 环 都 需 要 重 新 从 内 存 中 加 载 代 码, 效 率 将 会 受 到 影 响 为 了 避 免 这 种 不 利 情 形 的 发 生, 保 持 循 环 体 内 容 尽 量 简 介 很 有 帮 助 例 如 有 如 下 的 代 码 : for(int i=0;i< ;i++){ proc1(); proc2(); 如 果 proc1 和 proc2 干 的 事 情 毫 无 关 联, 同 样 可 以 写 成 这 样 : for(int i=0;i< ;i++)proc1(); for(int i=0;i< ;i++)proc2(); 那 么 哪 个 更 加 高 效 呢? 直 观 地 看 来, 第 二 段 代 码 比 第 一 段 干 了 更 多 的 事 情 : 计 数 器 变 量 i 的 比 较 和 累 加 需 要 进 行 两 次, 浪 费 了 时 间, 确 实, 如 果 proc1 和 proc2 都 非 常 的 简 单, 都 只 有 很 少 的 几 条 指 令, 第 一 段 代 码 或 许 会 更 有 效 率 但 是, 如 果 proc1 和 proc2 都 是 很 复 杂 的 过 程, 那 么 循 环 语 句 本 身 所 占 用 的 时 间 几 乎 可 以 忽 略 不 计, 另 一 方 面, 在 单 个 循 环 体 中 运 行 的 代 码 更 短 了, 一 来 代 码 本 身 有 更 大 的 可 能 全 部 存 在 于 高 速 缓 存 中, 更 重 要 的 是, 这 段 代 码 所 访 问 的 数 据 也 会 更 多 地 保 存 在 一 级 缓 存 中, 还 有 即 将 要 提 到 的 分 支 预 测 引 擎, 也 会 更 好 的 工 作 总 结 起 来, 对 于 CPU 缓 存 类 型 的 优 化, 我 们 编 写 代 码 的 大 体 原 则 就 是 : 本 来 就 有 关 联 的 东 西 ( 变 量 代 码 ), 尽 量 在 代 码 组 织 上 让 它 们 紧 密 地 联 系 起 来 本 来 毫 无 关 联 的 东 西, 第 24 页

25 就 应 该 把 它 们 相 分 隔 开 这 不 单 单 是 可 以 让 我 们 的 代 码 更 加 有 效 率, 同 样 也 是 编 写 更 优 美 的 代 码 的 基 本 原 则 二. 分 支 预 测 仅 仅 简 单 地 顺 序 执 行 一 条 一 条 的 指 令 并 不 能 满 足 程 序 设 计 的 需 要, 为 了 描 述 程 序 的 逻 辑, 我 们 至 少 需 要 一 种 条 件 性 的 改 变 程 序 执 行 流 程 的 方 式, 对 于 高 级 语 言, 我 们 有 各 种 if 语 句, 形 式 复 杂 的 循 环 语 句, 而 翻 译 到 汇 编 语 言, 就 只 有 一 组 简 单 的 条 件 跳 转 指 令 了 这 些 条 件 跳 转 的 形 式 是, 当 某 个 CPU 标 志 位 被 置 位 (set) 时, 跳 转 到 某 个 内 存 地 址 执 行, 否 则 顺 序 执 行, 从 而 将 程 序 分 成 两 路 条 件 跳 转 是 低 效 的 总 的 来 说, 条 件 跳 转 指 令 是 低 效 的, 它 会 影 响 到 代 码 缓 存 踪 迹 缓 存 (trace cache) CPU 流 水 线 等 机 构 的 工 作 而 对 CPU 流 水 线 的 影 响 是 最 大 的 现 代 CPU 执 行 一 条 指 令, 需 要 经 过 十 多 个 复 杂 的 步 骤, 例 如 指 令 预 取 指 令 解 码 寄 存 器 重 命 名 执 行 指 令 指 令 退 役 等 等, 如 果 每 处 理 一 个 指 令 它 都 需 要 独 占 CPU, 那 定 然 是 会 非 常 低 效 的 所 以 现 代 CPU 都 引 入 了 流 水 线 机 制, 每 一 条 指 令 都 好 像 流 水 线 上 的 一 个 产 品, 经 过 一 道 道 工 序 最 终 完 成, 一 条 指 令 还 没 有 完 成 时, 已 经 有 许 多 条 后 续 指 令 已 经 进 入 流 水 线 开 始 处 理 了 这 对 于 指 令 顺 序 执 行 时 是 很 有 效 的, 但 是 一 旦 出 现 一 条 条 件 分 支 指 令,CPU 就 会 不 知 道 该 把 哪 一 路 指 令 放 入 流 水 线, 现 在 它 可 以 选 择 暂 停 流 水 线, 当 条 件 分 支 指 令 的 走 向 确 定 了 以 后, 再 重 新 启 动 流 水 线, 但 这 样 会 有 10 来 个 时 钟 周 期 的 代 价, 是 十 分 巨 大 的 为 此 CPU 使 用 了 分 支 预 测 (branch prediction) 技 术, 它 通 过 一 系 列 算 法 来 估 计 当 前 分 支 的 走 向, 然 后 直 接 将 这 个 分 支 的 指 令 进 入 流 水 线 开 始 处 理, 这 样 流 水 线 就 不 需 要 停 工, 但 是 一 旦 误 测 (misprediction),cpu 需 要 倒 回 去 修 正 它 犯 下 的 错 误, 然 后 重 新 执 行 正 确 的 分 支, 这 个 代 价 极 其 巨 大, 会 高 达 几 十 个 时 钟 周 期 CPU 使 用 了 复 杂 的 算 法 来 做 这 个 预 测, 它 对 于 在 实 际 应 用 中 可 能 会 遇 到 的 许 多 模 式 都 能 很 好 的 工 作 实 验 观 察 分 支 预 测 的 存 在 性 我 们 还 是 先 通 过 一 个 实 际 的 例 子 来 感 受 它 的 存 在 性 : int main(){ for(int i=0;i<n;i++)a[i]=i%2; ull start=get_clock(); for(int i=0;i<n;i++){ if(a[i])a[i]= ; else a[i]= ; printf("%llu\n",get_clock()-start); return 0; 在 我 的 电 脑 上, 输 出 为 现 在 我 们 将 第 二 行 改 为 : for(int i=0;i<n;i++)a[i]=rand()%2; 第 25 页

26 输 出 变 成 了 : 注 意 到 我 们 的 改 变 根 本 没 有 涉 及 到 被 测 的 代 码, 在 第 一 个 程 序 中,a 数 组 中 的 值 为 交 替 的 0 和 1, 而 在 第 二 个 程 序 中 a 数 组 中 的 值 以 50% 的 概 率 随 机 为 0 或 者 1 CPU 的 分 支 预 测 技 术 有 能 力 探 寻 出 第 一 种 模 式, 从 而 高 效 地 执 行, 但 是 对 于 纯 粹 随 机 的 数 据 它 却 无 能 为 力 提 高 分 支 预 测 的 成 功 率 要 优 化 条 件 分 支 语 句, 一 方 面 可 以 考 虑 适 当 地 组 织 代 码 使 得 分 支 预 测 的 成 功 率 尽 量 高, 为 了 做 到 这 一 点, 我 们 需 要 大 致 了 解 条 件 分 支 算 法 的 特 点 在 以 下 情 况 下, 分 支 预 测 的 正 确 率 会 相 当 高 : 如 果 这 个 分 支 总 是 走 向 同 一 方 向 如 果 分 支 按 照 某 种 简 单 的 模 式 重 复 如 果 这 个 分 支 和 前 面 的 某 个 分 支 相 关 联 由 此 也 可 以 看 出, 在 循 环 语 句 中 计 数 器 的 比 较 操 作 所 导 致 的 条 件 分 支 还 是 相 当 安 全 的, 因 为 它 总 是 走 向 同 一 方 向 ( 除 了 最 后 一 次 退 出 循 环 ) 消 除 条 件 分 支 和 对 付 除 法 类 似, 优 化 条 件 分 支 的 另 一 个 办 法 是 消 除 掉 它, 下 面 给 出 一 些 比 较 有 启 发 性 的 例 子 : (1) 对 eax 取 绝 对 值 : cltd xorl %edx, %eax subl %edx, %eax 来 分 情 况 看 看 为 什 么 这 样 做 是 正 确 的 : 如 果 eax 0, 设 a=eax after line 1: eax=a edx=0 line 2: eax=a edx=0 line 3: eax=a edx=0 如 果 eax<0 after line 1: eax=a edx=-1 line 2: eax=~a edx=-1 line 3: eax=~a+1 edx=-1 而 ~a+1 就 是 在 计 算 机 中 -a 的 表 示 法 (2) 实 现 if(ebx>eax)ebx=eax: subl %ebx, sbbl %edx, andl %eax, addl %edx, %eax %edx %edx %ebx (3) 实 现 int cmp(int a) 函 数, 当 a=0 时 返 回 0, 当 a>0 时 返 回 1, 当 a<0 时 返 回 -1: int cmp(int a){return (a>>31)+(-a>>31&1); 第 26 页

27 需 要 注 意 的 是, 在 高 级 语 言 中 的 条 件 语 句 并 不 简 单 地 对 应 汇 编 语 言 中 的 一 条 条 件 跳 转 指 令, 而 是 逻 辑 表 达 式 中 的 每 一 项 都 会 产 生 一 个 条 件 跳 转, 所 以 在 编 写 高 级 语 言 中 的 if 语 句 时 应 该 尽 可 能 地 精 简 三. 乱 序 执 行 CPU 的 本 职 工 作, 是 执 行 一 条 条 的 指 令 序 列, 仅 仅 优 化 了 对 内 存 的 访 问 以 及 跳 转 指 令 的 效 率 并 不 解 决 根 本 问 题, 最 核 心 的 需 求 是, 对 于 一 大 段 的 指 令 代 码, 有 没 有 有 效 的 方 法 可 以 让 它 跑 得 更 快 现 代 CPU 在 这 上 面 已 经 走 得 很 远, 其 中 最 为 有 效 的 一 个 技 术 被 称 为 乱 序 执 行 (out-of-order excution), 乱 序 执 行, 正 如 字 面 含 义,cpu 企 图 打 乱 各 条 指 令 的 顺 序, 以 获 得 更 高 的 执 行 效 率 但 是 想 想 我 们 平 常 看 到 的 汇 编 程 序, 好 像 只 有 很 少 的 指 令 顺 序 可 以 交 换, 试 图 去 打 乱 顺 序 似 乎 是 浪 费 时 间 CPU 的 乱 序 执 行 确 实 并 不 是 这 样 单 纯, 它 主 要 依 赖 于 两 个 重 要 的 辅 助 技 术 : 寄 存 器 重 命 名 (register renaming) 和 微 指 令 (microcode) 微 指 令 微 指 令 简 称 为 uop, 是 一 套 类 似 于 risc 的 指 令 现 代 cisc 为 了 弥 补 和 risc 处 理 器 的 差 距, 将 外 部 送 入 的 x86 指 令 先 进 行 解 码, 分 解 为 更 为 细 小 的 操 作, 再 送 给 cpu 的 核 心 进 行 处 理, 当 然 这 个 解 码 过 程 本 身 也 是 需 要 时 间 的, 这 个 环 节 甚 至 一 度 成 为 瓶 颈 之 一, 需 要 程 序 员 在 编 写 代 码 时 注 意 许 多 规 则 来 优 化 解 码, 不 过 现 在 新 的 处 理 器 中 都 引 入 了 踪 迹 缓 存 (trace cache) 技 术, 这 种 技 术 会 缓 存 外 部 指 令 解 出 的 uop, 使 得 解 码 部 分 不 再 成 为 瓶 颈, 不 过 有 一 个 永 远 不 变 的 注 意 事 项 是 : 指 令 码 的 体 积 越 小 越 好, 对 解 码 单 元 也 好 踪 迹 缓 存 也 好 都 是 有 很 大 帮 助 的, 关 于 如 何 缩 小 指 令 码 的 体 积, 又 是 汇 编 语 言 的 智 力 游 戏, 不 在 这 里 展 开 讨 论 微 指 令 的 例 子 我 们 先 来 看 看 uop 是 什 么 样 的 : addl (%esi), %eax 这 条 指 令 将 esi 指 向 的 内 存 数 据 加 到 eax 中, 它 将 会 被 分 为 两 条 微 指 令, 第 一 条 加 载 esi 指 向 的 内 存, 第 二 条 做 运 算 并 保 存 结 果 到 eax 而 相 反 的, addl %eax, (%esi) 这 条 指 令 会 被 分 解 为 三 条 uop, 第 一 条 加 载 esi 指 向 的 内 存, 第 二 条 将 其 值 与 eax 的 值 相 加, 第 三 条 将 运 算 结 果 存 回 esi 指 向 的 内 存 位 置 微 指 令 与 乱 序 执 行 代 码 一 旦 被 分 解 为 uop, 乱 序 执 行 就 容 易 进 行 多 了 CPU 内 部 有 着 多 个 不 同 的 通 道, 有 的 负 责 从 内 存 中 加 载 数 据, 有 的 负 责 将 数 据 存 储 到 内 存, 有 的 负 责 执 行 整 数 指 令, 有 的 负 责 浮 点 指 令 不 同 的 uop 在 被 安 排 为 适 当 的 顺 序 后, 可 以 在 各 个 通 道 并 行 地 执 行, 例 如 这 一 条 指 令 正 在 等 待 从 内 存 中 加 载 一 个 不 在 缓 存 中 的 数 据, 这 时 其 它 几 个 通 道 可 以 提 前 开 始 进 行 后 面 的 整 数 运 算,CPU 的 工 作 能 力 可 以 被 充 分 的 利 用 起 来 寄 存 器 重 命 名 但 现 在 还 存 在 一 个 阻 碍 乱 序 执 行 良 好 工 作 的 障 碍 : 我 们 可 以 使 用 的 寄 存 器 数 目 是 很 有 限 的, 我 们 常 常 会 连 续 使 用 同 一 个 寄 存 器 来 完 成 某 些 工 作, 而 这 些 工 作 本 身 却 是 不 相 关 的, 例 如 如 下 代 码 : 第 27 页

28 a+=b; c+=d; 这 两 行 代 码 在 编 译 后 一 般 是 如 下 形 式 : 先 将 b 内 存 位 置 加 载 到 eax 中, 再 将 eax 加 到 a 内 存 位 置 然 后 对 c,d 做 同 样 的 工 作 假 如 变 量 b 并 不 存 在 于 高 速 缓 存 中, 那 么 在 执 行 到 第 一 条 指 令 的 时 候 就 会 发 生 延 迟, 这 时 如 果 d 在 缓 存 中, 就 可 以 同 时 开 始 进 行 c+=d 的 工 作 了 但 问 题 在 于, 现 在 两 行 代 码 都 使 用 eax 作 为 中 间 寄 存 器, 看 起 来 c+=d 必 须 等 待 了, 除 非 对 于 第 二 行 代 码 使 用 ebx 作 为 中 间 寄 存 器 如 果 每 一 行 代 码 都 换 寄 存 器 使 用 的 话, 很 快 就 没 有 寄 存 器 可 用 了 什 么 是 寄 存 器 重 命 名 寄 存 器 重 命 名 技 术 被 发 明 出 来 解 决 这 个 问 题, 现 代 CPU 内 部 实 际 上 有 大 量 可 用 的 物 理 寄 存 器, 我 们 编 程 时 可 见 的 eax 等 寄 存 器 只 是 一 个 虚 拟 的 概 念, 被 称 为 逻 辑 寄 存 器 在 代 码 需 要 使 用 某 个 逻 辑 寄 存 器 时,CPU 内 部 的 寄 存 器 分 配 表 (register allocation table,rat) 会 将 某 个 物 理 寄 存 器 映 射 到 它 上 面, 到 了 uop 的 级 别,eax,ebx 等 名 字 已 经 不 存 在 了, 取 而 代 之 的 是 其 映 射 的 物 理 寄 存 器 在 上 述 代 码 中, 虽 然 两 行 都 会 用 到 eax 寄 存 器, 但 是 在 经 过 寄 存 器 重 命 名 之 后, 它 们 已 经 是 不 同 的 寄 存 器, 就 有 机 会 乱 序 执 行 了 CPU 流 水 线 现 在 我 们 已 经 可 以 理 清 乱 序 执 行 以 及 相 关 优 化 机 制 的 大 概 流 程 了,CPU 的 指 令 预 取 单 元 会 提 前 读 取 接 下 来 要 执 行 的 一 定 数 目 的 指 令, 将 它 们 送 入 解 码 单 元, 经 过 解 码 和 寄 存 器 重 命 名 后, 进 入 重 定 序 缓 存 (reorder buffer) 被 适 当 地 打 乱 顺 序, 然 后 再 送 入 执 行 单 元 正 式 执 行, 执 行 后 结 果 将 被 保 存 起 来, 最 后 退 役 单 元 (retirement unit) 将 它 们 安 排 为 正 确 的 顺 序, 我 们 就 说 这 些 指 令 退 役 了, 也 就 是 正 式 执 行 完 毕 了 从 这 个 流 程 我 们 可 以 看 出, 如 果 一 开 始 的 指 令 预 取 一 步 就 出 现 了 问 题, 那 后 面 做 的 这 么 多 步 骤 都 是 无 用 功 了, 全 部 必 须 推 翻 重 来, 再 次 印 证 了 条 件 分 支 的 危 险 性 降 低 语 句 间 的 依 赖 关 系 在 一 条 指 令 被 执 行 的 这 个 复 杂 过 程 中, 有 许 多 环 节 都 有 可 能 成 为 瓶 颈, 如 果 编 写 汇 编 代 码, 有 太 多 的 细 节 值 得 注 意 但 如 果 是 使 用 高 级 语 言 来 编 写 代 码, 处 理 器 级 别 的 细 节 基 本 已 经 被 完 全 隔 离 开 来, 我 们 不 需 要 也 没 有 办 法 去 干 涉 背 后 的 行 为, 编 译 器 会 帮 我 们 处 理 一 切 惟 独 有 一 条 原 则 仍 然 可 以 指 导 我 们 编 写 高 级 语 言 代 码 : 降 低 语 句 之 间 的 依 赖 关 系 高 级 语 言 语 句, 经 过 编 译 器 的 编 译 转 换 为 数 条 汇 编 指 令, 我 们 没 有 能 力 也 没 有 精 力 在 编 写 高 级 语 言 时 还 在 cpu 级 别 思 考 微 指 令 乱 序 执 行 的 情 况, 但 高 级 语 言 中 充 斥 着 对 内 存 变 量 的 使 用, 内 存 变 量 不 像 寄 存 器, 没 有 重 命 名 单 元, 如 果 两 句 高 级 语 言 语 句 使 用 了 同 一 个 内 存 变 量 的 话, 后 一 句 是 一 定 要 等 前 一 句 执 行 完 毕 后 才 可 以 开 始 执 行 的, 这 样 就 影 响 了 CPU 流 水 线 的 工 作, 我 们 来 看 一 个 例 子 : double sum=0; for(int i=0;i<n;i++)sum+=a[i]; a 是 一 个 double 类 型 的 数 组,N 的 大 小 为 这 段 代 码 的 运 行 时 间 为 : 个 时 钟 周 期 简 单 地 将 其 改 为 4 路 加 法 : 第 28 页