4 ms·

> 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

> 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.

itamarst 3y ago
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.
- rewmie 3y ago
  [dead]
- bogwog 3y ago
  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.
  - gmm1990 3y ago
    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.
    - bogwog 3y ago
      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.
    - cogman10 3y ago
      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.
      - jandrewrogers 3y ago
        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.
        cogman10 3y ago
        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.
        gpderetta 3y ago
        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.
        jandrewrogers 3y ago
- kukkamario 3y ago
  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.
  - dmoy 3y ago
    Hyper threading is SMT? I can never keep the branding names straight.
    - nicoburns 3y ago
      Yes, hyper threading is SMT
adfgiknio 3y ago
>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.
- csdvrx 3y ago
  > 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
- 3y ago
deleted 3y ago
[deleted]

itamarst 3y ago

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.

rewmie 3y ago
[dead]
bogwog 3y ago
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.
- gmm1990 3y ago
  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.
  - bogwog 3y ago
    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.
  - cogman10 3y ago
    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.
    - jandrewrogers 3y ago
      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.
      - cogman10 3y ago
        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.
      - gpderetta 3y ago
        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.
        jandrewrogers 3y ago
kukkamario 3y ago
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.
- dmoy 3y ago
  Hyper threading is SMT? I can never keep the branding names straight.
  - nicoburns 3y ago
    Yes, hyper threading is SMT

adfgiknio 3y ago

>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.

csdvrx 3y ago
> 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
3y ago

deleted 3y ago

[deleted]