diff options
| author | Niles Salter <Validark@pm.me> | 2023-06-22 11:32:28 -0600 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2023-06-22 17:32:28 +0000 |
| commit | 7d511d642845c860ec212b9ee39e371d3f70a68b (patch) | |
| tree | e4e58d563eaff0c35b1b56a734914d0761b5e1d2 /src/type.zig | |
| parent | c60896743d3b0776a44ac63582f51b6e64892528 (diff) | |
| download | zig-7d511d642845c860ec212b9ee39e371d3f70a68b.tar.gz zig-7d511d642845c860ec212b9ee39e371d3f70a68b.zip | |
[heapsort] Protect against integer overflow
(Firstly, I changed `n` to `b`, as that is less confusing. It's not a length, it's a right boundary.)
The invariant maintained is `cur < b`. In the worst case `2*cur + 1` results in a maximum of `2b`. Since `2b` is not guaranteed to be lower than `maxInt`, we have to add one overflow check to `siftDown` to make sure we avoid undefined behavior.
LLVM also seems to have a nicer time compiling this version of the function. It is about 2x faster in my tests (I think LLVM was stumped by the `child += @intFromBool` line), and adding/removing the overflow check has a negligible performance difference on my machine. Of course, we could check `2b <= maxInt` in the parent function, and dispatch to a version of the function without the overflow check in the common case, but that probably is not worth the code size just to eliminate a single instruction.
Diffstat (limited to 'src/type.zig')
0 files changed, 0 insertions, 0 deletions