Hacker News Reader

Comment by dale_glass | Hacker News Reader

> But there is something unexpected too: the optimal number of threads is different for each function.

Nothing unexpected there. Amdahl's Law in its glory.

A fast running function finishes fast, and coordinating the job's execution over many cores requires doing work every time something finishes. If you split your job into chunks in the microsecond time range, then you'll be handling lots and lots of tiny minutia.

You want to set up your tasks such that each thread has a good amount of stuff to chew through before it needs to communicate with anything.

View on HN

That's not it. I updated the article with an experiment of processing 5 items at a time. The fast function doing 5 images at a time is slower than the slow function doing 1 image at a time (24*5 > 90).

If your theory was correct, we would expect the optimal number of threads for the fast function processing 5 images at a time to be similar to that of the slow function processing 1 image at a time.

In fact, the optimal threads in this case (5 images at a time) was 20 for slow function, 10 for fast function, so essentially the same as the original setup.

Is it a caching thing? The slow version seems less cache efficient, so if it is waiting due to cache misses, that could create an opportunity for something else to get scheduled in.

I doubt it the slow version uses division instead of bit shifting. My guess would be the fast version saturated like i/o or some non cpu portion of the processor and the division one was bottle necked by the division logic in the processor.

But it's iterating through the result vectors twice, so that's basically guaranteed to miss. Moving the threshold check into the loop above would at least eliminate that factor.

Maybe division vs bit shifting does play a factor, but it's hard to compare that while the cache behavior is so different.

Recalibrate how you feel about division and multiplication. It turns out, integer division on new processors is a 1 cycle process (and has been for a while now). Most of the multicycle instructions now-a-days are things like SIMD and encryption.

Which processor has 1-cycle latency for integer division? Even Apple Silicon, which has the mostly highly optimized implementation I am aware of appears to have 2-cycle latency. Recent x86 are much worse, though greatly improved. Integer division is much faster than it used to be but not single cycle.

Also, most of those SIMD and encryption instructions can retire one per cycle on modern cores, but that isn't the same as latency.

You are correct, I mistakenly thought it was 1/cycle because I had previously remembered IMUL taking 30 cycles (and now it has a 1 cycle throughput).

Agner Fog is reporting anywhere from 4->30 cycles on semi-recent architectures.

2-cycle latency for division seems extremely unlikely. From the instruction tables it seems that firestorm has 7-9 cycles latency SDIV (which is excellent). It also has an impressive 2-cycles reciprocal throughput.

Quite possible. I am not confident Apple Silicon has 2-cycle div latency, that seems improbably fast to me, but I had heard some reasonably well-sourced rumors to that effect. I have not measured it myself.

Even at somewhat higher latency it is still fast enough to not be worth optimizing around in most cases, which is great.

Based on the graph the fast function runtime is really short. You might be just seeing effects of efficiency vs performance cores. Lower thread count makes most of the stuff run on performance cores and task end times align more nicely. With larger number of threads tasks running on performance cores complete first and you are left waiting for efficiency tasks running on efficiency cores to complete, or context switches have to be done and tasks are moved between cores which causes overhead.

You could try what happens if you have 10 times more images when running fast function.

Also you have just 8 physical performance cores and 4 physical efficiency cores. Performance cores have hyper threading so they act as 2 logical cores but that doesn't mean that they can actually execute 2 threads at maximum performance. If processing tasks use the same parts of the processor core, then processor cannot run both threads at the same time and IPC will suffer. Slow task maybe uses more varied parts of the core which allows better IPC with hyper threading. So that also may reduce optimal thread count.

Hyper threading is SMT? I can never keep the branding names straight.

Yes, hyper threading is SMT

>Nothing unexpected there. Amdahl's Law in its glory.

That's not Amdahl's Law. Amdahl's Law describes the expected total speedup from a speedup to a segment of the program. It is usually used in the context of adding parallelism but is more general than that. It does not assume parallelism has any overhead.

Amdahl's Law predicts performance will approach a limit with added cores, but still predicts that each core will improve performance.

>A fast running function finishes fast, and coordinating the job's execution over many cores requires doing work every time something finishes. If you split your job into chunks in the microsecond time range, then you'll be handling lots and lots of tiny minutia.

Not necessarily. Modern systems have pools with independent per-core queues and clever ways of distributing work to them with minimal overhead. Work-stealing pools don't have any overhead from synchronization except when a core runs out of work, so each core just runs a `for` loop most of the time. I have seen a simple (pseudocode) `list.parallelMap(foo)` give a linear speedup on a modern JVM even on a large host with a `foo` that takes <100ns.

Trying to manually batch work risks one thread running faster than the others and then idling when it runs out of work. This is common on modern hardware with heterogeneous cores and dynamic frequency scaling.

If the tasks require their own coördination or the runtime isn't smart, then manual batching may be needed. I wouldn't assume Python does the right thing.

> Amdahl's Law predicts performance will approach a limit with added cores, but still predicts that each core will improve performance.

And I would agree: on my systems, efficiency cores are used to handle other tasks and keep the power core cold and ready to use when needed (dynamic frequency scaling)

> Trying to manually batch work risks one thread running faster than the others and then idling when it runs out of work. This is common on modern hardware with heterogeneous cores and dynamic frequency scaling.

Yes, I think the issue here is more that python can't introspect the cgroup artificial limitations placed by docker on the CPU it's using, causing the kink past 9.

If the goal is performance, I think it would be better to assign the cores manually + use cpu pinning + declare to the containers what resources it really has.

On a NOHZ kernel, you can do manual assignments like nohz_full=1-3,5-7 rcu_nocbs=0-3,5-7 irqaffinity=4

This puts the IRQ burden on one core but you can do 2 (with =4,5) etc

> That's not Amdahl's Law. Amdahl's Law describes the expected total speedup from a speedup to a segment of the program. It is usually used in the context of adding parallelism but is more general than that. It does not assume parallelism has any overhead.

Yeah, it's a fiction. An useful one, but still a sort of spherical cow in a vacuum scenario. It doesn't exactly describe real hardware.

> Amdahl's Law predicts performance will approach a limit with added cores, but still predicts that each core will improve performance.

Because it's a fiction. You can have slowdowns with bigger tasks on real hardware, like if you run out of L1 cache.

> Not necessarily. Modern systems have pools with independent per-core queues and clever ways of distributing work to them with minimal overhead.

True, but that's Java and this is Python. I may be wrong, but since the GIL removal is very new still, I don't expect Python to have nearly the same level of efficiency in this regard.

But I could be wrong somewhere, of course.

> Because it's a fiction. You can have slowdowns with bigger tasks on real hardware, like if you run out of L1 cache.

Yes...? But the difference between it and reality is exactly why "optimal number of threads" is not Amdahl's Law.

Reply on news.ycombinator.com