Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The compiler will optimize that away

blog.royalsloth.eu

Post reply on HN
Print view View original

41–50 of 329 posts

Re: The compiler will optimize that away

#41

Post by Const-me »

PixelOfDeath wrote: post #38
Const-me wrote: post #30

Earlier quoted context omitted.

> preferring to allocate fixed-size buffers on the stack When working set is measured in megabytes, it fits in L3 cache of modern CPUs. Memory layout is not too important for these programs. > most GC'd languages that aren't java have crappy GCs C# is good too. It also has value types, native memory spans, SIMD intrinsics, and stackalloc.

Don't forget that good cache locality also can cause data being pulled into cache that the prefetcher did know nothing about. I can create you a shitty linked list that fits perfectly in L3, but still has terrible cold cache performance because each individual cacheline has to be pulled in one by one.

Indeed, there're edge cases. Still, how many people using linked lists on the stack?

Re: The compiler will optimize that away

#42

Post by beagle3 »

> So far, the only programming language I know of that supports this type of crazy data transformations is JAI,

As far as I know JAI is indeed the only language that explicitly lets you switch between AoS and SoA with one bit, but the APL family of languages - (APL, J, K, Shakti, and a couple more) has basically - for 60 years no - taken the "data oriented" SoA approach for storage, and provides the language support that makes it as easy to use as the "object oriented approach" AoS. (For some definition of "as easy as" - the languages themselves are generally not considered easy to use, but within the language, treating things in either way is straightforward, at most a "flip" away, but usually not even that is needed).

Additionally, Nim macros (and I suspect Rust and D as well) allow this to be a library-level thing as well. Lisp does too, of course -- but Nim/Rust/D are much closer to the Algol family-and-friends list given in the article.

Re: The compiler will optimize that away

#44

Post by tgaj »

lordnacho wrote: post #13

Good article. My own thinking when coding performance is also towards data oriented approaches. For example Bevy in Rust. If stuff needs to be fast, it needs to be in cache. To do that, have everything nicely packed so you only ask for a chunk as often as you need. Then when you need it, it's already there. Thing about old fashioned OO is it's often fine enough for your run-of-the-mill CRUD app. If you look at the la…

> If you imagine a game that has characters, relationships, items, spells, and so on, it's often not that easy to model as encapsulated objects. Does each character have a list of other characters that they have a relationship with? What happens when you want to change the relationship, or a character casts a spell that temporarily changes the relationship? Can easily end up a mess, because it's not obvious where such things should live in >an OO model.

It's not really that hard. You just have one RelationshipManager that every Character have access to via simple public methods. OO is not so bad, especially when you forget about inheritance and use composition.

Re: The compiler will optimize that away

#45

Post by beagle3 »

lordnacho wrote: post #13

Good article. My own thinking when coding performance is also towards data oriented approaches. For example Bevy in Rust. If stuff needs to be fast, it needs to be in cache. To do that, have everything nicely packed so you only ask for a chunk as often as you need. Then when you need it, it's already there. Thing about old fashioned OO is it's often fine enough for your run-of-the-mill CRUD app. If you look at the la…

> Somehow over the years I've found that the animals/cars analogies given in OO tutorials are one of the few places that fit well with the model.

Yes, and I've never actually needed to implement a cat or a cow in any project :)

The other thing for which OO works much better than plain data is GUIs - and I think it is not a coincidence that OO popularity exploded together with the the coming-of-age of GUIs.

The other canonical example of OO - "Shapes" - doesn't actually work well at all; It doesn't work better with "plain data", but it exposes the fallacies of trying to use OO inheritance to model the real world. Every square is a rectangle, so square should inherit from rectangle ... but, you can't stretch width and height independently in a square, so it's not really a rectangle, etc. etc.

Re: The compiler will optimize that away

#46

Post by bsdubernerd »

bvrmn wrote: post #6

> 4. Data oriented way of programming has its own set of problems. This should be a top reason. Author is too shy to reveal the true cause.

Data-oriented programming is not hard by itself, rather as a consequence of how programming is done and what sort of flexibility you get in return.

