Implementing dynamic array of different sized types

I’m learning to write a GUI layout system, where I want to handle hierarchical structure of elements, where each element has an array of styles sorted by layout precedence. Each Style has a layout procedure associated with it so that styles can be added outside of the core lib.

Memory access pattern here is element parent id to determine if element is child of previous element, then process all styles for that element in presorted precedence [margin, border, padding], each style has associated layout procedure for example:

Margin_Start :: struct {
    top:  u8,
    left: u8,
}

margin_start :: proc(p: Position, m: Margin_Start) -> Change_Layout {
    return Change_Layout{add_x = m.left, add_y = m.top}
}

I’m wondering what the best approach is for something like that. I currently have a memory pool [dynamic]u8 where I pack:

[element_parent_id, styles_size, style_size, margin, margin_layout_proc, style_size, border, border_layout_proc, element_parent_id...]

What would be the best approach here if optimizing for memory access and not memory size ?

The suggestions here are by no means for optimizing memory access… just to get something sane looking work. That byte-packed array looks insane to me at least, structs exists for a reason.

The simple solution is to do subtyping and put things on the heap…

Layout_Proc :: #type proc(^Style) -> Change_Layout

Style :: struct {
    layout_proc: Layout_Proc,
}

Margin_Start :: struct {
    using _: Style,
    top, left: u8
}

Then you can store any style as [dynamic]^Style as long as a type is subtype of Style.
See the overview.


The slightly more complicated way is to have map[typeid]Style_Pool where

Style_Pool :: struct {
	styles:      runtime.Raw_Dynamic_Array,
	layout_proc: Layout_Proc,
}

Style :: struct {
	type: typeid,
	id:   int,
}

Styles :: map[typeid]Style_Pool

So you would have a different dynamic array for each type of style to hold it. runtime.Raw_Dynamic_Array is pretty handy if you want to take a [dynamic]T and make it opaque… :slightly_smiling_face:

Layout_Proc :: #type proc(rawptr) -> Change_Layout

register_style_type :: proc(styles: ^Styles, $St: typeid, 
                            layout_proc: Layout_Proc) {
	// FIXME: pass an allocator around...
	if St not_in styles {
		pool := make([dynamic]St)
		styles[St] = Style_Pool {
			styles      = (cast(^runtime.Raw_Dynamic_Array)&pool)^,
			layout_proc = layout_proc,
		}
	}
}

add_style :: proc(styles: ^Styles, style: $St) -> Style {
	pool := &styles[St]
	pool_styles := cast(^[dynamic]St)&pool.styles
	id := Style {
		type = St,
		id   = len(pool_styles)
	}
	append(pool_styles, style)
	return id
}

get_style :: proc(styles: Styles, style: Style) -> (rawstyle: rawptr) {
	pool, ok := styles[style.type]
	if !ok || pool.styles.len < style.id do return nil

	info := type_info_of(style.type)
	return rawptr(uintptr(pool.styles.data) + uintptr(info.size * style.id))
}

Also, Idk why you encode the parent id, you could just store the parent id in the element itself, no?

Element :: struct {
	parent: Element_Id,
	styles: [dynamic]Style,
	aabb:   [4]i32,
	// whatever else is common
}

Button :: struct {
	using _:  Element,
	text:     string,
	on_click: On_Click_Proc,
}

Thank you @zen3ger. I agree that this packed array kind of looks insane, I already did the memory size optimized way, by de-duplicating style data and having an array of elements, style_data and style_proc.

That approach worked great, but as an exercise I wanted to optimize the data layout for the pattern of access so that cache line is populated with as much useful data as possible.

Based on DoD the data layout should be optimized for access pattern, so I’m wondering if anyone had to tackle similar case to what I have described, with access pattern having data of varying size and different processing procedures for data type.

Hmm… You can probably implement it similarly to runtime.Map_Cell then.

CACHE_LINE_SIZE :: runtime.MAP_CACHE_LINE_SIZE

Packed_Cell :: struct #align(CACHE_LINE_SIZE) {
    data: [CACHE_LINE_SIZE]u8,
}

Packed :: struct {
    cells: [^]Packed_Cell,
    offsets: [^]u16,
    allocator: runtime.Allocator,
    // ... count and such
}

This way each Packed_Cell is cache line aligned/sized. Then use e.g. something like offsets[i] to check where next data starts in cell[i] (they all should at least be pointer aligned, so data starts at bitpos*8).

Edit: for retrieving data, as long as your styles contain typeid at offset 0, you could always return a any:

cast(any)runtime.Raw_Any{
    data = cast(rawptr)&packed_cell.data[data_offset], 
    id   = (cast(^typeid)&packed_cell.data[data_offset])^, 
}

I would try to figure out which elements need processing early on and then try to load their data.

