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

21–30 of 329 posts

Re: The compiler will optimize that away

#21

Post by disgruntledphd2 »

nine_k wrote: post #12

I can remember the columnar approach used in Fortran back in the day. Fortran did not have records, only scalar arrays, so a natural way to represent a bunch of "objects" was to have a bunch of arrays for each property value. IDK if such prior art is any helpful today, though :)

This approach is still used (conceptually, at least) in statistical computing. NumPy and R are good examples of this approach, and also have solutions for the indexing problems outlined in the article.

That being said, statistical computing is at the mercy of the high cost of matrix multiplication.

I think that you can alter the order of arrays in numpy, and examine the performance difference.

Re: The compiler will optimize that away

#22

Post by Blikkentrekker »

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 into a struct of arrays is indeed an optimization that would be possible in a language that did not make such guarantees about data layout. Perhaps it would be interesting to have a data structure that provides less guarantees on lower level access that in turn could be more aggressively optimized.

Re: The compiler will optimize that away

#23

Post by dhsysusbsjsi »

It’s true that compilers won’t optimise memory layout but I would argue this is an issue for only a subset of the software engineering industry. More important is robust bug-free code with separation of concerns which these tools allow. Remember the first rule of optimisation: “don’t”. The second rule of optimisation: “Don’t...yet”.

Re: The compiler will optimize that away

#24

Post by Const-me »

Disagree about garbage collected runtimes.

A lot of widely used software is written in C or C++ and uses malloc/free extensively (C++ new/delete is mostly a wrapper around it). This results in memory layout worse than an equivalent managed heap would be. Happens because the memory allocated on C heap is immovable, while garbage collectors may move data around to defragment the heap.

Re: The compiler will optimize that away

#25

Post by SuchAnonMuchWow »

mvanaltvorst wrote: post #7

“Programming languages are old, therefore they will never take advantage of our hardware.” Have you looked at how compilers have changed the past 30 years? How they take advantage of SIMD? AVX? The LLVM-revolution? It’s delusional to think compilers will never be smart enough to vectorise object-oriented code, which is the main gripe of this article.

No, the main gripe of this article is data locality, not vectorization. Those two are completely orthogonal and complementary: you can have data locality without vectorization and vectorization without data locality, and both bring performance improvements. But vectorization bring a constant speedup (from x2 to maybe x16 depending on the ISA of the processor), but data locality can improve performance much more because memory accesses are thousands of times slower than processor cycles.

But if the semantic of your programming languages doesn't allow your compiler to change the layout of your data in memory, then there is almost nothing the compiler can do to improve data locality in your application.

Re: The compiler will optimize that away

#26

Post by moonchild »

Const-me wrote: post #24

Disagree about garbage collected runtimes. A lot of widely used software is written in C or C++ and uses malloc/free extensively (C++ new/delete is mostly a wrapper around it). This results in memory layout worse than an equivalent managed heap would be. Happens because the memory allocated on C heap is immovable, while garbage collectors may move data around to defragment the heap.

Actually...https://arxiv.org/pdf/1902.04738.pdf

On a more serious note, most c programs I see don't do very much of that, preferring to allocate fixed-size buffers on the stack. Additionally, most GC'd languages that aren't java have crappy GCs, and those GC'd languages that are java lack value types. This harms spatial locality quite a bit, and compaction can't fully compensate for that.

They are working on adding value types to the jvm, though; it will be very interesting to see how performance changes. (I expect not very much in practice—those projects for which performance was important were already using whatever tricks they needed to—but perhaps it will improve the ergonomics of performant java.)

Re: The compiler will optimize that away

#27

Post by rhn_mk1 »

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…

To elaborate on Bevy: the data-oriented approach used is called an Entity Component System.

Re: The compiler will optimize that away

#28

Post by moonchild »

astrange wrote: post #18
mvanaltvorst wrote: post #7

“Programming languages are old, therefore they will never take advantage of our hardware.” Have you looked at how compilers have changed the past 30 years? How they take advantage of SIMD? AVX? The LLVM-revolution? It’s delusional to think compilers will never be smart enough to vectorise object-oriented code, which is the main gripe of this article.

This article is about transforming memory layouts, which compilers don't do. GCC has some really really basic support for it which never works. Autovectorizing doesn't transform memory layouts, which is part of the reason it doesn't work that well either.

The sad part is chris lattner (llvm author)'s phd dissertation was on that exact topic. And yet nothing seems to have come of it since despite llvm's hegemony. (https://llvm.org/pubs/2005-05-04-LattnerPHDThesis.html)

Re: The compiler will optimize that away

#29

Post by astrobe_ »

astrange wrote: post #17
aparsons wrote: post #4

Earlier quoted context omitted.

What do you mean by game-style here? I’m very intrigued. Any place to read more about these?

It's called entity-component systems in games. Note that OOP was designed for simulations but games, the only kind of simulation people like using, don't use OOP.

I think the more accurate references is "Parallel arrays", aka "Structure of Arrays" (SoA) [1]

The amusing thing is that SoA is something you could see in old languages that didn't have data structures, or the code of newbies that don't know data structures.

[1] https://en.wikipedia.org/wiki/Parallel_array

Re: The compiler will optimize that away

#30

Post by Const-me »

moonchild wrote: post #26
Const-me wrote: post #24

Disagree about garbage collected runtimes. A lot of widely used software is written in C or C++ and uses malloc/free extensively (C++ new/delete is mostly a wrapper around it). This results in memory layout worse than an equivalent managed heap would be. Happens because the memory allocated on C heap is immovable, while garbage collectors may move data around to defragment the heap.

Actually... https://arxiv.org/pdf/1902.04738.pdf On a more serious note, most c programs I see don't do very much of that, preferring to allocate fixed-size buffers on the stack. Additionally, most GC'd languages that aren't java have crappy GCs, and those GC'd languages that are java lack value types. This harms spatial locality quite a bit, and compaction can't fully compensate for that. They are working on adding…

> 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.

Post reply on HN