A defer-safe way to allocate nested arrays

Help
1

Use case: I’m generating MIP levels of a texture. Type hierarchy:

const Texture = struct {
    levels: []Level,
};
const Level = struct {
    width: u16,
    height: u16,
    pixels: []Color,
};
const Color = struct {
    r: u8,
    g: u8,
    b: u8,
};

I can allocate levels in my init:

const levels = try allocator.alloc(Level, n_levels);
errdefer allocator.free(levels);

But how do I allocate levels themselves such that everything gets freed if I fail in the middle of the process?

for (0..n_levels) |i| {
    const level_size = some.math();
    levels[i] = try allocator.alloc(Color, level_size);
    // cannot errdefer here, will go out of scope before doing anything
    populate(levels[i]);
}

One workaround that comes to mind is

const levels = try allocator.alloc(Level, n_levels); // returns uninitialized
// initialize each item such that it is safe to free
for (levels) |*level| {
    level.* = .{
        .width = 0,
        .height = 0,
        .pixels = &.{},
    };
}
errdefer freeLevels(allocator, levels);

...

fn freeLevels(allocator: std.mem.Allocator, levels: []Level) {
    for (levels) |level| {
        allocator.free(level.pixels);
    }
    allocator.free(levels);
}

It seems like this should work, but that’s a lot of boilerplate which only becomes more convoluted with depth. Is there a better way?

2

I think you should first try to use defer, in some situations it can be used instead of errdefer; there are situations where errdefer is really needed, but when defer suffices then the code usually becomes a lot simpler. (because both erroring and successfull code paths end up using the same code to handle the resources)

const Texture = struct {
    levels: []Level,
};
const Level = struct {
    width: u16,
    height: u16,
    pixels: []Color,

    pub const empty: Level = .{
        .width = 0,
        .height = 0,
        .pixels = &.{},
    };
};
const Color = struct {
    r: u8,
    g: u8,
    b: u8,
};

fn example(allocator: std.mem.Allocator, n_levels: u8) !void {
    const levels = try allocator.alloc(Level, n_levels);
    defer allocator.free(levels);
    @memset(levels, .empty);
    defer for (levels) |*level| allocator.free(level.pixels);

    for (levels, 0..) |*level, size| {
        const s: u16 = @intCast(size);
        level.* = .{
            .width = s,
            .height = s,
            .pixels = try allocator.alloc(Color, size * size),
        };
    }
}

test Level {
    const length: u8 = 255;
    const allocator = std.testing.allocator;
    try std.testing.checkAllAllocationFailures(allocator, example, .{length});
}

const std = @import("std");

Also remember to write tests that use std.testing.checkAllAllocationFailures to make sure you have handled all possible failure states. (Like for example half initialized state that is being deinitialized, which is easy to get wrong when using errdefer)

5 Likes
3

Multiple ways:
A: you could have arena that you store in the texture so you can free everything at one go by deiniting the arena
B:

var n_levels_allocated: usize = 0;
errdefer freeLevels(allocator, levels[0...n_levels_allocated]);
for (0..n_levels) |i| {
    const level_size = some.math();
    levels[i] = try allocator.alloc(Color, level_size);
    // cannot errdefer here, will go out of scope before doing anything
    populate(levels[i]);
    n_levels_allocated += 1;
}

C: Allocate the levels + all the memory needed to hold pixel data as single interleaved chunk
D: Make levels not dynamic since it’s probably low number of elements anyhow like 3-5, you still would need a cleanup strategy for the pixels.

5 Likes
4

You do not need to define a function. Use a block.

const levels = try allocator.alloc(Level, n_levels);

for (levels) |*level| level.pixels = &.{};

errdefer {
    for (levels) |level| allocator.free(level.pixels);
    allocator.free(levels);
}
2 Likes
5

So, since mip levels are half of the width and height of the previous level, you don’t really need to have the Level struct store width and height; the index of the current mip level allows you to derive its width and height.
In a similar vein, the index of the current mip level can also allow you to derive its offset into the pixel buffer.
The result might end up looking like this:

