Hacker News Reader

Comment by jeffbee | Hacker News Reader

This is what thread contention means in any language and runtime. Threads "contend" for mutexes by waiting.

Yes, but I think it's a revelation to many people that things like this map to queueing. Literally _everything_ related to performance is queueing, but we use different words for different scenarios, like "contention."

> Literally _everything_ related to performance is queueing

Well, _scaling_ is queuing. But other things: cache hit rates, data packing efficiency, efficient use of hardware intrinsics, etc, don't relate to queuing.

A queue is:

* An arrival rate of requests * A processing time for each request * A corresponding queue length when a new request comes in before the current one is done being processed.

So anything that affects processing time affects queueing. Cache hit rates, data packing, etc., all affect processing time, but processing time is in the context of a queue.

Most people would call that "throughput," not "queueing."

Throughput is a property of a queue.

How is the concept of algorithmic complexity analogous to queuing?

Your whole system is a queue. Requests come in, are processed, and some output is given.

Algorithmic complexity affects the processing time of each request / task. Knowing the latency distribution is crucial in understanding the queueing characteristics of the system, and the algorithmic complexity will greatly affect that distribution.

Most mutexes aren't fair; it's not strictly equivalent to queueing. That said, I agree with your larger point that I don't understand what the author finds revelatory about this.

Maybe not but even spinlocks logically contend this way. For example the Go and Abseil mutex libraries, which are similar, account cycles spun toward contention statistics.

Fairness isn't really relevant to the analysis in the article. I agree with jeffbee.

Reply on news.ycombinator.com