A single line of code made a 24-core server slower than a laptop (2021)

This is in a nutshell the moral of the performance story. I took a graduate level class in performance computing that was basically all lab based. In the end what I learned, overwhelmingly, first hand, is that in the performance computing world, what wins is what exploits the hardware intelligently.

Theoretical advancements matter too but usually only in so much as they can translate to hardware. Although, there are some special case where even a slight theoretical gain matters even more than how it translates to hardware, but they're limited.

Anyways, to that end, everything becomes about dividing work in a way that parallelizes nicely, exploits cache well, reduces the need to share information between threads, etc... and this ultimately comes down to data structures. However, these aren't your normal, fundamental data structures. Instead each problem sort of has some kind of exotic, hypothetically ideal data structure, that is fine tuned to exploit the machine's resources to the max for just that problem. By the time you're done they rarely resemble anything intelligible, let alone wha the whiteboard version of the algorithm was.

In that vein, there are a few general trends that appear over and over again. Trees vs graphs is definitely one of of those trends, although that's more of a general theme and not a literal rule.

> I need to split up my problem into spaces that don't require synchronization/serialisation.

When I first got a dual CPU (before "cores" were a thing) computer, I decided I'd try dipping my feet in some "proper" parallel coding.

I started with something simple, parallelizing a quicksort routine. This seemed quite trivial: instead of recursing, add the spans to be sorted to a list. I then spawned a thread per CPU, which fetched a span from the list, did a single quicksort pass on it and added up to two new spans to the list. Rinse repeat until list was empty.

Since each span was non-overlapping, the threads only had to synchronize while accessing the list of tasks.

When benchmarking it became clear that while there was a good performance win for large arrays, for short arrays the multithreaded code was much slower than the non-multithreaded version. At my hardware the threshold was around 50k items for integer elements and 20k or so for string elements, IIRC.

I added a threshold detection, where the thread would do a regular recursive quicksort on the span if the length was below the threshold, and this yielded significantly better results.

And with that the harsh reality of multithreading hit me: no free lunch. It was clear the threshold varies not just with element type (slow/complex comparators would reduce the threshold, and vice versa) but with the details of the hardware. So a hardcoded threshold was out of the picture, and it would have to be dynamically determined at runtime.

Was a great learning experience though.

The basic algorithm of A* is very sequential, isn't it? It works by taking the best scoring unexpanded node and expand that. Most of the time, there's only one such node. When expansion has finished, you need to re-sort the queue/heap of unexpanded nodes. All those steps are sequential. So I guess the only gain is when the node expansion can be done in parallel; expanding the top-N nodes probably is counterproductive for many problems. How much you gain then depends on the time expansion takes. The advantage of parallelism then depends on how much time one step "down" takes.

When I was noodling with the Traveling Salesman problem, I was sure that what I really needed was to spend X% of available resources on the Big Gamble (a low probability algorithm with fast results), Y% on a common heuristic and the rest on the honest work of plowing through the linear equations progressively culling the remaining scenarios that need to be tested. I had limited success with this though. I just haven’t done enough LP to make anything noteworthy, and it was a tool sharpening exercise, which made me a little more effective at more mundane batch processing tasks, not a great mind of NP-completeness.

FYI, there are lots of papers on parallel shortest path algorithms. If an approximate solution suffices, there’s also a lot of research available on that, often with some parameter that lets you trade more computation for a tighter approximation. It's not a problem that parallelises particularly well though, so not sure if you'll see good gains in practice.

If you can restrict the structure of your graphs (e.g. planar) then some very efficient methods exist.

Isn't a tree just a graph that is directed and acyclic (DAG)?

So a tree is just a subtype of a graph?

Can you share any of the parallel A* code? I’m currently looking at using A* for use in generative design and am pretty ignorant about parallelising code. Would love to learn more!

This is exactly a reason why I like Scylla as a database. One shard per CPU. Each shard owning different partition of data. Great performance.

I'd like your opinion: channels or locks?

This is really for a program I'm writing in Nim, so perhaps it depends on how channels are implemented?

