简单测试一下分支判断中的 switch/bitset/const array
·1198 words·6 mins
Table of Contents
这是一篇笔记，稍微记录一下自己测试的一些结果
环境信息 #
- zig version 0.12.0-dev.1604+caae40c21，编译 flag
-Doptimize=ReleaseFast - Linux 6.6.1-arch1-1 x86_64 unknown
- CPU : AMD Ryzen 7 5800H with Radeon Graphics
- CPU flags:
fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext fxsr_opt pdpe1gb rdtscp lm constant_tsc rep_good nopl nonstop_tsc cpuid extd_apicid aperfmperf rapl pni pclmulqdq monitor ssse3 fma cx16 sse4_1 sse4_2 movbe popcnt aes xsave avx f16c rdrand lahf_lm cmp_legacy svm extapic cr8_legacy abm sse4a misalignsse 3dnowprefetch osvw ibs skinit wdt tce topoext perfctr_core perfctr_nb bpext perfctr_llc mwaitx cpb cat_l3 cdp_l3 hw_pstate ssbd mba ibrs ibpb stibp vmmcall fsgsbase bmi1 avx2 smep bmi2 erms invpcid cqm rdt_a rdseed adx smap clflushopt clwb sha_ni xsaveopt xsavec xgetbv1 xsaves cqm_llc cqm_occup_llc cqm_mbm_total cqm_mbm_local user_shstk clzero irperf xsaveerptr rdpru wbnoinvd cppc arat npt lbrv svm_lock nrip_save tsc_scale vmcb_clean flushbyasid decodeassists pausefilter pfthreshold avic v_vmsave_vmload vgif v_spec_ctrl umip pku ospke vaes vpclmulqdq rdpid overflow_recov succor smca fsrm debug_swap - 测试集：10000 条随机 npm package name 数据，包含合法、非法的数据。所有 bench 均使用的同一份数据
Switch / If branch #
const std = @import("std");
pub fn isNPMPackageName(target: []const u8) bool {
if (target.len == 0) return false;
if (target.len > 214) return false;
const scoped = switch (target[0]) {
'A'...'Z', 'a'...'z', '0'...'9', '$', '-' => false,
'@' => true,
else => return false,
};
var slash_index: usize = 0;
for (target[1..], 0..) |c, i| {
switch (c) {
'A'...'Z', 'a'...'z', '0'...'9', '-', '_', '.' => {},
'/' => {
if (!scoped) return false;
if (slash_index > 0) return false;
slash_index = i + 1;
},
'!', '~', '*', '\'', '(', ')' => {
if (!scoped or slash_index > 0) return false;
},
else => return false,
}
}
return !scoped or slash_index > 0 and slash_index + 1 < target.len;
}
-Doptimize=ReleaseFast 下的结果
>> hyperfine -r 10000 --warmup 2000 -N "./zig-out/bin/TTT"
Benchmark 1: ./zig-out/bin/TTT
Time (mean ± σ): 785.9 µs ± 136.5 µs [User: 670.8 µs, System: 40.9 µs]
Range (min … max): 544.6 µs … 1775.2 µs 10000 runs
这里摘取部分的汇编代码
(lldb) disassemble --name isNPMPackageName
; ...
TTT[0x20bb8f] <+15>: ret
; ...
TTT[0x20bc57] <+215>: movabs rcx, 0x878200000000
TTT[0x20bc61] <+225>: xor eax, eax
TTT[0x20bc63] <+227>: movzx edx, byte ptr [rdi + rax + 0x1]
TTT[0x20bc68] <+232>: cmp rdx, 0x2f
TTT[0x20bc6c] <+236>: ja 0x20bc78 ; <+248> at main.zig:15:17
TTT[0x20bc6e] <+238>: bt rcx, rdx
TTT[0x20bc72] <+242>: jb 0x20bb8f ; <+15> at main.zig
TTT[0x20bc78] <+248>: cmp edx, 0x7e
TTT[0x20bc7b] <+251>: je 0x20bb8f ; <+15> at main.zig
TTT[0x20bc81] <+257>: cmp dl, 0x5f
; ...
从汇编代码可以看到，这个函数已经被修改的面目全飞了。原来函数中的 switch 因为 scoped 会产生部分的合并，然后有一部分的ASCII 范围上的比较会被转换成 bitset ，比如 0x878200000000 这个值
In [89]: for i in range(0, 255):
...: if biset & (1 << i) != 0:
...: print(i, hex(i), chr(i))
...:
33 0x21 !
39 0x27 '
40 0x28 (
41 0x29 )
42 0x2a *
47 0x2f /
函数中的第二个 for 循环，对应 movzx edx, byte ptr [rdi + rax + 0x1] 指令。这里将 char 赋值到了 edx 寄存器中。下一步则是比较了是否大于 0x2f => /，如果大于，如果大于那么跳转到 0x20bc78。这里会继续比较 0x7e => ~，如果相等那么直接函数返回了；如果小于 0x2f 那么会通过 bt rcx, rdx 来检测 rdx 所在的位是否为 1，我们可以通过上面的 Python 结果来看到，这里其实抠出来了几个在函数中用到的 ASCII 字符，如果不满足，那么直接返回。否则又重复一次 0x7e 的比较，但是这个应该永假的
ReleaseFast 编译后的这个逻辑流哈，感觉不知道在干些什么。。。🤯
std.bit_set.IntegerBitSet #
使用 std 中的 bitset，来看一下是否能够在不动用逻辑的前提下对函数进行加速
fn construct_bitset(chars: []const u8) std.bit_set.IntegerBitSet(255) {
var bitset = std.bit_set.IntegerBitSet(std.math.maxInt(u8)).initEmpty();
for (chars) |char| {
bitset.set(@as(u8, char));
}
return bitset;
}
pub fn isNPMPackageName(target: []const u8) bool {
if (target.len == 0) return false;
if (target.len > 214) return false;
const bset1 = comptime construct_bitset("ABCDEFGHIJKLMNOPQRSTUVWXYZ" ++
"abcdefghijklmnopqrstuvwxyz" ++
"0123456789" ++
"$-");
const bset2 = comptime construct_bitset("ABCDEFGHIJKLMNOPQRSTUVWXYZ" ++
"abcdefghijklmnopqrstuvwxyz" ++
"0123456789" ++
"-_.");
const bset3 = comptime construct_bitset("!~*'()");
const scoped = blk: {
if (bset1.isSet(target[0])) {
break :blk false;
} else if (target[0] == '@') {
break :blk true;
} else {
return false;
}
};
var slash_index: usize = 0;
for (target[1..], 0..) |c, i| {
if (bset2.isSet(c)) {
continue;
} else if (c == '/') {
if (!scoped) return false;
if (slash_index > 0) return false;
slash_index = i + 1;
} else if (bset3.isSet(c)) {
if (!scoped or slash_index > 0) return false;
} else {
return false;
}
}
return !scoped or slash_index > 0 and slash_index + 1 < target.len;
}
-Doptimize=ReleaseFast 下的结果
>> hyperfine -r 10000 --warmup 2000 -N "./zig-out/bin/TTT"
Benchmark 1: ./zig-out/bin/TTT
Time (mean ± σ): 786.9 µs ± 134.8 µs [User: 668.9 µs, System: 44.1 µs]
Range (min … max): 559.0 µs … 1819.6 µs 10000 runs
zig 的 std 中的 IntegerBitSet 就是掩码加位移，没有针对于数据量的不同进行特别的优化
/// Returns true if the bit at the specified index
/// is present in the set, false otherwise.
pub fn isSet(self: Self, index: usize) bool {
// assert(index < bit_length);
return (self.mask & maskBit(index)) != 0;
}
使用 bitset 厚的执行流没有之前修改的那么夸张，能够清晰的看到我们之前出现 magic number，并且有位移相关的指令
TTT[0x20bc8f] <+175>: movabs rcx, 0x7fffffe87fffffe
TTT[0x20bc99] <+185>: movabs rdx, 0x3ff600000000000
常量数组 [256]bool #
最后看一下常量的 256 元素数组来表示 Latin1 范围，128 其实也可以表示。bool 可以认为是 u1 的但是实际上 [256]u8 并不是 32 字节的，后面会说明
fn construct_array(chars: []const u8) [256]bool {
var array: [256]bool = undefined;
@memset(array[0..], false);
for (chars) |char| {
array[(@as(u8, char))] = true;
}
return array;
}
pub fn isNPMPackageName(target: []const u8) bool {
if (target.len == 0) return false;
if (target.len > 214) return false;
const array1 = comptime construct_array("ABCDEFGHIJKLMNOPQRSTUVWXYZ" ++
"abcdefghijklmnopqrstuvwxyz" ++
"0123456789" ++
"$-");
const array2 = comptime construct_array("ABCDEFGHIJKLMNOPQRSTUVWXYZ" ++
"abcdefghijklmnopqrstuvwxyz" ++
"0123456789" ++
"-_.");
const array3 = comptime construct_array("!~*'()");
const scoped = blk: {
if (array1[@as(u8, target[0])]) {
break :blk false;
} else if (target[0] == '@') {
break :blk true;
} else {
return false;
}
};
var slash_index: usize = 0;
for (target[1..], 0..) |c, i| {
if (array2[@as(u8, c)]) {
continue;
} else if (c == '/') {
if (!scoped) return false;
if (slash_index > 0) return false;
slash_index = i + 1;
} else if (array3[@as(u8, c)]) {
if (!scoped or slash_index > 0) return false;
} else {
return false;
}
}
return !scoped or slash_index > 0 and slash_index + 1 < target.len;
}
-Doptimize=ReleaseFast 下的结果
>> hyperfine -r 10000 --warmup 2000 -N "./zig-out/bin/TTT"
Benchmark 1: ./zig-out/bin/TTT
Time (mean ± σ): 785.9 µs ± 149.8 µs [User: 672.0 µs, System: 40.3 µs]
Range (min … max): 560.7 µs … 2907.7 µs 10000 runs
这次生成的函数的汇编的指令数目是最小的，摘录其中一段
TTT[0x20bec0] <+64>: movzx ecx, byte ptr [rdi + rax + 0x1]
TTT[0x20bec5] <+69>: cmp byte ptr [rcx + 0x202db0], 0x1
TTT[0x20becc] <+76>: jne 0x20beda ; <+90> at main.zig
TTT[0x20bece] <+78>: lea rcx, [rax + 0x1]
TTT[0x20bed2] <+82>: cmp rsi, rax
TTT[0x20bed5] <+85>: mov rax, rcx
TTT[0x20bed8] <+88>: jne 0x20bec0 ; <+64> at main.zig:38:23
TTT[0x20beda] <+90>: ret
此段汇编来源于第二个循环，这里 0x202db0 是 [256]bool 数组的首地址，可以看到区别于以前，这种方式使用的不是一个立即数。每次循环来判断的时候都是对内存单元的寻址，但是因为局部性原理，这里的消耗不会太大。我们也可以看到这里 byte ptr 然后直接比较的，所以其实每一个 bool 元素是按照 8 字节对齐的，[256]u8 的大小是 256 * 8 字节
Debug 模式下的结果 #
switch / if branch #
>> hyperfine -r 10000 --warmup 2000 -N "./zig-out/bin/TTT"
Benchmark 1: ./zig-out/bin/TTT
Time (mean ± σ): 14.1 ms ± 0.4 ms [User: 13.7 ms, System: 0.2 ms]
Range (min … max): 13.2 ms … 17.5 ms 10000 runs
bitset #
>> hyperfine -r 10000 --warmup 2000 -N "./zig-out/bin/TTT"
Benchmark 1: ./zig-out/bin/TTT
Time (mean ± σ): 15.0 ms ± 0.4 ms [User: 14.7 ms, System: 0.2 ms]
Range (min … max): 14.1 ms … 20.7 ms 10000 runs
[256]bool #
Benchmark 1: ./zig-out/bin/TTT
Time (mean ± σ): 13.3 ms ± 0.4 ms [User: 12.9 ms, System: 0.2 ms]
Range (min … max): 12.5 ms … 20.4 ms 10000 runs
在 Debug 模式下可以看到常量数组是速度最快的，其次是 switch 。bitset 的效果不明显。体验下来在分支判断这方面，如果数据少的话还是直接进行 switch 摊开，如果数据量大且动态那么还是要使用 bitset 来解决的。常量数组在空间使用上有点大
结论只是个大概，具体问题具体分析