Skip to contentSkip to conversation

[2.6] [2/2] hlist: remove IFs from hlist functions

PATCH Andi Kleen 2 participants 5 messages Feb 11, 2004 – Feb 12, 2004 3 messages not in the archive

lore
Share & tools
lore

Andi Kleen

author
#3 lore raw
In reply to a message not in the archive
Quoted 13 lines · Alex Pankratov
Quoted 11 lines · Stephen Hemminger

+++ linux-2.6.2.hlist/lib/list.c 2004-02-10 13:03:08.000000000 -0800

Review line 7

Quoted 8 lines
(quoted diff) +7 -0
@@ -0,0 +1,10 @@
+#include <linux/module.h>
+#include <linux/list.h>
+
+/*
+ *    shared tail sentinel for hlists
+ */
+struct hlist_node hlist_null;

Could this be const?

Quoted 1 line

No, because its 'pprev' field *is* getting modified.

I didn't notice this before, sorry. But this could end up being a scalability problem on big SMP systems. Even though the cache line of this is never read it will bounce all the time between all CPUs using hlists and add considerably latency and cross node traffic. Remember Linux is supposed to run well on 128 CPU machines now.

Maybe you can make it UP only, but I'm still not sure it's worth it.

-Andi

#4 lore raw
Quoted 9 lines · Andi Kleen
Quoted 2 lines · Alex Pankratov

No, because its 'pprev' field *is* getting modified.

I didn't notice this before, sorry. But this could end up being a scalability problem on big SMP systems. Even though the cache line of this is never read it will bounce all the
time between all CPUs using hlists and add considerably latency and cross node traffic. Remember Linux is supposed to run well on 128 CPU machines now.

That's a bit above my head. How does this potential latency compare to the speed up due to not having CMPs ? My cycle counting skills are a bit dusty :)

Quoted 3 lines

Maybe you can make it UP only, but I'm still not sure it's worth it.

Sorry, I didn't the 'UP' part.

author
#5 lore raw
Quoted 15 lines · On Wed, 11 Feb 2004 08:48:44 -0800 Alex Pankratov <[email protected]> wrote:
Quoted 11 lines · Andi Kleen
Quoted 2 lines · Alex Pankratov

No, because its 'pprev' field *is* getting modified.

I didn't notice this before, sorry. But this could end up being a scalability problem on big SMP systems. Even though the cache line of this is never read it will bounce all the time between all CPUs using hlists and add considerably latency and cross node traffic. Remember Linux is supposed to run well on 128 CPU machines now.

Quoted 3 lines

That's a bit above my head. How does this potential latency compare to the speed up due to not having CMPs ? My cycle counting skills are a bit dusty :)

A full cache miss is extremly costly on a modern Gigahertz+ CPU because memory and busses are far slower than the CPU core. As a rule of thumb 1000+ cycles. An CMP is extremly cheap (a few cycles at worst), the only thing that could be more expensive is an mispredicted conditional jump triggered by the CMP. But even that would be at best a few tens of cycles. If everything is mispredicted which should be common it's extremly fast (a few cycles only)

In addition on a big multiprocessor machine bouncing cache lines between CPUs is costly because it adds load to the interconnect.

One way to avoid the possible mispredicted jump would be to reorganize the code that the compiler can use CMOV. The issue is that on x86 CMOV cannot do a conditional store to memory, so it has to use something like

	unsigned long *target = realtarget;
	unsigned long dummy;
	if (condfalse) 
		target = &dummy;     /* <---- can be converted to CMOV */
	*target = dummy;

(gcc should do that on its own, but it doesn't). I'm not really sure it's practical to do that for the CMP here and if it's even worth it.

Most likely the hlist loops are dominated by cache misses in walking the nodes anyways.

Quoted 7 lines
Quoted 5 lines

Maybe you can make it UP only, but I'm still not sure it's worth it.

Sorry, I didn't the 'UP' part.

Uniprocessor = !CONFIG_SMP with an #ifdef.

-Andi

author
#6 lore raw
Quoted 7 lines · On Sat, 14 Feb 2004 19:59:49 +0100 Andi Kleen <[email protected]> wrote:

A full cache miss is extremly costly on a modern Gigahertz+ CPU because memory and busses are far slower than the CPU core. As a rule of thumb 1000+ cycles. An CMP is extremly cheap (a few cycles at worst), the only thing that could be more expensive is an mispredicted conditional jump triggered by the CMP. But even that would be at best a few tens of cycles. If everything is mispredicted which should be common it's extremly fast

^^^^^^^^^^^^^
predicted of course

-Andi

#7 lore raw
In reply to Andi Kleen
Quoted 8 lines · Andi Kleen
Quoted 1 line · On Wed, 11 Feb 2004 08:48:44 -0800 Alex Pankratov <[email protected]> wrote:

Andi Kleen wrote:

A full cache miss is extremly costly on a modern Gigahertz+ CPU because memory and busses are far slower than the CPU core...

[snip]

Thanks for the summary, I did some background reading, you're 100% right of course. Ignore the patch. Thanks again.

Alex