jump label: Reduce the cycle count by changing the link order

In the course of testing jump labels for use with the CFS bandwidth controller, Paul Turner, discovered that using jump labels reduced the branch count and the instruction count, but did not reduce the cycle count or wall time.

I noticed that having the jump_label.o included in the kernel but not used in any way still caused this increase in cycle count and wall time. Thus, I moved jump_label.o in the kernel/Makefile, thus changing the link order, and presumably moving it out of hot icache areas. This brought down the cycle count/time as expected.

In addition to Paul's testing, I've tested the patch using a single 'static_branch()' in the getppid() path, and basically running tight loops of calls to getppid(). Here are my results for the branch disabled case:

With jump labels turned on (CONFIG_JUMP_LABEL), branch disabled:

Performance counter stats for 'bash -c /tmp/getppid;true' (50 runs):

     3,969,510,217 instructions             #	   0.864 IPC     ( +-0.000% )
     4,592,334,954 cycles                     ( +-   0.046% )
       751,634,470 branches                   ( +-   0.000% )

        1.722635797  seconds time elapsed   ( +-   0.046% )

Jump labels turned off (CONFIG_JUMP_LABEL not set), branch disabled:

Performance counter stats for 'bash -c /tmp/getppid;true' (50 runs):

     4,009,611,846 instructions             #	   0.867 IPC     ( +-0.000% )
     4,622,210,580 cycles                     ( +-   0.012% )
       771,662,904 branches                   ( +-   0.000% )

        1.734341454  seconds time elapsed   ( +-   0.022% )

---
 kernel/Makefile |    3 ++-
 1 files changed, 2 insertions(+), 1 deletions(-)

index 2d64cfc..329dfcc 100644
@@ -10,7 +10,7 @@ obj-y     = sched.o fork.o exec_domain.o panic.o printk.o \
 	    kthread.o wait.o kfifo.o sys_ni.o posix-cpu-timers.o mutex.o \
 	    hrtimer.o rwsem.o nsproxy.o srcu.o semaphore.o \
 	    notifier.o ksysfs.o pm_qos_params.o sched_clock.o cred.o \
-	    async.o range.o jump_label.o
+	    async.o range.o
 obj-y += groups.o
 
 ifdef CONFIG_FUNCTION_TRACER

@@ -107,6 +107,7 @@ obj-$(CONFIG_PERF_EVENTS) += events/
 obj-$(CONFIG_USER_RETURN_NOTIFIER) += user-return-notifier.o
 obj-$(CONFIG_PADATA) += padata.o
 obj-$(CONFIG_CRASH_DUMP) += crash_dump.o
+obj-$(CONFIG_JUMP_LABEL) += jump_label.o
 
 ifneq ($(CONFIG_SCHED_OMIT_FRAME_POINTER),y)
 # According to Alan Modra <[email protected]>, the -fno-omit-frame-pointer is

1.7.5.4

Those numbers don't seem to be pre/post patch, but merely CONFIG_JUMP_LABEL=y/n so they don't tell us what the patch does.

Anyway, should we put a comment in the Makefile telling us we should keep jump_label.o last?

Also, pjt mentioned on IRC that mucking about with link order is something google is not unfamiliar with.. could we use some sort of runtime feedback to generate linker layout maps or so? That seems like a more scalable version than randomly mucking about with Makefiles :-)

I have some numbers to support this:

[
Key:

npo_XXX = with CONFIG_JUMP_LABEL, without link order patch (no patched order) po_XXX = with CONFIG_JUMP_LABEL, with link order patch (patched order) nojl_XXX = without CONFIG_JUMP_LABEL

head is tip (c5bafb3)

Test was repeated 3 times, each run was 50 repeats w/ typically ~<0.1 in-test variance on reported output
]
[
Key:

npo_XXX = with CONFIG_JUMP_LABEL, without link order patch (no patched order) po_XXX = with CONFIG_JUMP_LABEL, with link order patch (patched order) nojl_XXX = without CONFIG_JUMP_LABEL

base is tip (c5bafb3)

Test was repeated 3 times, each run was 50 repeats w/ typically ~<0.1 in-test variance on reported output
]

