5 ms·
Implementing a Struct of Arrays
- Enthouan 1y agoI’m definitely missing the point, but reading the article, I kept thinking "This would’ve been so much easier in C."
- deleted 1y ago[deleted]
- trealira 1y agoI don't see how it would be easier. Whatever you can do in C, you can do in C++. That said, I was also a bit confused, since I guess I don't keep up with the latest C++ updates enough.
- quotemstr 1y agoNo, it would be impossible in C, the "it" here being the automatic conversion of a struct to an array of the struct's fields. Sure, you can do that pretty easily by hand in C, but you can also do it easily by hand in C++, so whatever. The point of the article is the metaprogramming.
- zahlman 1y agoI get the impression that ("pure") C programmers say things like that because they don't get themselves into situations where they feel they'd want the metaprogramming.
- quotemstr 1y agoThey might think that they don't need metaprograming, but like everyone else, they eventually do. That's how we get monstrosities like https://github.com/freebsd/freebsd-src/blob/master/sys/sys/queue.h https://github.com/freebsd/freebsd-src/blob/master/sys/sys/q... (plenty of Linux equivalents --- e.g. the tracepoint stuff) Better to use a language with thoughtful metaprogramming than tack it on badly later.
- em-tg 1y ago[dead]
- TheHideout 1y agoSo, basically it's allowing you to use a struct like you would in OOP, but get the array benefits of ECS when that struct is in a vector?
- throwawaymaths 1y agoIsn't ECS often Type-Heterogeneous? I think you mean DoD.
- dgb23 1y agoIt's not necessary to think about the data interface in terms of object orientation. You can think about it as being a composition of fields, which are individually stored in their respective array. (Slightly beside the point: Often they are also stored in pairs or larger, for example coordinates, slices and so on are almost always operated on in the same function or block.) The benefit comes from execution. If you have functions that iterate over these structs, they only need to load the arrays that contain the fields they need. Zig does some magic here based on comptime to make this happen automatically. An ECS does something similar at a fundamental level. But usually there's a whole bunch of additional stuff on top, such as mapping ids to indices, registering individual components on the fly, selecting a components for entities and so on. So it can be a lot more complicated than what is presented here and more stuff happens at runtime. It is also a bit of a one size fits all kind of deal. The article recommends watching Andrew Kelley's Talk on DoD, which inspired the post. I agree wholeheartedly, it's a very fun and interesting one. One of the key takeaways for me is that he didn't just slap on a design pattern (like ECS), but went to each piece individually, thought about memory layout, execution, trade offs in storing information versus recalculating, doing measurements and back of the envelope calculations etc. So the end result is a conglomerate of cleverly applied principles and learnings.
- jayd16 1y agoMore like they used reflection to take a struct and generate a SOA collection for that type. Funnily enough, they skip the part where you can actually get at the arrays and focus on the struct type deconstruction and construction.
- monkeyelite 1y agoInterest in SOA is bringing to mind the “art of the meta object protocol” which argues for a stage between class definition and implementation that would allow you to choose the layout and access method for instances of a class.
- deleted 1y ago[deleted]
- corysama 1y agoYep. We’re in a situation where C-like languages couple layout and access interface very tightly. But, now cache is such an overriding issue in optimization, you really want to rapidly experiment with different layouts without rewriting your whole algorithm every time. AOS, SOA, AOSOA, hot/cold data for different stages, etc… Jon Blow’s Jai language famously added a feature to references that allowed you to easily experiment with moving data members between hot/cold arrays of structs. https://halide-lang.org/ https://halide-lang.org/ tackles a related problem. It decouples the math to be done from the access order so as to allow you to rapidly test looping over data in complicated ways to achieve cache-friendly access patterns for your specific hardware target without rewriting your whole core loop every time. Halide is primarily an about image processing convolution kernels. I’m not sure how general purpose it can get.
- tialaramex 1y agoAIUI Jai no longer has that SOA versus AOS functionality which Jon was very proud of when he invented it, I expect it's one of those "hot idea" things where for one week it seems as though this is a breakthrough with applications everywhere and then a week later you realise it was not as fundamental and you were just seeing applications everywhere due to recency illusion. The week after I first saw a Bloom Filter I imagined lots of places this would surely be great, in the decades since I probably have one bona fide use for a Bloom Filter per year, maybe less.
- monkeyelite 1y agoExactly. The SOA thing makes sense in so few cases - usually the one big data type your program operates on.
- sph 1y agodefine_aggregate(^^Pointers, nsdms(^^T) | std::views::transform([](std::meta::info member){ return data_member_spec(add_pointer(type_of(member)), {.name = identifier_of(member)}); })); What operator is ^^type?
- diath 1y agohttps://isocpp.org/files/papers/P2996R4.html#the-reflection-operator https://isocpp.org/files/papers/P2996R4.html#the-reflection-...
- tialaramex 1y agoback in R4 this operator is spelled ^ but in the accepted draft it was spelled ^^
- tialaramex 1y agoThis is the reflection operator. The committee† spent some time bikeshedding different squiggles for this operator, but eventually it looks like ^^ won because it was least awful. † WG21 of SC22 of JTC1 between ISO and the IEC, "the C++ committee". See P2996R11 for the latest draft of the work - https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p2996r11.html#the-reflection-operator https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p29...
- PessimalDecimal 1y agoI started thinking this would be a rehashing of how column-oriented storage formats can be far more efficient for certain access patterns. But it really was a showcase of what a bloated mess C++ has become.
- monkeyelite 1y agoAnd you just do not need to be doing this. Just write out which columns you need and use an index. You can write generic sort and remove, and just overload the swap function for your SOA thing.
- pragma_x 1y agoThat was my takeaway as well. Pivoting a conventional structure in a column-major storage system just smells like a look-aside of some kind (a database). Plus, you lose the benefits of bulk copy/move that the compiler will likely give you in a standard struct (e.g. memcpy()), should it be on the big side. From there, we can use lots of other tricks to further speed things up: hashes, trees, bloom filters... At the same time, I don't completely understand how such a pivot would result in a speedup for random access. I suppose it would speed up sequential access, since the multiple array storage scheme might force many more cache line updates.
- thesz 1y agoThese days one's program rarely does purely sequential random access. Usually, there are several threads or requests, all going into same data structure. In the extreme case where all memory accesses of a immensely massively parallel program are deferred, the result is complete absence of cache misses [1]. [1] https://disneyanimation.com/technology/hyperion/ While our programs usually not ran at Hyperion scale, they still can benefit from accesses shared between processing of several requests. For one such example, consider speech recognition with the HCLG graph. That graph is created through composition of four WFST [2] graphs, the last one is Grammar, derived from SRILM n-gram language model. This HCLG graph has scale free property [3] due to all G FST states has to backoff to the order-0 model, and some states are visited exponentially often than others. [2] https://en.wikipedia.org/wiki/Finite-state_transducer#Weighted_automata [3] https://en.wikipedia.org/wiki/Scale-free_network By sorting HCLG graph states by their fan-ins (number of states referring to a particular one), we sped recognition process up 5%. E.g., most referred state gets index 0, second most referred is 1, etc, and that's it. No code change, just preprocessing step that, I believe, lessen the pressure on the CPU's memory protection subsystem. The speech recognition process with HCLG graph uses beam search [4], there are several (9-20) hundredths of states in the beam front to be evaluated. Most of them have outgoing arc to some of the most visited (fan-in) states. By having these states close to each other we incur less page faults exception handling during processing. [4] https://en.wikipedia.org/wiki/Beam_search Basically, we shared more MMU information between requests in beam front. PS Fun fact: WFST created by OpenFST has "structure of arrays" layout. ;)
- mac3n 1y agoJOVIAL language had TABLE structures, which could be declared SERIAL or PARALLEL (https://ntrl.ntis.gov/NTRL/dashboard/searchResults/titleDetail/PB82135062.xhtml https://ntrl.ntis.gov/NTRL/dashboard/searchResults/titleDeta... page 281).
- gr4vityWall 1y agoInteresting article. It does show how modern C++ can be quite scary. It reminded me of a Haxe macro used by the Dune: Spice Wars devs to transform an AoS into a SoA at compile time to increase performance: https://youtu.be/pZcKyqLcjzc?t=941 https://youtu.be/pZcKyqLcjzc?t=941 The end result is quite cool, though those compile time type generation macros always look too magical to me. Makes me wonder if just getting values using an index wouldn't end up being more readable.
- gpderetta 1y agoThe use of reflection is interesting, but is there a significant advantage, compared to something like this: template<template<class> class G> struct Point { G<int> x; G<int> y; auto get() { return std::tie(x,y); } }; template<template<template<class> class> class C> struct SOA { template<class T> using Id = T; template<class T> using Ref = T&; C<std::vector> vs; void push_back(C<Id> x) { std::apply([&] (auto&&... r) { std::apply([&](auto&&... v){ ( (r.push_back(v)),...); }, x.get()); }, vs.get()); } C<Ref> operator[](size_t i) { return std::apply([&] (auto&&... r) { return C<Ref>{ r[i]...}; }, vs.get()); } }; int main() { SOA<Point> soa_point; soa_point.push_back({1,2}); auto [x,y] = soa_point[0]; }
- the__alchemist 1y agoI think I've lost the thread on the abstractions. (Me not being very familiar with Zig outside of its most basic syntax is probably why.) I've been doing a lot of SoA work in rust lately; specifically because I have numerical/scientific code that uses CPU SIMD and CUDA; SoA works great for these. The workflow is, I set up Vec3x8, and Quaternionx8, which wrap a simd instrinsic for each field (x: f32x8, y: f32x8...) etc. For the GPU and general flattening, I just pack the args as Vecs, then the fn signature contains them like eps: &[f32], sigma: &[f32] etc. So, I'm having trouble mapping this SoA approach to the abstractions used in the article. Then the (C++-like CUDA) kernel sees these as *float3 params etc. It also feels like a complexity reverse of the Rust/Zig stereotypes... Examples: struct Vec3x8 { x: f32x8, y: f32x8, z: f32x8 } // appropriate operator overloads... struct Setup { eps: Vec<f32>, sigma: Vec<f32>, } So, Structs of Arrays, plainly. Are the abstractions used here something like Jai is attempting, where the internal implementation is decoupled from the API, so you don't compromise on performance vice ergonomics?
- jcelerier 1y ago> The workflow is, I set up Vec3x8, and Quaternionx8, which wrap a simd instrinsic for each field (x: f32x8, y: f32x8...) etc. The point is why do that in a human, error-prone way every time (in the current software I work on, I would have hundreds of those structs for instance) when you can program your compiler to do it once for you
- jayd16 1y agoTowards the middle you realize this is about the reflection more than anything else. I do like how directly accessing the fields individually (the whole reason you would do this) is a hypothetical presented as an after thought. Enjoyably absurd.
- perihelions 1y agoI attempted to write a minimal version of the idea in Common Lisp, if anyone was curious about how it'd look like in that language, https://peri.pages.dev/struct-of-arrays-snippet https://peri.pages.dev/struct-of-arrays-snippet
- Dwedit 1y agoStruct of Arrays vs Array of Structs have different performance, depending on how they are accessed, mainly due to how memory will be cached. If you are iterating over objects sequentially, and looking at every field, they will perform about the same. If you are iterating over objects sequentially, and only looking at a few fields, Struct of Arrays performs better. If you are accessing objects at random, and reading every field, Array of Structs performs better. Array of Structs has a multiplication step when you calculate the address of an element. Struct of Arrays basically guarantees that the multiplication will be by a power of 2, so it's a bitshift rather than a multiplication. (Unless your struct contains a type whose size is not a power of 2). Multiplication is still very fast though on most architectures, so that's not all that much of a difference.
- bombela 1y agoHow could it not be a power of 2? The compiler makes sure to align fields and pad structs to power of 2 anyways.
- tomsmeding 1y agoIf your struct contains a field that is itself a struct, e.g. one containing three int32_t's, then that field has size 12, which is not a power of two.
- compiler-guy 1y agoDoesn't even need to be a struct within a struct: struct Foo { int8_t a; int8_t b; int8_t c; }; will have a size of 3 and an alignment of 1. Alignment is always power of 2, and size modulus alignment will always be zero. But alignment can be less than size, and size need not be a power of two, just have one power-of-two factor.
- bombela 1y agoBrain was not fully loaded yet, thank you. I don't think the struct in struct is relevant in your example by the way. i32 requires 4-bytes alignment. An array of a struct{3×i32} will be aligned to 12 bytes. Which maintains the 4 bytes alignment of the fields. If this structure is embedded into another one, it will be padded accordingly to the alignment requirement of the outer field. { { 3×i32 } i32 } will be 16 bytes. { { 3×i32 } i64 } will be 12, padding 4, 8. Totalling 24. I am assuming x86_64.
- adzm 1y agoNeat to see the reflection / unibrow operator ^^ in the wild!
- deleted 1y ago[deleted]
- gwenzek 1y agoInteresting to see the new C++ at work. But also I'm sure it's easier to learn Zig full language that just the new C++ metaprogramming
- hinkley 1y agoThe problem I run into with these sorts of structures is the whole aggregation versus composition issue. With composition the SoA problem is pretty simple. This object belongs to an owner or a category and it just never 'moves' so the most naive solution is just fine. I haven't looked at C++ in a million years, but looks like this implementation fixes the aggregation problem by handing out handles to the data, but I don't see anything in here where it tries to hand out the same handle for the same offset. I don't know about C++ but that matters in some languages.
- ozgrakkurt 1y agoI would recommend apache arrow, it has structures that handle nesting and keep data still fully columnar
- ozgrakkurt 1y agoIt is skeptical if this is even needed, why not design the structs etc. properly from the start so they are columnar if columnar works better? Meta programming is never free