Data-Oriented Demo: SOA, composition 

SOA = Structures of Arrays.

^ ^ ^ I'd also like to know where, I'm curious about the reason/ing

I'm guessing it's some twitch stream.

He's demoed it now bois, it's one of his most recent videos here on RU-vid

This is a super helpful comment, thank you! I'm just learning about this language and watching through all these so the heads up is great.

Mike Acton, "Data-Oriented Design and C++" ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-rX0ItVEVjHc.html

@@JustMe-fl1db the real MVP right here

I think it this is one of the side effects of these programming language wars. The neck beards wanted to build stuff, while corporations wanted to force people into buying into their ecosystem. I feel like this hurt programmers and customers the most, because of all the bad code that came from incorrect OOP implementations resulting in just plain bad software. Now that we know more about the importance and usefulness in considering the relationship of how CPUs like to have data laid out, things seem to be coalescing towards more flexible designs that consider the data being worked on/ the problem being solved and not the language a program is written in.

thanks, satan!

Yes you can do it in C++, I'm not sure what *post nightmare code* means since to me nightmare code is (a) subjective and (b) the fault of the programmer.

@@zemlidrakona2915 You forgot option (c): a joke by op

actually, you now can really do this in c++. the using keyword since c++17 now does exactly that. maybe the committee finally borrowed an idea from blow :D

@@zemlidrakona2915 Nightmare code is when one has to read code written by others. :o

Indie Game: The Movie?

agreed. it can be weird reading entity.pos.x and somewhere else entity.x when they both access the same member.

Sounds good, but I wish there was a written explanation.

It's still a work in progress, so I'm sure there will be one eventually. Want me to try to summarize here, or did you already watch it?

A quick summary would be nice. Please.

One is a neat flavour of inheritance, where struct A can say it is "using" struct B. All of B's members are then available as members of A. So far it's like C++ inheritance, in that A inherits all of B's members and can implicitly cast to B. But it also works with multiple inheritance ("using" multiple other structs), or defining that you only want a pointer to a B instance to be stored with A, rather than storing B contiguously within the A instance. This lets you do many kinds of transformation on how your data is defined and laid out in memory, without any changes to the code that is acting on the data. One use case is splitting an entity into a hot and cold component, stored in two parallel arrays (to maximize cache efficiency for high-frequency traversals/modifications to the hot members), with the flexibility to easily change which members belong in which part (even switching it based on the compile target, to optimize for different systems' cache characteristics) He shows how this can be used to implement vTables for other familiar inheritance benefits, but this isn't yet a core language feature so it's a bit verbose just now. He also allows defining an array as SOA, so it will store all instances' values for each member contiguously, but still let you access it in the familiar array_of_entities[i].member syntax. You can also add an SOA mark at the definition of the type, so that all arrays of that type (unless explicitly marked AOS) immediately become SOA, again transforming data layout without requiring changes to other code. (Pointers to instances implicitly become SOA pointers, which are larger due to the extra metadata, but if you're switching to SOA then you're probably in a use case with more sequential buffer traversal than pointer-chasing anyway. He's also got some neat tricks with "using" a function to decompress pointers from a significantly smaller ID value) The philosophy behind this project (and I recommend checking out the whole playlist) is that code evolves over time, and that incremental changes to the program's function should not require discontinuous changes to swaths of your code. So far, even at the basic level of my coding, there's a pile of stuff that I'd find useful - like not having to refactor my foreach loops into for(i = 0; i < limit; i++) anytime I need access to the index within an iteration. ;)

Very cool. Thanks for writing that summary. It's also a little over my level of OOP, but I get the gist of it. It sounds very good.

Someone linked me already to a D implementation of a subset of this stuff... you might want to search for that as a starting point.

Just found the implementation, appreciate the info! These things are easy to miss in small communities.

A similar thing for Julia: github.com/simonster/StructsOfArrays.jl.

The problem is that if you decide to use this for dynamic dispatch, you make it a lot slower, because the compiler has to re-call the function any time it thinks the result might be different. And because of aliasing problems, that is going to happen almost always. So you would end up calling the function tons of times, and it becomes slow. Whereas if you say this is just intended to be static dispatch with a compressed pointer, it can be very fast.

Jonathan Blow Thanks for replying. I can certainly see what you mean from a speed point of view - I suppose I saw that feature as having value beyond just being super fast. It seemed like a sort of operator overloading for structure dereferencing, which struck me as rather powerful. It could certainly contribute to your goal of a changing data layout requiring minimal code changes. Perhaps if arbitrary functions were allowed, there could be some sort of "static" keyword on the function, which could flag it as being simple, in the sense of always returning the same thing for a given input. The compiler could then do all the optimizations you mentioned. All the best!

Matthew Taylor In the past day or two I have thought about this more and in fact did think of tagging functions or variables with "static" to indicate that they don't change. So this might be the way the language goes in the future. It would definitely be in line with "make sure programs are correct first, but make it easy to make them fast".

