Partitioning memory into slices

Help
,
1

I find myself allocating a big chunk of memory of u8s and then repartitioning it into equally sized slices of []u8. I need to build some kind of table and the slices here are the rows in that table. Now to my question:

  • Is there a good std function for this (I saw std.mem.window as the closes thing)
  • If not, how can i do this in a better way?

I just dont really like doing two allocations for this kind of problem.
Maybe I should just write my own function. Here is some example code:

const chunk = try gpa.alloc(u8, cols * rows);
defer gpa.free(chunk);
const table = try gpa.alloc([]u8, rows);
defer gpa.free(table);

var it = std.mem.window(u8, chunk, cols, cols);
for (table) |*row| row.* = it.next() orelse unreachable;
2

You could allocate your data as, or cast it to, a slice of arrays (e.g. [][10]u8) although this requires you to know one dimension at comptime.

Another option is allocating it and casting the first segment into the table


var data = try gpa.allocWithOptions(
        u8,
        @sizeOf([]u8) * rows + cols * rows,
        .fromByteUnits(@alignOf([]u8)),
        null,
    );
defer gpa.free(data);
const chunk = data[@sizeOf([]u8) * rows ..];
const table: [][]const u8 = @ptrCast(data[0 .. @sizeOf([]u8) * rows]);

var it = std.mem.window(u8, chunk, cols, cols);
for (table) |*row| row.* = it.next() orelse unreachable;

Given row and col are not comptime known when splitting it, you’re either going to have an iterator or an allocating function so I believe using std.mem.window is probably as good as you’re going to get if you don’t mind std.mem.WindowIterator.next returning ?[]const T.

edit note: corrected memory alignment as pointed out by matklad and vulpesx

3 Likes
3

Very nice doing this all in one allocation! Thank you!

4

Why is this cast correct?

5

A more useful response for @DoingGitStuff:

@alignCast only asserts the runtime alignment is correct! The data is allocated at the natural alignment of u8 (1), whereas the alignment needed for table is 8 (or 4 on x32).

In otherworlds, it is entirely possible for data to be allocated at a runtime alignment that does not pass the @alignCast safety check, crashing your code.

Instead, use allocWithOptions and pass @alignOf([]u8) as the alignment. Then you can remove the @alignCast since they will be comptime known to be the same alignment.

6 Likes
6

Thanks, tbh I forgot about alignment and just wanted an example that compiles

1 Like
7

The approach that came to my mind would be to do away with the separate table variable entirely and turn row access into a member function of a struct, something like:

const Table = struct {
    chunk: []u8,

    pub fn row(self: Table, row_index: usize) []u8 {
        return self.chunk[row_index * cols..][0..cols];
    }
}

(cols may need to be stored in the struct depending on your use case, you might also want to handle out-of-bounds row indexes)

6 Likes
8

I chose something in the middle of @DoingGitStuff and @squeek502 and I want to make it generic. More specifically I also want to be able to generate tables of u24, it’s a weird number, i know, but it’s necessary for what I’m doing.

This code compiles fine, but during runtime when I check the length of the Table(u24).table.len member, it is multiplied by 4, i.e. I encountered an issue where it should have been 4 but it was 16.

I am really new to alignment things, what am I doing wrong here?

pub fn Table(comptime T: type) type {
    return struct {
        /// table.len == rows
        /// table[0].len == cols
        table: [][]T,
        /// the backing memory of all the rows
        chunk: []T,
        /// private
        _data: []align(@alignOf([]T)) T,

        pub fn init(ac: Allocator, rows: usize, cols: usize) Allocator.Error!@This() {
            var data = try ac.allocWithOptions(
                T,
                @sizeOf([]T) * rows + cols * rows * @sizeOf(T),
                .fromByteUnits(@alignOf([]T)),
                null,
            );
            errdefer ac.free(data);

            const chunk: []T = data[@sizeOf([]T) * rows ..];
            const table: [][]T = @ptrCast(data[0 .. @sizeOf([]T) * rows]);

            for (table, 0..) |*row, r| row.* = chunk[r * cols ..][0..cols];

            return .{
                ._data = data,
                .table = table,
                .chunk = chunk,
            };
        }

        pub fn deinit(self: *@This(), ac: Allocator) void {
            ac.free(self._data);
        }
    };
}
9

I don’t know if you want a solution or just a hint. So here is a hint:

pub fn main() !void {
    std.debug.print("type | size | bitSize | align \n", .{});
    inline for ([_]type{ u8, u16, u24, u32, u40, u56, u64 }) |T| {
        std.debug.print("{:4} | {:4} | {:7} | {:5}\n", .{ T, @sizeOf(T), @bitSizeOf(T), @alignOf(T) });
    }
}
10

Thanks for the hint, I know that u24 is a aligned by 4, but I still dont get how this line const table: [][]T = @ptrCast(data[0 .. @sizeOf([]T) * rows]); builds 16 rows instead of 4 ones :<

11

The issue is not alignment; your length calculation is in bytes, but the length the alloc* function takes is in units of T. simply always alloc u8 and cast.

But you do have an alignment problem! The alignment should be the max of the alignment of all the data, that is max of T and []T.
You haven’t run into this issue yet because u24 has a smaller alignment. But you should at least document your assumption, or remove it.

Another thing to be aware of: if the header data (your table) is smaller than T you will have to add padding to your allocation, and calculate an appropriately aligned start to the chunk slice.
Much easer to just assert that isn’t the case.

Lastly, it is inefficient to store multiple slices to the same backing slice. Ofc you dont have to care about that!

2 Likes
12

Thank you! You’re right, I think it’d be easier and more readable if I just switched back to having one chunk and methods that can index rows etc. So exactly like @squeek502 proposed.

Thanks for the help!

1 Like
13

Here is a nice answer in a similar older topic that does this:

1 Like