Cache invalidation really is one of the hardest problems in computer science

I came to this system with prior experience using Go and mysql where I expected base performance of 1-5k queries per second per node before any optimizations like (non cpu) caching but also didn't use triggers or anything fancy to prevent db cpu pressure.

I got a bit rambling and perhaps a bit off topic, but elixir is not something that side steps the need for a cache when your db is maxed out.

Something needs to be cached always, so the DB and Disk need at least cache blocks.

To anyone reading this, do not assume that you don't need to cache your Wordpress site! I remember running a test on my site once (basic WooCommerce site running on a DigitalOcean VPS), and simply turning on the free version of WP Fastest Cache was the difference between serving 30 users/min and crashing vs. serving 1000. Drastically lowered page load times too.

I don't understand how Phoenix/Elixir impacts this however.

Generally, I've found that, in the guise of doing the simplest thing, I've done the most naive-est thing possible, which unfortunately comes with the burden of tech debt. So, as a rule of thumb, given the small tech shop we are, I tend to favour systems that are fully-managed or serverless and prefer to take on whatever tech debt using it throws at me.

Caching gives sites about two orders of magnitude speed uplift in my experience. Sometimes more. Especially if you are building the pages live and compressing them.

Brotli -11 is really really expensive and egress data transfer is one of the more expensive commodities to purchase from cloud venders.

Caching also reduces latency significantly - which is a much better user experience.

Wait... wait what? Am to understand that if I have code like this:

    struct {
      int foo;
      int bar;
    } foobar;

    mutex io_mutex;

    void baz(int* x, int n) {
      *x = 0;
      for (int i = 0; i <= n; i++)
        *x += i;
      lock io_mutex;
      print *x;
      unlock io_mutex;
    }

    thread t1 {
      baz(&foobar.foo, 10000);
    };

    thread t2 {
      baz(&foobar.bar, 10000);
    };

Link from the OP, for the lazy

The logical coherency protocol that is (somewhat) above that level is what would dictate whether you can forward modified data between CPUs or it would have to write back and be fetched from memory.

AFAIK protocols don't tend to have the writer publish its modification to other owners for two major reasons. First because you then would no longer own it exclusive and would have to go off-chip if it wanted to modify it again immediately afterwards. Second because problems with supporting atomic operations and preventing deadlocks in the protocol can become unmanageable if you could have other owners while you are writing lines. I believe generally the transfer of data is demand-driven, so core 1 wanted to read the line, it would ask core 0 for it. And that modifications will always remove access permission from other cores before the modification completes, so core 0 would have send an intent to write message to core 1 in this case before its store could reach coherency.

Barriers don't necessarily drive any coherency on a cache line level. Caches are always coherent (ignoring access by incoherent agents, where the coherency has to be managed at a software level). Barriers provide ordering between more than one memory access.

The MESIF page is a good basic intro to concepts, naturally state of the art has moved beyond that. Here for example https://course.ece.cmu.edu/~ece742/f12/lib/exe/fetch.php?med... a 15 year old CPU has 13 states in its coherency protocol. It's difficult to find a lot of public information about this stuff. Suffice to say these things are so complex that mathematical proofs are used to ensure correctness, no deadlocks, etc. You are right right that data including updates can go directly between agents rather than via memory.

But no matter how smart the hardware gets, the advice to programmers is still the same: stores to a line will slow down access to that line by any other agent, so sharing read-only lines between CPUs is fine, but don't add a lot of writes to the mix.

This so much. I truly wish RISC-V had decided on the weak memory model (WMM)[0] that allowed load-value speculation in the absence of explicit `Reconcile` fences between dependent loads (i.e., when first loading an address from memory and then loading a value from that address, it can load an old value that was stored after the value's address was stored to memory, provided it speculated the value (of pointer-type) of the first load correctly and loaded from this speculated address before it properly executed the first load).

Not needing to repeat the load from a speculated address in response to that address getting a cache invalidation before the load that fetched the (correctly speculated) pointer "goes though" severs the cache snooping/invalidating feed to the reorder buffer(ROB). Essentially, the difference to banning the dependent-load-load reordering is that WMM frees up the second load's ROB entry once the value speculation of the first load confirms, so when the first load instruction returns and affirms the value speculated for it, the second load can retire immediately with the first load to free up both ROB entries. The decoupling between an L2 invalidating other L2's and responding to another L2's read-request allows the "Invalidation Buffer" of an L2 to function similar to an L1's store buffer. So if L3 is implemented by just giving each core a large multi-bank L2 so the L3-slices are just the different core's L2s, write-congestion into an L2 through other cores all writing to the same bank is just buffered away (and redundant stores can be squashed/adjacent stores write-combined, useful if the writing cores specify they themselves don't want read access to the cachelines those writes target).