Contended atomics don't scale. It is possible to construct concurrent structures which contend rarely (but which must still use atomics to guard against the rare case when mediation is required). There was also an interesting paper from a few years ago about using HTM to detect contention in a scalable fashion. I will aver that such code may be difficult to reason about—shared-nothing has far more obvious correctness and performance properties. (Queueing/amortisation also works, and lands somewhere in the middle wrt ease of reasoning.)

Riscv has an interesting compromise, which is to delineate a subset of ll/sc loops which is guaranteed to eventually make global progress. I do agree that it is better to include real wait-free primitives like cas and faa; but I wish that such guarantees of global progress would be provided to HTM.

Let’s be clear here, while you are 100% right that armv8 atomics kinda suck by default, neither compare and swap nor load linked store conditional scale but some atomics can scale if implemented and used appropriately. As parent points out, an atomic increment can scale, we proved they could scale to the performance of a load in the 80s for goodness sake. The fact that arm, ppc, and some others tend to implement these in the absolute worst way possible for performance doesn’t mean atomics can’t scale.

Ignorant question: what's the alternative? A normal mutex? I just sort of assumed atomics were abstractions around some type and a mutex.

It’s not just theoretical. In bad situations (many cores, heavy contention…) you can get cores to starve each other as they try to each poke the monitor and fail continuously. I know of at least one platform which moved to LSE immediately partly because it fixed stuff like this. LL/SC is nice from some perspectives but it fails if you scale it up and also can be difficult to reason about (cough, cough, Linux getting their cmpxchg implementation wrong for years…)

Atomics scale very well if you are reading often and writing rarely.

`lock ; xadd` isn't really fundamentally different than `ll ; add ; sc; b again`

The latter is a bit clunky but the core more or less implements them in the same way. Acquire a line exclusive, load value, increment it, write it back. And you can hold the line exclusive such that the conditional store failure cause is mostly a formality, and can't actually become an infinite loop.

No general purpose atomics are done by shipping the operation to the cache or to memory controllers, it just doesn't work[*]. So even if they look slightly different in the core, they all end up looking exactly the same at the caches and coherency protocols, and that is where atomics are slow. Well any sharing of cache lines updates really.

[*] EDIT: That is to say it doesn't work for performance, for many reasons. Some CPUs do have "remote atomics" something like that which does exactly this, but they are not intended to be broadly used.

> an atomic increment could theoretically become an infinite loop

Only if your software is badly implemented. If you follow the requirements specified by the architecture, forward progress is guaranteed. Of course there is no guarantee how long it will take, but the things that make it slow are essentially the same things that make atomics slow.

the x86 lock prefix does the same loop, this is the best performant and scaling way to do it

What about variables locked with mutexes or semaphores?

Lockless is not the same as lock-free, which is not the same as wait-free which seems to be what you are describing

lockless is often the wrong term, goal, idea and solution. mutexes/futexes do very well, almost zero cost when not contended.

> Therefore the Arc had to stay. Instead of using a single Arc value we can use one Arc per thread.

I thought the title sounded familiar, and the culprit is more or less the same (false or in this case unnecessary sharing). But I didn’t think it was quite that long ago, so maybe it’s two articles about the same classic blunder.

Not sure what is currently in swift, but this paper described biased reference counting approach - e.g. in way two counters - one non-atomic to be used only by specific thread (supposed owner?), and another (atomic) by all other threads - so the sum of these two shows the real reference count (somewhat). Paper here - https://dl.acm.org/doi/pdf/10.1145/3243176.3243195

(Before reading the paper I was expecting that the additional bytes were put for the split counter, plus thread id - but it actually packs them using lower bits for reference counting).

I wonder what abseil/folly/tbb do - need to check (we are heavy std::shared_ptr users, but I don't think 14 bits as described in the paper above would be enough for our use case)

Coalescing reference counting [0] avoids almost all synchronisation. n.b. The abstract says they do "not require any synchronized operation in its write barrier" but they rely on a micro-architectural hack; in practice I'd expect one atomic test-and-set per modified object per collection.

[0] https://sites.cs.ucsb.edu/~ckrintz/racelab/gc/papers/levanon...

There are no miracles here because it is not a language "feature". It is a property of algorithms. When you divide your large task into parts and schedule execution of those on multiple threads make absolutely sure that there is no locking (atomics are locking) happening inside each individual task.