添加二进制数据的二次复杂度

$ hyperfine -M 2 -L n 10000,100000,1000000 "fq -n 'add(limit({n}; repeat(0 | tobytes))) | empty'" Benchmark 1: fq -n 'add(limit(10000; repeat(0 | tobytes))) | empty' Time (mean ± σ): 146.1 ms ± 0.9 ms [User: 298.1 ms, System: 19.9 ms] Range (min … max): 145.4 ms … 146.7 ms 2 runs

Benchmark 2: fq -n 'add(limit(100000; repeat(0 | tobytes))) | empty' Time (mean ± σ): 1.972 s ± 0.001 s [User: 7.597 s, System: 0.162 s] Range (min … max): 1.971 s … 1.973 s 2 runs

Benchmark 3: fq -n 'add(limit(1000000; repeat(0 | tobytes))) | empty' Time (mean ± σ): 86.166 s ± 0.195 s [User: 520.231 s, System: 2.294 s] Range (min … max): 86.028 s … 86.304 s 2 runs My guess is that when fq does l + r for binary data l, r, it creates a new l' = l in memory distinct from l, which results in quadratic runtime. jq avoids this e.g. for string types, by "reusing" the l if the current position is the only place where l is referenced: