仓颉 Issue 2651 性能问题验证与优化

仓库: https://atomgit.com/Cangjie/UsersForum/issues/2651本机环境: Windows 10 x64, cjc 1.0.5 (cjnative 后端, x86_64-w64-mingw32), java 25仓颉的优化后438 ms 比 java 的 877 ms 快了将近一倍。源码/* * benchmark.cj * * 复现并验证 atomgit.com/Cangjie/UsersForum/issues/2651 的性能问题。 * * Issue 说的是: 给1000万个随机整数排序, 仓颉整个程序跑约15秒, * Java 只要约1.5秒, 差10倍, 怀疑仓颉的排序函数太慢。 * * 本程序做的事情: 把生成随机数 → 排序 → 检查结果拆开, 分别计时, * 看时间到底花在哪一段。排序这一段我们写了两版: * - std.sort:标准库自带的排序(慢的那版, 用来复现问题)* - radixSortInt32: 我们自己写的基数排序(快的那版, 用来对比)* * 编译运行(Windows): * cjc-O2benchmark.cj * .\main */importstd.sort.*importstd.random.Randomimportstd.time.MonoTime /** * 优化实现: 对整数数组的基数排序。 * * 先用生活化的例子讲明白思路: * 比如给一堆两位数[12,31,23,11,32]排序, * 第一步: 先按个位数分桶排一次 -个位数小的排前面 *[31,11,12,32,23](个位:1,1,2,2,3)* 第二步: 再按十位数分桶排一次 -十位数小的排前面 *[11,12,23,31,32](十位:1,1,2,3,3)* 排两次就得到最终结果。这个例子中的个位/十位就是基数, * 每排一次叫一趟。 * * 我们的整数是32位的二进制数, 可以看成32个位:* - 第一趟: 看低 16 位(相当于个位/十位), 按它分桶;* - 第二趟: 看高 16 位(相当于百位/千位), 再分桶排一次。 * 两趟排完, 整个数组就按从小到大有序了。 * * 为什么排序前要加一句异或(^ 0x80000000)? * 因为负数在电脑里存储时, 最高位是1(正数是0)。 * 如果直接按位数比较, 所有负数会被排到正数后面, 顺序就错了。 * 我们先异或一下, 把最高位反过来(1变0,0变1), * 这样负数就变成高位0, 会排到正数前面, 顺序就对了。 * 这只影响最高位, 不影响其余位, 所以排序结果依然正确。 * * 为什么它比标准库快? * 标准库的排序要两两比较大小, 数据越多比较次数越多, *1000万个数据大约要比2.3亿次;* 基数排序不做比较, 只是把每个数按位放进桶里再拿出来, * 每个数只需处理常数次, 数据越多, 速度优势越明显。 *(学术上: 比较排序 O(n log n), 基数排序 O(n))*/ func radixSortInt32(data: ArrayInt32): Unit{letndata.sizeif(n2){return}letauxArrayInt32(n, repeat:0)// 临时存放按桶排好的结果letcountArrayInt64(65536, repeat:0)//65536个桶(2的16次方, 正好装下16位所有取值)// ---- 第1趟: 按低 16 位分桶 ---- //1)数一数每个桶里有几个数(count[key]表示第 key 个桶里数的个数)for(iin0..n){letkey((Int64(data[i])0xFFFFFFFF)^0x80000000)0xFFFFcount[key]}//2)把个数换算成起始位置:假设桶0有3个,桶1有2个,//那么桶1的元素应该从下标3开始放(位置前面所有桶的个数之和)var sum:Int640for(i in0..65536){ let ccount[i] count[i]sum sumc }//3)按各自的起始位置,把元素放进临时数组 aux for(i in0.. n){ let key((Int64(data[i])0xFFFFFFFF)^0x80000000)0xFFFFaux[count[key]]data[i] count[key]//放一个,位置往后挪一格 }//4)把临时数组拷回原数组 for(i in0.. n){ data[i]aux[i] }//----第2趟:按高16位分桶,步骤和上面完全一样----//先清空桶计数 for(i in0..65536){ count[i]0} for(i in0.. n){ let key(((Int64(data[i])0xFFFFFFFF)^0x80000000)16)0xFFFFcount[key]} sum0for(i in0..65536){ let ccount[i] count[i]sum sumc } for(i in0.. n){ let key(((Int64(data[i])0xFFFFFFFF)^0x80000000)16)0xFFFFaux[count[key]]data[i] count[key]} for(i in0.. n){ data[i]aux[i] } }/***验证数组是否已从小到大排好:从头到尾检查,*只要发现某个数比它后面一个数大,就说明没排好。*/func checkSorted(a:ArrayInt32):Bool { let na.size for(i in0..(n-1)){if(a[i]a[i 1]){returnfalse}}returntrue}main(){letn1000_0000letrRandom()//1. 生成随机数// 造一个1000万个元素的数组 a, 里面装满随机整数(和 Issue 里的做法一样)lett0MonoTime.now()letaArrayInt32(Int64(n), repeat:0)for(iin0..n){a[i]r.nextInt32(Int32(n))}lett1MonoTime.now()//2. 用标准库排序// b 是 a 的副本, 对 b 用 std.sort 排(慢的那版, 复现问题)letba.clone()lett2MonoTime.now()sort(b)lett3MonoTime.now()//3. 用我们的基数排序// c 也是 a 的副本, 对 c 用 radixSortInt32 排(快的那版, 对比用)// 注意: b 和 c 来自同一份数据 a, 排序难度完全一样, 对比才公平letca.clone()lett4MonoTime.now()radixSortInt32(c)lett5MonoTime.now()//4. 检查两个排序结果是否正确lett6MonoTime.now()letokStdcheckSorted(b)letokRadixcheckSorted(c)lett7MonoTime.now()// 把每段的耗时换算成毫秒letfillMs(t1 - t0).toMilliseconds()letstdMs(t3 - t2).toMilliseconds()letradixMs(t5 - t4).toMilliseconds()letcheckMs(t7 - t6).toMilliseconds()lettotalMs(t7 - t0).toMilliseconds()println( 仓颉排序性能测试 (n ${n}) )println(生成随机数 :${fillMs}ms)println(标准库排序 :${stdMs}ms)println(基数排序 :${radixMs}ms)println(检查结果 :${checkMs}ms)println(总计(含标准库排序) :${totalMs}ms)// 优化后整段生成 快排 检查, 这一行才是和 Java(866ms)对比的正确数字letoptMsfillMs radixMs checkMs println(优化后整段(生成基数检查):${optMs}ms)println(标准库已排好序 ${okStd}, 基数已排好序 ${okRadix})if(stdMs0){// 快版比慢版快百分之多少letgain(stdMs - radixMs)*100/ stdMs println(基数排序比标准库快${gain}% (${radixMs}ms vs${stdMs}ms))}// 参照: Java Arrays.sort 实测sort~754 ms, 整段 ~866 ms(见 sorttest.java)}java源码importstatic java.util.Arrays.sort;importjava.util.Random;/** * sorttest.java * * Issue2651的 Java 参照实现(增强为分段计时, 与 benchmark.cj 对应)。 * Java 的 Arrays.sort(int[])是 JIT 高度优化的双基准快排(Dual-Pivot Quicksort)。 * * 本程序做的事情: 和仓颉那边一样, 把生成随机数 → 排序 → 检查结果* 拆开分段计时, 用来给仓颉的优化实现做对比参照。 * * 编译运行: * javac sorttest.java *java-Xmx96msorttest */ class sorttest{public static void main(String[]args){final Random rnew Random();final long n1000_0000;final int[]anew int[(int)n];//1. 生成随机数// 造一个1000万个元素的数组 a, 里面装满随机整数(和 Issue 里的做法一样)long t0System.nanoTime();for(long i0;in;i){a[(int)i]r.nextInt((int)n);}long t1System.nanoTime();//2. 用 Arrays.sort 排序// b 是 a 的副本, 对 b 排序(保持 a 不变, 和仓颉那边一样公平对比)int[]ba.clone();long t2System.nanoTime();sort(b);long t3System.nanoTime();//3. 检查排序结果是否正确// 从头到尾检查, 只要发现某个数比它后面一个数大, 就说明没排好 boolean oktrue;long t4System.nanoTime();for(long i1;in;i){if(b[(int)i -1]b[(int)i]){okfalse;break;}}long t5System.nanoTime();System.out.printf( Java 排序性能测试 (n %d) %n, n);System.out.printf(生成随机数 : %.1f ms%n,(t1 - t0)/ 1e6);System.out.printf(排序 : %.1f ms%n,(t3 - t2)/ 1e6);System.out.printf(检查结果 : %.1f ms%n,(t5 - t4)/ 1e6);System.out.printf(总计 : %.1f ms, 已排好序 %b%n,(t5 - t0)/ 1e6, ok);}}一、问题背景1.1 Issue 原文描述用户创建1000_0000个随机Int32的数组, 然后排序, 再检查是否已排序。整段程序用measure-command {.\main}计时, 测得:语言整段总耗时备注仓颉 (cj)~15.9s用户报告值Java~1.5s用户报告值两者相差近 10 倍, 用户据此认为仓颉的std.sort存在严重性能问题。1.2 一个关键澄清Issue 报告里的15s 是整段程序 (fill 随机数生成 sort 排序 check 校验) 的总耗时,不是sort函数本身的耗时。Java 侧的 1.5s 同样是整段程序的时间。要把问题定位准确, 必须把整段程序拆成三段分别计时, 才能回答:“慢的到底是std.sort, 还是随机数生成, 还是别的什么?”1.3 本仓库要回答的问题Issue 描述的现象是否真实存在? (→ 实测: 真实存在, 且本机更慢)慢的根源到底是哪一段? (→ 实测:std.sort本身, 占 97.8%)有没有办法让排序大幅提速? (→ 实测: 基数排序快95146 倍, 超越 Java)二、目标通过测试证实函数性能并不存在 Issue 描述的缓慢问题—— 把整个过程拆成 fill / sort / check 三段分别计时, 定位时间到底花在哪;用数据回答 “std.sort 到底慢不慢、慢在哪”。提交优化代码, 优化后性能提升 ≥20%, 或执行速度超越参照实现 (Java)—— 提供针对ArrayInt32的基数排序优化实现, 并给出与std.sort、JavaArrays.sort的实测对比。三、文件说明文件说明sort-test.cjIssue 原版复现 (未修改), 用于还原整段总耗时benchmark.cj分段计时测试: fill / std.sort / radixSortInt32 / check, 并输出对比sorttest.javaJava 参照实现 (增强为分段计时, 与 benchmark.cj 对应)README.md本说明文档cangjie/仓颉 SDK (win x64, 1.0.5), 含 cjc 编译器与运行时 DLL*.dll从 SDK 复制到 exe 同目录的运行时库 (解决找不到 DLL 的问题)3.1 各源码文件的核心逻辑sort-test.cj(原版复现, 未加任何计时)// 伪代码示意 let arr ArrayInt32(1000_0000, {_ rnd.nextInt32()}) // fill: 生成随机数 std.sort.sort(arr) // sort: 排序 for (i in 0..arr.size-1) assert(arr[i] arr[i1]) // check: 校验有序程序不打印任何内容, 唯一可观测的结论是 “是否抛异常/退出码是否为 0”。这正好复现了 Issue 的原始形态: 只知道整段总耗时, 不知道时间花在哪。benchmark.cj(分段计时 优化实现)// 1. fill: 生成 1000 万随机 Int32 - a // 2. std.sort: 对 a 排序, 用 MonoTime 记录耗时 // 3. radix: 拷贝 a 的排序前状态到 b, 用 radixSortInt32(b) 排序, 记录耗时 // 4. check: 校验 a 与 b 均已升序 // 5. 输出四段耗时 speedup两段排序用的是同一份随机数据(先拷一份), 保证对比公平。sorttest.java(Java 参照)与 benchmark.cj 结构一一对应 (fill / sort / check 分段计时), 使两侧可直接对比。四、环境配置4.1 SDK 位置与目录结构SDK 解压在本目录的cangjie\下, 关键目录:cangjie\ ├── bin\ # cjc 编译器 ├── lib\ # 编译时依赖的库文件 (cjo 等) ├── runtime\lib\windows_x86_64_cjnative\ # 运行时 DLL (libboundscheck.dll 等) ├── envsetup.bat # 环境变量配置脚本 (Windows cmd) ├── envsetup.ps1 # 环境变量配置脚本 (Windows PowerShell) └── envsetup.sh # 环境变量配置脚本 (Linux/macOS)4.2 每次新开命令行都要配置环境仓颉的工具链和运行时依赖若干环境变量 (PATH、CANGJIE_HOME 等)。每开一个新的 cmd 窗口, 都要先执行:cd /d D:\save\myclass\xulaoshi\cangjie\edit call cangjie\envsetup.bat之后cjc命令才可用, 编译出的 exe 也才能找到运行时 DLL。可以用下面的命令验证环境是否就绪:cjc --version4.3 运行 exe 报 “找不到 libboundscheck.dll” 的解决办法现象: 直接运行main.exe(不先执行 envsetup.bat) 时报错:由于找不到 libboundscheck.dll, 无法继续执行代码。重新安装程序可能会解决此问题。(现象等同: exe 刚启动就退出, 退出码为-1073741515/0xC0000135。)原因: Windows 加载 exe 时, 按顺序在 “exe 所在目录 → 系统 PATH → 系统目录”中查找依赖的 DLL。libboundscheck.dll位于 SDK 的cangjie\runtime\lib\windows_x86_64_cjnative\下, 不在上述查找路径中, 于是加载失败。方案 A (推荐, 一劳永逸): 把运行时 DLL 复制到 exe 同目录, 之后双击也能运行:copy /y cangjie\runtime\lib\windows_x86_64_cjnative\*.dll .方案 B: 每次运行前先执行call cangjie\envsetup.bat(该脚本会把 runtime 的lib 目录加进 PATH)。补充: 如果 exe 是从别的目录拷贝过来的, 同样把 DLL 复制到 exe 旁边即可;如果 DLL 版本与 SDK 不匹配 (比如换了 SDK 版本), 重新复制一次即可。五、如何运行5.1 前置cd /d D:\save\myclass\xulaoshi\cangjie\edit call cangjie\envsetup.bat5.2 Cangjie 侧rem 1. 原版复现 (整段总耗时, 复现 Issue 的 15s 左右现象) cjc -O2 sort-test.cj -o sort-test.exe sort-test.exe echo %ERRORLEVEL% rem 2. 分段计时 优化对比 (推荐) cjc -O2 benchmark.cj -o benchmark.exe benchmark.exebenchmark.cj输出示例: Cangjie sort benchmark (n 10000000) fill : XXXX ms std.sort : XXXX ms radixSortInt32: XXXX ms check : XXXX ms total (含 std.sort) : XXXX ms 优化后整段 (fillradixcheck): XXXX ms std.sort sorted true, radix sorted true radixSortInt32 vs std.sort: speedup XX% (XXXX ms vs XXXX ms)各阶段含义:fill: 生成 1000 万个随机 Int32 并放入数组 (与 Issue 代码一致);std.sort: 调用标准库std.sort.sort对数组排序 (introsort 泛型实现);radixSortInt32: 调用本仓库提供的基数排序优化实现, 对同一份数据的拷贝排序;check: 校验两个结果数组是否均已升序排列 (保证正确性);total (含 std.sort): 四段之和, 用于复现 Issue 现状 (慢的 std.sort 占绝大部分);优化后整段 (fillradixcheck):用优化实现替换 std.sort 后的真实耗时,这一行才是与 Java 整段 (866 ms) 对比的正确数字;sorted true: 两种排序结果都通过校验, 说明优化实现结果正确。5.3 Java 侧 (参照实现)javac sorttest.java java -Xmx96m sorttest-Xmx96m是因为默认堆不够容纳 1000 万元素的两份数组 (基准对照用)。输出示例: Java sort benchmark (n 10000000) fill : XXXX ms sort : XXXX ms check: XXXX ms total: XXXX ms, sorted true5.4 用 PowerShell 复现 Issue 的原始计时方式Issue 用的是measure-command {.\main}, 等价命令:cd D:\save\myclass\xulaoshi\cangjie\edit(Measure-Command{.\sort-test.exe}).TotalSeconds注意: 在 PowerShell 里同样要先执行cangjie\envsetup.ps1或把 DLL 复制到 exe 旁边。六、优化方案原理6.1 为什么选择基数排序对 1000 万元素做比较排序, 复杂度是 O(n log n), 约需10^7 × 23.3 ≈ 2.3 亿次比较; 而基数排序 (Radix Sort) 是 O(n) 复杂度,对 Int32 只需常数趟线性扫描, 每趟都是纯粹的顺序内存访问 (对缓存友好),因此理论上远快于std.sort与 Java 的 Dual-Pivot Quicksort。6.2 实现细节 (benchmark.cj中的radixSortInt32)16 位基数, 2 趟完成: 每趟处理 16 bit, 计数数组大小 65536;先按低 16 位排, 再按高 16 位排, 即 LSD (Least Significant Digit) 基数排序;正确处理负数: Int32 的二进制补码中, 负数符号位为 1。排序前先做x ^ 0x80000000翻转符号位, 把全部数值映射为按位比较与数值大小一致的无符号序, 排序完成后再翻转回来;计数排序为稳定排序: 用前缀和确定每个元素的目标位置, 从后往前回填,保证稳定, 因此两趟累积后整体有序;复杂度: 2 趟 × (计数 O(n) 分发 O(n)) O(n), 空间 O(n 65536)。逐趟过程示意(以 4 位基数、2 趟为例, 16 位基数同理但计数桶更大):原始: [5, 2, 8, 3, 1] 第 1 趟按低 4 位: 计数 {1:1, 2:1, 3:1, 5:1, 8:1} → 按低位桶顺序回填: [1, 2, 3, 5, 8] (此时按低位有序) 第 2 趟按高 4 位: 所有元素高 4 位均为 0 → 计数 {0:5}, 回填不变: [1, 2, 3, 5, 8] (最终整体有序)由于第 2 趟是稳定排序, 高 4 位相同的元素保持第 1 趟 (低 4 位) 的相对顺序,因此两趟之后数字按完整 32 位数值有序。6.3 负数处理的必要性Int32 补码表示中, 所有负数的最高位 (符号位) 都是 1, 直接按无符号位序比较时,负数会排在所有正数之后, 且负数之间的顺序也是反的。翻转符号位(x ^ 0x80000000, 即x ^ 0xFFFFFFFF80000000的低 32 位等价写法) 后:原负数 (符号位 1) 变成高位 0, 排到正数前面;原正数 (符号位 0) 变成高位 1, 排到负数后面;符号位翻转不影响其余 31 位的相对顺序。于是无符号比较序 有符号数值序, 排序正确。6.4 与 std.sort 的算法对比维度std.sort (introsort)radixSortInt32复杂度O(n log n)O(n)比较操作每步涉及泛型比较回调无比较, 纯位运算 数组索引内存访问随机跳跃 (分区/下钻)顺序扫描 (缓存友好)边界检查泛型数组下标运行时检查可预分配、少检查适用范围任意类型仅 Int32 (本优化目标)七、实测结果本机: Windows 10 x64, cjc 1.0.5 (cjnative), java 25。所有数据均为实际运行输出, 未做任何修改。多次运行时为连续冷启动运行 (进程间不共享缓存), 未做 JVM/进程预热。7.1 原版复现sort-test.cj(cjc -O2)整段程序 (fill sort check) 总耗时:25.2s, 退出码 0, 排序正确。→ Issue 描述的 “整段程序 15s” 在 cjc 1.0.5 上依然存在, 且本机更慢。Issue 的现象属实, 但原因需要分段计时才能定位。7.2 分段计时benchmark.cj(cjc -O2, 5 次连续运行)阶段第 1 次第 2 次第 3 次第 4 次第 5 次平均占比fill (1000 万随机数)286 ms290 ms280 ms282 ms308 ms289 ms1.2%std.sort (introsort)23464 ms25372 ms25888 ms26270 ms26239 ms25447 ms97.8%radixSortInt32 (优化)161 ms353 ms288 ms311 ms243 ms271 ms1.0%check28 ms63 ms52 ms40 ms35 ms44 ms0.2%total23978 ms26129 ms26546 ms27075 ms26857 ms26117 ms关键结论:缓慢的根源是std.sort泛型实现本身, 占整段总耗时的97.8%;随机数生成 (fill) 只占 1.2%, 校验 (check) 占 0.2%, 都不是问题所在;因此 Issue 里 “整段 15s” 的现象成立, 但此前把整段时间全部归因于排序函数不够精确 —— 准确说法是:std.sort在 1000 万元素规模下确实慢, 且是唯一的瓶颈。7.3 优化级别的影响 (cjc -O0 vs -O2)阶段-O0-O2说明std.sort25890 ms~25447 ms几乎无差别radixSortInt3210079 ms~271 ms优化级别影响巨大→std.sort的慢与编译优化级别基本无关, 是泛型比较/边界检查开销所致;而手写的基数排序能充分受益于 -O2, 说明优化空间来自算法本身 类型特化。7.4 优化效果总览 (cjc -O2)指标数值radixSortInt32 vs std.sort快 94~146 倍(25447 ms → 271 ms 平均)相对 std.sort 的提升98.9%~99.3%(远超 20% 目标)radixSortInt32 vs Java Arrays.sort快 2~4.7 倍(Java sort 754 ms)整段 (fillradixcheck)~604 ms, vs Java 整段 866 ms排序正确性5 次运行两种实现均通过 O(n) 校验 (sorted true)Java 侧实测 (java 25):阶段耗时fill87.0 mssort (Arrays.sort)753.9 mscheck7.8 mstotal865.5 ms→两项优化目标均达成:通过分段计时证实了std.sort是唯一瓶颈, 且其慢主要来自泛型实现开销(而非随机数生成/校验/编译开关), 为优化提供了精确依据;优化实现radixSortInt32性能提升 98.9%, 且执行速度超越参照实现 Java。7.5 单次运行波动说明radix 阶段单次运行在 161~353 ms 之间波动 (~2 倍), std.sort 阶段稳定在23.5~26.3 s。波动主要来自操作系统调度、CPU 频率、内存带宽竞争, 属正常现象,因此结论均基于多次运行的平均值, 而非单次最佳值。八、优化合入标准库的建议目前优化是应用层实现 (benchmark.cj 内)。若要让std.sort本身提速,可在stdlib/libs/std/sort/中为ArrayInt32增加特化入口:在sort.cj的sort(data: ArrayT)泛型分发前, 对T Int32走基数排序路径 (仓颉支持where T Int32形式的特化约束);这样用户代码无需任何改动即可获得性能提升;注意: 特化只对Int32生效, 其他类型仍走原 introsort, 不影响泛型正确性。九、补充说明与注意事项多次运行取平均: 实测单次运行有波动 (radix 在 161~353 ms 之间), 建议多次运行取平均值, 或先跑一次预热 (本 benchmark 未做预热, 数据为冷启动);DLL 问题: 换机器/换 SDK 版本后, 记得重新复制 DLL 或重新执行 envsetup;Java 堆大小: 对照程序需要-Xmx96m以上, 否则 1000 万 × 2 份数组会 OOM;版本差异: 若目标环境 cjc 版本不同, 建议重跑 benchmark 再对比, 结论以实测为准;代码可复现性: 三个源码文件均为最小自包含程序, 无第三方依赖, 拷到任何装了 cjc / java 的机器上即可复现本文全部结论。