See this excerpt from the paper: > Speculations: OOO can issue a load speculatively byaggressive predictions, such as branch prediction (Figure 3d),memory dependency prediction (Figure 3e) and even load-value prediction (Figure 3f). As long as all predictions relatedto the load eventually turn out to be correct, the load resultgot from the speculative execution can be preserved. Nofurther check is needed. Speculations effectively reorderdependent instructions, e.g., load-value speculation reordersdata-dependent loads. Since WMM does not require preserving any dependency ordering, speculations will neither breakWMM nor affect the above correspondence between OOOand WMM.

Yes, WMM is similar to Alpha, just that Alpha allowed a load from some address to be reordered after a store to a different address (which is forbidden in WMM).

[0]: https://arxiv.org/abs/1707.05923

In particular using snooping or shoot downs it one of those choices. Why use one or the other? Consider whether or not your memory controller is "single threaded" or not[1]. If you have multiple memory controllers that have access to the same "slow" memory, then a shoot down (cache invalidation message) over the cache coherency interconnect, can start the refresh transaction for unoccupied memory controller context. In these cases you can overlap memory transactions and "hide" some of the latency. If you're snooping, and see a write through (where write is headed for main memory), you can mirror a copy of that write through to update your cache, but you might simply invalidate your cache if there is a shared cache with the CPU (thread) in question, as it will get changed in the shared cache and the invalidation will cause the shared cache to move it from L2 to L1 as soon as you look at it again.

The availability of multi-core RISC-V designs for FPGAs give someone who is interested in this an opportunity to actually try the different strategies and to compare instruction throughput (instructions per clock) and maximum latency for correct operation.

There was a good paper at Microprocessor Forum in the early 2000's from Toshiba on a multi-core cache design where the L2 cache was visible but segmented between cores (it appeared as a single cache where you didn't have access to invalidate all of the look aside buffers. I thought it was very creative and it of course rewarded algorithms that understood that. (small working set per thread, larger working set for application)

[1] Basically how many memory transactions can it have outstanding at any given time.

Patching the JDK to skip the secondary cache altogether was the real solution.

It's thick but reads fairly easy in my recollection

A single modern CPU core is superscalar and has a deep instruction pipeline. With your help, it will decode and reorder many instructions and execute many instructions concurrently. Each of those instructions can operate on a lot of data.

As famous online controversial opinion haver Casey Muratori tells us, most software just sucks, like really really bad (e.g. commonly people will post hash table benchmarks of high-performance hash tables that do bulk inserts in ~100ns/op, but you can do <10ns/op easily if you try), and using SIMD instructions is table stakes for making good use of the machinery inside of a single CPU core. SIMD instructions are not just for math! They are tools for general purpose programming. When your program needs to make decisions based on data that does not contain obvious patterns, it is often a lot cheaper to compute both possible outcomes and have a data dependency than to have a branch. Instructions like pshufb or blendv or just movemask and then using a dang lookup table can replace branches. Often these instructions can replace 32 or 64 branches at a time[0]. Wojciech Muła's web site[1] is the best collection of notes about using SIMD instructions for general-purpose programming, but I have found some of the articles to be a bit terse or sometimes incorrect, and I have not yet done anything to fix the issue. "Using SIMD" ends up meaning that you choose the low-level layout of your data to be more suitable to processing using the instructions available.

Inside your single CPU core there is hardware for handling virtual -> physical address translation. This is a special cache called the translation lookaside buffer (TLB). Normally, chips other than recent Apple chips have a couple hundred entries of 1 4KiB page each in the TLB, and recent Apple chips have a couple hundred entries of 1 16KiB page each. Normal programs deal with a bit more than 1 meg of RAM today, and as a result they spend a huge portion of their execution time on TLB misses. You can fix this by using explicit huge pages on Linux. This feature nominally exists on Windows but is basically unusable for most programs because it requires the application to run as administrator and because the OS will never compact memory once it is fragmented (so the huge pages must be obtained at startup and never released, or they will disappear until you reboot). I have not tried it on Mac. As an example of a normal non-crazy program that is helped by larger pages, one person noted[2] that Linux builds 16% faster on 16K vs on 4K pages.

Inside your single CPU core is a small hierarchy of set-associative caches. With your help, it will have the data it needs in cache almost all the time! An obvious aspect of this is that when you need to work on some data repeatedly, if you have a choice, you should do it before you have worked on a bunch of other data and caused that earlier data to be evicted (that is, you can rearrange your work to avoid "capacity misses"). A less obvious aspect of this is that if you operate on data that is too-aligned, you will greatly reduce the effective size of your cache, because all the data you are using will go into the same tiny subset of your cache! An easy way to run into this issue is to repeatedly request slabs of memory from an allocator that returns pretty-aligned slabs of memory, and then use them all starting at the beginning. That this could cause problems at all seems relatively unknown, so I would guess lots and lots of software is losing 5-10% of its performance because of this sort of thing. Famous online good opinion haver Dan Luu wrote about this here[3]. The links included near the bottom of that post are also excellent resources for the topics you've asked about.

