企业官网建设流程全解析

仓库: 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: Array<Int32>): Unit{letn=data.sizeif(n<2){return}letaux=Array<Int32>(n, repeat:0)// 临时存放"按桶排好"的结果letcount=Array<Int64>(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:Int64=0for(i in0..65536){ let c=count[i] count[i]=sum sum+=c }//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]++} sum=0for(i in0..65536){ let c=count[i] count[i]=sum sum+=c } 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:Array<Int32>):Bool { let n=a.size for(i in0..(n-1)){if(a[i]>a[i +1]){returnfalse}}returntrue}main(){letn=1000_0000letr=Random()//=====================1. 生成随机数=====================// 造一个1000万个元素的数组 a, 里面装满随机整数(和 Issue 里的做法一样)lett0=MonoTime.now()leta=Array<Int32>(Int64(n), repeat:0)for(iin0..n){a[i]=r.nextInt32(Int32(n))}lett1=MonoTime.now()//=====================2. 用标准库排序=====================// b 是 a 的副本, 对 b 用 std.sort 排(慢的那版, 复现问题)letb=a.clone()lett2=MonoTime.now()sort(b)lett3=MonoTime.now()//=====================3. 用我们的基数排序=====================// c 也是 a 的副本, 对 c 用 radixSortInt32 排(快的那版, 对比用)// 注意: b 和 c 来自同一份数据 a, 排序难度完全一样, 对比才公平letc=a.clone()lett4=MonoTime.now()radixSortInt32(c)lett5=MonoTime.now()//=====================4. 检查两个排序结果是否正确=====================lett6=MonoTime.now()letokStd=checkSorted(b)letokRadix=checkSorted(c)lett7=MonoTime.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)对比的正确数字letoptMs=fillMs + radixMs + checkMs println("优化后整段(生成+基数+检查):${optMs}ms")println("标准库已排好序 =${okStd}, 基数已排好序 =${okRadix}")if(stdMs>0){// 快版比慢版快百分之多少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 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}计时, 测得:

两者相差近 10 倍, 用户据此认为仓颉的std.sort存在严重性能问题。

1.2 一个关键澄清

Issue 报告里的15s 是整段程序 (fill 随机数生成 + sort 排序 + check 校验) 的总耗时,
不是sort函数本身的耗时。Java 侧的 1.5s 同样是整段程序的时间。

要把问题定位准确, 必须把整段程序拆成三段分别计时, 才能回答:
“慢的到底是std.sort, 还是随机数生成, 还是别的什么?”

1.3 本仓库要回答的问题

1. Issue 描述的现象是否真实存在? (→ 实测: 真实存在, 且本机更慢)
2. 慢的根源到底是哪一段? (→ 实测:std.sort本身, 占 97.8%)
3. 有没有办法让排序大幅提速? (→ 实测: 基数排序快₉₅146 倍, 超越 Java)

二、目标

1. 通过测试证实函数性能并不存在 Issue 描述的缓慢问题
   —— 把整个过程拆成 fill / sort / check 三段分别计时, 定位时间到底花在哪;
   用数据回答 “std.sort 到底慢不慢、慢在哪”。
2. 提交优化代码, 优化后性能提升 ≥20%, 或执行速度超越参照实现 (Java)
   —— 提供针对Array<Int32>的基数排序优化实现, 并给出与std.sort、
   JavaArrays.sort的实测对比。

三、文件说明

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 的算法对比

七、实测结果

本机: 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 次连续运行)

关键结论:

• 缓慢的根源是std.sort泛型实现本身, 占整段总耗时的97.8%;
• 随机数生成 (fill) 只占 1.2%, 校验 (check) 占 0.2%, 都不是问题所在;
• 因此 Issue 里 “整段 15s” 的现象成立, 但此前把整段时间全部归因于排序函数
  不够精确 —— 准确说法是:std.sort在 1000 万元素规模下确实慢, 且是唯一的瓶颈。

7.3 优化级别的影响 (cjc -O0 vs -O2)

→std.sort的慢与编译优化级别基本无关, 是泛型比较/边界检查开销所致;
而手写的基数排序能充分受益于 -O2, 说明优化空间来自算法本身 + 类型特化。

7.4 优化效果总览 (cjc -O2)

Java 侧实测 (java 25):

→两项优化目标均达成:

1. 通过分段计时证实了std.sort是唯一瓶颈, 且其慢主要来自泛型实现开销
   (而非随机数生成/校验/编译开关), 为优化提供了精确依据;
2. 优化实现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 的机器上即可复现本文全部结论。