+Jonathan Blow I see this feature as a lazy evaluation. When the entity is accessed first time the procedure is called and the result is stored (lazy evaluation). The using keyword only makes sure that the evaluation is transparent for the caller. The only question for me is if you want to let users replace the value or invalidate the result. I guess it is a bit harder because the value is anonymous. Only the name of procedure is exposed. Maybe NAME_OF_PROCEDURE_value to make it accessible.

a long time apparently 😭😭😭

I just recently optimized a point projector (world space to screenspace) using SoA rep and handwritten SIMD intrinsics. It was the top profiling hotspot for a software rasterizer going at 14-15 FPS. I didn't have a benchmark just testing the point projection in isolation but after the optimization, the full rasterization process (including projecting, rasterizing, and shading) improved to over 35 FPS rendering 2 million triangles/frame. The projection function also disappeared completely as far as hotspots... not even in the top 20 in CodeXL or VTune after I converted to SoA rep and applied SIMD (just SSE2 using 128-bit XMM registers). I suspect it sped up more than the point projector itself to convert to an SoA rep since, while the projection function was the top hotspot, it was only taking around 33% of the time. I hardly expected it to more than double the framerates as it did. It was quite a tedious process to change it though. I didn't have this super cool JAI language -- had to use C++ so it was a fairly intrusive code change. In almost all cases where I've done that and in places where I did have a benchmark testing things in more isolation, I can usually get at least a 2x performance (maybe average 3-4x) over AoS in times where SoA is likely to help (sequential access patterns and possibly some cold fields that could be hoisted out or the ability to use more vertical SIMD without horizontal shuffling).

we are still waiting...

And waiting

A delayed language is eventually good. A bad language is bad forever.

@@nintendude794 i just hope it's not years from now

I think there is a beta version of Jai right now ready to be used.

or Sony/Toshiba/IBM. the PS3/CELL processor had a bigger need for this sort of thing. That chip is basically dead because it didn't suit C++.

Sure you can do this all in C. But as soon as you change the layout of your data, you'd need to change all the code logic that accesses that data. I think one of the key points of Jon's language proposal is that you can make these changes to data layout without any changes at all to your code logic.

Philip Fortier Ya, I definitely see the benefits there - and I'm not suggesting that they're useless. But changing entity.vector.x to entity.hot.vector.x (or whatever) is fairly trivial in most text editors. Again, it's great to see someone bringing these issues to light, I just want to make sure I'm understanding the purpose of these decisions. I'll be very interested to see where the language goes with respect to dependencies and the like.

Pollen Applebee We're not talking about small beginner programs. Imagine your program is between 300,000 lines and 5,000,000 lines, and consists of thousands of source files. You don't always say entity.vector.x; the variable is called a lot of different names depending on what is going on. A lot of the time you have functions operating on pointers to sub-structs. Maybe you have some macros that don't look anything like entity.vector.x but expand to entity.vector.x. Maybe you have some generated code, so you have to update the generator, which may be nontrivial. You could hope that a refactoring IDE helps you with many of these issues (but it wouldn't handle the macro or generated code case) ... but I have never seen one that works well enough to really use. But why make your language require such a thing to begin with?

but still N times less than C++ needs...

See my reply above to your previous comment. This structure would actually be a big win for pretty much all games.

what he's achieving is letting you easily change data layout based on profiler feedback, without having to decide the layout upfront.. change how data is split between structures,direct/indirect components etc but the functions that use that data don't need to be refactored at all, just the description. This will be a massive help, IMO.

we still want those features now lol

@@drygordspellweaver8761 still waiting 😅

Typically not for sequential access. Bitsets can far exceed performance there over an SoA of bools, especially if the loops don't use bitwise AND with variable right-shifts to test for each individual bit unless it has to (ex: skipping 64 bits at a time if they're all unset for a simple example, or using FFZ/FFS for a more complex one). Random access often can be and it's really important to try to distinguish, upfront, whether our data is most frequently going to be accessed in random patterns or sequential ones to determine an optimal representation.

You didn't understand anything.

@@marcossidoruk8033 I believe you are the one in the dark here.

@@Marius-ir1qn you believe. You are also objectively wrong, same as the other guy.

"live" just means at run-time. I.e. it's not some static compile-time syntactic sugar magic. It's the same as regular pointer.

Green conflict with the 'inline' keyword of inline functions

@@Otomega1 are there even inline functuons in jai?

@@s4ecki I dont really know about jai, but i think it can be smart to be consistent with other languages, there are many other keywords more accurate and shorter, pull, spill..

'using' is much easier to type, 'pull' is kind of a pain to type..

I think it means it's a pointer to the array, augmented with an index into the array (and possibly the array's length, if that isn't stored with the array itself). That way you can compute the address of any of the struct's members with only the information contained in the SOA pointer.

I don't really know how Vector works in C++, but the idea to reduce cache misses is: Smaller array entries means more entries are loaded into cache on cache misses. Therefore if a function only needs to access one or few members of a struct, the SOA approach (or splitting structs) will result in fewer cache misses.

