29 ms·

The compiler will optimize that away

• theamk 5y ago
  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 making it easy, and this is bad! Meanwhile you can data into columns and enjoy faster programs.
  • aparsons 5y ago
    What do you mean by game-style here? I’m very intrigued. Any place to read more about these?
    • foota 5y ago
      The keywords here are things like data oriented or "structures of arrays". Some examples are unity ECS or amethyst and bevy in Rust language.
    • astrange 5y ago
      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.
      • astrobe_ 5y ago
        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 https://en.wikipedia.org/wiki/Parallel_array
      • scambier 5y ago
        It's "Entity Component System". The "system" is part of the pattern name.
      • BlueTemplar 5y ago
        Plenty of games use OOP (C++ !). And ECS is just relational OOP.
    • loopz 5y ago
      Gaming has always been pushing boundaries of what's possible performance-wise. For high-throuhput data loops, there's already established patterns used by gamedevs that maximize use of cache and cpu/gpu.
    • elcapitan 5y ago
      Look for "Data oriented design" or "Structs of arrays". Here's a talk on the former by Mike Acton: https://www.youtube.com/watch?v=rX0ItVEVjHc https://www.youtube.com/watch?v=rX0ItVEVjHc On the latter, there's Jai, a new programming language for games (WIP, unpublished) by Jonathan Blow, who has been very public in documenting the process creating it, and which is centered around such concepts. There is some unofficial documentation of the ideas on SoA vs AoS and how the language can help switching between the two, e.g. here: https://pixeldroid.com/jailang/overview/Features/SOA/#/overview/ https://pixeldroid.com/jailang/overview/Features/SOA/#/overv... and here: https://github.com/BSVino/JaiPrimer/blob/master/JaiPrimer.md#data-oriented-structures https://github.com/BSVino/JaiPrimer/blob/master/JaiPrimer.md... Edit: Just realized that the articale even mentions Jai towards the end.
    • CodeArtisan 5y ago
      https://gameprogrammingpatterns.com/component.html https://gameprogrammingpatterns.com/component.html https://gameprogrammingpatterns.com/data-locality.html https://gameprogrammingpatterns.com/data-locality.html
  • speedplane 5y ago
    > Instead, we should be using game-style "data oriented programming" a.k.a. "column databases" for a much higher performance. This makes logical sense, but I don’t buy it in practice. Most of the heavy data reads are handled by databases, which do optimize for this stuff. I just doubt that, in most software, a significant amount of software performance issues are a result of poor memory alignment of data structures.
    • gumby 5y ago
      When your datasets are quite large a sql database becomes an absurd bottleneck. Think of weather or aerodynamics simulations.
    • nine_k 5y ago
      Cache misses can lead to major slowdowns. Everything depends on the access patterns in critical loops. If you need most of the fields of a struct in each iteration, the classic way is beneficial. If you need a narrow subset (a "column") of fields in a large collection of objects, splitting objects into these columns speeds things up.
      • tpxl 5y ago
        The most upvoted stackoverflow question is about branch prediction (which is caching in a way): https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array https://stackoverflow.com/questions/11227809/why-is-processi...
  • jhgb 5y ago
    > 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. Something like DataDraw (http://datadraw.sourceforge.net/ http://datadraw.sourceforge.net/) does with C? > However, most modern languages (C, C++, Python, Java, etc..) are not making it easy Funnily enough, it was yesterday when I though about how cool it would be to make an implementation of Oberon-07 (http://oberon07.com http://oberon07.com , https://people.inf.ethz.ch/wirth/ProjectOberon/index.html https://people.inf.ethz.ch/wirth/ProjectOberon/index.html - a simple-enough language to experiment with in various ways) that would use something like this as its in-memory data representation. It came up as a consequence of me wanting to have an implementation of Oberon-07 for WebAssembly, and realizing that the necessity of "restarting" the whole binary at any code change (necessitated by how WebAssembly works) also allows for some liberties in data representation (for example running out of compressed IDs for instances of a type could be handled in exactly the same way as changing the code of the running program - by generating a new binary with expanded space for these IDs and restarting it using the serialized old heap).
  • tom_mellior 5y ago
    > 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.
    • beagle3 5y ago
      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.
      • tom_mellior 5y ago
        A subset of an AntColony is another AntColony containing sub-arrays. One element of an AntColony is an Ant which you can instantiate with the data at the appropriate index from each array. I'm not trying to be difficult, I really don't see the problem with implementing these basic programming tasks. I agree that spelling out the fields can become tedious if you have a lot of structures of arrays or lots of fields per structure. A 100-line Python script can generate all this code for you if you prefer. Sure, it's a "limitation" of most programming languages that they don't provide this out of the box. But not a big limitation, I'd argue. Many languages even have features that allow you to write this functionality as a library, 100% inside the language (Python and Java annotations, for example).
        • beagle3 5y ago
          > I really don't see the problem with implementing these basic programming tasks. That you have to write them over and over again for every single class. You offer to do that with Python. > But not a big limitation, I'd argue. Many languages even have features that allow you to write this functionality as a library, 100% inside the language (Python and Java annotations, for example). This is an argument of the "all languages that are Turing complete are essentially equivalent" kind. True, but not interesting in this context. Ecosystem matters. If your Java program is the only one that does these things, it may just as well not be Java. You will be unable to use any other library without back-and-force adapters, for example.
  • mjevans 5y ago
    Structs are easy to envision as a repeating pattern tessellating across memory space; it makes slicing regions of data and bulk memory copy (e.g. DMA) easy. Yet if the algorithms mostly work with subsets of those fields then a 'column database' type of data layout clearly has benefits. Though for the complex case I would prefer more syntax sugar from the language. A "column struct" datatype that might include tuning suggestions for stride, size, etc; but would present a simple interface for humans. Given multiple underlying blocks of records a parallalizable foreach style loop might even shard across NUMA distributed threads if supported at runtime.
  • antpls 5y ago
    columnar layout is only faster if reads are sequential
    • cma 5y ago
      If things work one or a few columns at a time this isn't necessarily true. Prosumer CPU L3 caches are already up to 128MB and will be up to 1GB before long. If one or a few full columns fits fully in cache but all the data doesn't, columnar layout may still be faster in the face of random access within the column.
• conradludgate 5y ago
  If you want to utilise this data oriented approach in rust, check out soa-derive[0]. SoA stands for struct of array, rather than the conventional array of struct. [0]: https://crates.io/crates/soa_derive https://crates.io/crates/soa_derive
  • d0tnet 5y ago
    This is amazing!
  • teh_matt 5y ago
    I hacked up something similar (https://gitlab.com/mbryant/functiontrace/-/blob/master/src/profile_generator.rs#L123 https://gitlab.com/mbryant/functiontrace/-/blob/master/src/p...) a while ago. Your variant looks much more useful!
    • conradludgate 5y ago
      Yeah I'm a big fan of proc-macros. If utilised well, it can do some really great things
• bvrmn 5y ago
  > 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.
  • bsdubernerd 5y ago
    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.
    • bvrmn 5y ago
      I have experience with performant cache-friendly code. Yes, data oriented approach can be useful in some fields. But author blames the whole industry having low demand of performant code and wants python to accommodate cache-friendliness. This is a high level BS.
  • typon 5y ago
    Data oriented programming isn't a framework or paradigm. It's simply a principle that says that programs should be written to solve particular problems on particular hardware. If objects serve a purpose to this end, then they are also data oriented programming.
• mvanaltvorst 5y ago
  “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.
  • astrange 5y ago
    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.
    • moonchild 5y ago
      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 https://llvm.org/pubs/2005-05-04-LattnerPHDThesis.html)
  • SuchAnonMuchWow 5y ago
    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.
    • barrkel 5y ago
      Struct of arrays layouts does put you in a good position to apply vectorization techniques though. The article is rather more about columnar vs row formats for program entities than it is about locality generally. Columnar databases often use vectorized evaluation strategies because it's low-hanging fruit.
• gumby 5y ago
  > What if a programming language would provide us with a structure that would act like an array of structs, but internally it would really behave like a struct of arrays? I do this all the time (well, it’s not uncommon) in C++. The nice thing is I can mix the two with a bit of manual glue so callers don’t even have to know (though if you are doing this it’s often worth letting some callers know for the reasons described in this post.
• nine_k 5y ago
  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 :)
  • disgruntledphd2 5y ago
    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.
    • grayclhn 5y ago
      I think the desired functionality is closer to Pandas than Numpy — you want coordinated arrays of different data types, not higher-dimension arrays of the same data type. R and Pandas aren’t exactly known for their outstanding native performance (they’re generally fast after converting dataframes to arrays and outsourcing to C or Fortran) so they’re great demonstrations of the syntax for some of these indexing problems but leave a lot to be desired.
      • cozzyd 5y ago
        ROOT TTrees will "split" class members to effectively transform them into AoS although this is mostly for IO efficiency.
• lordnacho 5y ago
  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 latency chart he provides, there's another level to it: going to a database server. If you're gonna do that, you're not really in the speed game anyway, so why not make it simple? Just write it in the most uncomplicated way the language allows, and that's it. Waiting for the DB will take way longer than filtering the ants, forget all the optimizations. Edit: Forgot to mention with ECS, you have a different organizing principle. It can be quite enlightening to work with "systems that operate on data" as opposed to OO where you have the data declared next to the functions that mutate it. It can add clarity for certain problems. 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. 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.
  • rhn_mk1 5y ago
    To elaborate on Bevy: the data-oriented approach used is called an Entity Component System.
    • meheleventyone 5y ago
      And super importantly an ECS is not necessarily data-oriented.
  • tgaj 5y ago
    > 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.
• smasher164 5y ago
  Impedance mismatch. Languages don't give the compiler enough semantic information to work with, and some require heavy runtimes. Compilers, on top of having to infer semantic information about the above, aren't able to sufficiently utilize the hardware, either due to constraints on the types of analyses done, or lack of control. The hardware exposes an API too high-level or too unfamiliar to existing compilers. IMO, the future is bright, because all these layers are being re-thought. However, phrasing this as a debate over programming paradigms is a red herring. If coupling data and behavior is a useful mental model, we ought to accommodate that while giving the compiler more to work with.
• tester756 5y ago
  >The hardware has improved, but the languages didn’t I kinda disagree with author, because """languages""" improved Let's take a look at recent features in C#: Spans and CPU Intrinsics
• polishTar 5y ago
  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
  • Blikkentrekker 5y ago
    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.
    • gpderetta 5y ago
      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.
      • Blikkentrekker 5y ago
        The C standard provides guarantees about data layout even if the compiler can prove it will never be used internally, for the sake of, say, external debugging.
        • gpderetta 5y ago
          And C compilers routinely optimize structures in such a way that they are impossible to inspect in a debugger. Because of SRA, non escaping aggregates might even not be allocated on a memory location at all.
• dhsysusbsjsi 5y ago
  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”.
  • thrwaeasddsaf 5y ago
    Those two are followed by a third rule: "whoops it's too late now, we'd have to rearchitect and rewrite everything and we can't justify the cost"
• Const-me 5y ago
  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.
  • moonchild 5y ago
    Actually...https://arxiv.org/pdf/1902.04738.pdf 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.)
    • Const-me 5y ago
      > 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.
      • PixelOfDeath 5y ago
        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.
• elcapitan 5y ago
  > The programming languages listed above are all over 20 years old and their initial design decisions, like Python’s global interpreter lock or Java’s everything is an object mindset, no longer make any sense today I wonder what general purpose languages (as the mentioned Jai is meant for games primarily) will be the best fit for modern architectures, besides obvious things like doing it in C and just doing everything manually to fit the machine nicely.
  • NohatCoder 5y ago
    I don't see any particular reason why Jai shouldn't be usable for other stuff than games, there are no baked-in assumption about any gamey nature of programs.
  • beagle3 5y ago
    It's the APL/J/K/Fortran model. It fits modern CPU and memory architectures, it fits GPUs, and slow external storage. And rather surprisingly, it always has, even when memory latency was 1 cycle and there was no prefetch (for which you have to go back to the late 70s). The first APL implementation is from 1962 or so, first Fortran is 1955 or so. R and Numpy use it to deliver their speed while still providing high level semantics.
    • bloaf 5y ago
      I too suspect "data oriented programming" is just array programming rebranding itself.
  • dnautics 5y ago
    > I wonder what general purpose languages I'm looking forward to zig. The author is taking a lot of care and effort to make sure the content works on legacy systems as well as modern systems, so I think the level of flexibility that entails will also mean the flexibility to adapt to the future. Also, IIRC zig has an AOS to SOA transformation in its stdlib? In any case, they have been refactoring the language parser to use SOA to great effect: https://github.com/ziglang/zig/pull/7920 https://github.com/ziglang/zig/pull/7920
• TazeTSchnitzel 5y ago
  The metaprogramming available in languages like Rust and C++ could maybe be leveraged to make the struct-of-arrays model easier. Wouldn't be the same as native support, though.
  • PixelOfDeath 5y ago
    There is some, lets call them experimental, C++ libraries for that. But C++ not having static reflection is the main show stopper on that frontier.
    • f00zz 5y ago
      > There is some, lets call them experimental, C++ libraries for that. Could you provide some links?
      • PixelOfDeath 5y ago
        https://github.com/Yamahari/struct_array https://github.com/Yamahari/struct_array It uses C++20 features and macros. The macros limit it to a POD count of 8.
        • f00zz 5y ago
          Thanks!
  • mhh__ 5y ago
    I've seen this done in D fairly easily, almost definitely closed source unfortunately.
  • adgjlsfhk1 5y ago
    Julia has a package that provides incredibility easy to use SoA. https://github.com/JuliaArrays/StructArrays.jl https://github.com/JuliaArrays/StructArrays.jl Julia's metaprogramming and multiple dispatch mean that it can use user structs fully transparently. Everything just works.
• truth_seeker 5y ago
  Extremely well written and communicated.
• beagle3 5y ago
  > 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.
  • Tyr42 5y ago
    I also think that it's a shame he didn't bring up NumPy & Pandas, or R. He's just created a data frame and then complained that there's no functions to sort it, but we do have those. They are here. ants = pd.DataFrame({ "name": ["bob", "alice", "carol"], "color":["red", "blue", "red"], "age":[1.1, 0.5, 1.2], "warrior":[True, False, True]}) # Or read_csv to get the data in. # Count number of warriors. True => 1, False => 0 ants['warrior'].sum() # Returns 2 # Count old red ants ((ants.color == "red") & (ants.age > 1.0)).sum() # 2 again ants.sort_values(by="age") I think Pandas and NumPy should be up there as making the language easy to use in a SoA way.
    • CornCobs 5y ago
      Yeap. I think Pandas could and should see a lot more use outside data science as performant in-memory data storage in Python. The best thing is? Most data scientists don't even care about SoA vs AoS - tabular structure is easy to grok, easy to use AND performant by default!
  • celrod 5y ago
    ISPC also has first class support for "(array of) structure of arrays", see: https://ispc.github.io/ispc.html#structure-of-array-types https://ispc.github.io/ispc.html#structure-of-array-types For example: soa<8> Point pts[...]; declares an array of struct of arrays, where each inner struct array contains 8 elements. This would have the advantage of playing well with the streaming prefetcher if you're working with all fields of the `Point` type, and allowing the compiler to use and increment a single pointer for loading/storing, accessing each field with a small compile time offset (that can get folded into addressing calculations, making them essentially free). Julia's StructArrays package is also very convenient: https://github.com/JuliaArrays/StructArrays.jl https://github.com/JuliaArrays/StructArrays.jl
• 0-_-0 5y ago
  There is a Nim library inspired by this blog post that simulates array-of-structs with struct-of-arrays (implemented through macros): https://github.com/liquidev/datarray https://github.com/liquidev/datarray
• albertzeyer 5y ago
  Another orthogonal aspect with modern hardware is the increased amount of parallel execution. Most of the standard programming languages are not really designed to support this well. So we use extensions like CUDA. But this is not really general purpose but only for GPU. Once we reach maybe 100 cores, or 1000 cores, or some orders of magnitude more cores in the CPU, we have to have better general purpose language support for this. Most memory is local for some subset of cores. There are warps which execute the same code (SIMT).
  • astrange 5y ago
    What's this "once"? This was a theory of future CPUs from maybe a decade ago that totally hasn't happened. We're instead getting increasingly smaller few-core CPUs in things like smartwatches. In laptops, M1 replaces a hyperthreading CPU with one that runs a single thread much faster.
• andi999 5y ago
  Why wouldn't a new programming language like python nowadays decide to use a Gil? I thought the point was to make the interpreter easier to write.
  • toast0 5y ago
    A global interpreter lock made sense in the 1990s when multiple cpus was rare, and when it happened, it was usually two. Now, it's hard to find a system with just one cpu. Maybe something really embedded; but IoT stuff sometimes is multiprocessor these days. Anything intended for regular computers needs to be prepared for 1-16 cpus, and more isn't hard to find if you need it. Building a new programming language with a big constraint preventing it from using modern computing seems like a mistake. That doesn't mean an early version wouldn't start with a big lock, but fine grained locking is probably needed before release.
• Bancakes 5y ago
  Wish normal people witnessed how few innovations are being introduced on the CPU/GPU side in the 21st century. The high-performance software industry is low-key carrying the hardware architecture industry on its back. Shaders, pipelines, coroutines, etc are there to make the programmer's job easier in the end. On my old nokia 3110c, I could access my calendar and appointments instantly by clicking right on the d-pad. On my Nokia Lumia 710, I had to wait for a splash screen. On my Nokia 3.1, I had to wait for internet synching. The difference between slow and fast software far outstretches that of slow and fast hardware.
  • CyberDildonics 5y ago
    I can't believe anyone would say this, it is basically the opposite of reality. CPUs and GPUs have come a long way in two decades. Even CPUs are incredibly fast, but between memory allocations, memory layout, multi-threading and just weeding out terrible algorithms, most software can probably be sped up by 100x. > The high-performance software industry is low-key carrying the hardware architecture industry on its back. That doesn't even make sense. Do you think GPUs aren't more powerful than 20 years ago and that the difference between quake 3 and Order 1888 is software? > On my Nokia 3.1, I had to wait for internet synching. The difference between slow and fast software far outstretches that of slow and fast hardware. Right - doesn't this contradict everything you just said?
    • Bancakes 5y ago
      These are steady, predictable, iterative improvements. We have nothing groundbreaking like 1970s-1990s. Of course I'm not saying modern hardware is slow, but it's not progressing like it used to.
      • CyberDildonics 5y ago
        That is both not true and not what you said at first. Transistor density has continued to rise but there is only so much you can do when people mostly run javascript on a single thread. There were a lot more break throughs in the early days of electronic components too because everything was new. CPUs are a world away from where they were two decades ago, but people don't notice because typing into a facebook window still lags. It is an incredibly superficial nonsense way to look at what has really happened at the hardware level.
• pif 5y ago
  Bullshit! The most important feature for the utter most of enterprise software is to be maintainable over requirement, managing and employee changes. Such optimizations as those described in the article make sense only in a handful of situations, and using them must not be a light-heart decision, because their cost is big. I fully agree with going all in when it makes sense, but we all know what is the root of all evil.
  • CyberDildonics 5y ago
    > Such optimizations as those described in the article make sense only in a handful of situations, and using them must not be a light-heart decision, because their cost is big. This is really not true. Inheritance is not only slow it is needlessly complicated. It introduces dependencies and indirection while gaining nothing. People who have never programmed before think having a car class inherit from a vehicle class makes sense. Eventually they realize that what they have are arrays of positions and velocities that they need to combine. That could be multiple files with lots of boiler plate nonsense or it could be a single loop. > I fully agree with going all in when it makes sense, but we all know what is the root of all evil. If you are implying optimization, you should realize that that quote comes from someone telling his students not to noodle the tiniest details like post or pre increment in their for loops to get the compiler to output one less instruction when their program isn't even done yet. If you want modern software to run fast, you need to architect for it first. Then you can make things work, then you can profile and optimize. This idea that there are no consequences to the early design decisions you make is a gross distortion of the context of this quote.
• jefftk 5y ago
  It's not a fun language to work in, but SQL does a lot of what the author is asking for.
• jmull 5y ago
  There’s a nice introduction to a data-oriented approach in here, but it’s buried in some junk. E.g., I don’t think a lot of developers believe compilers are magic optimizers. And programming languages, including the ones referenced, have changed quite a bit over the last 20 years. A strong enough case for general data-oriented features would cause at least some of them to support it. Also, a great amount of code should be written for maintainability — that is, to be read and easily understood by a future developer without special insight — rather the performance. Talk of “software cultists” is silly and shows how poorly the author understands the issues driving software development approaches. Not to mention, a performance analysis of software systems that stops at main memory is about only a subset of software (one that has a pretty thin slice of overlap with “enterprise” software, where your bottlenecks are overwhelmingly IO and DB).
  • jolux 5y ago
    To me, the goal of language implementations should be to make the most maintainable code also the fastest code. I shouldn't have to worry much about the performance characteristics of my software outside of general concerns about algorithmic complexity.
    • deleted 5y ago
      [deleted]
    • secondcoming 5y ago
      That all depends on what type of software you write. I don't think there'll ever be a language that ticks every requirement box.
      • jolux 5y ago
        You can’t get all the way there but it’s a North Star, I think.
    • blakehaswell 5y ago
      At the end of the day our software is going to run on real machines, sending data across real networks. I feel like we'll always be leaving performance on the table if we don't understand the characteristics of the hardware we're developing on. I can build a cubby house in the backyard (low performance system) without understanding the the physical characteristics on the materials I'm using, but if I want to build a sky-scraper (high performance system) I need to understand the actual physical materials and how to use them effectively.
• jupp0r 5y ago
  The implicit premise of the article seems to be that all software has to be heavily optimized. This is completely wrong. All the languages mentioned in the article are still around because it doesn’t matter how performant 99% of code is. For the 1%, we can think about cache misses, SIMD and data parallel approaches. In my experience this is totally possible and not too hard, but has the enormous downside of making that code hard to reason about. You are also optimizing for today’s hardware, which means that it might not run that great on new hardware in 20 years. This means that somebody has to go in and rewrite that hard to understand optimized code. It’s really a tradeoff between the cost of that and the benefits from optimization. Some of the future costs can be mitigated by using a few techniques from the start. One good idea is to keep an vanilla unoptimized version of the part that you are optimizing around as a reference implementation. This will help understanding what the optimized code does and can be used as a stopgap to support new hardware. It can also be a nice baseline to compare optimizations against. The beauty of compilers is that they do a decent job of optimizing the 99% of code that would otherwise never be optimized, at 0 cost. This is a different sweet spot on the cost benefit curve.
  • esailija 5y ago
    I disagree. Almost all software I use these days is absurdly slower than it should be and probably a massive drain on collective productivity. I have ssd, fast internet, 64gb ddr4 etc, almost everything I do should be impercetibly instant but instead takes seconds and even minutes. Yeah of course most of that slowness is not even because of ignorance of the low level stuff but complete disregard of performance aspect of software. If it's even slightly more convenient for a programmer to do something that is very stupid performance wise, they will do it. Sure developer time costs, but this cannot actually be the reason. Because tooling is also ridiculously slow in exactly same way and wastes countless of hours of that costly developer time.
    • einpoklum 5y ago
      You're both right - but about different kinds of software. I believe the GP post was thinking an application which has some heavy computational kernel to it, where most of the processor time (and other resources) are spent - with a lot of other code for UI, configuration, some parsing etc. And you seem to be talking about everyday desktop applications: Browser, mail client, word processor, instant messaging client, and maybe even your IDE as a programmer. Those kind of apps don't have that kernel of hard computational work - their work is much more diffuse.
• jamesbrock 5y ago
  > What if a programming language would provide us with a structure that would act like an array of structs, but internally it would really behave like a struct of arrays? We could program in the typical object oriented way that is convenient for humans, while still enjoying in great performance due to playing nice with the hardware. > So far, the only programming language I know of that supports this type of crazy data transformations is JAI, Haskell supports this type of data transformation. http://hackage.haskell.org/package/vector-0.12.3.0/docs/Data-Vector-Unboxed.html http://hackage.haskell.org/package/vector-0.12.3.0/docs/Data... > unboxed vectors of pairs are represented as pairs of unboxed vectors.
  • CyberDildonics 5y ago
    Haskell uses linked lists everywhere, so any transformation like this likely does nothing for speed.
    • tom_mellior 5y ago
      The given link describes unboxed vectors. This is Haskell-speak for "actual array of actual machine numbers".
    • astrange 5y ago
      Haskell uses linked lists as a metaphor for generators (since it's a lazy language), which is a strange decision since linked lists are a bad data structure, so you have to write the program to avoid accidentally ever doing what it says it does.
      • dnautics 5y ago
        > linked lists are a bad data structure Why is that? They're perfectly fine for most purposes, and have the advantage that when you pass one across a function boundary the callee can play with it or modify it or do whatever the hell they want and when the callee returns, the caller's linked list is untouched. That's an incredibly valuable feature for correctness and safety.
• commandlinefan 5y ago
  I’ve never been able to get my head around the “anti-optimization” mindset. Like... what else should we be doing? If you’re going to be writing code anyway, you might as well take optimal advantage of the hardware while you’re at it. Now, some people point out that attempts to optimize sometimes backfire, but that’s a different problem - that’s something you should work on improving though practice (and measurement).
  • fwip 5y ago
    "Anti-optimization" advocates doesn't say "optimized code is bad." It means "other things are more important than optimization." One of those things is the amount of work required. For example, if it takes 30 minutes to get a "good-enough" solution, and 2 days to get a "very optimized" solution, most of the time you should go with the good-enough solution, because most of the code you're writing isn't performance-critical.
• einpoklum 5y ago
  This article makes a bunch of invalid (sometimes implicit) assumptions or claims: *A 20 yro language's design decisions don't make sense today because of the hardware perf situation change.* 1. Most languages were not designed for optimal utilization of the specific hardware situation during their conception. 2. Even languages designed with performance in mind somehow are still incredibly general and flexible things. 3. The article itself shows that CPU hardware has been changing along a mostly predictable path for decades. Everyone knew Dennard scaling would end, even if you couldn't predict it to within the single year. Everyone saw CPU latency was decreasing much much faster than memory latency, already in the 1980s. -- * The main problem that we have today lies in utilizing the CPUs to their full potential.* This is _a_ main problem, not _the_ main problem: * There are other, specialized processing hardware (like GPUs). * There's computation happening elsewhere on the system, e.g. on disk controllers and NICs. * And actually, if you look at desktop environments and apps: They really don't need to utilize the CPU to its full potential; they're a mess of entanglement of things which get in each other's way and it's difficult to figure out why your system ends up being sluggish despite your brand-new shiny hardware. -- *Another problem with the current programming languages is that they didn’t evolve beyond the C-style type of programming. * * C-style type of programming is just fine for C-style kinds of programming tasks. Every language has strengths and weaknesses. Some pairs of languages have a more obvious "X is an evolved Y" or "X is a better Y" relationship, but not that many. * Most languages do not evolve or change to exploit specific hardware capabilities. Or at least - few language changes are intended to achieve that. -- etc. It's not a junk article though. The data orientation of program design is a useful notion, in many programming languages. It's just that, instead of reading this blog post, which quotes Mike Acton, you can just watch Acton's talk on this principle: https://www.youtube.com/watch?v=rX0ItVEVjHc https://www.youtube.com/watch?v=rX0ItVEVjHc
  • tialaramex 5y ago
    Another example: > “Use const and the compiler will optimize that away!” Nobody knows what the compiler will do, if nobody checked what the compiler did. Rust (in the Rustonomicon if nowhere else) specifically promises that const gives you the same results you'd get by calculating and manually inlining the constant itself everywhere. It even spells out all the things you thus can, and can't do in a constant so that your compiler can definitely correctly evaluate the constant from the point of view of the target architecture despite potentially different hardware. e.g. if you tell Rust const BAR :isize = isize::from_be(0x1234); You've conjured a constant BAR whose size and data layout depends on the target architecture, but the language promises that figuring this out incurs no runtime cost, the work will be done at compile time. Indeed Rust will refuse to compile your program if it can't figure out how to do this, explaining what went wrong, e.g. that same above snippet would not have worked years ago, because isize::from_be() was not yet marked as suitable for such endeavours and so the compiler wouldn't attempt it. If you mark a function the compiler can't evaluate as being suitable, the compiler will reject that too, even if you don't use the function, somebody else might and it won't disappoint them.
• CameraSupra 5y ago
  Why aren’t hardware designers designing hardware for the languages and methods we have?
  • sesuximo 5y ago
    There are physical limits. E.g. clock speed can’t go so high that information must travel across the cpu faster than the speed of light. E.g.2. As caches get bigger, it takes more time to index them.
  • astrange 5y ago
    They are (through prediction, reordering, etc in the CPU), but manual approaches like hinting or VLIW have always turned out to fail, and the automatic approaches we're using now turn out to have security issues like Spectre.
• alfiedotwtf 5y ago
  > While not having to think about the memory is going to make you more productive, that productivity comes at a heavy price. I highly recommend "Code Optimization: Effective Memory Usage" if you want to think more about these problems
• maydup-nem 5y ago
  The first approach creates a list, which means cheap insert/delete. But it's not a fair comparison, as the second approach doesn't let you do that. For that, you would need to allocate an array of objects in the first approach instead of a list.
• dnautics 5y ago
  > So far, the only programming language I know of that supports this type of crazy data transformations is JAI I believe zig supports this too, and it's very encouraging that the creator has recently done a refactoring of the language parser taking a data-oriented approach, so that has surfaced pain points to be repaired for folks who would like to do things that way.
• Gibbon1 5y ago
  I'm late to the party but his table is missing an entry Event Latency Scaled Latency Network Access 50-200ms 5-20 years.
• jvanderbot 5y ago
  Did you also notice how the need for interface and type abstractions goes away? If you have a function that sum()'s a list of numbers, you can use that to sum() any of the Ant's members by passing a ref to the list. Otherwise you have to write AntSummer classes that take Ant (and all the children of Ant's class). It does occur to me that there's a certain type of programmer for whom this is obvious. And that type of programmer was not using classes anyway for the reasons above. For that programmer, objects are a massively overused hammer in software design. I know those types, and they're very good. It might be there's too much brainpower wasted in designing object hierarchies that could go to exploring functionality or producing value. Or it might be coincidence. I'm not really that guy necessarily, but for simply reasons of communicating and comprehending designs I always thought objects more than a few members were just plain wasteful. There just never seemed to be a reason to have all those mutable hidden member variables unless it was to abstract something like a data structure.
• jayd16 5y ago
  The real answer is you almost never need to solve this silly problem. If your data is static, why are you counting through arrays? If its dynamic, your n is probably low enough it doesn't matter or you're using some better data structure than an array. If you do hit this kind of problem its usually in games (lots of dynamic user generated content) and even then the n is usually negligible. The parts where this does matter are already very data oriented. (Although not just in the way the article implies. Think vertex buffers and bitmaps.) Point is, languages could probably add some kind of column oriented type of array and compilers could efficiently loop through them but it probably wouldn't really help all that much.
  • bigbizisverywyz 5y ago
    Would have to agree, common data structures like linked lists and maps can't really be easily composed into this sort of sequential layout as required, and the main advantages only come about when you're searching through the data for something. The other data we process a lot of is strings which are commonly variable in length and scattered around in separate mem allocations. Still, the performance difference between the 2 examples was eye-opening so I'll definitely spend a bit of time looking at Data-Oriented Design book for some ideas.
• rusanu 5y ago
  There are several versions available of Scott Meyers' CPU Caches and Why You care talk: - https://vimeo.com/97337258 https://vimeo.com/97337258 - https://www.aristeia.com/TalkNotes/PDXCodeCamp2010.pdf https://www.aristeia.com/TalkNotes/PDXCodeCamp2010.pdf
• xiaodai 5y ago
  Something I genuinely don't understand "buttery smooth 3D game"s are created with C++ too but why isn't C++ an issue for games? Seems to contradict the premise which is that programming languages were designed in the past and hence not efficient for modern computers.
  • mort96 5y ago
    If you use C++ in the "default" object-oriented way, your program won't be as efficient as it could've been. Computers are fast, so you can still make games which run well, but not as well as they could've been. C++ can also be used in ways which are really fast on modern machines. You can, for example, write code in a data-oriented "struct of arrays" approach with C++. The argument is just that C++ isn't designed with that in mind, and that a high performance language designed today could be designed with modern machines in mind.
    • kaba0 5y ago
      > If you use C++ in the "default" object-oriented way, your program won't be as efficient as it could've been That’s way too general to hold any truth. C++’s classes are zero cost, SoA vs AoS is not always relevant. If I have three instances of my class, each doing something compute-intensive in a simple method, how is it different to dod? Also, even virtual functions are not necessarily any more expensive than the alternative if one knows what he/she does.
      • mort96 5y ago
        The context of the discussion is one where the difference between SoA and AoS is significant. It’s not always true in general that your program won’t be as efficient as possible, but it’s true in the context we’re discussing, where you have a lot of things (entities or whatever) and you’re iterating through them, which is what is being discussed. I was writing a direct answer to the question of “how can it be true that C++ isn’t built for modern machines even though modern games with good performance on modern machines use C++”. I think the answer is entirely correct in context.
• BlueTemplar 5y ago
  At some point there's an assumption that OOP and DOD are incompatible, while they are actually orthogonal.
• zmmmmm 5y ago
  It's interesting that Java/JVM is both one of the worst cases and best here. When you work only with arrays of primitives its performance is shockingly good and aligns well with the needs for locality. Hopefully future improvements extend that to include structs/records and then it may actually be quite a powerful platform in this regard.
• viktorcode 5y ago
  Jai can't come out fast enough. Don't think for one instance that the language is only for writing games; it will serve equally well for writing any kind of software where the performance is nice to have.
• oever 5y ago
  If memory controller could be given a mask for what bits or bytes are wanted, then the memory overhead could be reduced without changing the representation in the programming language. At that point the compiler can optimize memory access by generating the mask.
  • incrudible 5y ago
    If you had the opportunity to change the entire cache hierarchy at a hardware level and make all the compilers support that, you could do a lot of things. You don't. You control the software.
• selimnairb 5y ago
  The data-oriented design approach is and has been standard practice for doing numerical simulations on High Performance Computing (HPC) environments. Still the problem of language support and syntactic sugar to make this style less error-prone and easier to do needs more work.
  • selimnairb 5y ago
    I think this approach applies even more so for GPU compute as it’s the only sensible way to code these devices.
• jeff-davis 5y ago
  "What if a programming language would provide us with a structure that would act like an array of structs, but internally it would really behave like a struct of arrays?" What about SQL when using a columnar data store?
  • rualca 5y ago
    An array of structs is already a struct of arrays if you're willing to do some offset math.
    • incrudible 5y ago
      That would make the whole thing moot. The crucial difference between AOS and SOA is that the "physical" memory layout is different: AOS: [xyzw][xyzw][xyzw][xyzw] vs SOA: [xxxx][yyyy][zzzz][wwww] If you have such a layout, a SIMD instruction touching 4 packed words has quite different behavior. Arguably, SIMD is pointless without SOA or AOSOA.
      • rualca 5y ago
        > SOA: [xxxx][yyyy][zzzz][wwww] That difference only occurs if, for some random reason, you came about what's the address of element zero of that array, or if for any even rarer reason you have a hard requirement of when you cease to process x and start to process y, and you find a single memory jump prohibitively expensive. Meanwhile, AOS is already by definition [xxxx] and [yyyy] and [zzzz] and [wwww], given the remaining members of the struct are treated as padding.
        • incrudible 5y ago
          > Meanwhile, AOS is already by definition [xxxx] and [yyyy] and [zzzz] and [wwww] There must be a misunderstanding here. AOS is by definition [xyzw][xyzw](...), the (C/C++) compiler has no leeway in rearranging this. I'm also assuming that there's no padding necessary, in either case. Perhaps my way of notation is confusing, in that case I'm going to refer you to this page, which has code examples: https://software.intel.com/content/www/us/en/develop/articles/memory-layout-transformations.html https://software.intel.com/content/www/us/en/develop/article...
• offtop5 5y ago
  Back in the real world the best code is code that ships. Occasionally I find myself doing something stupid ( if you use Unity and try to do advance distance calculation in Update your going to have a bad time ) , but usually I never have to optimize. Modern computers might as well be magic
• dragontamer 5y ago
  While this article starts to discuss the low level details that underlie our code, I feel like its incomplete. * Latency hiding -- CPUs work extremely hard on latency hiding. A lot of those OOP-indirect calls will be branch predicted by the CPU in the simple cases (ex: if one object-type is more common than others, then those indirect branches will be branch predicted correctly in most situations). There are other bits of latency hiding: Hyperthreads, Out-of-order execution, pipelines. * Cache: L1, L2, and L3 caches can grossly mitigate a lot of the problems. While CPUs today are far faster than DDR4 RAM, L1 cache scales perfectly with the CPU. If you can keep your code+data under 64kB, you'll always be executing in L1 cache and basically get the full benefits. If 64kB is too restrictive, then you have 256kB or 512kB (L2 cache), or 8MB (L3 cache), both of which scale with the CPU. ------------ SIMD and Multicore goes backwards IMO. It turns out that the 1970s and 1980s were filled with very intelligent programmers working on extremely sophisticated supercomputers. I enjoy going back to the 1980s and reading Connection Machine articles on C-Star (a parallel language that's arguably the precursor to CUDA), or Star-Lisp. -------- If you write multicore software, then SMT / Hyperthreads are very effective at latency hiding. Running two threads on one core (or 4-threads or 8-threads, in the case of some IBM processors) allows your cores to "find something else to do" during those long latency periods where your CPU is traversing memory and waiting for RAM to respond. Working extremely hard to optimize just a single thread seems somewhat counterproductive. Its often easier to write "less optimized" multicore software than highly optimized single-core software. And SMT / hyperthreads will converge those onto a single core ANYWAY. So might as well take advantage of that feature.
  • joshuamorton 5y ago
    > * Cache: L1, L2, and L3 caches can grossly mitigate a lot of the problems. While CPUs today are far faster than DDR4 RAM, L1 cache scales perfectly with the CPU. If you can keep your code+data under 64kB, you'll always be executing in L1 cache and basically get the full benefits. I think even now you're underselling this. Depending on the types of transforms you're doing, an object-oriented (or row-oriented) instead of data-oriented (or column-oriented) approach can be faster due to caching. With OOP approaches, the object you're operating on will basically always be in L1 cache. On the other hand, if your ants name and age are in different columns and each column has 10000 things, you'll have to load both into L1 cache separately. Stuff like vectorization can further complicate things, but it isn't' as simple as data-oriented is more performant.
• jakear 5y ago
  Article seems to suppose the entities will only ever exist in one collection. If that’s the case then sure remap the field layouts to behave better in cache. But the second you want to reference only a single element of that collection, or reference many elements of many different collections, you’re now dealing with managing N pointers for N fields, which of course all get invalidated when the collection is modified, and ha w lifetimes tied to the lifetime of the collection. As opposed to the single object with its own lifetime. And of course all the cache locality arguments go out the window. The takeaway seems to be: if the entity in an atomic collection of items, represent that collection as the entity in as efficient manner as you see fit, rather than crating entities for each one. This makes sense, and is not out-of-line with OOP reasoning: each object corresponds to an atomic logical unit.
• kgr 5y ago
  The article seems to claim that if we did as he says and rewrote all of our code to be data-oriented instead of object-oriented, then our code would run ~2X faster and all of our performance problems would be solved. However, I got my first 64 thread server CPU 15 years ago and my first 64 thread desktop CPU six years ago, so I could get a much larger increase by instead keeping my OO code and making it concurrent (64X > 2X). Also, if being 2X faster would make everything better, we could just wait 18 months and let Moore's law take care of the 2X savings, rather than the much longer period of time it would take to redesign our languages and rewrite all of our code.
• Sohcahtoa82 5y ago
  > You may even realize that all of that enterprise cruft is not really necessary I will never understand why so many Java developers insist that every public value must be implemented as a private value with get/set with no exceptions. Or that every class needs to extend an abstract class that implements an interface. Haven't they heard of YAGNI?