const Texture = struct{
	resolution_x: u16,
	resolution_y: u16,
	pixels: [*]Color,
	miplevel_count: u16,
	
	/// Get the slice of the pixel buffer representing a given miplevel.
	/// Prefer calling .deinit() instead of freeing the returned slice.
	pub fn miplevel(self: Texture, miplevel_index: usize) []Color {
		var i_start: usize = 0;
		var current_res_x: usize = @as(usize, self.resolution_x);
		var current_res_y: usize = @as(usize, self.resolution_y);
		for(0..miplevel_index + 1) |_| {
			i_start += current_res_x * current_res_y;
			current_res_x = @divExact(current_res_x, 2);
			current_res_y = @divExact(current_res_y, 2);
		}
		return self.pixels[i_start..i_start + current_res_x * current_res_y];
	}
	
	/// The total number of pixels across all mip levels.
	/// Useful for allocating and freeing the texture's pixel value.
	pub fn pixel_count(self: Texture) usize {
		var out: usize = 0;
		var current_res_x: usize = @as(usize, self.resolution_x);
		var current_res_y: usize = @as(usize, self.resolution_y);
		for(0..self.miplevel_count + 1) |_| {
			out += current_res_x * current_res_y;
			current_res_x = @divExact(current_res_x, 2);
			current_res_y = @divExact(current_res_y, 2);
		}
		return out;
	}
	
	pub fn init(
		alc: std.mem.Allocator,
		resolution_x: u16, resolution_y: u16,
		miplevel_count: u16,
	) error{OutOfMemory}!Texture {
		var out: Texture = .{
			.resolution_x = resolution_x,
			.resolution_y = resolution_y,
			.pixels = undefined,
			.miplevel_count = miplevel_count,
		};
		const pixels = try alc.alloc(Color, out.pixel_count());
		out.pixels = pixels.ptr;
		return out;
	}
	
	pub fn deinit(self: Texture, alc: std.mem.Allocator) void {
		alc.free(self.pixels[0..self.pixel_count()]);
	}
};

test Texture {
	var texture: Texture = try .init(
		std.testing.allocator,
		1024, 1024,
		3,
	);
	defer texture.deinit(std.testing.allocator);
	
	for(0..3) |miplevel| {
		const miplevel_slice = texture.miplevel(miplevel);
		std.debug.print(
			\\MIPLEVEL {d}
			\\BEGIN: 0x{X}
			\\LEN: 0x{X}
			\\
		, .{
			miplevel,
			@as(usize, @intFromPtr(miplevel_slice.ptr)) -
			@as(usize, @intFromPtr(texture.pixels))
			,
			miplevel_slice.len,
		});
	}
}

Assuming that textures will be largely static, you could probably improve performance by storing pixel_count and/or a buffer of miplevel pixel offsets as a struct field.

2 Likes
6

This is definitely part of the puzzle. I got stuck in the C land and didn’t realize/forgot that @memset could use arbitrary initializers, and you could have a predefined .empty value. Very idiomatic.

:+1:

Is it common to make tiny arenas for individual actions? Doesn’t this create memory pressure in itself?

I’m not a fan… Not only you need to remember to increment this, but you also need to dothis in the exact right place. I feel like this would be a refactoring hazard.

That would be a very reasonable approach if I was optimizing my game engine. This wasn’t my intention – which you couldn’t know of course. My intended question was how to deal with such recursive allocations if I really had to do it. Another example would be parsing a rich text where a document consists of pages which consist of blocks which consist of spans. Also, even though my actual tool does build kind of mip maps, it is not limited to square power of 2 exactly divisible sizes.

Again this is a workaround which might work in this particular case but cannot be generalized. I’m trying to get a feel for the language, not to solve a particular optimization problem.

That’s a useful trick to know.

2 Likes
7

My intended question was how to deal with such recursive allocations if I really had to do it.

If necessary, I would do what @truly-not-taken and @Sze suggested, but code like this is not what I would write in Zig (and C).

I know that this is a specific “how to handle this scenario in Zig”, but part of Zig’s philosophy to me is that it forces you to think about the underlying domain’s constraints, so I will add my 2 cents on how I would approach this:

Instead of mixing the object’s logic with allocation, I’d try to decouple object and allocation to mostly sidestep the book keeping complexity that comes from hierarchical allocations.

If I know all these sub-allocations will live as long as their parent allocations, then they all live in the same arena then call it a day. Adapting @Sze 's example:

fn example(arena: std.mem.Allocator, n_levels: u8) !void {
    const levels = try arena.alloc(Level, n_levels);
    @memset(levels, .empty);

    for (levels, 0..) |*level, size| {
        const s: u16 = @intCast(size);
        level.* = .{
            .width = s,
            .height = s,
            .pixels = try arena.alloc(Color, size * size),
        };
    }
}

test Level {
	var arena_back = std.heap.ArenaAllocator.init(std.testing.allocator);
	defer arena_back.deinit();

    const length: u8 = 255;
    try std.testing.checkAllAllocationFailures(arena_back.allocator(), example, .{length});
}

The real gain here is pushing allocation concerns up in the execution flow and callstack, and minimizing its interference with the program’s logic.

Of course there may be scenarios where you may have longer-lived objects and you may want to reuse memory, so you don’t want to throw everything away. In the most general case I tend to mix Pools and Arenas—but getting into that would make this a lot longer, and will deviate too much from the more concrete question : ).