Benjamin Pedersen Maybe Vector is not the best example. Laying out structs SOA or AOS is possible in C, the only thing missing is pulling in the name spaces. Regarding fewer cache misses: not sure, since the "united struct" with two pointers will have to be loaded to cache first, and following the pointer will stop prefetching. We actually increase cache pressure by using indirect access.

Michael Pankov You increase cache pressure in the case where you are doing a lot of computation that can run in parallel with the fetch and/or in code that runs rarely and is expected to be slower. Meanwhile you remove stalls from the tight loops that need to be really fast. For most games this would be a huge win. That said, this is more about providing a toolkit that lets you set up the data layout you want. You certainly don't have to do it the way I mentioned in the demo. As for your claim that laying out structs in SOA is possible in C ... no it isn't. You can take the members that you would have put into a struct and put them into arrays instead, but you can't then treat it as a struct in the language.

Jonathan Blow Thanks for explanation. Keep up all the good work! :)

Jonathan Blow By the way: do you have any preliminary benchmarks / timing results? I wonder how much of a win SOA would be. Not being picky, just interested if there are any data you could share :)

I use OpenGL in demos all the time.

Jonathan Blow is there even a lot of restriction in that matter? Can you use any languages together if the compiler and linker are supporting both languages? it's kind of a general question out of interest

+Jonathan Blow 1) what is this implemented in? (assembly? c? c++?) 2) could this be done as an extension to C++? (compiler extension?)

1) C++. 2) No.

+Jonathan Blow what file type does your custom compiler output?

+Konstantin Konev Any modern processor that has a cache will favor SOA because what ultimately matters is getting rid of random memory accesses. It doesn't matter what instruction set you will use.

Uhh, that's not multiple inheritance, it is single inheritance.

Yes, but I assumed from the syntax and what you said that it extends to multiple inheritance. Sorry if I misunderstood.

It doesn't currently, because we only do this conversion for things at memory offset 0, and there can be only one of those. We *could* make it work generally, but I haven't seen a need to do that.

Aha, that makes sense. Thank you! Second question: In the video, you said "We didn't express inheritance here". Apart from syntax, what is the difference from actual inheritance? They seem to behave very similarly.

We don't currently provide any way of shadowing declarations in the thing you are childed from, so the whole OO idea of "subclass the parent but replace some methods" does not apply here. In fact we don't have any such thing as methods, so there is that too.

Yes

+PixelOutlaw | I like the idea of an implicit interface, which would make what you said entirely possible and extremely simple in a statically typed language that supports it. The idea is as such: You can declare a interface (it can even be private) that represents what you want to operate on. The type checker, when faced with that interface, will simply check if the type in question implements the methods (or whatever the requirement is) of that interface. It needn't do it explicitly, so long as (for example) the `update(delta: float)` method exists (again, or any similar construct in question) then it's able to be treated as that interface implicitly. interface updatable { proc update(delta : float) } proc update(all : []updatable) { /# do things } struct player { /# fields } impl player { proc update(delta : float) { /# update the player } } /# now `player` is implicitly `updatable` That's entirely example code using a similar syntax to a language I'm working on, hopefully that explains the idea well enough.

Best of luck on your language!

When using a dynamic language, you pay the price at runtime. It might not matter for a small game, but what you suggest is already orders of magnitude slower than the cache problems that Jon has been trying to avoid.

It _does_ matter for a small game. Even a single order of magnitude, as you suggested, will inevitably show up in the user experience.

I'm calling Common Lisp within a SFML C++ project at the moment (via ECL). But it is mostly for assigning instance behaviors at runtime to avoid creating 100 classes for each type of enemy. Users will be able to edit huge sections of my game without ever having to compile source code. And it runs very well having 1000 instances calling updates in real time on an i7 from 3 years ago. I've not even bothered to compile the Lisp functions yet. Would I use it for rendering? Probably not. For user definable behaviors? Works for my needs. This is a 2D bullet hell game, everything is light and fast, the worst being a very fast rectangle to rectangle collision check with 3 early exit conditions. Majority of the time the collision exits early too. As a bonus I can make edits to my bullet pattern scripts and watch the game change without recompiling the damn thing.

He was being sarcastic.

Yeah, when I said that I meant more-complicated stuff like message-passing schemes, but it seems the definition of "dynamic dispatch" includes virtual functions called from base classes, so it was an incorrect utterance.

Hehe, that's fine, am currently watching it further -- a very nice talk, indeed (was searching for more like Mike Acton's talk on these matters) :)

www.amazon.com/Generative-Programming-Methods-Tools-Applications/dp/0201309777 is a nice source of terms and insights, if one wants to sound snobby (static VS subtype polymorphism, etc.) :)

I just realized that you can already basically have "normal" classes with compile-time code generation. I forgot that was a thing. Classes are nice because of methods, which are nice in the sense that it's some operations associated with a specific type... but really all a method is is a function that takes the object as an implicit first argument. But really, classes don't have much place in a data-oriented language.

This reads like a nonsense comment to me.