The traditional (or should I call "inverse") approach is to define what the program should do and make it modular enough so that parts can be changed easily. For this to work well, functions are given a state snapshot to read/operator or change. Encapsulating this state into a struct/object allows functions operating on the same data to be extended easily, without having to think which functions do what, when and where they're called.

Thinking about locality though does force you to think not only about program structure, but overall program flow, which can be much, much harder to implement in a flexible fashion.

Struct-of-arrays or arrays-or-structs has little to do with it, although it's a common pattern seen when working with some kind of highly structured datasets.

Look at high-performance graphics pipelines to see how this affects the structure of the code. There's a lot of duplication which is required to handle data which is structured in a different way for efficiency, something which is not solved by just SOA/AOS swapping, but requires thinking of what data is used, what are the access patterns of the algorithm and how to pack the data so that locality is optimized. It's also harder to change as a consequence.

Re: The compiler will optimize that away

#47

Post by beagle3 »

tgaj wrote: post #44
lordnacho wrote: post #13

Good article. My own thinking when coding performance is also towards data oriented approaches. For example Bevy in Rust. If stuff needs to be fast, it needs to be in cache. To do that, have everything nicely packed so you only ask for a chunk as often as you need. Then when you need it, it's already there. Thing about old fashioned OO is it's often fine enough for your run-of-the-mill CRUD app. If you look at the la…

> If you imagine a game that has characters, relationships, items, spells, and so on, it's often not that easy to model as encapsulated objects. Does each character have a list of other characters that they have a relationship with? What happens when you want to change the relationship, or a character casts a spell that temporarily changes the relationship? Can easily end up a mess, because it's not obvious where suc…

Ah ... here we are again.

http://www.paulgraham.com/reesoo.html

OO is not so bad because OO is not well defined.

Re: The compiler will optimize that away

#48

Post by [deleted] »

beagle3 wrote: post #45
lordnacho wrote: post #13

Good article. My own thinking when coding performance is also towards data oriented approaches. For example Bevy in Rust. If stuff needs to be fast, it needs to be in cache. To do that, have everything nicely packed so you only ask for a chunk as often as you need. Then when you need it, it's already there. Thing about old fashioned OO is it's often fine enough for your run-of-the-mill CRUD app. If you look at the la…

> Somehow over the years I've found that the animals/cars analogies given in OO tutorials are one of the few places that fit well with the model. Yes, and I've never actually needed to implement a cat or a cow in any project :) The other thing for which OO works much better than plain data is GUIs - and I think it is not a coincidence that OO popularity exploded together with the the coming-of-age of GUIs. The other…

[deleted]

Re: The compiler will optimize that away

#49

Post by beagle3 »

tom_mellior wrote: post #40
theamk wrote: post #2

Summary: the computer has changed -- memory latency measured in CPU cycles has grown a lot. So we should not be using traditional struct/class-like programming model, where we put all properties of an object next to each other. Instead, we should be using game-style "data oriented programming" a.k.a. "column databases" for a much higher performance. However, most modern languages (C, C++, Python, Java, etc..) are not…

> However, most modern languages (C, C++, Python, Java, etc..) are not making it easy, The article shows how easy it is to declare a struct of arrays in Java: You declare a struct (class). Inside it you declare arrays. Done.

It is easy to declare, but it is not easy to use:

You can pass the whole thing, but if you want to pass a subset of it? just one element?

When you want to extend it, you have to extend many individual arrays, etc. When you want to copy entry 17 to entry 50, you can't loop over the fields - you have to spell out every field.

Re: The compiler will optimize that away

#50

Post by gpderetta »

Blikkentrekker wrote: post #22
polishTar wrote: post #16

Why can't a compiler optimize that? Perhaps I'm naive, but it seems totally possible for a compiler to have some sort of heuristic that allows it to do this transformation behind-the-scenes when it makes sense

The ironic part is that the compiler can't because the languages are fairly low level for performance's sake. C and Rust make various guarantees about data layout which programmers rely upon. C compilers cannot turn an array of structs into a struct of arrays because the layout of arrays is guaranteed, and needed to make common and trivial C accesses work which work by pointer arithmetic. Turning an array of structs…

It is technically also possible in C as long as the program can't tell the difference (thanks to the as-if rule). This is hard to prove though and in practice requires whole program compilation.
Post reply on HN