4 ms·

Static linking gives you better instruction cache utilization as you are executing local code linearly rather than going through indirection with more boilerpla

Static linking gives you better instruction cache utilization as you are executing local code linearly rather than going through indirection with more boilerplate. This indirection costs a few cycles too. Inlining external code reduces the size not only by saving the call, PLT and and stack dance, but also through specialization (removal of unused conditional, pruning of no longer referenced symbols) as the code is locally optimized. This further reduction in size further improves cache behavior and performance. Duplication can be an issue (not necessarily for performance, but for total binary size), but compilers have heuristics for that. Even just having the symbol local saves some space and call overhead though (no PLT). The case for the shared library having better caching implies multiple processes that are distinct executables (otherwise they share program memory regardless of linkage) trying to hammer it at once, sharing the continued caching, but such scenario is hurt by the call overhead and lower optimization opportunities, negating the result.

marwis 3y ago
> The case for the shared library having better caching implies multiple processes that are distinct executables But this is the most common case for desktops/multipurpose systems. On my desktop there are tens or hundreds distinct processes sharing most of their code.
- arghwhat 3y ago
  No it is not. Depending on your CPU, you might have, say, 32KB of 8-way associative instruction cache per core. Just being shared does not make it fit in the cache. A shared library would only be there across processes of different executable images if its users primarily, continuously execute the same paths in shared libs rather than anything unique in their own executable image - e.g., they'd more or less need to be stuck in the same processing-intensive shared routine in the lib. There would also have to be no other processing done in between by other processes that would have trashed the cache. On the other hand, the severe cache penalty of longer code paths for each executable and the larger PLT call overhead will universally lead to a loss in performance for all library usage. The scenarios you may hit where different processes are actually executing the same shared code paths to the point of benefiting from shared cache utilization would be cases where they share executable image as well. E.g., browser processes, threads, compilers. Electron too if using system-packaged electron binaries.
  - marwis 3y ago
    > A shared library would only be there across processes of different executable images if its users primarily, continuously execute the same paths in shared libs rather than anything unique in their own executable image Yes, like libc/WinApi, Cairo/whatever graphics library of your OS, Gtk/Qt etc All of the apps on my desktop (I don't use electron) share vast majority of their code (see above) and spend most of their time drawing UI through shared libs or doing their own business logic but that's part of their code and not subject to shared lib overhead.
    - arghwhat 3y ago
      It's really important to emphasize how small caches are (especially as even the KBs they have cannot always be fully utilized). When we talk about processor caches, we're trying to make the current routine of one process fit well* - not even the whole thing. No, you don't have a desktop environment where a majority of your unique executables all spend time at the same time in the same small, compute-heavy libc routine with no other processes to trash the cache in between. For Gtk for example, the applications are not taking the same inputs and drawing the same GUI at the same time, with no other processes in between to wipe the cache. Instead they're primarily running their own application logic in their own time, and interaction with Gtk (accepting input, rendering) is on timescales so long that the cache has been wiped out over and over in between (16ms is practically infinity at these scales). In these cases, the cache will be filled at the time of execution with e.g. that apps runtime data, widget tree and what not. At the same time, remember that a static routine is much smaller and faster. Even if way say you fetch a shared library routine from cache and save some cycles there, every single call to it incurs large performance hits over the static linkage: a few cycles to every call from the PLT, possibly many cycles from poorer optimization (e.g., branches you never need), and cycles from not fitting as well in the tiny instruction cache as the process executes it. ... And if that shared lib routine calls other shared libs, then you get to apply the overheads and lost optimization recursively. This recursion where the static linkage pruning is especially effective: you might have tens or hundreds of megabytes of dependencies dynamically, but single megabyte static output as unused functionality is pruned. There is no realistic scenario where dynamic linkage wins on performance or cacheability - it just doesn't play well with how caches end up used. Overall system memory utilization can be slightly lower for dynamic linkage in some cases, but not in a notable way.
inkyoto 3y ago
> Static linking gives you better instruction cache utilization as you are executing local code linearly rather than going through indirection with more boilerplate. No, it does not, it worsens it. For example, «strlen», if it comes from a dynamic library, will be loaded into the physical memory once and only once, and it will be mapped into each process's address space as many times as there are processes. Since «strlen» is a very frequently used function, there is a very high chance that the page will remain resident in memory for a very long time, and since the physical page is resident in memory, there is also a very good chance that the page will remain resident at least in the L2 cache, but – depending on circumstances – in the L1 cache, too. A TLB flush might not even be necessary in specific circumstances, which is a big performance win. It is a 1:N scenario. With the static linking, on the other hand, if there are 10k processes in the system, there will be 10k distinct pages containing «strlen» loaded into memory at 10k random addresses. It is a M:N scenario. Since the physical memory pages are now distinct, the context switching will nearly always require the TLB to be flushed out which is costly or very costly, and more frequent L1/L2 cache invalidations due to «strlen» now residing at 10k distinct physical memory addresses. P.S. I am aware that C compilers now inline «strlen» so there is no actual function call, but let's pretend that it is not inlined for the sake of the conversation.
- arghwhat 3y ago
  The compiler has built-ins for parts of libc exactly because dynamic linkage is ridiculous for performance, but they cannot statically link with a dynamic libc. It's a hack to make dynamic linked libc have at least somewhat acceptable performance. If your libc was statically linked, you would not need the built-in - the strlen impl from your libc would get inlined by LTO. The chances of a particular routine being in L1 is absolutely miniscule - it's hard enough to keep a single process and it's data in L1 and L2. What might happen is that you find it in L3, but: 1. The code you're loading is now much larger (fitting less well in L1 so you'll get more L1 misses) and slower (cache aside, it has redirection overhead and has not been LTO'd for this use), and 2. The inlined version would probably also be found in L3 - either resident or prefetched as that section if the process executable obviously had to be loaded to switch to it. 3. Unless the system is idle, the cache will be trashed in between process switches by the loads from other processes. So while you could technically have a case where the shared lib is in cache, I do not think a realistic scenario exists where that setup wins out. There are more distinct pages, but the pages didn't fit in the first place: by having each process access fewer pages overall it can miss less while it is running.

marwis 3y ago

> The case for the shared library having better caching implies multiple processes that are distinct executables But this is the most common case for desktops/multipurpose systems. On my desktop there are tens or hundreds distinct processes sharing most of their code.

arghwhat 3y ago
No it is not. Depending on your CPU, you might have, say, 32KB of 8-way associative instruction cache per core. Just being shared does not make it fit in the cache. A shared library would only be there across processes of different executable images if its users primarily, continuously execute the same paths in shared libs rather than anything unique in their own executable image - e.g., they'd more or less need to be stuck in the same processing-intensive shared routine in the lib. There would also have to be no other processing done in between by other processes that would have trashed the cache. On the other hand, the severe cache penalty of longer code paths for each executable and the larger PLT call overhead will universally lead to a loss in performance for all library usage. The scenarios you may hit where different processes are actually executing the same shared code paths to the point of benefiting from shared cache utilization would be cases where they share executable image as well. E.g., browser processes, threads, compilers. Electron too if using system-packaged electron binaries.
- marwis 3y ago
  > A shared library would only be there across processes of different executable images if its users primarily, continuously execute the same paths in shared libs rather than anything unique in their own executable image Yes, like libc/WinApi, Cairo/whatever graphics library of your OS, Gtk/Qt etc All of the apps on my desktop (I don't use electron) share vast majority of their code (see above) and spend most of their time drawing UI through shared libs or doing their own business logic but that's part of their code and not subject to shared lib overhead.
  - arghwhat 3y ago
    It's really important to emphasize how small caches are (especially as even the KBs they have cannot always be fully utilized). When we talk about processor caches, we're trying to make the current routine of one process fit well* - not even the whole thing. No, you don't have a desktop environment where a majority of your unique executables all spend time at the same time in the same small, compute-heavy libc routine with no other processes to trash the cache in between. For Gtk for example, the applications are not taking the same inputs and drawing the same GUI at the same time, with no other processes in between to wipe the cache. Instead they're primarily running their own application logic in their own time, and interaction with Gtk (accepting input, rendering) is on timescales so long that the cache has been wiped out over and over in between (16ms is practically infinity at these scales). In these cases, the cache will be filled at the time of execution with e.g. that apps runtime data, widget tree and what not. At the same time, remember that a static routine is much smaller and faster. Even if way say you fetch a shared library routine from cache and save some cycles there, every single call to it incurs large performance hits over the static linkage: a few cycles to every call from the PLT, possibly many cycles from poorer optimization (e.g., branches you never need), and cycles from not fitting as well in the tiny instruction cache as the process executes it. ... And if that shared lib routine calls other shared libs, then you get to apply the overheads and lost optimization recursively. This recursion where the static linkage pruning is especially effective: you might have tens or hundreds of megabytes of dependencies dynamically, but single megabyte static output as unused functionality is pruned. There is no realistic scenario where dynamic linkage wins on performance or cacheability - it just doesn't play well with how caches end up used. Overall system memory utilization can be slightly lower for dynamic linkage in some cases, but not in a notable way.

inkyoto 3y ago

> Static linking gives you better instruction cache utilization as you are executing local code linearly rather than going through indirection with more boilerplate. No, it does not, it worsens it. For example, «strlen», if it comes from a dynamic library, will be loaded into the physical memory once and only once, and it will be mapped into each process's address space as many times as there are processes. Since «strlen» is a very frequently used function, there is a very high chance that the page will remain resident in memory for a very long time, and since the physical page is resident in memory, there is also a very good chance that the page will remain resident at least in the L2 cache, but – depending on circumstances – in the L1 cache, too. A TLB flush might not even be necessary in specific circumstances, which is a big performance win. It is a 1:N scenario. With the static linking, on the other hand, if there are 10k processes in the system, there will be 10k distinct pages containing «strlen» loaded into memory at 10k random addresses. It is a M:N scenario. Since the physical memory pages are now distinct, the context switching will nearly always require the TLB to be flushed out which is costly or very costly, and more frequent L1/L2 cache invalidations due to «strlen» now residing at 10k distinct physical memory addresses. P.S. I am aware that C compilers now inline «strlen» so there is no actual function call, but let's pretend that it is not inlined for the sake of the conversation.

arghwhat 3y ago
The compiler has built-ins for parts of libc exactly because dynamic linkage is ridiculous for performance, but they cannot statically link with a dynamic libc. It's a hack to make dynamic linked libc have at least somewhat acceptable performance. If your libc was statically linked, you would not need the built-in - the strlen impl from your libc would get inlined by LTO. The chances of a particular routine being in L1 is absolutely miniscule - it's hard enough to keep a single process and it's data in L1 and L2. What might happen is that you find it in L3, but: 1. The code you're loading is now much larger (fitting less well in L1 so you'll get more L1 misses) and slower (cache aside, it has redirection overhead and has not been LTO'd for this use), and 2. The inlined version would probably also be found in L3 - either resident or prefetched as that section if the process executable obviously had to be loaded to switch to it. 3. Unless the system is idle, the cache will be trashed in between process switches by the loads from other processes. So while you could technically have a case where the shared lib is in cache, I do not think a realistic scenario exists where that setup wins out. There are more distinct pages, but the pages didn't fit in the first place: by having each process access fewer pages overall it can miss less while it is running.