6 ms·

The next phase of language design is making it possible to write "data-oriented" programs which largely live within the cache of the CPU. Ie., the next frontie

The next phase of language design is making it possible to write "data-oriented" programs which largely live within the cache of the CPU. Ie., the next frontier is moving from RAM to cache, since CPUs are not going to get faster than programs are "already slow". If you rewrite some OOP/Pointer-Machine-Model/RAM-Thrashing programs for modern CPUs, you can get 100-1000x speed-up. The evolution in language design seems, then, to be about exposing more of the hardware to enable developers to target it effectively.

zelphirkalt 4y ago
I don't think the next step is to expose more complexity of underlying hardware to the developer. If at all, then the next step is to have compilers deal with that. Let them rewrite the program.
- dgb23 4y ago
  You make a good, general point. But I found that a data oriented approach has benefits outside of performance and resource usage, because it nudges you towards: - normalized, small/tight data structures - data structures that are closely related in computational terms - smaller interfaces and functions that tend to be more re-usable and general - fewer if/else branches and more existence based branching via loops - fewer "business level" generics, macros and similar abstractions, because you can dispatch easily via tagging to concrete types - less code that "digs"/"drills" into data and more code that composes data - generally a simpler (less coupled) end result This all comes with a cost of having to do upfront design and exploration in order to decompose and lay out your data. And while it reduces the mental overhead of understanding the individual pieces of your program on a day by day basis, it might increase learning curve of seeing the big picture, especially at the beginning. So it is a tradeoff. But I think it would be too dismissive to say that the programmer is doing compiler work here. It is design work, and it is unlearning some of the notions of how to structure programs that carried on since the 90's. Some of which are performance related and some of which are about sensible code structure.
KapKap55 4y ago
The 100x plus speedup is no exaggeration either, I've noticed some incredulity from others at the numbers. For a very simple comparison, I recently was testing a (poorly) custom built data-oriented Entity-Component-System for usage in games with a more typical "componentized" object approach. No multithreading or anything complicated. On my system, the typical approach could generate about 1000 new objects and attach a single component in about 1 millisecond. The data-oriented approach could generate about 100,000 new "objects" and attach a single component in about 0.5 milliseconds. Same thing in the end, but one is roughly 200x faster in the same time frame. It's pretty stunning when you see stuff like this in benchmarks.
- moonchrome 4y ago
  I don't get this - you're talking about generating objects - I'm assuming you're talking allocating new objects. What's your bottleneck ? Allocator or do you have some poor data structure to update it ? Where is the speedup coming from ? The kind of speedup you're talking about sounds like moving from allocating each object separately to some arena and avoiding allocator overhead. I could be wrong in the assumptions - but OP is talking about fitting stuff in CPU cache don't really see how that translates to your scenario.
