tiehuis
commented
2 years ago The big integer routines aren't too optimized so there may be some algorithmic differences which are affecting this but a large issue is an inefficient toString implementation.
Take the following modified program:
const std = @import("std");
const Managed = std.math.big.int.Managed;
pub fn main() anyerror!void {
const allocator = std.heap.c_allocator;
var a = try Managed.initSet(allocator, 0);
defer a.deinit();
var b = try Managed.initSet(allocator, 1);
defer b.deinit();
var i: u128 = 0;
while (i < 500000) : (i += 1) {
var c = try Managed.init(allocator);
defer c.deinit();
try c.add(a.toConst(), b.toConst());
a.swap(&b);
b.swap(&c);
}
const as = try a.toString(allocator, 10, std.fmt.Case.lower);
defer allocator.free(as);
std.log.info("Fib: {s}", .{as});
std.debug.print("number of limbs = {}\n", .{a.limbs.len});
} $ time ./t
number of limbs = 5425
________________________________________________________
Executed in 5.83 secs fish external
usr time 5.70 secs 663.00 micros 5.70 secs
sys time 0.01 secs 88.00 micros 0.01 secsRemoving the toString and log results in the following for 500,000.
$ time ./t
number of limbs = 5425
________________________________________________________
Executed in 2.62 secs fish external
usr time 2.56 secs 631.00 micros 2.56 secs
sys time 0.01 secs 81.00 micros 0.01 secsThis looks to increase proprotionally. For reference I got the following times with the conversion to string removed.
1,000,000 10.41s
2,500,000 97.48sWhich looks much more in line with the Golang performance scaling. One would need to investigate toString more in detail. The algorithm used is fairly trivial for base-10 and requires a lot of divisions in the current state. There may be a smarter algorithm to convert to a string for this or some assumptions we can make note of to improve this.
derpycoder
ominitay
Ev1lT3rm1nal
Zig Version
0.10.0-dev.316+4938fb8f5
Steps to Reproduce
Run the following code using
zig build-exe ./src/main.zig -O ReleaseFast --strip -lc:Expected Behavior
The program should execute and return result in less time than Golang or Rust.
Actual Behavior
Ziglang took: (On a Mac Mini 2020 M1)
Rust took: (On a slower computer)
Golang took: (On a slower computer)
Also memory usage was upto 5.4 mb for n = 1 million, Rust kept the memory usage under 3 mb even for 10 million!!
Links: Rust & Golang Benchmark StackOverflow Issue