Skip to content

Instantly share code, notes, and snippets.

@kubkon
Created December 29, 2022 15:21
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kubkon/64aac8dd23ff2458564c82d32f916e59 to your computer and use it in GitHub Desktop.
Save kubkon/64aac8dd23ff2458564c82d32f916e59 to your computer and use it in GitHub Desktop.
Why Zig?
const std = @import("std");
const math = std.math;
pub fn main() void {
const size: u32 = 1198;
std.debug.print("{d} => {d}\n", .{ size, capacityForSize(size) });
}
fn capacityForSize(size: u32) u32 {
const min_cap = math.cast(u32, @as(u64, size) * 4 / 3) orelse unreachable;
return tabulateCapacity2(min_cap);
}
// Tabulate next capacity value for a hashset using unrolled while loop instead of
// tabulating it by hand as in:
// https://github.com/llvm/llvm-project/blob/b16d04d2b921211d567b6f2eadf513d2b66bb57a/llvm/lib/DebugInfo/PDB/Native/PDBStringTableBuilder.cpp#L58
fn tabulateCapacity(min_cap: u32) u32 {
comptime var cap: u64 = 1;
inline while (comptime math.cast(u32, cap)) |next_cap| {
if (next_cap > min_cap) return next_cap;
cap = cap * 3 / 2 + 1;
// @compileLog(cap);
} else unreachable;
}
fn tabulateCapacity2(min_cap: u32) u32 {
comptime var cap: u32 = 1;
inline while (true) {
if (cap > min_cap) return cap;
comptime var next_cap = @as(u64, cap) * 3 / 2 + 1;
cap = comptime math.cast(u32, next_cap) orelse return cap;
// @compileLog(cap);
}
}
❯ zig run main.zig
1198 => 2396
❯ zig run main.zig
main.zig:19:9: error: found compile log statement
@compileLog(cap);
^~~~~~~~~~~~~~~~
Compile Log Output:
@as(u64, 2)
@as(u64, 4)
@as(u64, 7)
@as(u64, 11)
@as(u64, 17)
@as(u64, 26)
@as(u64, 40)
@as(u64, 61)
@as(u64, 92)
@as(u64, 139)
@as(u64, 209)
@as(u64, 314)
@as(u64, 472)
@as(u64, 709)
@as(u64, 1064)
@as(u64, 1597)
@as(u64, 2396)
@as(u64, 3595)
@as(u64, 5393)
@as(u64, 8090)
@as(u64, 12136)
@as(u64, 18205)
@as(u64, 27308)
@as(u64, 40963)
@as(u64, 61445)
@as(u64, 92168)
@as(u64, 138253)
@as(u64, 207380)
@as(u64, 311071)
@as(u64, 466607)
@as(u64, 699911)
@as(u64, 1049867)
@as(u64, 1574801)
@as(u64, 2362202)
@as(u64, 3543304)
@as(u64, 5314957)
@as(u64, 7972436)
@as(u64, 11958655)
@as(u64, 17937983)
@as(u64, 26906975)
@as(u64, 40360463)
@as(u64, 60540695)
@as(u64, 90811043)
@as(u64, 136216565)
@as(u64, 204324848)
@as(u64, 306487273)
@as(u64, 459730910)
@as(u64, 689596366)
@as(u64, 1034394550)
@as(u64, 1551591826)
@as(u64, 2327387740)
@as(u64, 3491081611)
@as(u64, 5236622417)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment