commit 5b7bff417c3d32284526b446db5b7fa7180753f4
parent e9943f6c98aa1f61f8bbe318a1fd30b2f0284b7b
Author: Martin Ashby <martin@ashbysoft.com>
Date: Tue, 30 Jan 2024 23:15:50 +0000
tidy, update README
Diffstat:
| M | README.md | | | 14 | +++++++++++++- |
| M | src/main.zig | | | 121 | +++++++++++++++++++++++++++++++------------------------------------------------ |
2 files changed, 61 insertions(+), 74 deletions(-)
diff --git a/README.md b/README.md
@@ -2,4 +2,15 @@
Zig version of [One Billion Row Challenge](https://github.com/gunnarmorling/1brc)
-This is my naïve solution.
+This solution uses
+- memory-mapped input file
+- threads to divide the work
+- standard library hashmap and float parsing
+
+And on my tiny Pinebook Pro laptop it completes in about 85 seconds.
+
+The leading java solution completes (on a _standard_ JVM not graal...) in about 85 seconds on the same machine.
+
+Failures:
+- I've tried using integers instead of parsing floats, it doesn't seem to make much difference
+- I've tried playing with the hash function for the hash map. The default for StringArrayHashMap is Wyhash and none of the other options make it go faster.
+\ No newline at end of file
diff --git a/src/main.zig b/src/main.zig
@@ -4,6 +4,13 @@ pub const std_options = struct {
pub const log_level = .info;
};
+const Accumulator = struct {
+ min: f32,
+ max: f32,
+ sum: f64,
+ count: u64,
+};
+
pub fn main() !void {
var t = try std.time.Timer.start();
std.log.info("start!", .{});
@@ -26,6 +33,14 @@ pub fn main() !void {
std.log.info("finished at {} s", .{t.read() / std.time.ns_per_s});
}
+// Result must be closed with std.os.munmap
+fn open_mmap(dir: std.fs.Dir, file_path: []const u8) ![]align(std.mem.page_size) u8 {
+ var f = try dir.openFile(file_path, .{ .mode = .read_only });
+ defer f.close();
+ const stat = try f.stat();
+ return try std.os.mmap(null, stat.size, std.os.PROT.READ, std.os.MAP.PRIVATE, f.handle, 0);
+}
+
fn run(a: std.mem.Allocator, infile: []const u8, _: *std.time.Timer) ![]const u8 {
const threadcount = try std.Thread.getCpuCount();
var ress = try a.alloc(std.StringArrayHashMap(Accumulator), threadcount);
@@ -39,12 +54,12 @@ fn run(a: std.mem.Allocator, infile: []const u8, _: *std.time.Timer) ![]const u8
for (0..threadcount) |i| {
ress[i] = std.StringArrayHashMap(Accumulator).init(a);
var end = ((infile.len * (i+1)) / threadcount);
- while (infile.len > end and infile[end] != '\n') end += 1;
+ while (end < infile.len and infile[end] != '\n') end += 1;
const infile_part = infile[start..end];
const threadname = try std.fmt.allocPrint(a, "threads {}", .{i});
threadnames[i] = threadname;
threads[i] = try std.Thread.spawn(.{}, run_part, .{&ress[i], infile_part, threadname});
- start = end;
+ start = end+1;
}
defer {
for (0..threadcount) |i| {
@@ -82,56 +97,18 @@ fn run(a: std.mem.Allocator, infile: []const u8, _: *std.time.Timer) ![]const u8
try ww.writeAll(k);
try ww.writeAll("=");
const v = nxt.value_ptr.*;
- const mm = @as(i32, v.min) - 999;
- try std.fmt.format(ww, "{}.{}", .{@divTrunc(mm ,10),@abs(@rem(mm, 10))});
+ try std.fmt.format(ww, "{d:.1}", .{v.min});
try ww.writeAll("/");
- const mx = @as(i32, v.max) - 999;
- try std.fmt.format(ww, "{}.{}", .{@divTrunc(mx,10), @abs(@rem(mx, 10))});
+ try std.fmt.format(ww, "{d:.1}", .{v.max});
try ww.writeAll("/");
- const s_1 = v.sum / v.count; // mean
- const s_2 = @as(i64, @intCast(s_1)) - 999; // shift
- // std.log.warn("s_2 {}", .{s_2});
- try std.fmt.format(ww, "{}.{}", .{@divTrunc(s_2 ,10), @abs(@rem(s_2, 10))}); // scale
- //try std.fmt.format(ww, " ct {} sum {}", .{v.count, v.sum});
+ const mean = v.sum / @as(f64, @floatFromInt(v.count));
+ try std.fmt.format(ww, "{d:.1}", .{mean});
try ww.writeAll(", ");
}
try ww.writeAll("}");
return try rr.toOwnedSlice();
}
-fn merge_in(res_f: *std.StringArrayHashMap(Accumulator), res_a: *std.StringArrayHashMap(Accumulator)) !void {
- var it = res_a.iterator();
- while (it.next()) |e| {
- const r = e.value_ptr.*;
- const gpr = try res_f.getOrPut(e.key_ptr.*);
- if (gpr.found_existing) {
- const rr = gpr.value_ptr.*;
- gpr.value_ptr.* = Accumulator{
- .min = @min(rr.min, r.min),
- .max = @max(rr.max, r.max),
- .sum = rr.sum + r.sum,
- .count = rr.count + r.count,
- };
- } else {
- gpr.value_ptr.* = r;
- }
- }
-}
-
-const Accumulator = struct {
- min: u16,
- max: u16,
- sum: u64,
- count: u64,
-};
-
-fn free_keys_and_deinit(hm: *std.StringArrayHashMap(Accumulator)) void {
- for (hm.keys()) |*k| {
- hm.allocator.free(k.*);
- }
- hm.deinit();
-}
-
fn run_part(res: *std.StringArrayHashMap(Accumulator), infile: []const u8, name: []const u8) !void {
var t = try std.time.Timer.start(); // I know it's supported on my platform
var lines = std.mem.tokenizeScalar(u8, infile, '\n');
@@ -145,29 +122,9 @@ fn run_part(res: *std.StringArrayHashMap(Accumulator), infile: []const u8, name:
}
var spl = std.mem.splitScalar(u8, line, ';');
const key = spl.first();
- var val_s = spl.next() orelse unreachable;
- var val: u16 = 0;
- const is_neg: bool = val_s[0] == '-';
- if (is_neg) {
- val_s = val_s[1..];
- }
- for (val_s) |c| {
- if (c >= '0' and c <= '9') {
- const x = c - '0';
- val *= 10;
- val += x;
- }
- }
- if (is_neg) {
- val = 999-val;
- } else {
- val += 999;
- }
-
- // if (std.mem.eql(u8, key, "Istanbul")) {
- // std.log.warn("Istanbul val {}", .{val});
- // }
-
+ const val_s = spl.next() orelse unreachable;
+ const val = std.fmt.parseFloat(f32, val_s) catch unreachable;
+
if (res.contains(key)) {
const e = res.getPtr(key) orelse unreachable;
e.* = .{
@@ -188,12 +145,30 @@ fn run_part(res: *std.StringArrayHashMap(Accumulator), infile: []const u8, name:
}
}
-// Result must be closed with std.os.munmap
-fn open_mmap(dir: std.fs.Dir, file_path: []const u8) ![]align(std.mem.page_size) u8 {
- var f = try dir.openFile(file_path, .{ .mode = .read_only });
- defer f.close();
- const stat = try f.stat();
- return try std.os.mmap(null, stat.size, std.os.PROT.READ, std.os.MAP.PRIVATE, f.handle, 0);
+fn merge_in(res_f: *std.StringArrayHashMap(Accumulator), res_a: *std.StringArrayHashMap(Accumulator)) !void {
+ var it = res_a.iterator();
+ while (it.next()) |e| {
+ const r = e.value_ptr.*;
+ const gpr = try res_f.getOrPut(e.key_ptr.*);
+ if (gpr.found_existing) {
+ const rr = gpr.value_ptr.*;
+ gpr.value_ptr.* = Accumulator{
+ .min = @min(rr.min, r.min),
+ .max = @max(rr.max, r.max),
+ .sum = rr.sum + r.sum,
+ .count = rr.count + r.count,
+ };
+ } else {
+ gpr.value_ptr.* = r;
+ }
+ }
+}
+
+fn free_keys_and_deinit(hm: *std.StringArrayHashMap(Accumulator)) void {
+ for (hm.keys()) |*k| {
+ hm.allocator.free(k.*);
+ }
+ hm.deinit();
}
