Creating a big 2D array

Help
,
1

I want to create a big 2D array. Because the array is fairly big, I’m trying to allocate the majority of the data on the heap. But for some reason I’m causing a segmentation fault in the program, and I’m not really sure why.

The segmentation fault happens on the stdout.print() line.

const std = @import("std");
const stdout = std.io.getStdOut().writer();

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    const allocator = gpa.allocator();
    const Random = std.crypto.random;
    const n: usize = 1000;
    var A: [n][]u64 = undefined;
    var B: [n][]u64 = undefined;
    var C: [n][]u64 = undefined;
    for (0..n) |i| {
        A[i] = try allocator.alloc(u64, n);
        B[i] = try allocator.alloc(u64, n);
        C[i] = try allocator.alloc(u64, n);
        defer allocator.free(A[i]);
        defer allocator.free(B[i]);
        defer allocator.free(C[i]);

        for (0..n) |j| {
            const random_num = Random.int(u8);
            A[i].ptr[j] = random_num;
            B[i].ptr[j] = random_num;
            C[i].ptr[j] = 0;
        }
    }

    try stdout.print("{any}\n", .{A[0].ptr[0]});
}
2

You’re allocating and then immediately deallocating these arrays at the end of each iteration.

Did you mean to write this?

        A[i] = try allocator.alloc(u64, n);
        errdefer allocator.free(A[i]);

        B[i] = try allocator.alloc(u64, n);
        errdefer allocator.free(B[i]);

        C[i] = try allocator.alloc(u64, n);
        errdefer allocator.free(C[i]);
2 Likes
3

Uhmm you are right. I forgot that defer executes the expression at the end of the current scope, and that, the for loop is a scope by itself.

4

Is amazing how we forget the most basic things sometimes. The program is causing a segmentation fault, because when I try to access the element of the array in the stdout.print line, the array does not exist anymore, because it was deallocated by the free() operation that is executed at the end of the for loop scope.

So, you can fix the program by either:

  • following @jmc suggestion on transforming the defer’s in errdefer’s.
  • or moving the free operations to the end of the main’s function scope.

Thank you so much for the help @jmc !

const std = @import("std");
const stdout = std.io.getStdOut().writer();

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    const allocator = gpa.allocator();
    const Random = std.crypto.random;
    const n: usize = 100;
    var A: [n][]u64 = undefined;
    var B: [n][]u64 = undefined;
    var C: [n][]u64 = undefined;
    for (0..n) |i| {
        A[i] = try allocator.alloc(u64, n);
        B[i] = try allocator.alloc(u64, n);
        C[i] = try allocator.alloc(u64, n);
        for (0..n) |j| {
            const random_num = Random.int(u8);
            A[i].ptr[j] = random_num;
            B[i].ptr[j] = random_num;
            C[i].ptr[j] = 0;
        }
    }

    try stdout.print("{any}\n", .{A[0].ptr[0]});

    for (0..n) |i| {
        allocator.free(A[i]);
        allocator.free(B[i]);
        allocator.free(C[i]);
    }
5

Just curious. Would that not open the code up to a possible memory leak if an error occurred somewhere in the above for loops and it never reached that last for loop? If that could be possible then what would the solution be then?

I realize that in this particular example, it might not be possible, but say the code was more complex.

Thanks,
Glenn

6

Two quick observations:

  • n is constant, so if you want a 2D array on the stack you could just do:

    const std = @import("std");

pub fn main() !void {
  const stdout = std.io.getStdOut().writer();
  const Random = std.crypto.random;
  const n: usize = 1000;
  var A: [n][n]u64 = undefined;
  var B: [n][n]u64 = undefined;
  var C: [n][n]u64 = undefined;
  for (0..n) |i| {
      for (0..n) |j| {
          const random_num = Random.int(u8);
          A[i][j] = random_num;
          B[i][j] = random_num;
          C[i][j] = 0;
      }
  }

  try stdout.print("{any}\n", .{A[0][0]});
}

    Of course, this would only work for reasonably small values of n and only live as long as the scope they’re defined in.

  • Since this is a case of more complex initialization/deinitialization (e.g. the allocation of the rows of this 2D array could fail after some other allocations have succeeded, and you would need to ensure proper cleanup). For that I would consider using helper methods to allocate/free the array as needed and properly handle edge cases so that they can be used in defer/errdefer contexts:

    const std = @import("std");

fn allocArray(comptime T: type, allocator: std.mem.Allocator, comptime n: usize) std.mem.Allocator.Error![][]u64 {
    var arr = try allocator.alloc([]T, n);
    var rows: usize = 0;
    errdefer {
        for (0..rows) |i| {
            allocator.free(arr[i]);
        }
        allocator.free(arr);
    }

    while (rows < n) : (rows += 1) {
        arr[rows] = try allocator.alloc(T, n);
    }
    return arr;
}

fn freeArray(allocator: std.mem.Allocator, arr: [][]u64) void {
    for (0..arr.len) |i| {
        allocator.free(arr[i]);
    }
    allocator.free(arr);
}

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    const allocator = gpa.allocator();
    const Random = std.crypto.random;
    const stdout = std.io.getStdOut().writer();

    const n: usize = 1000;
    var A = try allocArray(u64, allocator, n);
    defer freeArray(allocator, A);
    var B = try allocArray(u64, allocator, n);
    defer freeArray(allocator, B);
    var C = try allocArray(u64, allocator, n);
    defer freeArray(allocator, C);
    for (0..n) |i| {
        for (0..n) |j| {
            const random_num = Random.int(u8);
            A[i][j] = random_num;
            B[i][j] = random_num;
            C[i][j] = 0;
        }
    }

    try stdout.print("{any}\n", .{A[0][0]});
}
1 Like
7

You might consider to actually allocate arrays of size n*n instead of arrays of slices. Then you have way fewer allocations to create / clean up. On the downside, the 2D index math is now on you:

const std = @import("std");
const stdout = std.io.getStdOut().writer();

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    const allocator = gpa.allocator();
    const Random = std.crypto.random;
    const n: usize = 100;
    var A: []u64 = try allocator.alloc(u64, n * n);
    defer allocator.free(A);
    var B: []u64 = try allocator.alloc(u64, n * n);
    defer allocator.free(B);
    var C: []u64 = try allocator.alloc(u64, n * n);
    defer allocator.free(C);

    for (0..n) |i| {
        for (0..n) |j| {
            const random_num = Random.int(u8);
            A[i * n + j] = random_num;
            B[i * n + j] = random_num;
            C[i * n + j] = 0;
        }
    }

    try stdout.print("{any}\n", .{A[0 * n + 0]});
}
8

I think the best solution would be to allocate the entire 2d array in one piece on the heap, instead of allocating them in parts. This is much simpler and should give you a better memory layout:

const A: *[n][n]u64 = try allocator.create([n][n]u64);
defer allocator.destroy(A);
8 Likes