instructions cycles
branches elapsed
---------------------------------------------------------------------------------------------------------------------
Westmere:
njl_base.1 798832892 722624737

     145375836             0.203218936
njl_base.2                  798888783 (+0.01)       746118188 (+3.25)
     145386807 (+0.01)     0.208573683 (-2.18)
njl_base.3                  798864253 (+0.00)       731537139 (+1.23)
     145382747 (+0.00)     0.204098175 (-4.28)
npo_base.1                  797033521 (-0.23)       731239359 (+1.19)
     144571358 (-0.55)     0.206910496 (-2.96)
npo_base.2                  797166434 (-0.21)       728926020 (+0.87)
     144603465 (-0.53)     0.202906392 (-4.84)
npo_base.3                  797165370 (-0.21)       725930458 (+0.46)
     144603438 (-0.53)     0.202118274 (-5.21)
po_base.1                   797019904 (-0.23)       699008145 (-3.27)
     144567652 (-0.56)     0.197272615 (-7.48)
po_base.2                   797037682 (-0.22)       705732419 (-2.34)
     144572115 (-0.55)     0.197101692 (-7.56)
po_base.3                   797079804 (-0.22)       698007668 (-3.41)
     144580964 (-0.55)     0.194871253 (-8.61)

       Barcelona:
njl_base.1                  816842028               748362637
     147462095             0.341654152
njl_base.2                  816849735 (+0.00)       748480742 (+0.02)
     147462652 (+0.00)     0.341450734 (-2.90)
njl_base.3                  816834963 (-0.00)       747083797 (-0.17)
     147460200 (-0.00)     0.340802353 (-3.09)
npo_base.1                  815068563 (-0.22)       775012690 (+3.56)
     146661357 (-0.54)     0.353797321 (+0.61)
npo_base.2                  815033261 (-0.22)       759613364 (+1.50)
     146654106 (-0.55)     0.346462671 (-1.48)
npo_base.3                  815029611 (-0.22)       762660196 (+1.91)
     146654169 (-0.55)     0.347565129 (-1.16)
po_base.1                   815026489 (-0.22)       767229109 (+2.52)
     146653376 (-0.55)     0.350241833 (-0.40)
po_base.2                   815035127 (-0.22)       770224495 (+2.92)
     146654019 (-0.55)     0.351352092 (-0.09)
po_base.3                   815109904 (-0.21)       774954096 (+3.55)
     146662020 (-0.54)     0.353505054 (+0.53)

At least on Nehalem/Westmere systems it looks worthwhile.

Without doing some sort of FDO sampling this list is always going to have junk arbitrary ordering constraints (which unfortunately extend beyond jump_label.o).

