在 Zig Lang 中正确实现 BigInt Fibonacci

Question

我是 Zig Lang 的新手，我一直在寻找 Big Int Fibonacci 的现有实现，但无济于事。

所以，我查看了 Zig Lang 的源代码，特别是 Big Int Source & Big Int Tests，以弄清楚如何使用 Big Int 功能，然后获得了所需的解决方案。

这是我在学习之前尝试衡量语言速度时遵循的一种传统。就像我做的那样：Big Int Fibonacci Benchmark for Go & Rust。（N.B。我不必为那些语言编写解决方案！）

现在，这是我在 Zig 中的实现，供您细读：

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});
}

如果我尝试将数字增加到 500,000，内存使用量会增加到超过 10 GB。

我希望程序运行没有内存泄漏 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)

我尝试了大部分分配器，page_allocator, ArenaAllocator, GeneralPurposeAllocator，以加快进程并到达 c_allocator。至于内存泄漏怎么堵，我也不知道！

P.S。我刚刚浏览了 ZigLang 和 ZigLearn 的文档以了解这一点。我不掌握整个语言。所以请放轻松！

P.P.S。我用来构建应用程序的命令：

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

系统信息：Mac Mini 2020，基本型号。

Answer 1

我找到了解决方案：（使用内置交换方法进行高效内存交换！）

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});
}

使用这个，内存使用量上升到 3.4 MB，最大值，n = 1,000,000!!

但是花了一分钟才完成，比 Rust 或 Golang 慢多了！

P.S。我在 Git 上创建了一个问题：Super slow Big Int Implementation in Zig

Answer 2

查看您的原始代码，您似乎在每个循环中都泄漏 a。我认为你需要在分配 b 之前释放它。

在 Zig Lang 中正确实现 BigInt Fibonacci

Correct BigInt Fibonacci Implementation in Zig Lang

memory

biginteger

allocator

zig