Strategy for AMD64 cache optimization - stacks, symbols, variables and strings tables

Question

Intro

I am going to write my own FORTH "engine" in GNU assembler (GAS) for Linux x86-64 (specifically for AMD Ryzen 9 3900X that is siting on my table).

(If it will be success, I may use similar idea for make firmware for retro 6502 and similar home-brewed computer)

I want to add some interesting debugging features, as saving comments with the compiled code in for of "NOP words" with attached strings, which would do nothing in runtime, but when disassembling/printing out already defined words it would print those comment too, so it would not loose all the headers ( a b -- c) and comments like ( here goes this particular little trick ) and I would be able try to define new words with documentation, and later print all definitions in some nice way and make new library from those, which I consider good. (And have switch to just ignore comments for "production release")

I had read too much of optimalization here and I am not able to understand all of that in few weeks, so I will put out microoptimalisation until it will suffer performance problems and then I will start with profiling.

But I want to start with at least decent architectural decisions.

What I understood yet:

• it would be nice, if the programs was run mainly from CPU cache, not from memory
• the cache is filled somehow "automagically", but having related data/code compact and as near as possible may help a lot
• I identified some areas, that would be good candidates for caching and some, that are not so good - I sorted it in order of importance:
  • assembler code - the engine and basic words like "+" - used all the time (fixed size, .text section)
  • both stacks - also used all the time (dynamic, I will probably use rsp for data stack and implement return stack independly - not sure yet, which will be "native" and which "emulated")
  • forth bytecode - the defined and compiled words - used at runtime, when the speed matters (still growing size)
  • variables, constants, strings, other memory allocations (used in runtime)
  • names of words ("DUP", "DROP" - used only when defining new words in compilation phase)
  • comments (used one daily or so)

---

Question:

As there is lot of "heaps" that grows up (well, there is not "free" used, so it may be also stack, or stack growing up) (and two stacks that grows down) I am unsure how to implement it, so the CPU cache will cover it somehow decently.

My idea is to use one "big heap" (and increse it with brk() when needed), and then allocate big chunks of alligned memory on it, implementing "smaller heaps" in each chunk and extend them to another big chunk when the old one is filled up.

I hope, that the cache would automagically get the most used blocks first keep it most of the time and the less used blocks would be mostly ignored by the cache (respective it would occupy only small parts and get read and kicked out all the time), but maybe I did not it correctly.

But maybe is there some better strategy for that?

Answer 1

Your first stops for further reading should probably be:

• What Every Programmer Should Know About Memory? re: cache
• https://agner.org/optimize/ re: everything else about writing efficient asm.
• https://uops.info/ for a better version of Agner Fog's instruction tables.
• See also other links in https://stackoverflow.com/tags/x86/info

so I will put out microoptimalisation until it will suffer performance problems and then I will start with profiling.

Yes, probably good to start trying stuff so you have something to profile with HW performance counters, so you can correlate what you're reading about performance stuff with what actually happens. And so you get some ideas of possible details you hadn't thought of yet before you go too far into optimizing your overall design idea. You can learn a lot about asm micro-optimization by starting with something very small scale, like a single loop somewhere without any complicated branching.

---

Since modern CPUs use split L1i and L1d caches and first-level TLBs, it's not a good idea to place code and data next to each other. (Especially not read-write data; self-modifying code is handled by flushing the whole pipeline on any store too near any code that's in-flight anywhere in the pipeline.)

Related: Why do Compilers put data inside .text(code) section of the PE and ELF files and how does the CPU distinguish between data and code? - they don't, only obfuscated x86 programs do that. (ARM code does sometimes mix code/data because PC-relative loads have limited range on ARM.)

---

Yes, making sure all your data allocations are nearby should be good for TLB locality. Hardware normally uses a pseudo-LRU allocation/eviction algorithm which generally does a good job at keeping hot data in cache, and it's generally not worth trying to manually clflushopt anything to help it. Software prefetch is also rarely useful, especially in linear traversal of arrays. It can sometimes be worth it if you know where you'll want to access quite a few instructions later, but the CPU couldn't predict that easily.

AMD's L3 cache may use adaptive replacement like Intel does, to try to keep more lines that get reused, not letting them get evicted as easily by lines that tend not to get reused. But Zen2's 512kiB L2 is relatively big by Forth standards; you probably won't have a significant amount of L2 cache misses. (And out-of-order exec can do a lot to hide L1 miss / L2 hit. And even hide some of the latency of an L3 hit.) Contemporary Intel CPUs typically use 256k L2 caches; if you're cache-blocking for generic modern x86, 128kiB is a good choice of block size to assume you can write and then loop over again while getting L2 hits.

The L1i and L1d caches (32k each), and even uop cache (up to 4096 uops, about 1 or 2 per instruction), on a modern x86 like Zen2 (https://en.wikichip.org/wiki/amd/microarchitectures/zen_2#Architecture) or Skylake, are pretty large compared to a Forth implementation; probably everything will hit in L1 cache most of the time, and certainly L2. Yes, code locality is generally good, but with more L2 cache than the whole memory of a typical 6502, you really don't have much to worry about :P

---

Of more concern for an interpreter is branch prediction, but fortunately Zen2 (and Intel since Haswell) have TAGE predictors that do well at learning patterns of indirect branches even with one "grand central dispatch" branch: Branch Prediction and the Performance of Interpreters - Don’t Trust Folklore