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

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

[Alex Pankratov]

Part 2

--------------------

diff -NuprX dontdiff linux-2.6.2/include/linux/list.h 
linux-2.6.2.hlist/include/linux/list.h
--- linux-2.6.2/include/linux/list.h	2004-02-10 12:35:57.000000000 -0800
+++ linux-2.6.2.hlist/include/linux/list.h	2004-02-10 14:57:09.000000000 
-0800
@@ -434,10 +434,12 @@ struct hlist_node {
  	struct hlist_node *next, **pprev;
  };

-#define HLIST_HEAD_INIT { .first = NULL }
-#define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
-#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
-#define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL)
+extern struct hlist_node hlist_null; /* shared tail sentinel */
+
+#define HLIST_HEAD_INIT { .first = &hlist_null }
+#define HLIST_HEAD(name) struct hlist_head name = {  .first = &hlist_null }
+#define INIT_HLIST_HEAD(ptr) ((ptr)->first = &hlist_null)
+#define INIT_HLIST_NODE(ptr) ((ptr)->next = &hlist_null, (ptr)->pprev = 
NULL)

  static __inline__ void hlist_node_init(struct hlist_node *h)
  {
@@ -446,7 +448,7 @@ static __inline__ void hlist_node_init(s

  static __inline__ int hlist_last(const struct hlist_node *h)
  {
-	return !h->next;
+	return h->next == &hlist_null;
  }

  static __inline__ int hlist_unhashed(const struct hlist_node *h)
@@ -456,7 +458,7 @@ static __inline__ int hlist_unhashed(con

  static __inline__ int hlist_empty(const struct hlist_head *h)
  {
-	return !h->first;
+	return h->first == &hlist_null;
  }

  static __inline__ void __hlist_del(struct hlist_node *n)
@@ -464,8 +466,7 @@ static __inline__ void __hlist_del(struc
  	struct hlist_node *next = n->next;
  	struct hlist_node **pprev = n->pprev;
  	*pprev = next;
-	if (next)
-		next->pprev = pprev;
+	next->pprev = pprev;
  }

  static __inline__ void hlist_del(struct hlist_node *n)
@@ -506,8 +507,7 @@ static __inline__ void hlist_add_head(st
  {
  	struct hlist_node *first = h->first;
  	n->next = first;
-	if (first)
-		first->pprev = &n->next;
+	first->pprev = &n->next;
  	h->first = n;
  	n->pprev = &h->first;
  }
@@ -518,8 +518,7 @@ static __inline__ void hlist_add_head_rc
  	n->next = first;
  	n->pprev = &h->first;
  	smp_wmb();
-	if (first)
-		first->pprev = &n->next;
+	first->pprev = &n->next;
  	h->first = n;
  }

@@ -542,16 +541,15 @@ static __inline__ void hlist_add_after(s

  #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
  #define hlist_entry_safe(ptr, type, member) \
-	((ptr) == 0 ? NULL : container_of(ptr,type,member))
+	((ptr) == &hlist_null ? NULL : container_of(ptr,type,member))

-/* Cannot easily do prefetch unfortunately */
  #define hlist_for_each(pos, head) \
-	for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
-	     pos = pos->next)
+	for (pos = (head)->first, prefetch(pos->next); pos != &hlist_null; \
+	     pos = pos->next, prefetch(pos->next))

  #define hlist_for_each_safe(pos, n, head) \
-	for (pos = (head)->first; n = pos ? pos->next : 0, pos; \
-	     pos = n)
+	for (pos = (head)->first, n = pos->next; pos != &hlist_null; \
+	     pos = n, n = pos->next)

  /**
   * hlist_for_each_entry	- iterate over list of given type
@@ -561,10 +559,10 @@ static __inline__ void hlist_add_after(s
   * @member:	the name of the hlist_node within the struct.
   */
  #define hlist_for_each_entry(tpos, pos, head, member)			 \
-	for (pos = (head)->first;					 \
-	     pos && ({ prefetch(pos->next); 1;}) &&			 \
+	for (pos = (head)->first, prefetch(pos->next);			 \
+	     pos != &hlist_null &&					 \
  		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
-	     pos = pos->next)
+	     pos = pos->next, prefetch(pos->next))

  /**
   * hlist_for_each_entry_continue - iterate over a hlist continuing 
after existing point
@@ -573,10 +571,10 @@ static __inline__ void hlist_add_after(s
   * @member:	the name of the hlist_node within the struct.
   */
  #define hlist_for_each_entry_continue(tpos, pos, member)		 \
-	for (pos = (pos)->next;						 \
-	     pos && ({ prefetch(pos->next); 1;}) &&			 \
+	for (pos = (pos)->next, prefetch(pos->next);			 \
+	     pos != &hlist_null &&					 \
  		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
-	     pos = pos->next)
+	     pos = pos->next, prefetch(pos->next))

  /**
   * hlist_for_each_entry_from - iterate over a hlist continuing from 
existing point
@@ -585,9 +583,10 @@ static __inline__ void hlist_add_after(s
   * @member:	the name of the hlist_node within the struct.
   */
  #define hlist_for_each_entry_from(tpos, pos, member)			 \
-	for (; pos && ({ prefetch(pos->next); 1;}) &&			 \
+	for (prefetch(pos->next); 					 \
+		pos != &hlist_null &&					 \
  		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
-	     pos = pos->next)
+	     pos = pos->next, prefetch(pos->next))

  /**
   * hlist_for_each_entry_safe - iterate over list of given type safe 
against removal of list entry
@@ -598,10 +597,10 @@ static __inline__ void hlist_add_after(s
   * @member:	the name of the hlist_node within the struct.
   */
  #define hlist_for_each_entry_safe(tpos, pos, n, head, member) 		 \
-	for (pos = (head)->first;					 \
-	     pos && ({ n = pos->next; 1; }) && 				 \
+	for (pos = (head)->first, n = pos->next;			 \
+	     pos != &hlist_null && 					 \
  		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
-	     pos = n)
+	     pos = n, n = pos->next)
  #else
  #warning "don't include kernel headers in userspace"
  #endif /* __KERNEL__ */
diff -NuprX dontdiff linux-2.6.2/lib/Makefile linux-2.6.2.hlist/lib/Makefile
--- linux-2.6.2/lib/Makefile	2004-02-03 19:43:07.000000000 -0800
+++ linux-2.6.2.hlist/lib/Makefile	2004-02-10 13:03:23.000000000 -0800
@@ -6,7 +6,7 @@
  lib-y := errno.o ctype.o string.o vsprintf.o cmdline.o \
  	 bust_spinlocks.o rbtree.o radix-tree.o dump_stack.o \
  	 kobject.o idr.o div64.o parser.o int_sqrt.o mask.o \
-	 bitmap.o extable.o
+	 bitmap.o extable.o list.o

  lib-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o
  lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o
diff -NuprX dontdiff linux-2.6.2/lib/list.c linux-2.6.2.hlist/lib/list.c
--- linux-2.6.2/lib/list.c	1969-12-31 16:00:00.000000000 -0800
+++ linux-2.6.2.hlist/lib/list.c	2004-02-10 13:03:08.000000000 -0800
@@ -0,0 +1,10 @@
+#include <linux/module.h>
+#include <linux/list.h>
+
+/*
+ *	shared tail sentinel for hlists
+ */
+struct hlist_node hlist_null;
+
+EXPORT_SYMBOL(hlist_null);
+

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

[Stephen Hemminger]

  +++ linux-2.6.2.hlist/lib/list.c    2004-02-10 13:03:08.000000000 -0800
> @@ -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?

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

[Alex Pankratov]

Stephen Hemminger wrote:
>  +++ linux-2.6.2.hlist/lib/list.c    2004-02-10 13:03:08.000000000 -0800
> 
>> @@ -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?

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

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

[Andi Kleen]

Alex Pankratov <ap@swapped.cc> writes:

> Stephen Hemminger wrote:
> >  +++ linux-2.6.2.hlist/lib/list.c    2004-02-10 13:03:08.000000000 -0800
> >
> >> @@ -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?
> 
> 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

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

[Alex Pankratov]

Andi Kleen wrote:

> Alex Pankratov <ap@swapped.cc> writes:
> 
>>
>>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 :)

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

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

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

[Alex Pankratov]

Andi Kleen wrote:
> On Wed, 11 Feb 2004 08:48:44 -0800
> Alex Pankratov <ap@swapped.cc> 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

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

[Andi Kleen]

On Wed, 11 Feb 2004 08:48:44 -0800
Alex Pankratov <ap@swapped.cc> wrote:

> 
> Andi Kleen wrote:
> 
> > Alex Pankratov <ap@swapped.cc> writes:
> > 
> >>
> >>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 :)

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.

> 
> > 
> > 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

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

[Andi Kleen]

On Sat, 14 Feb 2004 19:59:49 +0100
Andi Kleen <ak@suse.de> 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