Questions on Multi-Thread Speed-Up and Efficiency

[MathMan]

Hello all,

I started looking into multi-threaded extensions to some applications of mine. As I'm completely new to this I would appreciate some guidance
on speed-up and efficienvy figures I see. So my questions indeed target people who actually (and successfully) work with multi-threading
developments in Free Pascal.

Here is a simple breakdown of my environment:

- CPU: AMD Ryzen 7 7730U, 8 physical, 16 SMT cores
- Mem: 16 GByte
- OS: Win 11 Home, 25H2, 26200.8655
- Lazarus: 4.2
- FPC: 3.2.2

Here is what I'm doing:

- I have computational tasks that I can divide into fully independent sub-tasks (no common data, no synch requirements, etc.)
- I use threadpool-fp (https://github.com/ikelaiah/threadpool-fp) in the simple 'fire-and-forget' variant to multi-thread
- the data memory footprint ranges from small (1 MByte) over medium (10 MByte) to large (100 MByte)
- I use my own pure Pascal and assembler enhanced compute kernels
- I minimised heap management, allocating one large chunk and doing pointer math to provide fitting parts to sub-tasks
- I don't do anything 'special' yet, like playing with affinity or priority, switch to large/hughe OS memory tables etc.

Here is what i measure:

- using pure Pascal kernels
  - 8 threads (aligned to physical core count) provide speed-up ~5.8 vs single thread and efficiency of ~73% vs physical cores
  - 16 threads (aligned to SMT core count) provide speed-up ~6.6 vs single thread and efficiency of ~83% vs physical cores
- using assembler enhanced kernels
  - 8 threads (aligned to physical core count) provide speed-up ~4.6 vs single thread and efficiency of ~58% vs physical cores
  - 16 threads (aligned to SMT core count) provide speed-up ~4.8 vs single thread and efficiency of ~60% vs physical cores

Here are my questions:

- do the above figures look reasonable?
- can I expect substantial/measurable improvements if I invest in 'specials' and what would those be?

Kind regards,
MathMan

[Martin_fr]

So my questions indeed target people who actually (and successfully) work with multi-threading
developments in Free Pascal.

I wouldn't say I fit the group, at least not the way you likely mean it. I have done some code using threads, but really not gone deep.

But from my superficial understanding, at least your figures look explainable (and therefore reasonable).
- Since your tasks are independent, I don't expect any locks/critical-section/waiting to happen.
- But your tasks go over huge amount of memory. Likely way outside the cache on your CPU.

The latter would explain the efficiency loss, as now all threads fight for the time to load from RAM. It would also explain the worsening of the effect for your handcrafted asm code, as this would do the compute faster, and the percentage of each thread spending loading from RAM is therefore higher, the slowdown more noticeable.

There are some articles (but I don't recall any) on optimizing memory access/layout. So in case that any of your code repeatedly accesses data, in such ways that it may have been out of cache and needs to be loaded again, then that would be something to look at.

I am not sure if valgrind (cachegrind) may be able to identify this (it wont help with threads, but if you analyze a single thread, then you might learn about its data access...). I haven't done any cache-grinding myself. So I really don't know if it is any good for what you need.

Of course given you have highly optimized your code already, you may already have done some steps of the above...

[JCLRQ]

On my algo, it scales perfectly or above with the performance core count. Pass the performance core, going to logical core the scaling slow down by 20-30%. The reason is that my code heavily SIMD aligned and ASM is fighting memory allocation between logical and performance core. I have a AMD 5950X. I use the MultiThread package.
Ask any AI agent to debottleneck your code. I found it much better than me in doing so.

[MathMan]

So my questions indeed target people who actually (and successfully) work with multi-threading
developments in Free Pascal.

I wouldn't say I fit the group, at least not the way you likely mean it. I have done some code using threads, but really not gone deep.

Don't belittle yourself - you surely know way more about FPC than me. Though I hinted on the target audience I really appreciate any feedback.

But from my superficial understanding, at least your figures look explainable (and therefore reasonable).
- Since your tasks are independent, I don't expect any locks/critical-section/waiting to happen.
- But your tasks go over huge amount of memory. Likely way outside the cache on your CPU.

The latter would explain the efficiency loss, as now all threads fight for the time to load from RAM. It would also explain the worsening of the effect for your handcrafted asm code, as this would do the compute faster, and the percentage of each thread spending loading from RAM is therefore higher, the slowdown more noticeable.

There are some articles (but I don't recall any) on optimizing memory access/layout. So in case that any of your code repeatedly accesses data, in such ways that it may have been out of cache and needs to be loaded again, then that would be something to look at.

I am not sure if valgrind (cachegrind) may be able to identify this (it wont help with threads, but if you analyze a single thread, then you might learn about its data access...). I haven't done any cache-grinding myself. So I really don't know if it is any good for what you need.

Of course given you have highly optimized your code already, you may already have done some steps of the above...

Some food for thought in the above. I haven't played with val-/cachegrind on the single threaded variant - maybe I give it a try.

Regarding memory access pattern - my algo is highly recursive and works more or less over the full data area in memory. I could re-work the recursive descent approach into k (k = recursion depth) linear sweeps over the data area - like things done in modern FFT implementations and such. Will look into that.

Regarding main memory access - yepp, unfortunately all modern consumer CPU are totally memory bandwifth starved, <sigh>

[MathMan]

On my algo, it scales perfectly or above with the performance core count. Pass the performance core, going to logical core the scaling slow down by 20-30%.

Interesting! Is your memory footprint similar to my own? And do you access memory in a linear fashion (see my answer to @martin_fr)?

The reason is that my code heavily SIMD aligned and ASM is fighting memory allocation between logical and performance core.

Same on my side.

I have a AMD 5950X. I use the MultiThread package.

So we both run on Zen 3 architecture, but you have 4 times the cache. What exactly do you mean by 'MultiThread package' - the threadpool implementation in FPC?

Ask any AI agent to debottleneck your code. I found it much better than me in doing so.

This probably won't happen. I'm a hobbyist and all this is just a pet project. As the freely available AI instances are not up to the task (I tried) and I'm not willing to spend money on this.

[creaothceann]

There are some articles (but I don't recall any) on optimizing memory access/layout. So in case that any of your code repeatedly accesses data, in such ways that it may have been out of cache and needs to be loaded again, then that would be something to look at

Gallery of Processor Cache Effects
CppCon 2014: Mike Acton "Data-Oriented Design and C++"
Infographics: Operation Costs in CPU Clock Cycles
MIT Cache oblivious algorithms

Basically,
- structure your data to fit the task you're doing (fill cache lines with relevant data),
- reduce tasks to work in (a few) 32 KB chunks of data at a time,
- avoid sharing cache lines,
- access data in predictable patterns (arena allocators, array walking).

Remember that main RAM access is at least a hundred cycles. Cache is the reason why I got a 7800X3D.

[avra]

Ask any AI agent to debottleneck your code. I found it much better than me in doing so.

This probably won't happen. I'm a hobbyist and all this is just a pet project. As the freely available AI instances are not up to the task (I tried) and I'm not willing to spend money on this.

1. Download opencode
2. Navigate to your project dir
3. Backup your project
4. Run opencode command from terminal or command line while in project dir
5. type /models with enter, then type free, then choose some model from Opencode Zen provider (like MiMo 2.5 Free)
6. tell opencode to analyze your project, ask questions, find bottlenecks, and make improvements/optimizations

That is 100% free, with some limits that are quite acceptable. All much better then web chat bots.

If you want to improve your setup further, look at https://forum.lazarus.freepascal.org/index.php/topic,74082.msg584542.html

[Martin_fr]

Just one side note, most likely not needed.. I.e. I assume you already have this sorted.

Don't use "managed types" (dynamic array, ansistring, smart pointer). They all use interlocked instructions, and that slows down memory access for all threads. Even if each string/array was only used by a single thread (as you stated each thread has its own separate mem/data).

Well, you can put the data in there, but the don't access strings directly, and don't assign/copy the reference holding array variable.

[MathMan]

<snip>

Gallery of Processor Cache Effects
CppCon 2014: Mike Acton "Data-Oriented Design and C++"
Infographics: Operation Costs in CPU Clock Cycles
MIT Cache oblivious algorithms

Many thanks - I'll read carefully.

Basically,
- structure your data to fit the task you're doing (fill cache lines with relevant data),
- reduce tasks to work in (a few) 32 KB chunks of data at a time,
- avoid sharing cache lines,
- access data in predictable patterns (arena allocators, array walking).

Remember that main RAM access is at least a hundred cycles. Cache is the reason why I got a 7800X3D.

Ok, but I can (and have) only follow parts of that, due to the underlying algorithmic of my pet project. Arbitrary precision arithmetic is full of highly recursive algorithms - it might improve once I have finished my implementation of Number Theoretic Transforms though.

[MathMan]

Ask any AI agent to debottleneck your code. I found it much better than me in doing so.

This probably won't happen. I'm a hobbyist and all this is just a pet project. As the freely available AI instances are not up to the task (I tried) and I'm not willing to spend money on this.

1. Download opencode
2. Navigate to your project dir
3. Backup your project
4. Run opencode command from terminal or command line while in project dir
5. type /models with enter, then type free, then choose some model from Opencode Zen provider (like MiMo 2.5 Free)
6. tell opencode to analyze your project, ask questions, find bottlenecks, and make improvements/optimizations

That is 100% free, with some limits that are quite acceptable. All much better then web chat bots.

If you want to improve your setup further, look at https://forum.lazarus.freepascal.org/index.php/topic,74082.msg584542.html

That at least sounds promising - I'll give it a try once I'm done looking into the other suggestions.

[MathMan]

Just one side note, most likely not needed.. I.e. I assume you already have this sorted.

Don't use "managed types" (dynamic array, ansistring, smart pointer). They all use interlocked instructions, and that slows down memory access for all threads. Even if each string/array was only used by a single thread (as you stated each thread has its own separate mem/data).

Well, you can put the data in there, but the don't access strings directly, and don't assign/copy the reference holding array variable.

Yes, I took care of that from the beginning. I do my own memory management, only use pChar, all data access is pointer based, etc.

[microxa]

On the subject of multithreading, Gemini in Chrome provided a solid example utilizing purely native, out-of-the-box FPC features. I initially assumed that OpenGL PBOs would be more efficient, but they turned out to be completely useless. Meanwhile, simple dual-threading actually delivered a speedup.

[microxa]

Anyway, sometimes seeing it once is better than reading or talking about it a hundred times.

[jamie]

I've found using multiple threads does not give me much of any increase of application performance because the OS just switches the threads and you still have the same processing time however, I do use them for blocking operations and they work well for that so they can allow the main thread to run smoothly.

 Things like COM ports, networking, USB device operations etc.


Jamie

[creaothceann]

the OS just switches the threads and you still have the same processing time

That means there are too many threads for that CPU?