Again this is a workaround which might work in this particular case but cannot be generalized. I’m trying to get a feel for the language, not to solve a particular optimization problem.

I’m not sure if I would consider the above as optimizations, they are very much inline with how systems programming encourage you to think about the underlying domain rather than create a general abstraction in a lab with a spherical cow.

Creating a general abstract—no assumptions made—solution will not give an accurate feel for the language, so even in an abstract sense, many answers will nudge towards “we can simplify this with this assumption about the domain”. I.e. if everything is a variable, there is no constant to stand on.

4 Likes
8

I would simplify the whole data structure setup tbh. Technically you don’t need all that redundant per-mip-level info, instead you only need the width and height of the top-most mip-level and the number of mipmaps.

From that you can compute:

  • the size of each mipmap (block-size-restrictions for some pixel formats in mind, e.g. compressed formats like BCn)
  • the offset of each mipmap surface in a single chunk of memory that holds all miplevels

That way you don’t need a slice of mip levels, and only a single allocation for all pixel data.

The DirectXTexUtils have a nice reference function for how to compute the ‘surface pitch’ of a mip level given its pixel format, width and height:

In sokol-gfx I have simplified that a bit to:

…_sg_block_dim() and _sg_block_bytesize():

…and finally _sg_pixelformat_bytesize for linear texture formats:

…since you only seem to care about linear RGB-data, you can skip most of that complexity though :smiley:

E.g. the size of your miplevels is simply w * h * 3, where each lower miplevel is half the width and height. One thing I would change is to store a pixel in an u32, or a packed [4]u8 struct, even if you don’t have an alpha channel - 4 is just a nicer number than 3, and it even might speed things up a bit when pixels are 4-bytes–aligned instead of 3-bytes-aligned.

4 Likes
9

Well, any language forces you to avoid things that are hard to do in that particular language. If it was Go, or C#, or Python, or even C++, I would just allocate and forget about it. Because it’s a command line tool which handles one texture at a time, and allocation is not the interesting part. But I’m learning Zig. And when handling multiple allocations felt hard I thought that maybe I was missing something. Turns out I didn’t, at least not anything big. @Sze pointed out a few minor things that can help. But otherwise it’s similar to C. Maybe not as hard, thanks to defer and a library of allocators, but on the same level of hard.

If you must know… :smiley: I’m building a tool which converts a normal map into a bump/displacement map. Partly for fun, partly to make Skyrim character models 3D-printable. And I thought that it would be a good Zig learning project. So no, I’m not interested in RGB. I’m interested in diagonal and cross-diagonal slopes which I then use for number crunching.

1 Like
10

My go to way to allocate slice of resources is to use temporary ArrayList which is allocated to have exactly capacity equal to number of elements. And in errdefer you can clean up only elements which were actually successfully allocated.

const std = @import("std");
const Texture = struct {
    levels: []Level,
};
const Level = struct {
    width: u16,
    height: u16,
    pixels: []Color,
};
const Color = struct {
    r: u8,
    g: u8,
    b: u8,
};

fn init(gpa: std.mem.Allocator, n_levels: usize) !Texture {
    var levels: std.ArrayList(Level) = try .initCapacity(gpa, n_levels);
    defer {
        for (levels.items) |level| gpa.free(level.pixels);
        levels.deinit(gpa);
    }

    for (0..n_levels) |i| {
        const mip_size = @as(u16, 1) << @intCast(i);
        const colors = try gpa.alloc(Color, @as(u32, mip_size) * mip_size);
        @memset(colors, .{ .r = 0, .g = 0, .b = 0 });
        levels.appendAssumeCapacity(.{
            .width = mip_size,
            .height = mip_size,
            .pixels = colors,
        });
    }

    return .{ .levels = levels.toOwnedSliceAssert() };
}

fn deinit(texture: Texture, gpa: std.mem.Allocator) void {
    for (texture.levels) |level| gpa.free(level.pixels);
    gpa.free(texture.levels);
}

test {
    try std.testing.checkAllAllocationFailures(std.testing.allocator, struct {
        fn foo(gpa: std.mem.Allocator) !void {
            const texture = try init(gpa, 10);
            std.debug.assert(texture.levels.len == 10);
            defer deinit(texture, gpa);
        }
    }.foo, .{});
}

Notice how you don’t need any errdefer since I think they are harder to reason about. Regular defer always triggers but toOwnedSliceAssert() replaces ArrayList’s slice with empty so deinit is a nope.
It also doesn’t require to have an empty state for your type.
You can also notice a test which checks for proper cleanup in all possible places so you can be sure its correct.

2 Likes