Skip to contentSkip to conversation

improve .text size on gcc 4.0 and newer compilers

PATCH Chuck Ebbert 11 participants 37 messages Jan 5, 2006 – Jan 6, 2006

lore
Share & tools
lore
#0 lore raw

In-Reply-To: <[email protected]>

Quoted 7 lines · Matt Mackall
Quoted 4 lines · Martin J. Bligh

It seems odd to me that we're doing this by second-hand effect on code size ... the objective of making the code smaller is to make it run faster, right? So ... howcome there are no benchmark results for this?

Quoted 5 lines

Because it's extremely hard to design a benchmark that will show a significant change one way or the other for single kernel functions that doesn't also make said functions unusually cache-hot. And part of the presumed advantage of uninlining is that it leaves icache room for random other code that you're _not_ benchmarking.

Moving code out-of-line can have some serious drawbacks, too. For example, if you have a 12 byte function that is called frequently, you are pinning an additional 52 bytes of code in the L1 cache. Unless that code is also called often you might waste more space than you gain from un-inlining.

E.g. a look at arch/i386/kernel/apic.c shows a bunch of functions that are only there because of CPU hotplug, to handle errors or deal with suspend/resume/shutdown. Such code should be in its own text section.

And the only way to get meaningful benchmarks so you can figure out where to place the code would be to instrument the kernel and then run real-world applications.

Signature · 1 line
Chuck
#1 lore raw
Quoted 25 lines · Chuck Ebbert

In-Reply-To: <[email protected]>

Quoted 8 lines · Matt Mackall
Quoted 4 lines · Martin J. Bligh

It seems odd to me that we're doing this by second-hand effect on code size ... the objective of making the code smaller is to make it run faster, right? So ... howcome there are no benchmark results for this?

Quoted 5 lines

Because it's extremely hard to design a benchmark that will show a significant change one way or the other for single kernel functions that doesn't also make said functions unusually cache-hot. And part of the presumed advantage of uninlining is that it leaves icache room for random other code that you're _not_ benchmarking.

Moving code out-of-line can have some serious drawbacks, too. For example, if you have a 12 byte function that is called frequently, you are pinning an additional 52 bytes of code in the L1 cache. Unless that code is also called often you might waste more space than you gain from un-inlining.

Quoted 7 lines

E.g. a look at arch/i386/kernel/apic.c shows a bunch of functions that are only there because of CPU hotplug, to handle errors or deal with suspend/resume/shutdown. Such code should be in its own text section.

And the only way to get meaningful benchmarks so you can figure out where to place the code would be to instrument the kernel and then run real-world applications.

What would be nice to do is pack all the frequently used code together in close proximity. Would probably have much larger effects with userspace code, esp where we touch disk (which is more page-size granularity), but is probably worth doing with kernel code too (where AFAICS we'd only get cacheline granular).

M.

#2 lore raw
Quoted 6 lines

What would be nice to do is pack all the frequently used code together in close proximity. Would probably have much larger effects with userspace code, esp where we touch disk (which is more page-size granularity), but is probably worth doing with kernel code too (where AFAICS we'd only get cacheline granular).

in the kernel we could make a .text.rare section for functions, which we could annotate with __rare.
The other way around, __fastpath or whatever is a bad idea, everyone will consider all of their own functions as such (just like inline ;)... go-fast-stripes all the way :-(

obvious candidates for __rare are
* pm suspend/resume functions
* error handling functions
* initialization stuff (including mount time stuff for filesystems, and hardware setup for drivers)

I wonder if gcc can be convinced to put all unlikely() code sections into a .text.rare as well, that'd be really cool.

#3 lore raw
Quoted 8 lines · Arjan van de Ven

obvious candidates for __rare are
* pm suspend/resume functions
* error handling functions
* initialization stuff (including mount time stuff for filesystems, and hardware setup for drivers)

I wonder if gcc can be convinced to put all unlikely() code sections into a .text.rare as well, that'd be really cool.

gcc 4.1 calls them .text.unlikely and you need to use -freorder-blocks-and-partition
switch. But I haven't been able to reproduce it on a short testcase I cooked up, so maybe it is broken ATM (it put the whole function into .text rather than the expected part into .text.unlikely and left empty .text.unlikely).

Jakub

#4 lore raw
Quoted 10 lines · Jakub Jelinek
Quoted 3 lines

I wonder if gcc can be convinced to put all unlikely() code sections into a .text.rare as well, that'd be really cool.

gcc 4.1 calls them .text.unlikely and you need to use -freorder-blocks-and-partition
switch. But I haven't been able to reproduce it on a short testcase I cooked up, so maybe it is broken ATM (it put the whole function into .text rather than the expected part into .text.unlikely and left empty .text.unlikely).

If it causes the conditional jump to become a long one instead of a byte offset one, it's actually a pessimisation for no gain (yes, it might give better cache density _if_ the function that is linked after the current one is cache-dense with the function in question and _if_ the unlikely sequence is really really unlikely, but that's two fairly big ifs).

So I'm not at all convinced of the feature (or maybe gcc actually does the right thing, and the reason you can't reproduce it is because gcc is being understandably reluctant to use the other section).

Basically, there's "biased one way", "unlikely", and there's "practically never happens". And even the "practically never" case will probably be better off with the unlikely case close-by, if it means that the likely case can use a short branch.

Linus

#5 lore raw
Quoted 20 lines · Linus Torvalds
Quoted 10 lines · Jakub Jelinek
Quoted 3 lines

I wonder if gcc can be convinced to put all unlikely() code sections into a .text.rare as well, that'd be really cool.

gcc 4.1 calls them .text.unlikely and you need to use -freorder-blocks-and-partition
switch. But I haven't been able to reproduce it on a short testcase I cooked up, so maybe it is broken ATM (it put the whole function into .text rather than the expected part into .text.unlikely and left empty .text.unlikely).

If it causes the conditional jump to become a long one instead of a byte offset one, it's actually a pessimisation for no gain (yes, it might give better cache density _if_ the function that is linked after the current one is cache-dense with the function in question and _if_ the unlikely sequence is really really unlikely, but that's two fairly big ifs).

Quoted 3 lines

So I'm not at all convinced of the feature (or maybe gcc actually does the right thing, and the reason you can't reproduce it is because gcc is being understandably reluctant to use the other section).

It triggers either rarely or never in basic compilation; it's designed to work off profile feedback. With that it worked in gcc 4.1 a couple of weeks ago.

Signature · 2 lines
Daniel Jacobowitz
CodeSourcery
#6 lore raw
In reply to Arjan van de Ven
Quoted 7 lines · Arjan van de Ven
Quoted 6 lines