This commit being in the reflog for the file is already going to serve as evidence to that. :(

I think this is a good longer term direction, but that getting there will take a while (What are the right workloads to drive the FDO data for example?).

In the short term it's probably just worth taking since the effects aren't going away.

oops. I did record all that data, I just didn't include it :( So here it is:

jump label eanbled:

new makefile ordering:

Performance counter stats for 'bash -c /tmp/timing;true' (50 runs):

     4,578,321,415 cycles                     ( +-   0.021% )
     3,969,511,833 instructions             #      0.867 IPC     ( +-   0.000% )
       751,633,846 branches                   ( +-   0.000% )

        1.717374497  seconds time elapsed   ( +-   0.021% )

old makefile ordering:

Performance counter stats for 'bash -c /tmp/timing;true' (50 runs):

     4,623,129,746 cycles                     ( +-   0.015% )
     3,969,600,140 instructions             #      0.859 IPC     ( +-   0.000% )
       751,648,318 branches                   ( +-   0.000% )

        1.734843587  seconds time elapsed   ( +-   0.028% )

jump label disabled:

new makefile ordering:

Performance counter stats for 'bash -c /tmp/timing;true' (50 runs):

     4,620,784,202 cycles                     ( +-   0.014% )
     4,009,564,429 instructions             #      0.868 IPC     ( +-   0.000% )
       771,654,211 branches                   ( +-   0.000% )

        1.733853839  seconds time elapsed   ( +-   0.031% )

old makefile ordering:

Performance counter stats for 'bash -c /tmp/timing;true' (50 runs):

     4,623,191,826 cycles                     ( +-   0.009% )
     4,009,561,402 instructions             #      0.867 IPC     ( +-   0.000% )
       771,655,250 branches                   ( +-   0.000% )

        1.734191186  seconds time elapsed   ( +-   0.009% )

So, with jump labels enabled we get instructions and branches to fall even with the old Makefile ordering, but we don't get the corresponding fall in cycles/wall time, without the new Makefile ordering. This testing was done on a Kentsfield system.

Yes, I think that would be a good idea. I can re-post with the complete testing results and a Makefile comment, if we are ok with this change.

Agreed. Definitely a good area to research. However, until we have that done, I think this patch makes sense.

Thanks,

-Jason

Hi,

this might be a dumb question as I do not know much about that, but couldn't hot code be put in their own section ?

Thanks,
- Arnaud

Ah, but what is the hot code? The whole problem statement is finding that.

Commit-ID:  b77f0f3c1f587791aa5d9bd1b0012c9a89eb9258
Gitweb:     http://git.kernel.org/tip/b77f0f3c1f587791aa5d9bd1b0012c9a89eb9258
Author:     Jason Baron <[email protected]>
AuthorDate: Fri, 5 Aug 2011 16:40:40 -0400
Committer:  Ingo Molnar <[email protected]>
CommitDate: Fri, 5 Aug 2011 23:57:33 +0200

jump label: Reduce the cycle count by changing the link order

In the course of testing jump labels for use with the CFS bandwidth controller, Paul Turner, discovered that using jump labels reduced the branch count and the instruction count, but did not reduce the cycle count or wall time.

I noticed that having the jump_label.o included in the kernel but not used in any way still caused this increase in cycle count and wall time. Thus, I moved jump_label.o in the kernel/Makefile, thus changing the link order, and presumably moving it out of hot icache areas. This brought down the cycle count/time as expected.

In addition to Paul's testing, I've tested the patch using a single 'static_branch()' in the getppid() path, and basically running tight loops of calls to getppid(). Here are my results for the branch disabled case:

With jump labels turned on (CONFIG_JUMP_LABEL), branch disabled:

Performance counter stats for 'bash -c /tmp/getppid;true' (50 runs):

     3,969,510,217 instructions             #	   0.864 IPC     ( +-0.000% )
     4,592,334,954 cycles                     ( +-   0.046% )
       751,634,470 branches                   ( +-   0.000% )

        1.722635797  seconds time elapsed   ( +-   0.046% )

Jump labels turned off (CONFIG_JUMP_LABEL not set), branch disabled:

Performance counter stats for 'bash -c /tmp/getppid;true' (50 runs):

     4,009,611,846 instructions             #	   0.867 IPC     ( +-0.000% )
     4,622,210,580 cycles                     ( +-   0.012% )
       771,662,904 branches                   ( +-   0.000% )

        1.734341454  seconds time elapsed   ( +-   0.022% )

---
 kernel/Makefile |    3 ++-
 1 files changed, 2 insertions(+), 1 deletions(-)

index d06467f..eca595e 100644
@@ -10,7 +10,7 @@ obj-y     = sched.o fork.o exec_domain.o panic.o printk.o \
 	    kthread.o wait.o kfifo.o sys_ni.o posix-cpu-timers.o mutex.o \
 	    hrtimer.o rwsem.o nsproxy.o srcu.o semaphore.o \
 	    notifier.o ksysfs.o pm_qos_params.o sched_clock.o cred.o \
-	    async.o range.o jump_label.o
+	    async.o range.o
 obj-y += groups.o
 
 ifdef CONFIG_FUNCTION_TRACER

@@ -107,6 +107,7 @@ obj-$(CONFIG_PERF_EVENTS) += events/
 obj-$(CONFIG_USER_RETURN_NOTIFIER) += user-return-notifier.o
 obj-$(CONFIG_PADATA) += padata.o
 obj-$(CONFIG_CRASH_DUMP) += crash_dump.o
+obj-$(CONFIG_JUMP_LABEL) += jump_label.o
 
 ifneq ($(CONFIG_SCHED_OMIT_FRAME_POINTER),y)
 # According to Alan Modra <[email protected]>, the -fno-omit-frame-pointer is