Correct BigInt Fibonacci Implementation in Zig Lang

I am new to Zig Lang, and I was searching for an existing implementation for Big Int Fibonacci to no avail.

So, I went through the source code of Zig Lang, Specifically Big Int Source & Big Int Tests, to figure out how to use the Big Int functionality and then winged the desired solution.

It's sort of a tradition I follow while trying to gauge the speed of a language before learning. Like I did with: Big Int Fibonacci Benchmark for Go & Rust. (N.B. I didn't have to write the solution for those languages!)

Now, here's my implementation in Zig, for your kind perusal:

const std = @import("std");
const Managed = std.math.big.int.Managed;

pub fn main() anyerror!void {
    // var arena = std.heap.ArenaAllocator.init(std.heap.c_allocator);
    // defer arena.deinit();
    // const allocator = arena.allocator();

    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 < 50000) : (i += 1) {
        var c = try Managed.init(allocator);

        try c.add(a.toConst(), b.toConst());

        a = b;
        b = try c.clone();

        c.deinit();
    }

    const as = try a.toString(allocator, 10, std.fmt.Case.lower);
    defer allocator.free(as);
    std.log.info("Fib: {s}", .{as});
}

If I try to increase the number to 500,000, the memory usage increases to over 10 GB.

I want the program to run without memory leak for n =

    50,000 (Runs fine, with Arena & General Purpose Alloc!)
   500,000 (Mem Leak)
 1,000,000 (Mem Leak)
 5,000,000 (Mem Leak)
10,000,000 (Mem Leak)

I tried most of the allocators, page_allocator, ArenaAllocator, GeneralPurposeAllocator, to speed up the process and arrived at c_allocator. As for how to plug the memory leak, I have no clue!

P.S. I have just skimmed the documentation of ZigLang & ZigLearn to get to this point. I have no grasp of the entire language. So please go easy on me!

P.P.S. Command I used to build the app:

zig build-exe ./src/main.zig -O ReleaseFast --strip -lc

System Info: Mac Mini 2020, base variant.

Solution 1:

I figured out the solution: (Using inbuilt swap method for efficient memory swaps!)

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;

    var c = try Managed.init(allocator);
    defer c.deinit();

    while (i < 1000000) : (i += 1) {
        try c.add(a.toConst(), b.toConst());

        a.swap(&b); // This is efficient than using Clone!
        b.swap(&c); // This reduced memory leak.
    }

    const as = try a.toString(allocator, 10, std.fmt.Case.lower);
    defer allocator.free(as);
    std.log.info("Fib: {s}", .{as});
}

Using this, the memory usage went upto 3.4 mb, max, for n = 1,000,000!!

But it took a minute to finish, far slower than Rust or Golang!

P.S. I created an issue on Git: Super slow Big Int Implementation in Zig