- ly3xqhl8g9 4y ago
  -----s.-ms.-us.-ns|---------------------------------------------------------- 0.1 ns - NOP 0.3 ns - XOR, ADD, SUB 0.5 ns - CPU L1 dCACHE reference (1st introduced in late 80-ies ) 0.9 ns - JMP SHORT 1 ns - speed-of-light ?~~~~~~~~~~~ 1 ns - MUL ( i**2 = MUL i, i ) 3~4 ns - CPU L2 CACHE reference (2020/Q1) 5 ns - CPU L1 iCACHE Branch mispredict 7 ns - CPU L2 CACHE reference 10 ns - DIV 19 ns - CPU L3 CACHE reference (2020/Q1 considered slow on 28c Skylake) 71 ns - CPU cross-QPI/NUMA best case on XEON E5-46* 100 ns - MUTEX lock/unlock 100 ns - own DDR MEMORY reference 135 ns - CPU cross-QPI/NUMA best case on XEON E7-* 202 ns - CPU cross-QPI/NUMA worst case on XEON E7-* 325 ns - CPU cross-QPI/NUMA worst case on XEON E5-46* |Q>~~~~~ 5,000 ns - QPU on-chip QUBO ( quantum annealer minimiser 1 Qop ) 10,000 ns - Compress 1K bytes with a Zippy PROCESS 20,000 ns - Send 2K bytes over 1 Gbps NETWORK 250,000 ns - Read 1 MB sequentially from MEMORY 500,000 ns - Round trip within a same DataCenter ?~~~ 2,500,000 ns - Read 10 MB sequentially from MEMORY~~ 10,000,000 ns - DISK seek 10,000,000 ns - Read 1 MB sequentially from NETWORK ?~~ 25,000,000 ns - Read 100 MB sequentially from MEMORY~~ 30,000,000 ns - Read 1 MB sequentially from a DISK 150,000,000 ns - Send a NETWORK packet CA -> Netherlands 1s: | | | . | | ns| . | us| . ms| (https://stackoverflow.com/a/33065382 https://stackoverflow.com/a/33065382) However, 0.001 ns light transfer in Gemmatimonas phototrophica bacteriae biology has much more performant/optimized machines, therefore, yes, plenty of room for improvement in silico.
nine_k 4y ago
APL-like array-oriented languages can shine here. And do not complain about syntax; think numpy or pandas instead.
cassianoleal 4y ago
Caches are much more limited than RAM though. If every program under the sun starts targetting them directly, is the 100-1000x speedup hold true? Legit question, I have no idea about how this would behave.
- deleted 4y ago
  [deleted]
- asah 4y ago
  Reserve cache for performance sensitive programs? (OS support?)
  - cassianoleal 4y ago
    How does the OS know for which programs I require better performance?
jagged-chisel 4y ago
What if we just put all the RAM on the CPU die? Imagine the speedups for everyone! I know, sounds crazy. Who’s gonna make such a drastic change to the industry?
- Olreich 4y ago
  You don’t even solve the problem by moving the memory on-die, as the majority of time is not spent sending the signal on traces, it’s waiting for the relatively slow memory to find, read, and send the data on the bus. Expanding the cache so everything fits in it is one way to achieve the performance uplift of cache hits, but cache is expensive compared to memory, and current cache sizes are tiny compared to RAM. If cache gets 50x bigger tomorrow, chips will get at least 10x as hot, power-hungry, and expensive.
- gpderetta 4y ago
  think about it, L1, L2 and L3 are already on die, yet they are progressively slower. Why do you think it is the case?
  - jagged-chisel 4y ago
    Distance from the CPU. And traditionally, RAM sits waaaaaay across the motherboard. If you put it on the CPU die, it’s much closer and much faster. Still slower than L1 and L2 cache, sure, but much faster than waiting on the fetch across the motherboard. Look into Apple’s unified memory.
- speed_spread 4y ago
  Imagine not being able to upgrade or have a memory configuration outside of what the manufacturer provides! Incredible!
  - jrochkind1 4y ago
    Apple machines are already pretty much not RAM-upgradeable. And they design their own chips too. So if there were benefits to putting RAM on the die (I don't know myself, others in this thread suggest there are in fact not), Apple would seem like a possible first mover, they don't seem subject to the downsides.
logicchains 4y ago
A 100x speedup makes sense because a cache miss costs around 100 nanoseconds, compared to arithmetic operations themselves costing under one nanosecond. If you traverse a data structure in which everything's a pointer, every access may well be a cache miss, especially if the rest of the code is also pointer-heavy and thrashes the cache.
vsnf 4y ago
Are there any available practical examples of what this actually means, how to do it, and what the limits of this technique might be with programs that your average programmer may encounter/write?

zelphirkalt 4y ago

I don't think the next step is to expose more complexity of underlying hardware to the developer. If at all, then the next step is to have compilers deal with that. Let them rewrite the program.

dgb23 4y ago
You make a good, general point. But I found that a data oriented approach has benefits outside of performance and resource usage, because it nudges you towards: - normalized, small/tight data structures - data structures that are closely related in computational terms - smaller interfaces and functions that tend to be more re-usable and general - fewer if/else branches and more existence based branching via loops - fewer "business level" generics, macros and similar abstractions, because you can dispatch easily via tagging to concrete types - less code that "digs"/"drills" into data and more code that composes data - generally a simpler (less coupled) end result This all comes with a cost of having to do upfront design and exploration in order to decompose and lay out your data. And while it reduces the mental overhead of understanding the individual pieces of your program on a day by day basis, it might increase learning curve of seeing the big picture, especially at the beginning. So it is a tradeoff. But I think it would be too dismissive to say that the programmer is doing compiler work here. It is design work, and it is unlearning some of the notions of how to structure programs that carried on since the 90's. Some of which are performance related and some of which are about sensible code structure.

KapKap55 4y ago

The 100x plus speedup is no exaggeration either, I've noticed some incredulity from others at the numbers. For a very simple comparison, I recently was testing a (poorly) custom built data-oriented Entity-Component-System for usage in games with a more typical "componentized" object approach. No multithreading or anything complicated. On my system, the typical approach could generate about 1000 new objects and attach a single component in about 1 millisecond. The data-oriented approach could generate about 100,000 new "objects" and attach a single component in about 0.5 milliseconds. Same thing in the end, but one is roughly 200x faster in the same time frame. It's pretty stunning when you see stuff like this in benchmarks.

moonchrome 4y ago
I don't get this - you're talking about generating objects - I'm assuming you're talking allocating new objects. What's your bottleneck ? Allocator or do you have some poor data structure to update it ? Where is the speedup coming from ? The kind of speedup you're talking about sounds like moving from allocating each object separately to some arena and avoiding allocator overhead. I could be wrong in the assumptions - but OP is talking about fitting stuff in CPU cache don't really see how that translates to your scenario.
ly3xqhl8g9 4y ago
-----s.-ms.-us.-ns|---------------------------------------------------------- 0.1 ns - NOP 0.3 ns - XOR, ADD, SUB 0.5 ns - CPU L1 dCACHE reference (1st introduced in late 80-ies ) 0.9 ns - JMP SHORT 1 ns - speed-of-light ?~~~~~~~~~~~ 1 ns - MUL ( i**2 = MUL i, i ) 3~4 ns - CPU L2 CACHE reference (2020/Q1) 5 ns - CPU L1 iCACHE Branch mispredict 7 ns - CPU L2 CACHE reference 10 ns - DIV 19 ns - CPU L3 CACHE reference (2020/Q1 considered slow on 28c Skylake) 71 ns - CPU cross-QPI/NUMA best case on XEON E5-46* 100 ns - MUTEX lock/unlock 100 ns - own DDR MEMORY reference 135 ns - CPU cross-QPI/NUMA best case on XEON E7-* 202 ns - CPU cross-QPI/NUMA worst case on XEON E7-* 325 ns - CPU cross-QPI/NUMA worst case on XEON E5-46* |Q>~~~~~ 5,000 ns - QPU on-chip QUBO ( quantum annealer minimiser 1 Qop ) 10,000 ns - Compress 1K bytes with a Zippy PROCESS 20,000 ns - Send 2K bytes over 1 Gbps NETWORK 250,000 ns - Read 1 MB sequentially from MEMORY 500,000 ns - Round trip within a same DataCenter ?~~~ 2,500,000 ns - Read 10 MB sequentially from MEMORY~~ 10,000,000 ns - DISK seek 10,000,000 ns - Read 1 MB sequentially from NETWORK ?~~ 25,000,000 ns - Read 100 MB sequentially from MEMORY~~ 30,000,000 ns - Read 1 MB sequentially from a DISK 150,000,000 ns - Send a NETWORK packet CA -> Netherlands 1s: | | | . | | ns| . | us| . ms| (https://stackoverflow.com/a/33065382 https://stackoverflow.com/a/33065382) However, 0.001 ns light transfer in Gemmatimonas phototrophica bacteriae biology has much more performant/optimized machines, therefore, yes, plenty of room for improvement in silico.

nine_k 4y ago

APL-like array-oriented languages can shine here. And do not complain about syntax; think numpy or pandas instead.

cassianoleal 4y ago

Caches are much more limited than RAM though. If every program under the sun starts targetting them directly, is the 100-1000x speedup hold true? Legit question, I have no idea about how this would behave.

deleted 4y ago
[deleted]
asah 4y ago
Reserve cache for performance sensitive programs? (OS support?)
- cassianoleal 4y ago
  How does the OS know for which programs I require better performance?

jagged-chisel 4y ago

What if we just put all the RAM on the CPU die? Imagine the speedups for everyone! I know, sounds crazy. Who’s gonna make such a drastic change to the industry?

Olreich 4y ago
You don’t even solve the problem by moving the memory on-die, as the majority of time is not spent sending the signal on traces, it’s waiting for the relatively slow memory to find, read, and send the data on the bus. Expanding the cache so everything fits in it is one way to achieve the performance uplift of cache hits, but cache is expensive compared to memory, and current cache sizes are tiny compared to RAM. If cache gets 50x bigger tomorrow, chips will get at least 10x as hot, power-hungry, and expensive.
gpderetta 4y ago
think about it, L1, L2 and L3 are already on die, yet they are progressively slower. Why do you think it is the case?
- jagged-chisel 4y ago
  Distance from the CPU. And traditionally, RAM sits waaaaaay across the motherboard. If you put it on the CPU die, it’s much closer and much faster. Still slower than L1 and L2 cache, sure, but much faster than waiting on the fetch across the motherboard. Look into Apple’s unified memory.
speed_spread 4y ago
Imagine not being able to upgrade or have a memory configuration outside of what the manufacturer provides! Incredible!
- jrochkind1 4y ago
  Apple machines are already pretty much not RAM-upgradeable. And they design their own chips too. So if there were benefits to putting RAM on the die (I don't know myself, others in this thread suggest there are in fact not), Apple would seem like a possible first mover, they don't seem subject to the downsides.

logicchains 4y ago

A 100x speedup makes sense because a cache miss costs around 100 nanoseconds, compared to arithmetic operations themselves costing under one nanosecond. If you traverse a data structure in which everything's a pointer, every access may well be a cache miss, especially if the rest of the code is also pointer-heavy and thrashes the cache.

vsnf 4y ago

Are there any available practical examples of what this actually means, how to do it, and what the limits of this technique might be with programs that your average programmer may encounter/write?