"using" is very much like "with ... " in Pascal. Yours is, of course, much more powerful. I am baffled as to why such a useful construct is not present in the vast majority of programming language. Well done for adding it. Special kudos for SOA. It is such a pain to do this manually.
Just in case somebody's watching this just now: Jon said recently that the SOA feature is not in the language anymore, but it will be brought back in a different way that is more generic and useful for more things.
Been through the pain of refactoring OOP virtual based code on the xbox 360, splitting data up for DMA into SPUs on the ps3.. etc. this is a really nice idea.. being able to chop & change data layout without having to butcher source too much. It is indeed a big deal that the language herds you in one direction with its' inbuilt syntax IMO.
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.
I tried to implement something like that "using" keyword in C++, but it was impossible for me to do so in a simple manner. Good feature. What I like the most is that you are not sticking to the old dogmas (as opposed to what some so-academic people do), you know, "this has been done this way always! why should we change it?" or "It cannot be done!". Even if you are right or not, that does not matter, the main point is that you are doing experiments in the right direction thinking about real problems. I'm sure many people will come after you and will contribute to improve what you are doing, and that's great.
I cannot "Like" this enough. Ever since I learned about data-oriented design, I've wanted to do stuff like this, and had a vague sense that a compiler *should* be able to let us write familiar AoS-style syntax describing fast SoA access... but I lacked the deep insight to say exactly how. Now I really really want to use this language. :D
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. ;)
9:22 The main challenge / puzzle to solve when using a DOD approach. You hit the nail on the head. 18:15 Again, talking about what we want with DOD, but we don't immediately have. 24:44 The concept of using 'using' to refer to members without using classes. 37:40 Creating new objects creates them in random places on the heap, which DOD tries to get away from, so... 39:00 ...a better way to do it using a namespace and pointers. SOA (structure of arrays). and that is what the rest of the video is mostly about, it appears.
Just to toss in some food for thought, the 'mixin' idea came to mind for the use of 'using' with structs as it seems to describe the resulting behavior fairly well. However, 'mixin' might feel a bit awkward if used in the context of function arguments and code blocks. I really love the work going on here and can't wait to get my hands on it. Thanks for exploring this space!
This is incredibly interesting, and it's actually rather surprising no-one has thought of something like this for data layout in memory before. I feel rather inspired after watching this, and may take a stab at implementing something similar (albeit slightly contrived) with the aid of templates in D (accessing data laid out in SOA as if it was AOS).
I pondered whether "embed" would be better than "using" inside struct.. or "collapse", but after some thought I think using "using" everywhere is better.
Holy crap, these semantics are cool, I'll put up with the additional colons and backwards definitions (name type as opposed to type name) if this is what I get in return!
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.
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
I think your new language is enormously exciting. The OO hierarchy is rarely a perfect fit for a problem (why would it be?). Your method allows much richer, more flexible constructions, I especially love the cross cutting power. I would ditch C++ and use such a language tomorrow, without question. I was slightly disappointed with the section where you were "using" a function within your structure to manage access to a global array. This feature was really great, but then you seemed to back away from its full implications. You mentioned that it was NOT dynamic dispatch - which confused me, as it seemed as if the compiler could sort it out unambiguously. Anyway, for what its worth, I would say let the user write whatever functions they like in that situation - though the chances are I've not thought things through properly! Great work Jonathan, and my best wishes for this language's ongoing development!
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.
I am already loving the language. This data-oriented approach is actually simple(r) in your language than others (especially C++)! The 'using' keyword doesn't need to be changed. It's pretty clear what is does (even if it technically means different things). This is opposite where in C/C++ 'static' keyword means many different things (global, internal, local persist, etc.) (I make it clearer by doing #define global static, etc.) Would it be possible for operator overloading? I don't like using it that often in C++ but when I do, it is usually to implement a math library (Vectors, Matrices, Quaternions, etc.) as it is much more natural to write code with these types where the operators are overloaded. Would it be possible to just view the code for the demos and invaders example (not the compiler) to get a better understanding of the language and to suggest more ideas?
Hey, Jonathan! If this video is about performance and Data-Oriented approach benefits, It'd be cool if you show us some SOA vs AOS benchmark results. I have watched all the video and now I percept SOA as a cool and strange approach to store my data and unfortunately that's it. But I wanna see it as "the best way to store your data", you know Thank you for the video, I hope your language gets more popular, better and faster
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).
Two levels of indirection might induce way more overhead than occupying cache with big structs. Prefetching of big structs is predictable, but fetching stuff via pointer is not. In other words, AFAIK, CPU won't prefetch a struct behind the pointer. Having nested pointers means prefetching effectively stops. And even if it will, we add another level of indirection meaning cache pressure actually increases. Is it a loss or a gain in performance would depend on relation of sizes of caches and structures, but generally, there's a trade-off presented, not an efficiency silver bullet.
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.
I really appreciate all the hard work that's going into this. Am I correct in seeing the primary value here being the syntactic sugar? After about 45 minutes or so, I can't help but think that all the performance based ideas are easily achievable in C. All I'm seeing is essentially an Entity struct with a bunch of pointers to data in contiguous arrays. The syntactic sugar of "using" is probably convenient, but that's fairly subjective right? This is all super easy in C, and the SoA stuff is also fairly trivial to set up once you understand it. The talk itself is very useful for those who might be new to these optimization techniques.
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?
Jon, if you want to take your programming to the next level (in readability) invest in multi-column alignment. i.e. You would horizontally align all the colons in a sub-section such as mount_parent_id, mount_position, mount_orientation, mount_scale, mount_bone_index. Try it, :-)
To solve that issue in c++ I just naturally included an attribute by reference. For example class A can have an attribute which is a reference to class B.
This is literally the flyweight pattern...as described in GoF's Design Patterns book published in 1994. The opening line 'Some applications could benefit from using objects throughout their deign, but a naive implementation would be prohibitively expensive.'
AOS-SOA stuff is exactly what the compiler and language should provide for the programmer. C++ pushes out all these 11-17-etc standards, and where's SOA?
Wow, the Witness actually looks like this? Starbound as well. I got to the limits of OOP really fast and was able to switch architecture quite early, thankfully
I thought the problem of cache misses would be solved by allocating same objects in pools (like, Vector stores all humans compactly). What do you think of it?
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 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 :)
@@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..
It's looking great! I really can't wait to start using this full time. These demos are equally exciting and depressing because I'll probably still be stuck with C++ for at least the next few years and converting my entire code base will not be too fun. How long after The Witness is finished do you think it will be until the language is production ready and your using it for your next game?
I'm not sure C++, as a language, encourages that kind of structuring. C++ is a multi-paradigm language. I think Stroustrup himself has specifically said this. So, it's up to you if you want to implement your Entities like that.
Suggestion: meta_struct myStruct { hot type name; hot type name; type name; type name; } compiler generates the _hot and _cold structs and generates myStruct with those as members, the members that miss hot/cold will go in hot or cold if the compiler decides there's room for it in the cache of the target ?
Here are the links from the video so you don't have to type them by hand: Noel Llopis, "Data-Oriented Design" gamesfromwithin.com/data-oriented-design Chandler Carruth, "Efficiency with Algorithms, Performance with Data Structures" th-cam.com/video/fHNmRkzxHWs/w-d-xo.html Mike Action, "Data-Oriented Design in C++" th-cam.com/video/rX0ItVEVjHc/w-d-xo.html
One thing I like about many dynamically typed languages is that they let me shove all game objects into a container and call update on them all regardless of type. This avoids the mess of derived classes and also interface after interface for composite classes' methods. You just store all objects that need to be together together and apply a universal series of functions that hopefully they all have. Yes it s dangerous for people new to your code. But you know what? It is super clean for a one man development team. I think it is much nicer to have a language that lets me put all kinds enemy classes in a container and simply call update on each one with no type casts and messy case/switch statements.
+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.
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.
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.
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.
what about recursive using? struct A { int: value; } struct B { using A: a; } struct C { using B: b; } ... struct Z { using Y: y; } can I say z.value directly instead of z.y.(...).b.a.value?
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.
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.) :)
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
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.
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.
Is it only me who thinks that the idea of "using" namespaces is just a bad idea ? I don't know, for me, it just introduces confusion while reading the code. Why would we introduce 2 different ways of refering to a variable.
+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.
Bjarne Stroustrup (the Danish inventor of C++) does not call C++ an OO language. He calls it a multi-paradigm language. With features to support (among other things) OO.
Thank you for nice intriguing talk. I wrote down a response to all the problems discussed in a different view. github.com/kamanashisroy/aroop/tree/master/talks/data_oriented_talks
hey you know this thing with keyword using inside the struct, is much like mixins in ES5-style React classes in JavaScript React.js ecosystem. I know that JAI is not like JavaScript by design, but possibly you should find it out for yourself for educational purposes. P.S. I'm just middle-level game developer (btw working with Python), so maybe my comment is not useful! But my programmer intuition says that React Native project is trying to solve the same problems as the JAI project is about. (defining user interactions and entity representation in data driven way)
Intel should invest in this project. :P So if you can already simulate polymorphic classes, you might as well just put classes in, right? I will admit that classes are kind of overrated, but you can basically implement them by hand... sooo.... Either way, that's cool what you can do with this. I'm just curious as to how it would compare with C++'s implementation of classes. My intuition tells me it might be slower... until you get into SOA shenanigans. That alone probably makes the biggest difference.
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.
I'd like: modules Group1{ uses TreeNode as TN // get everything from TreeNode under Group1.TN:fn(); uses DoubleLinkedList as DLL // get everything from D.L.L under Group1.DLL:var TN:next DLL:next // both use the same memory cell for their next properties } // "this.property" or "self" refers to scope Group1.TN:property or Group1
It's all fine, but the witness is not that fast of a game, considering how simple it is and there are unreal engine 4 in production, which is written with all those slow things, all in-game object are heap allocated and their renderer doesn't look that slow.
in second though, you are totaly complicating this thing, you dont need to traverse your entities multiple times, if you need speed, then you add "collecg geometry" to your entities, you make a pass, and you collect all the geometry data you need for rendering, this way you still pay only once for cache misses, but you end up with a buffer that is compatible for the gpu, then you render this buffer as many times as you need. and this way you dont need all this low level of control of your memory layout. - so you still have simple inheritence which is useful, and you have your speed.
Jonathan has had the same character development as Saitama. As he becomes a better programmer he loses more hair.
Thanks for the links about Data-Oriented at 16:31 - yes this is me lazily providing myself a link back to that point in the video :)
Mike Acton, "Data-Oriented Design and C++"
th-cam.com/video/rX0ItVEVjHc/w-d-xo.html
@@JustMe-fl1db the real MVP right here
"using" is very much like "with ... " in Pascal. Yours is, of course, much more powerful.
I am baffled as to why such a useful construct is not present in the vast majority of programming language.
Well done for adding it.
Special kudos for SOA. It is such a pain to do this manually.
Just in case somebody's watching this just now: Jon said recently that the SOA feature is not in the language anymore, but it will be brought back in a different way that is more generic and useful for more things.
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 TH-cam
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.
Been through the pain of refactoring OOP virtual based code on the xbox 360, splitting data up for DMA into SPUs on the ps3.. etc.
this is a really nice idea.. being able to chop & change data layout without having to butcher source too much. It is indeed a big deal that the language herds you in one direction with its' inbuilt syntax IMO.
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.
I tried to implement something like that "using" keyword in C++, but it was impossible for me to do so in a simple manner. Good feature. What I like the most is that you are not sticking to the old dogmas (as opposed to what some so-academic people do), you know, "this has been done this way always! why should we change it?" or "It cannot be done!". Even if you are right or not, that does not matter, the main point is that you are doing experiments in the right direction thinking about real problems. I'm sure many people will come after you and will contribute to improve what you are doing, and that's great.
I cannot "Like" this enough. Ever since I learned about data-oriented design, I've wanted to do stuff like this, and had a vague sense that a compiler *should* be able to let us write familiar AoS-style syntax describing fast SoA access... but I lacked the deep insight to say exactly how.
Now I really really want to use this language. :D
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.
9:22 The main challenge / puzzle to solve when using a DOD approach. You hit the nail on the head.
18:15 Again, talking about what we want with DOD, but we don't immediately have.
24:44 The concept of using 'using' to refer to members without using classes.
37:40 Creating new objects creates them in random places on the heap, which DOD tries to get away from, so...
39:00 ...a better way to do it using a namespace and pointers. SOA (structure of arrays).
and that is what the rest of the video is mostly about, it appears.
Just to toss in some food for thought, the 'mixin' idea came to mind for the use of 'using' with structs as it seems to describe the resulting behavior fairly well. However, 'mixin' might feel a bit awkward if used in the context of function arguments and code blocks.
I really love the work going on here and can't wait to get my hands on it. Thanks for exploring this space!
agreed. it can be weird reading entity.pos.x and somewhere else entity.x when they both access the same member.
This is incredibly interesting, and it's actually rather surprising no-one has thought of something like this for data layout in memory before.
I feel rather inspired after watching this, and may take a stab at implementing something similar (albeit slightly contrived) with the aid of templates in D (accessing data laid out in SOA as if it was AOS).
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.
I pondered whether "embed" would be better than "using" inside struct.. or "collapse", but after some thought I think using "using" everywhere is better.
Holy crap, these semantics are cool, I'll put up with the additional colons and backwards definitions (name type as opposed to type name) if this is what I get in return!
You can do this in C++! **posts nightmare code**
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
Love the videos, first saw you on a documentary about Indie Games. Have been a fan ever since. Very excited about the new language :)
Indie Game: The Movie?
Ok, door_test_4 was like: Why doesn't this exist already?
Keep up the good work! This is starting to look awesome.
Coincidentally I was looking you up yesterday, wondering if anything new on the language had surfaced on the web. This is a nice surprise.
I think your new language is enormously exciting. The OO hierarchy is rarely a perfect fit for a problem (why would it be?). Your method allows much richer, more flexible constructions, I especially love the cross cutting power. I would ditch C++ and use such a language tomorrow, without question.
I was slightly disappointed with the section where you were "using" a function within your structure to manage access to a global array. This feature was really great, but then you seemed to back away from its full implications. You mentioned that it was NOT dynamic dispatch - which confused me, as it seemed as if the compiler could sort it out unambiguously. Anyway, for what its worth, I would say let the user write whatever functions they like in that situation - though the chances are I've not thought things through properly!
Great work Jonathan, and my best wishes for this language's ongoing development!
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.
dude that using.. was amazing.. just drool
RIP in peace John Blow's majestic mane
I am already loving the language. This data-oriented approach is actually simple(r) in your language than others (especially C++)! The 'using' keyword doesn't need to be changed. It's pretty clear what is does (even if it technically means different things). This is opposite where in C/C++ 'static' keyword means many different things (global, internal, local persist, etc.) (I make it clearer by doing #define global static, etc.)
Would it be possible for operator overloading? I don't like using it that often in C++ but when I do, it is usually to implement a math library (Vectors, Matrices, Quaternions, etc.) as it is much more natural to write code with these types where the operators are overloaded.
Would it be possible to just view the code for the demos and invaders example (not the compiler) to get a better understanding of the language and to suggest more ideas?
Hey, Jonathan! If this video is about performance and Data-Oriented approach benefits, It'd be cool if you show us some SOA vs AOS benchmark results. I have watched all the video and now I percept SOA as a cool and strange approach to store my data and unfortunately that's it. But I wanna see it as "the best way to store your data", you know
Thank you for the video, I hope your language gets more popular, better and faster
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).
It's getting more and more interesting each time :)
I really hope there is a working prototype within a year or so :D
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.
Your videos make me forget about my web developer job 😄
Also: this language is going to need crazy amount of documentation =)
but still N times less than C++ needs...
You answered my question on a prior video before I posed it, nice.
Two levels of indirection might induce way more overhead than occupying cache with big structs.
Prefetching of big structs is predictable, but fetching stuff via pointer is not. In other words, AFAIK, CPU won't prefetch a struct behind the pointer. Having nested pointers means prefetching effectively stops. And even if it will, we add another level of indirection meaning cache pressure actually increases.
Is it a loss or a gain in performance would depend on relation of sizes of caches and structures, but generally, there's a trade-off presented, not an efficiency silver bullet.
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.
43:54 This is great.
I really appreciate all the hard work that's going into this. Am I correct in seeing the primary value here being the syntactic sugar? After about 45 minutes or so, I can't help but think that all the performance based ideas are easily achievable in C. All I'm seeing is essentially an Entity struct with a bunch of pointers to data in contiguous arrays. The syntactic sugar of "using" is probably convenient, but that's fairly subjective right? This is all super easy in C, and the SoA stuff is also fairly trivial to set up once you understand it. The talk itself is very useful for those who might be new to these optimization techniques.
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?
I'm wondering why Intel hasn't created this language in the past >10 years.
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++.
I am excited to use this language in my own projects.
Jon, if you want to take your programming to the next level (in readability) invest in multi-column alignment.
i.e. You would horizontally align all the colons in a sub-section such as mount_parent_id, mount_position, mount_orientation, mount_scale, mount_bone_index.
Try it, :-)
To solve that issue in c++ I just naturally included an attribute by reference. For example class A can have an attribute which is a reference to class B.
That's how composition works
Great video, Jonathan!! I'm enjoying it as I watch in parts.
Keep it up! :D
This is literally the flyweight pattern...as described in GoF's Design Patterns book published in 1994. The opening line 'Some applications could benefit from using objects throughout their deign, but a naive implementation would be prohibitively expensive.'
AOS-SOA stuff is exactly what the compiler and language should provide for the programmer. C++ pushes out all these 11-17-etc standards, and where's SOA?
Wow, the Witness actually looks like this? Starbound as well. I got to the limits of OOP really fast and was able to switch architecture quite early, thankfully
I thought the problem of cache misses would be solved by allocating same objects in pools (like, Vector stores all humans compactly).
What do you think of it?
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 :)
36:00 I started humming that song right before you said that.
How about using a keyword like 'pull' instead of 'using'? Kind of like 'pull all the contents of that struct into this struct/function/whatever'.
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 want those features now! :C they are so awesome i love it
we still want those features now lol
@@drygordspellweaver8761 still waiting 😅
It's looking great! I really can't wait to start using this full time. These demos are equally exciting and depressing because I'll probably still be stuck with C++ for at least the next few years and converting my entire code base will not be too fun. How long after The Witness is finished do you think it will be until the language is production ready and your using it for your next game?
a long time apparently 😭😭😭
I'm not sure C++, as a language, encourages that kind of structuring. C++ is a multi-paradigm language. I think Stroustrup himself has specifically said this. So, it's up to you if you want to implement your Entities like that.
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.
Suggestion: meta_struct myStruct { hot type name; hot type name; type name; type name; } compiler generates the _hot and _cold structs and generates myStruct with those as members, the members that miss hot/cold will go in hot or cold if the compiler decides there's room for it in the cache of the target ?
Here are the links from the video so you don't have to type them by hand:
Noel Llopis, "Data-Oriented Design"
gamesfromwithin.com/data-oriented-design
Chandler Carruth, "Efficiency with Algorithms, Performance with Data Structures"
th-cam.com/video/fHNmRkzxHWs/w-d-xo.html
Mike Action, "Data-Oriented Design in C++"
th-cam.com/video/rX0ItVEVjHc/w-d-xo.html
One thing I like about many dynamically typed languages is that they let me shove all game objects into a container and call update on them all regardless of type. This avoids the mess of derived classes and also interface after interface for composite classes' methods. You just store all objects that need to be together together and apply a universal series of functions that hopefully they all have. Yes it s dangerous for people new to your code. But you know what? It is super clean for a one man development team. I think it is much nicer to have a language that lets me put all kinds enemy classes in a container and simply call update on each one with no type casts and messy case/switch statements.
+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.
Jonathan, very interesting stuff, do you have a public repository so we can look at the code?
if small SOA members are smaller than one byte, wouldn't accessing them be slower? i suppose some bitwise operations aren't too bad
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.
that is pretty sweet absolutely
Hi Jonathon, is there a similar, simplified implementation of composition for the door example in C#?
Would I be able to use this language somehow?
Very interesting
Very good video :D
STRUCTOR is a Public Enemy!
Where could I find some benchmarks of this?
Jon where do you live stream?
6:59 What about custom allocators?
'vtable' pointer is only the extra overhead that got introduced if you use inheritance over composition.
Great Video ! Hows The Witness Coming Along ? :)
what about recursive using?
struct A { int: value; }
struct B { using A: a; }
struct C { using B: b; }
...
struct Z { using Y: y; }
can I say z.value directly instead of z.y.(...).b.a.value?
Yes
3:40 or so -- but you DO use dynamic dispatch! As that func over there is virtual :)
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.) :)
th-cam.com/video/zgoqZtu15kI/w-d-xo.html
hot tight packed data array ...haha
Ohh so The Witness is going to have Mounts?
I want this so bad...
Do you think this language will be able to work together with APIs like OpenGL and GLFW?
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?
What does it mean for a pointer to be SOA? Is it simply a pointer to something that is SOA?
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.
This was 8 years ago!?
Johnathan, if you don't mind me asking; what is a live pointer in respect to a regular pointer? I wasn't even able to Google it.
"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.
33:18 How is this different from the multiple inheritance that Mike Acton described as "just dumb"?
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.
Is it only me who thinks that the idea of "using" namespaces is just a bad idea ? I don't know, for me, it just introduces confusion while reading the code. Why would we introduce 2 different ways of refering to a variable.
Does ARM favor SOA too?
+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.
I love the ideas behind using and it seems very handy but this vtable nonsense looks real messy.
Bjarne Stroustrup (the Danish inventor of C++) does not call C++ an OO language. He calls it a multi-paradigm language. With features to support (among other things) OO.
@28:20 super verbose? wat? super succinct you mean.
He was being sarcastic.
"abusing using"
Thank you for nice intriguing talk. I wrote down a response to all the problems discussed in a different view. github.com/kamanashisroy/aroop/tree/master/talks/data_oriented_talks
hey you know this thing with keyword using inside the struct, is much like mixins in ES5-style React classes in JavaScript React.js ecosystem. I know that JAI is not like JavaScript by design, but possibly you should find it out for yourself for educational purposes.
P.S. I'm just middle-level game developer (btw working with Python), so maybe my comment is not useful! But my programmer intuition says that React Native project is trying to solve the same problems as the JAI project is about. (defining user interactions and entity representation in data driven way)
Intel should invest in this project. :P
So if you can already simulate polymorphic classes, you might as well just put classes in, right? I will admit that classes are kind of overrated, but you can basically implement them by hand... sooo....
Either way, that's cool what you can do with this. I'm just curious as to how it would compare with C++'s implementation of classes. My intuition tells me it might be slower... until you get into SOA shenanigans. That alone probably makes the biggest difference.
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.
Doesn't SOA vs AOS depend on use? Like if you iterate through the struct in order..... Ha, nevermind. That never happens.
I'd like:
modules Group1{
uses TreeNode as TN // get everything from TreeNode under Group1.TN:fn();
uses DoubleLinkedList as DLL // get everything from D.L.L under Group1.DLL:var
TN:next DLL:next // both use the same memory cell for their next properties
}
// "this.property" or "self" refers to scope Group1.TN:property or Group1
It's all fine, but the witness is not that fast of a game, considering how simple it is and there are unreal engine 4 in production, which is written with all those slow things, all in-game object are heap allocated and their renderer doesn't look that slow.
This reads like a nonsense comment to me.
in second though, you are totaly complicating this thing, you dont need to traverse your entities multiple times, if you need speed, then you add "collecg geometry" to your entities, you make a pass, and you collect all the geometry data you need for rendering, this way you still pay only once for cache misses, but you end up with a buffer that is compatible for the gpu, then you render this buffer as many times as you need.
and this way you dont need all this low level of control of your memory layout. - so you still have simple inheritence which is useful, and you have your speed.
So, what about the performance? Data-oriented programming is all about performance...
I can't watch this, it's using emacs
Now we have entt in c++