[element_parent_id, styles_size, style_size, margin, margin_layout_proc, style_size, border, border_layout_proc,

Perhaps I misunderstand, but with this approach if element_parent_id doesn’t match, then a lot of unnecessary data will get loaded just to be thrown away immediately. Instead if the element ids were packed together it would be more efficent to check which ones need processing.

Thanks @waqar144, yeah I was a bit unclear I should have said that I’m not trying to solve a specific issue, I’m trying to learn how to implement this specific variable size memory layout for iteration.

I was also describing a simplified version, but this is the final form of the data it just needs to iterated over in this exact order. Also this trivial example can be solved with static types using a bit of preprocessing of the data, but I have less trivial example in full implementation.

I’m new to Odin, so after a lot of segmentation fault’s, I got a minimal working example. If anyone knows the reason why using [8]u8 size of rawptr with transmuting to the Layout_Proc works, but taking raw_data from the same range and transmuting to Layout_Proc results in segmentation fault. Looking at docs it says that “A procedure type is internally a pointer to a procedure in memory”, I’m also not sure if I’m taking the right memory address in the first place.

This is the proof of concept code, it is unsafe and handles zero edge cases, I would be grateful for any pointers to all the things I’m doing wrong in here and what are some common approaches for handling this use case:

package tests

import "core:testing"

@(test)
packed_data :: proc(t: ^testing.T) {
	pool := new_style_pool()

	m := Margin_Start {
		top  = 2,
		left = 4,
	}

	add_style_layout(pool, m, margin_start)

	style_data, layout_proc := get_style_layout(pool)

	change_layout := layout_proc(style_data)

	testing.expect_value(t, change_layout, Change_Layout{add_x = m.left, add_y = m.top})
}

Style_Pool :: struct {
	cursor: u32,
	data:   [dynamic]u8,
}

new_style_pool :: proc() -> ^Style_Pool {
	return new_clone(Style_Pool{cursor = 0, data = make([dynamic]u8)})
}

add_style_layout :: proc(
	pool: ^Style_Pool,
	style_data: $Data,
	layout_proc: proc(style_data: ^Data) -> Change_Layout,
) {
	append(&pool.data, size_of(Data))

	data_slice := transmute([size_of(Data)]u8)style_data
	append(&pool.data, ..data_slice[:])

	layout_proc_slice := transmute([size_of(Layout_Proc)]u8)layout_proc
	append(&pool.data, ..layout_proc_slice[:])
}

get_style_layout :: proc(pool: ^Style_Pool) -> (rawptr, Layout_Proc) {
	style_data_size := u32(pool.data[pool.cursor])
	pool.cursor += 1

	style_data := raw_data(pool.data[pool.cursor:pool.cursor + style_data_size])
	pool.cursor += style_data_size

	pool_layout_proc_slice := [size_of(Layout_Proc)]u8{}
	for i in 0 ..< u32(size_of(Layout_Proc)) {
		pool_layout_proc_slice[i] = pool.data[pool.cursor + i]
	}

	/* Segmentation fault.
	layout_proc := transmute(Layout_Proc)raw_data(
		pool.data[pool.cursor:pool.cursor + size_of(Layout_Proc)],
	)*/

	layout_proc := transmute(Layout_Proc)pool_layout_proc_slice

	pool.cursor += size_of(Layout_Proc)

	return style_data, layout_proc
}

Layout_Proc :: #type proc(style_data: rawptr) -> Change_Layout

Change_Layout :: struct {
	add_x: u8,
	add_y: u8,
}

Margin_Start :: struct {
	top:  u8,
	left: u8,
}

margin_start :: proc(m: ^Margin_Start) -> Change_Layout {
	return Change_Layout{add_x = m.left, add_y = m.top}
}

Edit: Just realized that, I should be casting raw_data to a pointer of Layout_Proc and then de-referencing it.

get_style_layout :: proc(pool: ^Style_Pool) -> (rawptr, Layout_Proc) {
	style_data_size := u32(pool.data[pool.cursor])
	pool.cursor += 1

	style_data := raw_data(pool.data[pool.cursor:pool.cursor + style_data_size])
	pool.cursor += style_data_size

	layout_proc := cast(^Layout_Proc)raw_data(
		pool.data[pool.cursor:pool.cursor + size_of(Layout_Proc)],
	)

	pool.cursor += size_of(Layout_Proc)

	return style_data, layout_proc^
}

Wouldn’t it be simpler to just use tagged union here assuming there are different kinds of styles that need to live in the pool? Something like:

Style_Data :: union { /* ... */}
style_pool :: struct {
   [dynamic]Style_Data
}

This will store all the datas in a buffer packed and make your life easier because you will be working with types and not raw bytes.

Also, is there a reason you want to store the layout_proc with the data? Unless every data value has a different kind of layout_proc, which is very unlikely, you can just have a bunch of proc that can be called after checking the type of data.

   if (data.(Margin_Start)) {
       layout_proc_for_margin(...)
   }

I would really suggest writing the simplest possible code.


As an aside, what you are doing is similar to what microui vendor package does (Odin/vendor/microui/microui.odin at master · odin-lang/Odin · GitHub) or my lite port (lite-odin/rencache.odin at master · Waqar144/lite-odin · GitHub). But both these pieces of code work with a fixed memory region and want to store all of the data inline, including the strings so using this kind of optimization makes sense.

2 Likes

@waqar144 thank you for those links, this is what I was looking for to get some ideas and see different possible approaches. I’m trying to learn the language so I’m mostly exploring what patterns are commonly used, and experimenting a bit to see what makes sense.

I agree with you about simplest possible code, but there are tradeoffs, union is the size of the largest member + type tag. Then you also need to specify which layout procedure will be called in a switch statement that handles all members of Style_Data union. Also not sure if there is any way for user of the library to extend the Style_Data union with their own styles, while with raw data approach, they could in theory register their own styles and specify layout and rendering procedures.

But I can see an upside of unions having type safety and code that is probably easier to understand, thank you for your time and ideas, I will try them out.