仓颉 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 -O2 benchmark.cj
* .\main
*/
import std.sort.*
import std.random.Random
import std.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: Array<Int32>): Unit {
let n = data.size
if (n < 2) {
return
}
let aux = Array<Int32>(n, repeat: 0) // 临时存放"按桶排好"的结果
let count = Array<Int64>(65536, repeat: 0) // 65536 个桶 (2 的 16 次方, 正好装下 16 位所有取值)
// ---- 第 1 趟: 按"低 16 位"分桶 ----
// 1) 数一数每个桶里有几个数 (count[key] 表示第 key 个桶里数的个数)
for (i in 0 .. n) {
let key = ((Int64(data[i]) & 0xFFFFFFFF) ^ 0x80000000) & 0xFFFF
count[key]++
}
// 2) 把"个数"换算成"起始位置": 假设桶 0 有 3 个, 桶 1 有 2 个,
// 那么桶 1 的元素应该从下标 3 开始放 (位置 = 前面所有桶的个数之和)
var sum: Int64 = 0
for (i in 0 .. 65536) {
let c = count[i]
count[i] = sum
sum += c
}
// 3) 按各自的起始位置, 把元素放进临时数组 aux
for (i in 0 .. n) {
let key = ((Int64(data[i]) & 0xFFFFFFFF) ^ 0x80000000) & 0xFFFF
aux[count[key]] = data[i]
count[key]++ // 放一个, 位置往后挪一格
}
// 4) 把临时数组拷回原数组
for (i in 0 .. n) {
data[i] = aux[i]
}
// ---- 第 2 趟: 按"高 16 位"分桶, 步骤和上面完全一样 ----
// 先清空桶计数
for (i in 0 .. 65536) {
count[i] = 0
}
for (i in 0 .. n) {
let key = (((Int64(data[i]) & 0xFFFFFFFF) ^ 0x80000000) >> 16) & 0xFFFF
count[key]++
}
sum = 0
for (i in 0 .. 65536) {
let c = count[i]
count[i] = sum
sum += c
}
for (i in 0 .. n) {
let key = (((Int64(data[i]) & 0xFFFFFFFF) ^ 0x80000000) >> 16) & 0xFFFF
aux[count[key]] = data[i]
count[key]++
}
for (i in 0 .. n) {
data[i] = aux[i]
}
}
/**
* 验证数组是否已从小到大排好: 从头到尾检查,
* 只要发现某个数比它后面一个数大, 就说明没排好。
*/
func checkSorted(a: Array<Int32>): Bool {
let n = a.size
for (i in 0 .. (n - 1)) {
if (a[i] > a[i + 1]) {
return false
}
}
return true
}
main() {
let n = 1000_0000
let r = Random()
// ===================== 1. 生成随机数 =====================
// 造一个 1000 万个元素的数组 a, 里面装满随机整数 (和 Issue 里的做法一样)
let t0 = MonoTime.now()
let a = Array<Int32>(Int64(n), repeat: 0)
for (i in 0 .. n) {
a[i] = r.nextInt32(Int32(n))
}
let t1 = MonoTime.now()
// ===================== 2. 用标准库排序 =====================
// b 是 a 的副本, 对 b 用 std.sort 排 (慢的那版, 复现问题)
let b = a.clone()
let t2 = MonoTime.now()
sort(b)
let t3 = MonoTime.now()
// ===================== 3. 用我们的基数排序 =====================
// c 也是 a 的副本, 对 c 用 radixSortInt32 排 (快的那版, 对比用)
// 注意: b 和 c 来自同一份数据 a, 排序难度完全一样, 对比才公平
let c = a.clone()
let t4 = MonoTime.now()
radixSortInt32(c)
let t5 = MonoTime.now()
// ===================== 4. 检查两个排序结果是否正确 =====================
let t6 = MonoTime.now()
let okStd = checkSorted(b)
let okRadix = checkSorted(c)
let t7 = MonoTime.now()
// 把每段的耗时换算成毫秒
let fillMs = (t1 - t0).toMilliseconds()
let stdMs = (t3 - t2).toMilliseconds()
let radixMs = (t5 - t4).toMilliseconds()
let checkMs = (t7 - t6).toMilliseconds()
let totalMs = (t7 - t0).toMilliseconds()
println("===== 仓颉排序性能测试 (n = ${n}) =====")
println("生成随机数 : ${fillMs} ms")
println("标准库排序 : ${stdMs} ms")
println("基数排序 : ${radixMs} ms")
println("检查结果 : ${checkMs} ms")
println("总计(含标准库排序) : ${totalMs} ms")
// 优化后整段 = 生成 + 快排 + 检查, 这一行才是和 Java (866 ms) 对比的正确数字
let optMs = fillMs + radixMs + checkMs
println("优化后整段(生成+基数+检查): ${optMs} ms")
println("标准库已排好序 = ${okStd}, 基数已排好序 = ${okRadix}")
if (stdMs > 0) {
// 快版比慢版快百分之多少
let gain = (stdMs - radixMs) * 100 / stdMs
println("基数排序比标准库快 ${gain}% (${radixMs} ms vs ${stdMs} ms)")
}
// 参照: Java Arrays.sort 实测 sort ~754 ms, 整段 ~866 ms (见 sorttest.java)
}
java源码：
import static java.util.Arrays.sort;
import java.util.Random;
/**
* sorttest.java
*
* Issue 2651 的 Java 参照实现 (增强为分段计时, 与 benchmark.cj 对应)。
* Java 的 Arrays.sort(int[]) 是 JIT 高度优化的双基准快排 (Dual-Pivot Quicksort)。
*
* 本程序做的事情: 和仓颉那边一样, 把"生成随机数 → 排序 → 检查结果"
* 拆开分段计时, 用来给仓颉的优化实现做对比参照。
*
* 编译运行:
* javac sorttest.java
* java -Xmx96m sorttest
*/
class sorttest {
public static void main(String[] args) {
final Random r = new Random();
final long n = 1000_0000;
final int[] a = new int[(int)n];
// ===== 1. 生成随机数 =====
// 造一个 1000 万个元素的数组 a, 里面装满随机整数 (和 Issue 里的做法一样)
long t0 = System.nanoTime();
for (long i = 0; i < n; i++) {
a[(int)i] = r.nextInt((int)n);
}
long t1 = System.nanoTime();
// ===== 2. 用 Arrays.sort 排序 =====
// b 是 a 的副本, 对 b 排序 (保持 a 不变, 和仓颉那边一样公平对比)
int[] b = a.clone();
long t2 = System.nanoTime();
sort(b);
long t3 = System.nanoTime();
// ===== 3. 检查排序结果是否正确 =====
// 从头到尾检查, 只要发现某个数比它后面一个数大, 就说明没排好
boolean ok = true;
long t4 = System.nanoTime();
for (long i = 1; i < n; i++) {
if (b[(int)i - 1] > b[(int)i]) {
ok = false;
break;
}
}
long t5 = System.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)
—— 提供针对Array<Int32>的基数排序优化实现, 并给出与std.sort、
JavaArrays.sort的实测对比。
三、文件说明
| 文件 | 说明 |
|---|---|
sort-test.cj |
Issue 原版复现 (未修改), 用于还原整段总耗时 |
benchmark.cj |
分段计时测试: fill / std.sort / radixSortInt32 / check, 并输出对比 |
sorttest.java |
Java 参照实现 (增强为分段计时, 与 benchmark.cj 对应) |
README.md |
本说明文档 |
cangjie/ |
仓颉 SDK (win x64, 1.0.5), 含 cjc 编译器与运行时 DLL |
*.dll |
从 SDK 复制到 exe 同目录的运行时库 (解决找不到 DLL 的问题) |
3.1 各源码文件的核心逻辑
sort-test.cj (原版复现, 未加任何计时)
// 伪代码示意
let arr = Array<Int32>(1000_0000, {_ => rnd.nextInt32()}) // fill: 生成随机数
std.sort.sort(arr) // sort: 排序
for (i in 0..arr.size-1) assert(arr[i] <= arr[i+1]) // 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 --version
4.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.bat
5.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.exe
benchmark.cj 输出示例:
===== Cangjie sort benchmark (n = 10000000) =====
fill : XXXX ms
std.sort : XXXX ms
radixSortInt32: XXXX ms
check : XXXX ms
total (含 std.sort) : XXXX ms
优化后整段 (fill+radix+check): 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 占绝大部分);优化后整段 (fill+radix+check): 用优化实现替换 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 = true
5.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 ms | 290 ms | 280 ms | 282 ms | 308 ms | 289 ms | 1.2% |
| std.sort (introsort) | 23464 ms | 25372 ms | 25888 ms | 26270 ms | 26239 ms | 25447 ms | 97.8% |
| radixSortInt32 (优化) | 161 ms | 353 ms | 288 ms | 311 ms | 243 ms | 271 ms | 1.0% |
| check | 28 ms | 63 ms | 52 ms | 40 ms | 35 ms | 44 ms | 0.2% |
| total | 23978 ms | 26129 ms | 26546 ms | 27075 ms | 26857 ms | 26117 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.sort | 25890 ms | ~25447 ms | 几乎无差别 |
| radixSortInt32 | 10079 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) |
| 整段 (fill+radix+check) | ~604 ms, vs Java 整段 866 ms |
| 排序正确性 | 5 次运行两种实现均通过 O(n) 校验 (sorted = true) |
Java 侧实测 (java 25):
| 阶段 | 耗时 |
|---|---|
| fill | 87.0 ms |
| sort (Arrays.sort) | 753.9 ms |
| check | 7.8 ms |
| total | 865.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/ 中为 Array<Int32> 增加特化入口:
- 在
sort.cj的sort(data: Array<T>)泛型分发前, 对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 的机器上即可复现本文全部结论。
一站式 AI 云服务平台
更多推荐
7
0- 0
已为社区贡献2条内容
所有评论(0)