When coordinating between multiple CPU cores, as noted in TFA, it is helpful to avoid false sharing[4]. People who write trading systems have mostly found that it is helpful to avoid sharing *at all*, which is why they have work explicitly divided among cores and communicate over queues rather than dumping things into a concurrent hash map and hoping things work out. In general this is not a popular practice, and if you go online and post stuff like "Well, just don't allocate any memory after startup and don't pass any data between threads other than by using queues" you will generally lose imaginary internet points.

There are some incantations you may want to apply if you would like Linux to prioritize running your program, which are documented in the Red Hat Low Latency Performance Tuning guide[5] and Erik Rigtorp's web site[6].

Some other various resources are highload.fun[7], a web site where you can practice this sort of thing, a list of links associated with highload.fun[8], Sergey Slotin's excellent online book Algorithms for Modern Hardware[9], and Dendi Bakh's online course Perf Ninja[10] and blog easyperf[11].

> Off topic: What level of sophistication about modern CPUs is _good_ to have?

Probably none? These skills are basically unemployable as far as I can tell.

[0]: https://github.com/lemire/despacer

[1]: http://0x80.pl/articles/index.html

[2]: https://twitter.com/AtTheHackOfDawn/status/13338951151741870...

[3]: https://danluu.com/3c-conflict/

[4]: https://rigtorp.se/ringbuffer/

[5]: https://access.redhat.com/sites/default/files/attachments/20...

[6]: https://rigtorp.se/low-latency-guide/

[7]: https://highload.fun/

[8]: https://github.com/Highload-fun/platform/wiki

[9]: https://en.algorithmica.org/hpc/

[10]: https://github.com/dendibakh/perf-ninja

[11]: https://easyperf.net/notes/

Another one is Computer Systems: A Programmer’s Perspective: http://csapp.cs.cmu.edu/

I’m not sure whether a single target architecture can (either in theory or in practice) map to hardware with different line sizes. If so, another problem is that the compiler’s idea of the cache line size might not match the hardware’s.

Invalidation means to remove a potentially inconsistent element from the cache, like after the original or a part of the inputs of the function were changed. Both problems are important with huge effects, but different.

We sell particularly high-value, unique jewels, that are seated in jewellery. In fact, our jewels are so valuable to us, that our stores are able to modify the case around the jewel even before they sell to a customer. Each customer will be offered the last casing the jewel was in, and be given the opportunity to change it - though they might still choose not to buy.

We have a set of stores that we can sell from, and of course only one store can have the jewel in it at a time. We’re losing customers by only having the local stock available to sell, so we instigate a new policy; every store takes a picture of the casing for the jewel when they have it in store, they can show this last copy of the jewel in their catalogue. If a customer wants the jewel from the catalogue, we call around the other stores asking for the physical jewel to be brought to us.

This works well a lot of the time, but we find a new problem. Sometimes the customer really liked the casing the jewel was in for the photograph in the catalogue, but when the physical jewel arrives the casing has changed. The customer mutters something about false advertising and storms out disgusted by the stale photo shown. So we add a new policy. If a store changes the casing for a jewel it has to send a picture to every other store of the new casing so they can all update their catalogues.

Well! Now we have chaos! Every store owner is so busy updating catalogues and sending pictures around the other stores that they’re getting less real work done. We look at our catalogue, sometimes we’re updating the same page many times without a customer even seeing it!

So we come up with a new policy - instead of immediately changing the catalogue when we get told that another store has changed the physical jewel, we’re just going to mark the catalogue page as out of date. If eventually a customer asks to see that jewel, we’ll apologise to them for the wait, we’ll ask the other stores who has the jewel right now, then we’ll go get the physical jewel from them, take a picture for our catalogue, and show it to the customer. (As a minor optimisation, if we think the customer will want to change the casing we’ll politely inform the store we picked it up from that they can now mark their catalogue out of date).

It is all going well, but there’s a lot of overhead in our catalogue with only one jewel per page, so we start putting multiple jewels on each page. That makes our catalogue page update a bit difficult so we declare that a store must always collect all physical jewels for any given catalogue page.

One day we find that two stores are sending the same two jewels backwards and forwards all day. We investigate and find that the two jewels are on the same catalogue page, one jewel is being changed by a particularly indecisive customer in one store, and the other is being change by an equally determined customer in the other store. Neither cares about the jewel the other is trying to change, but both customers are getting frustrated by the wait as our policy requires both jewels in the same location before an update can be made. The store managers bemoan ever putting the two jewels on the same page to create this false sharing nightmare. They agree that even if wasteful, for these particular jewels they’ll leave blank space in the catalogue, the two jewels land on different pages, and the shuffling of jewels between stores stops.

I hope it doesn’t seem supporting the HN guidelines is, against fun or anything. I think it’d be great to hear at some social get-together or even as part of a tech talk.

One problem with it here is as you can see are long cascading joke reply comments which make it hard for interesting comments to be seen.

https://en.wikipedia.org/wiki/Naming_and_Necessity

-- Karl Pilkington

1. Cache invalidation

2. Off by one errors

3. Naming Things

Famous CS Joke

Usually when people talk about a topic being hard, they don’t mean the very constrained cases that are easy.