#bigint code slower than expected

1 messages · Page 1 of 1 (latest)

rain ermine
#

Hi, I am new to Zig, trying to port some Go code (runs in 5 seconds) but my Zig implementation is slower (7 seconds), I would appreciate hints about how to improve the performance (sample code below, attached both examples in the thread):

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

pub fn maxTotalReward(
    allocator: std.mem.Allocator,
    rewards: []const u32,
) !u32 {
    // 1) Sort & dedupe in-place
    var vals = try allocator.dupe(u32, rewards);
    defer allocator.free(vals);
    std.mem.sort(u32, vals, {}, comptime std.sort.asc(u32));

    // Compact unique values at the front
    var write: usize = 0;
    for (vals) |v| {
        if (write == 0 or vals[write - 1] != v) {
            vals[write] = v;
            write += 1;
        }
    }
    const nums = vals[0..write];
    if (nums.len == 0) return 0;

    // 2) Initialize BigInts: dp=1, one=1, mask=0, temp=0
    var dp = try Big.initSet(allocator, 1);
    defer dp.deinit();
    var one = try Big.initSet(allocator, 1);
    defer one.deinit();
    var mask = try Big.init(allocator);
    defer mask.deinit();
    var temp = try Big.init(allocator);
    defer temp.deinit();

    // 3) Core loop: mask = (1<<r)-1; temp = (dp & mask)<<r; dp |= temp
    for (nums) |r| {
        const br: usize = @intCast(r);

        // mask = 1 << r
        try mask.shiftLeft(&one, br);
        
        // mask -= 1
        try mask.sub(&mask, &one);

        // temp = dp & mask
        try temp.bitAnd(&dp, &mask);

        // temp <<= r
        try temp.shiftLeft(&temp, br);

        // dp |= temp
        try dp.bitOr(&dp, &temp);
    }

    // 4) Compute bit-length via base-2 string
    const bin = try dp.toString(allocator, 2, .lower);
    defer allocator.free(bin);
    // bitLength = number of bits = string length; subtract 1 for max index
    return @intCast(bin.len - 1);
}
serene pendant
#

Which allocator are you using? If you're using something like std.heap.GeneralPurposeAllocator I'd recommend switching to an arena or using std.heap.SmpAllocator.

rain ermine
#

I was using std.heap.page_allocator in d.zig, let me try with another one

#

I tried with std.heap.smp_allocator but found no difference in execution time

serene pendant
#

you'll probably find a difference with using an arena for the big int operations

rain ermine
#

I am using std.heap.ArenaAllocator.init(std.heap.smp_allocator), and then creating the bigint like Big.init(allocator)

pseudo finch
#

compiled in release?

rain ermine
#

I am using zig build-exe -O ReleaseFast

rain ermine
#

Funny, even Python matches the speed of my Zig code:

def maxTotalReward(rv: list[int]) -> int:
    nums = sorted(set(rv))
    dp = 1  # Bitmask for dynamic programming
    for x in nums:
        mask = (1 << x) - 1
        new_sums = (dp & mask) << x
        dp |= new_sums
    return dp.bit_length() - 1

# Generate and use the rewards
rewards = list(range(500_000, 0, -1))
result = maxTotalReward(rewards)
print(result)
solar cargo
#

You could try linking libc and using the c_allocator to see if that changes something

rain ermine
#

thanks, I am trying with std.heap.ArenaAllocator.init(std.heap.c_allocator) and then compiling with zig build-exe -O ReleaseFast -lc but I am getting the saame results

abstract sleet
#

try return dp.bitCountAbs()

#

instead of the str allocation

rain ermine
#

still takes 7s instead of 5s for some reason. My profiling shows all the time is spend in this:

for (nums) |r| {
        const br: usize = @intCast(r);
        try mask.shiftLeft(&one, br);
        try mask.sub(&mask, &one);
        try temp.bitAnd(&dp, &mask);
        try temp.shiftLeft(&temp, br);
        try dp.bitOr(&dp, &temp);
    }
#

I think the difference is just the big int implementation between languages, Zig is implemented in Zig while Go has hand crafted assembly per architecture

azure juniper
#

Zig is pre 1.0 and bigint clearly hasn't been optimized yet. Great project for a knowledgeable dev to take on.

buoyant canyon
rain ermine
#

@buoyant canyon you are correct! I used try temp.truncate(&dp, .unsigned, br) and the code went from 7s to 3s, impressive!