What would be nice to do is pack all the frequently used code together in close proximity. Would probably have much larger effects with userspace code, esp where we touch disk (which is more page-size granularity), but is probably worth doing with kernel code too (where AFAICS we'd only get cacheline granular).

Quoted 5 lines

in the kernel we could make a .text.rare section for functions, which we could annotate with __rare.
The other way around, __fastpath or whatever is a bad idea, everyone will consider all of their own functions as such (just like inline ;)... go-fast-stripes all the way :-(

Gah, we don't want to do this by hand in either direction. It's the inline nightmare all over again.

It'd be better to take a tool like oprofile and run it against some test suite to generate a usage map, then re-sort based on the map. Then ship a "standard" map in the stock tarball. Note that the map need only list the popular functions.

The ideal sampling tool can collect second order information: which functions are executed near each other as well as which are executed most frequently.

Signature · 1 line
Mathematics is the supreme nostalgia of our time.
#7 lore raw
Quoted 11 lines · Matt Mackall
Quoted 7 lines · Arjan van de Ven
Quoted 1 line

What would be nice to do is pack all the frequently used code together in close proximity. Would probably have much larger effects with userspace code, esp where we touch disk (which is more page-size granularity), but is probably worth doing with kernel code too (where AFAICS we'd only get cacheline granular).

in the kernel we could make a .text.rare section for functions, which we could annotate with __rare.
The other way around, __fastpath or whatever is a bad idea, everyone will consider all of their own functions as such (just like inline ;)... go-fast-stripes all the way :-(

Quoted 2 lines

Gah, we don't want to do this by hand in either direction. It's the inline nightmare all over again.

Absolutely.

Quoted 8 lines

It'd be better to take a tool like oprofile and run it against some test suite to generate a usage map, then re-sort based on the map. Then ship a "standard" map in the stock tarball. Note that the map need only list the popular functions.

The ideal sampling tool can collect second order information: which functions are executed near each other as well as which are executed most frequently.

There are tools already around to do this sort of thing as well - "profile directed optimization" or whatever they called it. Seems to be fairly commonly done with userspace, but not with the kernel. I'm not sure why not ... possibly because it's not available for gcc ?

M.

#8 lore raw
Quoted 5 lines

There are tools already around to do this sort of thing as well - "profile directed optimization" or whatever they called it. Seems to be fairly commonly done with userspace, but not with the kernel. I'm not sure why not ... possibly because it's not available for gcc ?

gcc has this for sure
the problem is that it expects the profile info in a special format that.. gets written to a file. So to do it in the kernel you need SomeMagic(tm), for example to use the kernel profiler but to let it output it somehow in a gcc compatible format.

#9 lore raw
Quoted 11 lines · Arjan van de Ven
Quoted 5 lines

There are tools already around to do this sort of thing as well - "profile directed optimization" or whatever they called it. Seems to be fairly commonly done with userspace, but not with the kernel. I'm not sure why not ... possibly because it's not available for gcc ?

gcc has this for sure
the problem is that it expects the profile info in a special format that.. gets written to a file. So to do it in the kernel you need SomeMagic(tm), for example to use the kernel profiler but to let it output it somehow in a gcc compatible format.

Right - at some point I remember a discussion of nifty Eclipse plugins to allow test runs on a custom workload and rebuild with feedback, but it never materialized.

Signature · 2 lines
Daniel Jacobowitz
CodeSourcery
#10 lore raw
In reply to Martin Bligh
Quoted 5 lines · Martin Bligh

There are tools already around to do this sort of thing as well - "profile directed optimization" or whatever they called it. Seems to be fairly commonly done with userspace, but not with the kernel. I'm not sure why not ... possibly because it's not available for gcc ?

.. and they are totally useless.

The fact is, the last thing we want to do is to ship a magic profile file around for each and every release. And that's what we'd have to do to get consistent and _useful_ performance increases.

That kind of profile-directed stuff is useful mainly for commercial binary releases (where the release binary can be guided by a profile file), or speciality programs that can tune themselves a few times before running.

A kernel that people recompile themselves simply isn't something where it works.

What _would_ work is something that actually CHECKS (and suggests) the hints we already have in the kernel. IOW, you could have an automated test-bed that runs some reasonable load, and then verifies whether there are branches that go only one way that could be annotated as such, or whether some annotation is wrong.

That way the "profile data" actually follows the source code, and is thus actually relevant to an open-source project. Because we do _not_ start having specially optimized binaries. That's against the whole point of being open source and trying to get users to get more deeply involved with the project.

Linus

#11 lore raw
Quoted 6 lines · Linus Torvalds

That way the "profile data" actually follows the source code, and is thus actually relevant to an open-source project. Because we do _not_ start having specially optimized binaries. That's against the whole point of being open source and trying to get users to get more deeply involved with the project.

Btw, having annotations obviously works, although it equally obviously will limit the scope of this kind of profile data. You won't get the same kind of granularity, and you'd only do the annotations for cases that end up being very clear-cut. But having an automated feedback cycle for adding (and removing!) annotations should make it pretty maintainable in the long run, although the initial annotations migh only end up being for really core code.

There's a few papers around that claim that programmers are often very wrong when they estimate probabilities for different code-paths, and that you absolutely need automation to get it right. I believe them. But the fact that you need automation doesn't automatically mean that you should feed the compiler a profile-data-blob.

You can definitely automate this on a source level too, the same way sparse annotations can help find user access problems.

There's a nice secondary advantage to source code annotations that are actively checked: they focus the programmers themselves on the issue. One of the biggest advantages (in my opinion) of the "struct xyzzy __user *" annotations has actually been that it's much more immediately clear to the kernel programmer that it's a user pointer. Many of the bugs we had were just the stupid unnecessary ones because it wasn't always obvious.

The same is likely true of rare functions etc. A function that is marked "rare" as a hint to the compiler to put it into another segment (and perhaps optimize more aggressively for size etc rather than performance) is also a big hint to a programmer that he shouldn't care. On the other hand, if some branch is marked as "always()", that also tells the programmer something real.

So explicit source hints may be more work, but they have tons of advantages. Ranging from repeatability and distribution to just the programmer being aware of them.

In other projects, maybe people don't care as much about the programmer being aware of what's going on - garbage collection etc silent automation is all wonderful. In the kernel, I'd rather have people be aware of what happens.

Linus

#12 lore raw
Quoted 9 lines · Linus Torvalds
Quoted 1 line · Linus Torvalds

That way the "profile data" actually follows the source code, and is thus actually relevant to an open-source project. Because we do _not_ start having specially optimized binaries. That's against the whole point of being open source and trying to get users to get more deeply involved with the project.

Btw, having annotations obviously works, although it equally obviously will limit the scope of this kind of profile data. You won't get the same kind of granularity, and you'd only do the annotations for cases that end up being very clear-cut. But having an automated feedback cycle for adding (and removing!) annotations should make it pretty maintainable in the long run, although the initial annotations migh only end up being for really core code.

There's a few papers around that claim that programmers are often very wrong when they estimate probabilities for different code-paths, and that you absolutely need automation to get it right. I believe them. But the fact that you need automation doesn't automatically mean that you should feed the compiler a profile-data-blob.

Hmm. if you're just going to do it as binary on/off ...is it not pretty trivial to do a crude test implementation by booting the kernel, turning on profiling, running a bunch of different tests, then marking anything
that never appears at all in profiling as rare?

Not saying it's a good long-term approach, but would it not give us enough data to know whether the whole approach was worthwhile? I suspect (on random gut-feel) we never call at over 50% of the functions we have
(an even easier hypothesis to test)

OTOH, do we have that much to gain anyway in kernel space? all we're doing is packing stuff down into the same cacheline or not, isn't it? As we have all pages pinned in memory, does it matter for any reason
beyond that?

M.

#13 lore raw
Quoted 5 lines · Martin Bligh

Hmm. if you're just going to do it as binary on/off ...is it not pretty trivial to do a crude test implementation by booting the kernel, turning on profiling, running a bunch of different tests, then marking anything that never appears at all in profiling as rare?

Yes, I think "crude" is exactly where we want to start. It's much easier to then make it smarter later.

Quoted 2 lines

Not saying it's a good long-term approach, but would it not give us enough data to know whether the whole approach was worthwhile?

Yes. And it's entirely possible that "crude" is perfectly fine even in the long run. I suspect this is very much a "5% of the work gets us 80% of the benefit", with a _very_ long tail with tons of more work to get very minor incremental savings..

Quoted 4 lines

OTOH, do we have that much to gain anyway in kernel space? all we're doing is packing stuff down into the same cacheline or not, isn't it?
As we have all pages pinned in memory, does it matter for any reason beyond that?

The cache effects are likely the biggest ones, and no, I don't know how much denser it will be in the cache. Especially with a 64-byte one.. (although 128 bytes is fairly common too).

There are some situations where we have TLB issues, but those are likely cases where we don't care about placement performance anyway (ie they'd be in situations where you use the page-alloc-debug stuff, which is very expensive for _other_ reasons ;)

Linus

#14 lore raw
Quoted 4 lines · Linus Torvalds

The cache effects are likely the biggest ones, and no, I don't know how much denser it will be in the cache. Especially with a 64-byte one.. (although 128 bytes is fairly common too).

Oh, but validatign things like "likely()" and "unlikely()" branch hints might be a noticeably bigger issue.

In user space, placement on the macro level is probably a bigger deal, but in the kernel we probably care mostly about just single cachelines and about branch prediction/placement.

Linus

#15 lore raw
Quoted 8 lines · Linus Torvalds
Quoted 4 lines · Linus Torvalds

The cache effects are likely the biggest ones, and no, I don't know how much denser it will be in the cache. Especially with a 64-byte one.. (although 128 bytes is fairly common too).

Oh, but validatign things like "likely()" and "unlikely()" branch hints might be a noticeably bigger issue.

i frequently validate branches in performance-critical kernel code like the scheduler (and the mutex code ;), via instruction-granularity profiling, driven by a high-frequency (10-100 KHz) NMI interrupt. A bad branch layout shows up pretty clearly in annotated assembly listings:

c037313c:     1715 <schedule>:
c037313c:     1715 	55                   	push   %ebp
c037313d:      264 	b8 00 f0 ff ff       	mov    $0xfffff000,%eax
c0373142:      150 	89 e5                	mov    %esp,%ebp
c0373144:        0 	57                   	push   %edi
c0373145:      852 	56                   	push   %esi
c0373146:      215 	53                   	push   %ebx
c0373147:        0 	83 ec 30             	sub    $0x30,%esp
c037314a:      184 	21 e0                	and    %esp,%eax
c037314c:      120 	8b 10                	mov    (%eax),%edx
c037314e:        0 	83 ba 84 00 00 00 00 	cmpl   $0x0,0x84(%edx)
c0373155:       83 	75 2b                	jne    c0373182 <schedule+0x46>
c0373157:      104 	8b 48 14             	mov    0x14(%eax),%ecx
c037315a:       39 	f7 c1 ff ff ff ef    	test   $0xefffffff,%ecx
c0373160:      112 	74 20                	je     c0373182 <schedule+0x46>
c0373162:        0 	ff b2 9c 00 00 00    	pushl  0x9c(%edx)
c0373168:        0 	8d 82 a4 01 00 00    	lea    0x1a4(%edx),%eax
c037316e:        0 	51                   	push   %ecx
c037316f:        0 	50                   	push   %eax
c0373170:        0 	68 7e 0e 39 c0       	push   $0xc0390e7e
c0373175:        0 	e8 a3 36 da ff       	call   c011681d <printk>
c037317a:        0 	e8 48 03 d9 ff       	call   c01034c7 <dump_stack>
c037317f:        0 	83 c4 10             	add    $0x10,%esp
c0373182:      323 	8b 55 04             	mov    0x4(%ebp),%edx
c0373185:        5 	b8 02 00 00 00       	mov    $0x2,%eax
c037318a:        0 	e8 b3 3f da ff       	call   c0117142 <profile_hit>
c037318f:      349 	b8 00 f0 ff ff       	mov    $0xfffff000,%eax
c0373194:      880 	21 e0                	and    %esp,%eax
c0373196:        0 	8b 00                	mov    (%eax),%eax
c0373198:        0 	89 45 d4             	mov    %eax,0xffffffd4(%ebp)
c037319b:      440 	83 78 14 00          	cmpl   $0x0,0x14(%eax)
c037319f:        5 	78 05                	js     c03731a6 <schedule+0x6a>

the second column is the number of profiler hits. As you can see, the branch at c0373160 is always taken, and there's a hole of 32 bytes in the instruction stream. It is relatively easy to identify the likely/unlikely candidates for various workloads. (It would probably be even better to have a visual tool that also associates the source code with the data.)

i've seen alot of such profiles on alot of different workloads, and my guesstimate would be that with 'perfect' likely/unlikely hints, and with 'perfect' function ordering, we could roughly halve (!) the current icache footprint of the kernel on complex workloads too.

Especially with 64 or 128 byte L1 cachelines our codepaths are really fragmented and we can easily have 3-4 times of the optimal icache footprint, for a given syscall. We very often have cruft in the hotpath, and we often have functions that belong together ripped apart by things like e.g. __sched annotators. I havent seen many cases of wrongly judged likely/unlikely hints, what happens typically is that there's no annotation and the default compiler guess is wrong.

the dcache footprint of the kernel is much better, mostly because it's so easy to control it in C. The icache footprint is alot more elusive. (and also alot more critical to execution speed on nontrivial workloads)

so i think there are two major focus areas to improve our icache footprint:

- reduce code size
- reduce fragmentation of the codepath

fortunately both are hard and technically challenging projects, and both will improve the icache footprint - and they will also bring other benefits. [ We usually have much more problems with the easy and boring stuff ;-) ]

icache fragmentation reduction is also hard because it has to deal with fundamentally conflicting constraints: one workload's ideal ordering is different from another workload's ideal ordering, and such workloads can be superimposed on a system.

I think the only sane solution [that would be endorsed by distributions] is to allow users to reorder function sections runtime (per boot). That is alot faster and more robust (from a production POV) than a full recompilation of the kernel. Recompilation is always risky, it needs too much context, and has too many tool dependencies - and is thus currently untestable. And we dont really need a recompilation of the kernel technically - we need a relinking. Relinking is much safer from a testability POV: reordering of the functions doesnt change their internal instruction sequence or their interactions.

and we could use mcount() to gather function-cohesion data runtime. The mcount() call could be patched out from the image runtime, when no data gathering is happening. Given that the average function size is ~100 bytes, and an mcount call costs 5 bytes, the overhead would be +5% of size and an extra 5-byte NOP per function. That's not good, but it is still at least an order of magnitude smaller than the possible gain in icache footprint. (Also, people could run mcount()-less kernels as well, once the data has been gathered, and the relink was done.)

one problem are modules though - they could only be reordered within themselves. On an average system which has ~100 modules loaded, the average icache fragmentation is +100*128/2 == 6.4K [with 128 byte L1 cachelines], which can be significant (depending on the workload). OTOH, modules do have strong internal cohesion - they contain functions that belong together conceptually. So by reordering functions within modules we'll likely be able to realize most of the icache savings possible. The only exception would be workloads that utilize many modules at a high frequency. Such workloads will likely trash the icache anyway.

Ingo

#16 lore raw
Quoted 5 lines · Ingo Molnar

i frequently validate branches in performance-critical kernel code like the scheduler (and the mutex code ;), via instruction-granularity profiling, driven by a high-frequency (10-100 KHz) NMI interrupt. A bad branch layout shows up pretty clearly in annotated assembly listings:

Yes, but we only do this for routines that we look at anyway.

Also, the profiles can be misleading at times: you often get instructions with zero hits, because they always schedule together with another instruction. So parsing things and then matching them up (correctly) with the source code in order to annotate them is probably pretty nontrivial.

But starting with the code-paths that get literally zero profile events is definitely the way to go.

Quoted 7 lines

Especially with 64 or 128 byte L1 cachelines our codepaths are really fragmented and we can easily have 3-4 times of the optimal icache footprint, for a given syscall. We very often have cruft in the hotpath, and we often have functions that belong together ripped apart by things like e.g. __sched annotators. I havent seen many cases of wrongly judged likely/unlikely hints, what happens typically is that there's no annotation and the default compiler guess is wrong.

We don't have likely()/unlikely() that often, and at least in my case it's partly because the syntax is a pain (it would probably have been better to include the "if ()" part in the syntax - the millions of parenthesis just drive me wild).

So yeah, we tend to put likely/unlikely only on really obvious stuff, and only on functions where we think about it. So we probably don't get it wrong that often.

Quoted 11 lines

the dcache footprint of the kernel is much better, mostly because it's so easy to control it in C. The icache footprint is alot more elusive. (and also alot more critical to execution speed on nontrivial workloads)

so i think there are two major focus areas to improve our icache footprint:

- reduce code size
- reduce fragmentation of the codepath

fortunately both are hard and technically challenging projects

That's an interesting use of "fortunately". I tend to prefer the form where it means "fortunately, we can trivially fix this with a two-line solution that is obviously correct" ;)

Linus

#17 lore raw
Quoted 5 lines · Linus Torvalds

Also, the profiles can be misleading at times: you often get instructions with zero hits, because they always schedule together with another instruction. So parsing things and then matching them up (correctly) with the source code in order to annotate them is probably pretty nontrivial.

yeah, but schedules-together isnt a big problem in terms of branch
predictions: unused branches really stick out with their zero counters. Especially if there enough profiling hits, it's usually a quick glance to figure out the hotpath:

c0119e1f:   582904 <sys_gettimeofday>:
c0119e1f:   582904 	57                   	push   %edi
c0119e20:   312621 	56                   	push   %esi
c0119e21:       29 	53                   	push   %ebx
c0119e22:        0 	50                   	push   %eax
c0119e23:   285471 	50                   	push   %eax
c0119e24:       15 	8b 74 24 18          	mov    0x18(%esp),%esi
c0119e28:       21 	8b 7c 24 1c          	mov    0x1c(%esp),%edi
c0119e2c:   325688 	89 f0                	mov    %esi,%eax
c0119e2e:       26 	89 fa                	mov    %edi,%edx
c0119e30:        0 	e8 86 fe ff ff       	call   c0119cbb <timeofday_API_hacks>
c0119e35:   377758 	83 f8 01             	cmp    $0x1,%eax
c0119e38:   384539 	75 3f                	jne    c0119e79 <sys_gettimeofday+0x5a>
c0119e3a:        0 	85 f6                	test   %esi,%esi
c0119e3c:        0 	74 19                	je     c0119e57 <sys_gettimeofday+0x38>
c0119e3e:        0 	89 e0                	mov    %esp,%eax
c0119e40:        0 	e8 4b c6 fe ff       	call   c0106490 <do_gettimeofday>
c0119e45:        0 	b9 08 00 00 00       	mov    $0x8,%ecx
c0119e4a:        0 	89 f0                	mov    %esi,%eax
c0119e4c:        0 	89 e2                	mov    %esp,%edx
c0119e4e:        0 	e8 3e f2 0b 00       	call   c01d9091 <copy_to_user>
c0119e53:        0 	85 c0                	test   %eax,%eax
c0119e55:        0 	75 19                	jne    c0119e70 <sys_gettimeofday+0x51>
c0119e57:        0 	85 ff                	test   %edi,%edi
c0119e59:        0 	74 1c                	je     c0119e77 <sys_gettimeofday+0x58>
c0119e5b:        0 	b9 08 00 00 00       	mov    $0x8,%ecx
c0119e60:        0 	ba 88 3e 53 c0       	mov    $0xc0533e88,%edx
c0119e65:        0 	89 f8                	mov    %edi,%eax
c0119e67:        0 	e8 25 f2 0b 00       	call   c01d9091 <copy_to_user>
c0119e6c:        0 	85 c0                	test   %eax,%eax
c0119e6e:        0 	74 07                	je     c0119e77 <sys_gettimeofday+0x58>
c0119e70:        0 	b8 f2 ff ff ff       	mov    $0xfffffff2,%eax
c0119e75:        0 	eb 02                	jmp    c0119e79 <sys_gettimeofday+0x5a>
c0119e77:        0 	31 c0                	xor    %eax,%eax
c0119e79:      308 	5e                   	pop    %esi
c0119e7a:   749654 	5f                   	pop    %edi
c0119e7b:   415831 	5b                   	pop    %ebx
c0119e7c:      744 	5e                   	pop    %esi
c0119e7d:   361201 	5f                   	pop    %edi
c0119e7e:   373195 	c3                   	ret    

here at the top you can see that the CPU is a nice 3-issue design and that in this workload the branch at c0119e38 is untaken and returns from the function afterwards. A branch instruction followed by more than 2 zero profile-count instructions (that are not jumps) is a good sign of an untaken branch. This would be a pretty strong heuristics as well i think. We could really make the requirement be 'zero profiling hits', and the branch instruction would have to get 'enough' hits, to conclude that the branch is a candidate for likely/unlikely.

Ingo

#18 lore raw
Quoted 3 lines · Ingo Molnar

Especially if there enough profiling hits, it's usually a quick glance to figure out the hotpath:

Ehh. What's a "quick glance" to a human can be quite hard to automate. That's my point.

If we do the "human quick glances", we won't be seeing much come out of this. That's what we've already been doing, for several years.

I thought the discussion was about trying to automate this..

Linus

#19 lore raw
Quoted 10 lines · Linus Torvalds
Quoted 2 lines

Especially if there enough profiling hits, it's usually a quick glance to figure out the hotpath:

Ehh. What's a "quick glance" to a human can be quite hard to automate. That's my point.

If we do the "human quick glances", we won't be seeing much come out of this. That's what we've already been doing, for several years.

I thought the discussion was about trying to automate this..

i think it could be automated reasonably well. An 80% effective "which condition is judged incorrectly" decision could be made based on:

branch instruction with more than 10% of the average per-instruction cycle count, followed by an at least 4-instruction sequence of non-branch (and non-jump) instructions that have exactly zero profiling hits. ('few hits' we are not interested in - those are not likely/unlikely candidates)

another part is to feed this back into .c, automatically. I've done DEBUG_INFO, gdb vmlinux and list *0x12341234 based scripts before, but they are not always reliable. They could probably do something like: "if the resulting source code contains a clear 'if (' sequence, modify it to 'if __unlikely (', or something like that.

i'd expect such a method to catch ~50-60% of the interesting cases, not more. (the rest would be stuff the heuristics doesnt catch, and it would also be stuff like 'while' or 'break' or 'goto', which are much harder to rewrite automatically.

but it does feel quite a bit fragile.

Ingo

#20 lore raw
In reply to Ingo Molnar
Quoted 1 line

I think the only sane solution [that would be endorsed by distributions] is to allow users to reorder function sections runtime (per boot). That is alot faster and more robust (from a production POV) than a full recompilation of the kernel. Recompilation is always risky, it needs too much context, and has too many tool dependencies - and is thus currently untestable.

<smhuch> - the sound of my eyeballs popping out and splatting against the opposite wall.

So ... recompilation is not testable, but boot time reordering of the code somehow is? ;-) Yes, I understand the distro toolchain issues, but it's still a scary solution ...

Personally, I'd think the sane thing is not to try to optimise by workload, but get 80% of the benefit by just reordering on a more generalized workload. Doing boot-time reordering for this on non-custom kernels just seems terrifying .. it's not that huge a benefit, surely?

Quoted 1 line

one problem are modules though - they could only be reordered within themselves. On an average system which has ~100 modules loaded, the average icache fragmentation is +100*128/2 == 6.4K [with 128 byte L1 cachelines], which can be significant (depending on the workload). OTOH, modules do have strong internal cohesion - they contain functions that belong together conceptually. So by reordering functions within modules we'll likely be able to realize most of the icache savings possible. The only exception would be workloads that utilize many modules at a high frequency. Such workloads will likely trash the icache anyway.

I was thinking about that with modules earlier, and whether modular kernels would actually be faster because of that than a statically compiled one. But don't you get similar effects from the .o groupings by file we get? or does the linker not preserve those groupings?

M.

#21 lore raw
Quoted 7 lines · Martin Bligh
Quoted 6 lines

I think the only sane solution [that would be endorsed by distributions] is to allow users to reorder function sections runtime (per boot). That is alot faster and more robust (from a production POV) than a full recompilation of the kernel. Recompilation is always risky, it needs too much context, and has too many tool dependencies - and is thus currently untestable.

Quoted 6 lines

<smhuch> - the sound of my eyeballs popping out and splatting against the opposite wall.

So ... recompilation is not testable, but boot time reordering of the code somehow is? ;-) Yes, I understand the distro toolchain issues, but it's still a scary solution ...

'testable' in the sense that the stability and reliability of the system is alot less dependent on function ordering, than it is dependent on compilation. It's not 'testable' in the sense of being able to cycle through all the 60000-factorial function combinations - but that's not really a problem, as long as the risk of the worst-case effect of function reordering can be judged and covered. The kernel stopped being 'fully testable' sometime around version 0.2 already ;-)

Quoted 5 lines

Personally, I'd think the sane thing is not to try to optimise by workload, but get 80% of the benefit by just reordering on a more generalized workload. Doing boot-time reordering for this on non-custom kernels just seems terrifying .. it's not that huge a benefit, surely?

i'm not so sure, see the ballpark figures below.

Quoted 10 lines
Quoted 9 lines

one problem are modules though - they could only be reordered within themselves. On an average system which has ~100 modules loaded, the average icache fragmentation is +100*128/2 == 6.4K [with 128 byte L1 cachelines], which can be significant (depending on the workload). OTOH, modules do have strong internal cohesion - they contain functions that belong together conceptually. So by reordering functions within modules we'll likely be able to realize most of the icache savings possible. The only exception would be workloads that utilize many modules at a high frequency. Such workloads will likely trash the icache anyway.

Quoted 4 lines

I was thinking about that with modules earlier, and whether modular kernels would actually be faster because of that than a statically compiled one. But don't you get similar effects from the .o groupings by file we get? or does the linker not preserve those groupings?

they are mostly preserved (except for things like __sched which move functions out of .o), but look at a call-chain like this:

| new stack-footprint maximum: khelper/1125, 2412 bytes (out of 8140 bytes). ------------|

{   40} [<c0144a31>] debug_stackoverflow+0xb6/0xc4
{   60} [<c0144f66>] __mcount+0x47/0xe0
{   20} [<c0110b24>] mcount+0x14/0x18
{  116} [<c05fec5e>] __down_mutex+0xe/0x87b
{   28} [<c0601544>] _spin_lock+0x24/0x49
{   36} [<c015aa7e>] kmem_cache_alloc+0x40/0xe9
{   16} [<c0154ddd>] mempool_alloc_slab+0x1d/0x1f
{   56} [<c0154c82>] mempool_alloc+0x39/0xf1
{   44} [<c02f3519>] get_request+0xf7/0x2dc
{   60} [<c02f372d>] get_request_wait+0x2f/0x10f
{   88} [<c02f43bc>] __make_request+0xae/0x552
{   88} [<c02f4b9b>] generic_make_request+0xaf/0x24c
{   84} [<c02f4d90>] submit_bio+0x58/0x127
{   20} [<c0196912>] mpage_bio_submit+0x31/0x39
{  292} [<c0196d4e>] do_mpage_readpage+0x2f5/0x451
{   88} [<c0196f99>] mpage_readpages+0xef/0x19e
{   24} [<c01dfeb4>] ext3_readpages+0x2c/0x2e
{   80} [<c0158b4b>] read_pages+0x38/0x14d
{   60} [<c0158de1>] __do_page_cache_readahead+0x181/0x186
{   36} [<c0158f40>] blockable_page_cache_readahead+0x69/0xd0
{   44} [<c015918e>] page_cache_readahead+0x13c/0x185

{ 120} [<c0151abf>] do_generic_mapping_read+0x436/0x6c3
{ 80} [<c0151fc8>] __generic_file_aio_read+0x17f/0x22e
{ 44} [<c01520c8>] generic_file_aio_read+0x51/0x7f
{ 160} [<c0171091>] do_sync_read+0xba/0x109
{ 40} [<c017119e>] vfs_read+0xbe/0x1a0
{ 40} [<c017c5fa>] kernel_read+0x4b/0x55
{ 192} [<c019f844>] load_elf_binary+0x5e9/0xd2d
{ 32} [<c017d4d1>] search_binary_handler+0x80/0x136
{ 176} [<c019e87e>] load_script+0x246/0x258

{   32} [<c017d4d1>] search_binary_handler+0x80/0x136
{   36} [<c017d7c2>] do_execve+0x23b/0x268
{   36} [<c0101c4e>] sys_execve+0x41/0x8f

{=2368} [<c01030ca>] syscall_call+0x7/0xb
<---------------------------

[readers beware, quick & dirty and possibly wrong guesstimations: ]

these 30 functions involve roughly 10-15 .o files, so we've got 2-3 functions per .o file only. And that's typical for VFS, IO, networking and lots of other syscall types. So if the full kernel image is 3MB, and we've got 30 functions totalling to 3000 bytes, they are spread out in 10-15 groups right now - creating 10-15 split icache lines. (in reality we have in excess of 20 split icache-lines, due to weak cohesion even within .o files) With 64-byte lines that's 320-480 bytes 'lost' due to fragmentation alone, with 128-byte lines it's 640-960 bytes - which is 10%-21% in the 64-byte case, and 21%-42% in the 128-byte case. I.e. the icache bloat just due to the placement is quite significant. Adding .o-level fragmentation plus inter-function inactive code to the mix can easily baloon this even higher. Plus the current method of doing unlikely() means the unlikely instructions are near the end of the function - so they still 'spread apart' the footprint and thus have a nontrivial icache cost.

[ now the above one is a random example out of my logs that is also a
really bad example: in reality would win little from better icache
footprint: an execve() takes 100,000-200,000 cycles even when everything comes from the pagecache, and most of those cycles are spent in very tight codepaths. ]

Ingo

#22 lore raw
Quoted 2 lines

these 30 functions involve roughly 10-15 .o files, so we've got 2-3 functions per .o file only. And that's typical for VFS, IO, networking and lots of other syscall types. So if the full kernel image is 3MB, and we've got 30 functions totalling to 3000 bytes, they are spread out in 10-15 groups right now - creating 10-15 split icache lines. (in reality we have in excess of 20 split icache-lines, due to weak cohesion even within .o files) With 64-byte lines that's 320-480 bytes 'lost' due to fragmentation alone, with 128-byte lines it's 640-960 bytes - which is 10%-21% in the 64-byte case, and 21%-42% in the 128-byte case. I.e. the icache bloat just due to the placement is quite significant. Adding .o-level fragmentation plus inter-function inactive code to the mix can easily baloon this even higher. Plus the current method of doing unlikely() means the unlikely instructions are near the end of the function - so they still 'spread apart' the footprint and thus have a nontrivial icache cost.

mmm. will take me a little time to digest that.

But we were just discussing here ... wouldn't it be worth moving "unlikely" sections of code completely out of line? If they were calls to separate functions, all this optimisation stuff could just work at a function level, and would be pretty trivial to do?

ie instead of:

if (unlikely(conditon)) {
	do;
	some;
	stuff;
	BUG();
	error();
	oh_dear();
}

we'd have

if (unlikely(conditon)) {
	call_oh_shit();
}

__rarely_called void call_oh_shit()

{
	do;
	some;
	stuff;
	BUG();
	error();
	oh_dear();
}

depends how long they are, I suppose. Moving that out of line would seem to make more difference to icache footprint to me than just cacheline packing functions.

M.

#23 lore raw
Quoted 4 lines · Martin Bligh

But we were just discussing here ... wouldn't it be worth moving "unlikely" sections of code completely out of line? If they were calls to separate functions, all this optimisation stuff could just work at a function level, and would be pretty trivial to do?

...assuming that they don't need to access many local variables. And don't
have any "goto" statements... and... etc, etc.

Quoted 7 lines

we'd have

if (unlikely(conditon)) {
	call_oh_shit();
}

__rarely_called void call_oh_shit()

Quoted 8 lines
{
	do;
	some;
	stuff;
	BUG();
	error();
	oh_dear();
}

As I described in my other mail on this thread, the _ideal_ solution would be to tell the compiler that BUG() is a __rarely_called function (well, it's a macro now but it could be made into an inline function) and let the compiler figure the rest out without further annotation

Quoted 3 lines

Moving that out of line would seem
to make more difference to icache footprint to me than just cacheline packing functions.

Assuming "-funit-at-a-time" (which all archs will probably be using soon) you'd probably get exactly the same opcodes either way.

-Mitch

#24 lore raw
In reply to Linus Torvalds
Quoted 2 lines · Linus Torvalds

Oh, but validatign things like "likely()" and "unlikely()" branch hints might be a noticeably bigger issue.

I think the issues are somewhat intertwined.

For instance, assume you have code like:

	if (some_function(skb)) {
		blah();
		printk(KERN_WARN "bad packet...\n");
	} else {
		process_skb(skb);
	}

Now just by annotating printk() as "rare" then gcc should be able to guess that the "if" is unlikely() without explicitly marking it as such since one of its paths calls a rare function and the other does not. If instead both paths called rare functions then the compiler could decide that the whole block is probably "rare" and optimize accordingly.

I haven't looked at gcc 4.1 yet so I don't know how sophisticated its "rare" promotion rules are yet but this is certainly the kind of thing the compiler should be able to handle.

So basically better inter-functional locality hints should also help intra-functional locality.

[from another message]

Quoted 4 lines

We don't have likely()/unlikely() that often, and at least in my case it's partly because the syntax is a pain (it would probably have been better to include the "if ()" part in the syntax - the millions of parenthesis just drive me wild).

I actually did that in a project once (an "unlikely_if()" macro) It was not a good idea. The problem is that every syntax-highlighter knows that "if" is a keyword but you'd have to teach it about "unlikely_if". It was surprising how visually jarring having different pretty-printing for different types of "if" statements was. "if (unlikely())" looks much cleaner in comparison.

-Mitch

#25 lore raw
Quoted 6 lines · Mitchell Blank Jr

I actually did that in a project once (an "unlikely_if()" macro) It was not a good idea. The problem is that every syntax-highlighter knows that "if" is a keyword but you'd have to teach it about "unlikely_if". It was surprising how visually jarring having different pretty-printing for different types of "if" statements was. "if (unlikely())" looks much cleaner in comparison.

a better syntax would be:

	if __unlikely (cond) {
		...
	}

since it's the extra parantheses that are causing the visual complexity.

Ingo

#26 lore raw
Quoted 5 lines · Ingo Molnar

a better syntax would be:

	if __unlikely (cond) {
		...
	}

Well you could just throw an extra set of parenthesis around the expansion of the current "unlikely()" macro and get this effect now.

-Mitch

#27 lore raw
In reply to Linus Torvalds
Quoted 18 lines · Linus Torvalds
Quoted 6 lines · Linus Torvalds

That way the "profile data" actually follows the source code, and is thus actually relevant to an open-source project. Because we do _not_ start having specially optimized binaries. That's against the whole point of being open source and trying to get users to get more deeply involved with the project.

Btw, having annotations obviously works, although it equally obviously will limit the scope of this kind of profile data. You won't get the same kind of granularity, and you'd only do the annotations for cases that end up being very clear-cut. But having an automated feedback cycle for adding (and removing!) annotations should make it pretty maintainable in the long run, although the initial annotations migh only end up being for really core code.

Quoted 5 lines

There's a few papers around that claim that programmers are often very wrong when they estimate probabilities for different code-paths, and that you absolutely need automation to get it right. I believe them. But the fact that you need automation doesn't automatically mean that you should feed the compiler a profile-data-blob.

I think it's a mistake to interleave this data into the C source. It's expensive and tedious to change relative to its volatility. What I was proposing was something like, say, arch/i386/popularity.lst, which would simply contain a list of the most popular n% of functions sorted by popularity. As text, of course.

Signature · 1 line
Mathematics is the supreme nostalgia of our time.
#28 lore raw
Quoted 3 lines · Matt Mackall

I think it's a mistake to interleave this data into the C source. It's expensive and tedious to change relative to its volatility.

I don't believe it is actually all _that_ volatile. Yes, it would be a huge issue _initially_, but the incremental effects shouldn't be that big, or there is something wrong with the approach.

Quoted 3 lines

What I was proposing was something like, say, arch/i386/popularity.lst, which would simply contain a list of the most popular n% of functions sorted by popularity. As text, of course.

I suspect that would certainlty work for pure function-based popularity, and yes, it has the advantage of being simple (especially for something that ends up being almost totally separated from the compiler: if we're using this purely to modify link scripts etc with special tools).

But what about the unlikely/likely conditional hints that we currently do by hand? How are you going to sanely maintain a list of those without doing that in source code?

Linus

#29 lore raw
Quoted 9 lines · Linus Torvalds
Quoted 3 lines · Matt Mackall

I think it's a mistake to interleave this data into the C source. It's expensive and tedious to change relative to its volatility.

I don't believe it is actually all _that_ volatile. Yes, it would be a huge issue _initially_, but the incremental effects shouldn't be that big, or there is something wrong with the approach.

No, perhaps not. But it would be nice in theory for people to be able to do things like profile their production system and relink. And having to touch hundreds of files to do it would be painful.

Quoted 4 lines
Quoted 3 lines

What I was proposing was something like, say, arch/i386/popularity.lst, which would simply contain a list of the most popular n% of functions sorted by popularity. As text, of course.

Quoted 8 lines

I suspect that would certainlty work for pure function-based popularity, and yes, it has the advantage of being simple (especially for something that ends up being almost totally separated from the compiler: if we're using this purely to modify link scripts etc with special tools).

But what about the unlikely/likely conditional hints that we currently do by hand? How are you going to sanely maintain a list of those without doing that in source code?

Dunno. Those bits are all anonymous so marking them in situ is about the only way to go. But we can do better for whole functions.

Signature · 1 line
Mathematics is the supreme nostalgia of our time.
#30 lore raw
Quoted 10 lines
Quoted 6 lines
Quoted 2 lines

What I was proposing was something like, say, arch/i386/popularity.lst, which would simply contain a list of the most popular n% of functions sorted by popularity. As text, of course.

I suspect that would certainlty work for pure function-based popularity, and yes, it has the advantage of being simple (especially for something that ends up being almost totally separated from the compiler: if we're using this purely to modify link scripts etc with special tools).

But what about the unlikely/likely conditional hints that we currently do by hand? How are you going to sanely maintain a list of those without doing that in source code?

Dunno. Those bits are all anonymous so marking them in situ is about the only way to go. But we can do better for whole functions.

Would also make it easier to rank it as a percentage, or group by locality of reference to other functions, rather than just a binary split of "rare" vs "not-rare".

Of course it's all very dependant on workload, which drivers you're using too, etc, etc. So a profile that's separate also makes it much easier to tweak for one machine than the source base in general, which
theoretically represents everyone (and thus has little info ;-)).

Which also makes me think it's easier to mark hot functions than cold ones, in a more general maintainance sense.

M.

#31 lore raw
Quoted 22 lines · Martin Bligh
Quoted 10 lines
Quoted 10 lines
Quoted 4 lines

What I was proposing was something like, say, arch/i386/popularity.lst, which would simply contain a list of the most popular n% of functions sorted by popularity. As text, of course.

I suspect that would certainlty work for pure function-based popularity, and yes, it has the advantage of being simple (especially for something that ends up being almost totally separated from the compiler: if we're using this purely to modify link scripts etc with special tools).

Quoted 7 lines
Quoted 3 lines

But what about the unlikely/likely conditional hints that we currently do by hand? How are you going to sanely maintain a list of those without doing that in source code?

Dunno. Those bits are all anonymous so marking them in situ is about the only way to go. But we can do better for whole functions.

Would also make it easier to rank it as a percentage, or group by locality of reference to other functions, rather than just a binary split of "rare" vs "not-rare".

Quoted 7 lines

Of course it's all very dependant on workload, which drivers you're using too, etc, etc. So a profile that's separate also makes it much easier to tweak for one machine than the source base in general, which theoretically represents everyone (and thus has little info ;-)).

Which also makes me think it's easier to mark hot functions than cold ones, in a more general maintainance sense.

Yes, I think it definitely makes sense to think in terms of hot functions. We surely have a nice long tail on the popularity distribution and only the first 5% or so are actually worth sorting and packing.

Signature · 1 line
Mathematics is the supreme nostalgia of our time.
#32 lore raw
In reply to Matt Mackall
Quoted 7 lines · Matt Mackall
Quoted 3 lines

I don't believe it is actually all _that_ volatile. Yes, it would be a huge issue _initially_, but the incremental effects shouldn't be that big, or there is something wrong with the approach.

No, perhaps not. But it would be nice in theory for people to be able to do things like profile their production system and relink. And having to touch hundreds of files to do it would be painful.

we can (almost) do that: via -ffunction-sections. It does seem to work on both the gcc and the ld side. [i tried to use this for --gc-sections to save more space, but that ld option seems unstable, i couldnt link a bootable image. -ffunction-sections itself seems to work fine in gcc4.]

i think all that is needed to reorder the functions is a build-time generated ld script, which is generated off the 'popularity list'.

so i think the two concepts could nicely co-exist: in-source annotations help us maintain the popularity list, -ffunction-sections allows us to reorder at link time. In fact such a kernel could be shipped in 'unlinked' state, and could be relinked based on per-system profiling data. As long as we have KALLSYMS, it's not even a big debuggability issue.

the branch-likelyhood thing is a separate issue from function-cohesion, but could be handled by the same concept: if there was a --ffunction-unlikely-sections option in gcc (there's none currently, AFAICS), then those could be reordered in a smart way too. (We wouldnt get the 8-byte relative jumps back though, gcc would always have to assume that the jump is far away.)

Ingo

#33 lore raw
Quoted 7 lines · Ingo Molnar
Quoted 4 lines · Matt Mackall
Quoted 3 lines

I don't believe it is actually all _that_ volatile. Yes, it would be a huge issue _initially_, but the incremental effects shouldn't be that big, or there is something wrong with the approach.

Quoted 8 lines
Quoted 3 lines

No, perhaps not. But it would be nice in theory for people to be able to do things like profile their production system and relink. And having to touch hundreds of files to do it would be painful.

we can (almost) do that: via -ffunction-sections. It does seem to work on both the gcc and the ld side. [i tried to use this for --gc-sections to save more space, but that ld option seems unstable, i couldnt link a bootable image. -ffunction-sections itself seems to work fine in gcc4.]

Yeah, we've been talking about --gc-sections for years. It'd be nice if we could work the build system in that direction with this profiling concept.

(I suspect something silly happened in your test like dropping the fixup table, btw.)

Quoted 9 lines

i think all that is needed to reorder the functions is a build-time generated ld script, which is generated off the 'popularity list'.

so i think the two concepts could nicely co-exist: in-source annotations help us maintain the popularity list, -ffunction-sections allows us to reorder at link time. In fact such a kernel could be shipped in 'unlinked' state, and could be relinked based on per-system profiling data. As long as we have KALLSYMS, it's not even a big debuggability issue.

I'm still not sure about in-source annotations for popularity. My suspicion is that it's just too workload-dependent, and a given author's workload will likely be biased towards their code.

Signature · 1 line
Mathematics is the supreme nostalgia of our time.
#34 lore raw
Quoted 3 lines · Matt Mackall

I'm still not sure about in-source annotations for popularity. My suspicion is that it's just too workload-dependent, and a given author's workload will likely be biased towards their code.

To some extent that's true, but like Linus implied with his "5% work gets us 80% there" I think there are a ton of obvious cases, e.g. kmalloc, alloc_pages, interrupt handling, etc. that could be marked right away and put into a frequently used section.

Jesse

#35 lore raw
In reply to Matt Mackall
Quoted 10 lines · Matt Mackall
Quoted 6 lines

so i think the two concepts could nicely co-exist: in-source annotations help us maintain the popularity list, -ffunction-sections allows us to reorder at link time. In fact such a kernel could be shipped in 'unlinked' state, and could be relinked based on per-system profiling data. As long as we have KALLSYMS, it's not even a big debuggability issue.

I'm still not sure about in-source annotations for popularity. My suspicion is that it's just too workload-dependent, and a given author's workload will likely be biased towards their code.

in-source annotations can do more:

- inlines could be driven by profile data: if a function is used in a hot path and it's used only once, it makes sense to inline that function into that hot path - because the kernel size increase will be in the cold portion.

- we could drive the likely/unlikely annotations via profiling data.

OTOH i think that _most_ of the benefit (80% :-) could be achieved via the much simpler (and more robust) link-time-reordering solution. It is also alot less intrusive, and can still be presented in some plain-text format that can be distributed along the upstream kernel:

linux/profiles/webserver.list
linux/profiles/database-server.list
linux/profiles/desktop.list
linux/profiles/beowulf-node.list

and users could pick their profile at build time / relink time. There is no binary compatibility problem with such plaintext lists - they dont have to be fully complete, nor do they have to be fully accurate - they dont impact correctness in any way. In fact profiles could merge all architectures into one file, so they would be pretty generic as well.

Ingo

#36 lore raw
In reply to Linus Torvalds
Quoted 8 lines · Linus Torvalds
Quoted 5 lines · Martin Bligh

There are tools already around to do this sort of thing as well - "profile directed optimization" or whatever they called it. Seems to be fairly commonly done with userspace, but not with the kernel. I'm not sure why not ... possibly because it's not available for gcc ?

.. and they are totally useless.

[snip]

Quoted 10 lines

A kernel that people recompile themselves simply isn't something where it works.

What _would_ work is something that actually CHECKS (and suggests) the hints we already have in the kernel. IOW, you could have an automated test-bed that runs some reasonable load, and then verifies whether there are branches that go only one way that could be annotated as such, or whether some annotation is wrong.

Quoted 5 lines

That way the "profile data" actually follows the source code, and is thus actually relevant to an open-source project. Because we do _not_ start having specially optimized binaries. That's against the whole point of being open source and trying to get users to get more deeply involved with the project.

This is exactly what I am thinking for quite some time (for my userspace projects).

I would really want to see some program in gcc package that takes source code and some profile results (maybe even multiple profile results from many different environments and systems under different loads) and tries to suggest some annotations for the code like

- __fastpath,
- likely/unlikely,
- inline (normal for performance reasons not some forced inline because code breaks if not inlined - this could be marked __always_inline)
- maybe something for small loops on fastpath
- possibly some detection of dead code - if some part of code is never or nearly never executed it should be double checked for 1. is it still needed? 2. bugs - because if it never executes it is probably not tested enough,

and so on. It also should warn if it finds annotations already in the code that don't match profile results (especially if it differs greatly).

It could also try to check possible inline scenarios using some heuristics and searches. Something like "Ok, if I will inline this function and this --- will it improve things [== reduce code size for example] because some things will become constants?" This is probably not possible to do at compile time because it will make normal compiles much longer. But it could be run from time to time or continously on some automated testing farm and then generate reports for programmer to add or remove some annotations (and why and how certain the report is about some annotation). This way the (not only) linux kernel problem with inlines will be solved once and for ever.

Also I think that "profile driven optimizations" like currently in gcc are evil because the profile is most often biased and incomplete (for example the one used in gcc compile itself). Also it can make debuging strange problems (that can be caused by buggy compiler) much harder because everyone can have completly different binary code generated by their compiler because completly different profile was used. This way reproducing the bug by developer is much harder if not nearly impossible.

And gcc (like any other compiler) can have some bug that will cause it to make some completly stupid decision in some cases making program much slower. This can't be investigated without looking directly at assembler code for several hours and this is not what human programmers should be doing probably. And if we will be using such "hinter" and it will have some bug and will tell us that something is likely while it is clearly not we could easily invwstigate - the whole process becomes transparent and could be well managed.

Unfortunatelly I don't know gcc good enough to add such code to it. But I will hapily help by testing and reporting bugs if someone will want to write such code.... ;-)

Grzegorz Kulewski