[Xen-devel] [PATCH] xen/list: Remove prefetching

Andrew Cooper posted 1 patch 36 weeks ago
Patches applied successfully (tree, apply log)
git fetch https://github.com/patchew-project/xen tags/patchew/20200114203545.8897-1-andrew.cooper3@citrix.com
xen/include/xen/list.h | 46 +++++++++++++---------------------------------
1 file changed, 13 insertions(+), 33 deletions(-)

[Xen-devel] [PATCH] xen/list: Remove prefetching

Posted by Andrew Cooper 36 weeks ago
Xen inherited its list infrastructure from Linux.  One area where has fallen
behind is that of prefetching, which as it turns out is a performance penalty
in most cases.

Prefetch of NULL on x86 is now widely measured to have glacial performance
properties, and will unconditionally hit on every hlist use due to the
termination condition.

Cross-port the following Linux patches:

  75d65a425c (2011) "hlist: remove software prefetching in hlist iterators"
  e66eed651f (2011) "list: remove prefetching from regular list iterators"
  c0d15cc7ee (2013) "linked-list: Remove __list_for_each"

to Xen, which results in the following net diffstat on x86:

  add/remove: 0/1 grow/shrink: 27/83 up/down: 576/-1648 (-1072)

(The code additions comes from a few now-inlined functions, and slightly
different basic block padding.)

No functional change.

Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
---
CC: Jan Beulich <JBeulich@suse.com>
CC: Wei Liu <wl@xen.org>
CC: Roger Pau Monné <roger.pau@citrix.com>
CC: Stefano Stabellini <sstabellini@kernel.org>
CC: Julien Grall <julien@xen.org>
CC: Volodymyr Babchuk <Volodymyr_Babchuk@epam.com>
---
 xen/include/xen/list.h | 46 +++++++++++++---------------------------------
 1 file changed, 13 insertions(+), 33 deletions(-)

diff --git a/xen/include/xen/list.h b/xen/include/xen/list.h
index 1387abb211..dc5a8c461b 100644
--- a/xen/include/xen/list.h
+++ b/xen/include/xen/list.h
@@ -42,9 +42,6 @@ struct list_head {
 #define LIST_HEAD_READ_MOSTLY(name) \
     struct list_head __read_mostly name = LIST_HEAD_INIT(name)
 
-/* Do not move this ahead of the struct list_head definition! */
-#include <xen/prefetch.h>
-
 static inline void INIT_LIST_HEAD(struct list_head *list)
 {
     list->next = list;
@@ -455,20 +452,6 @@ static inline void list_splice_init(struct list_head *list,
  * @head:    the head for your list.
  */
 #define list_for_each(pos, head)                                        \
-    for (pos = (head)->next; prefetch(pos->next), pos != (head);        \
-         pos = pos->next)
-
-/**
- * __list_for_each - iterate over a list
- * @pos:    the &struct list_head to use as a loop cursor.
- * @head:   the head for your list.
- *
- * This variant differs from list_for_each() in that it's the
- * simplest possible list iteration code, no prefetching is done.
- * Use this for code that knows the list to be very short (empty
- * or 1 entry) most of the time.
- */
-#define __list_for_each(pos, head)                              \
     for (pos = (head)->next; pos != (head); pos = pos->next)
 
 /**
@@ -477,8 +460,7 @@ static inline void list_splice_init(struct list_head *list,
  * @head:   the head for your list.
  */
 #define list_for_each_prev(pos, head)                                   \
-    for (pos = (head)->prev; prefetch(pos->prev), pos != (head);        \
-         pos = pos->prev)
+    for (pos = (head)->prev; pos != (head); pos = pos->prev)
 
 /**
  * list_for_each_safe - iterate over a list safe against removal of list entry
@@ -509,7 +491,7 @@ static inline void list_splice_init(struct list_head *list,
  */
 #define list_for_each_entry(pos, head, member)                          \
     for (pos = list_entry((head)->next, typeof(*pos), member);          \
-         prefetch(pos->member.next), &pos->member != (head);            \
+         &pos->member != (head);                                        \
          pos = list_entry(pos->member.next, typeof(*pos), member))
 
 /**
@@ -520,7 +502,7 @@ static inline void list_splice_init(struct list_head *list,
  */
 #define list_for_each_entry_reverse(pos, head, member)                  \
     for (pos = list_entry((head)->prev, typeof(*pos), member);          \
-         prefetch(pos->member.prev), &pos->member != (head);            \
+         &pos->member != (head);                                        \
          pos = list_entry(pos->member.prev, typeof(*pos), member))
 
 /**
@@ -547,7 +529,7 @@ static inline void list_splice_init(struct list_head *list,
  */
 #define list_for_each_entry_continue(pos, head, member)                 \
     for (pos = list_entry(pos->member.next, typeof(*pos), member);      \
-         prefetch(pos->member.next), &pos->member != (head);            \
+         &pos->member != (head);                                        \
          pos = list_entry(pos->member.next, typeof(*pos), member))
 
 /**
@@ -560,7 +542,7 @@ static inline void list_splice_init(struct list_head *list,
  * Iterate over list of given type, continuing from current position.
  */
 #define list_for_each_entry_from(pos, head, member)                     \
-    for (; prefetch(pos->member.next), &pos->member != (head);          \
+    for (; &pos->member != (head);                                      \
          pos = list_entry(pos->member.next, typeof(*pos), member))
 
 /**
@@ -635,7 +617,7 @@ static inline void list_splice_init(struct list_head *list,
  */
 #define list_for_each_rcu(pos, head)                            \
     for (pos = (head)->next;                                    \
-         prefetch(rcu_dereference(pos)->next), pos != (head);   \
+         rcu_dereference(pos) != (head);                        \
          pos = pos->next)
 
 #define __list_for_each_rcu(pos, head)          \
@@ -672,8 +654,7 @@ static inline void list_splice_init(struct list_head *list,
  */
 #define list_for_each_entry_rcu(pos, head, member)                      \
     for (pos = list_entry((head)->next, typeof(*pos), member);          \
-         prefetch(rcu_dereference(pos)->member.next),                   \
-         &pos->member != (head);                                        \
+         &rcu_dereference(pos)->member != (head);                       \
          pos = list_entry(pos->member.next, typeof(*pos), member))
 
 /**
@@ -689,7 +670,7 @@ static inline void list_splice_init(struct list_head *list,
  */
 #define list_for_each_continue_rcu(pos, head)                           \
     for ((pos) = (pos)->next;                                           \
-         prefetch(rcu_dereference((pos))->next), (pos) != (head);       \
+         rcu_dereference(pos) != (head);                                \
          (pos) = (pos)->next)
 
 /*
@@ -918,8 +899,7 @@ static inline void hlist_add_after_rcu(struct hlist_node *prev,
 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
 
 #define hlist_for_each(pos, head)                                       \
-    for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; });     \
-         pos = pos->next)
+    for (pos = (head)->first; pos; pos = pos->next)
 
 #define hlist_for_each_safe(pos, n, head)                       \
     for (pos = (head)->first; pos && ({ n = pos->next; 1; });   \
@@ -934,7 +914,7 @@ static inline void hlist_add_after_rcu(struct hlist_node *prev,
  */
 #define hlist_for_each_entry(tpos, pos, head, member)                   \
     for (pos = (head)->first;                                           \
-         pos && ({ prefetch(pos->next); 1;}) &&                         \
+         pos &&                                                         \
          ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});       \
          pos = pos->next)
 
@@ -947,7 +927,7 @@ static inline void hlist_add_after_rcu(struct hlist_node *prev,
  */
 #define hlist_for_each_entry_continue(tpos, pos, member)                \
     for (pos = (pos)->next;                                             \
-         pos && ({ prefetch(pos->next); 1;}) &&                         \
+         pos &&                                                         \
          ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});       \
          pos = pos->next)
 
@@ -959,7 +939,7 @@ static inline void hlist_add_after_rcu(struct hlist_node *prev,
  * @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 (; pos &&                                                       \
          ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});       \
          pos = pos->next)
 
@@ -992,7 +972,7 @@ static inline void hlist_add_after_rcu(struct hlist_node *prev,
  */
 #define hlist_for_each_entry_rcu(tpos, pos, head, member)               \
      for (pos = (head)->first;                                          \
-          rcu_dereference(pos) && ({ prefetch(pos->next); 1;}) &&       \
+          rcu_dereference(pos) &&                                       \
           ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});      \
           pos = pos->next)
 
-- 
2.11.0


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

Re: [Xen-devel] [PATCH] xen/list: Remove prefetching

Posted by Jan Beulich 36 weeks ago
On 14.01.2020 21:35, Andrew Cooper wrote:
> Xen inherited its list infrastructure from Linux.  One area where has fallen
> behind is that of prefetching, which as it turns out is a performance penalty
> in most cases.
> 
> Prefetch of NULL on x86 is now widely measured to have glacial performance
> properties, and will unconditionally hit on every hlist use due to the
> termination condition.
> 
> Cross-port the following Linux patches:
> 
>   75d65a425c (2011) "hlist: remove software prefetching in hlist iterators"
>   e66eed651f (2011) "list: remove prefetching from regular list iterators"
>   c0d15cc7ee (2013) "linked-list: Remove __list_for_each"

Just as an observation (not an objection), the 2nd of these says
"normally the downsides are bigger than the upsides", which makes
it unbelievably clear what these supposed downsides are. I can
accept prefetches through NULL to be harmful. I can also accept
prefetches on single entry lists to not be very useful. But does
this also render them useless on long lists with not overly much
cache churn done by the body of the iteration loop? Wouldn't it
at least be worthwhile to have list_for_each_prefetch() retaining
prior behavior, and use it in places where prefetching can be
deemed to help?

Jan

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

Re: [Xen-devel] [PATCH] xen/list: Remove prefetching

Posted by Andrew Cooper 36 weeks ago
On 15/01/2020 11:17, Jan Beulich wrote:
> On 14.01.2020 21:35, Andrew Cooper wrote:
>> Xen inherited its list infrastructure from Linux.  One area where has fallen
>> behind is that of prefetching, which as it turns out is a performance penalty
>> in most cases.
>>
>> Prefetch of NULL on x86 is now widely measured to have glacial performance
>> properties, and will unconditionally hit on every hlist use due to the
>> termination condition.
>>
>> Cross-port the following Linux patches:
>>
>>   75d65a425c (2011) "hlist: remove software prefetching in hlist iterators"
>>   e66eed651f (2011) "list: remove prefetching from regular list iterators"
>>   c0d15cc7ee (2013) "linked-list: Remove __list_for_each"
> Just as an observation (not an objection), the 2nd of these says
> "normally the downsides are bigger than the upsides", which makes
> it unbelievably clear what these supposed downsides are. I can
> accept prefetches through NULL to be harmful. I can also accept
> prefetches on single entry lists to not be very useful. But does
> this also render them useless on long lists with not overly much
> cache churn done by the body of the iteration loop?

Yes.

Prefetch is only useful when you're making an access which none of the
hardware prefetchers can predict, and that the costs (extra instruction,
L1 cache perturbance, and tying up the pagewalker for a while) are
outweighed by the perf improvement from not stalling against the access.

A programmer cannot figure this out by just looking at the C.  The
details are micro-architectural, and based on rare and unpredictable
data access patterns.  (Incorrectly) tying up the pagewalker early can
be far more detrimental to performance than to have forward speculation
pull it in at the next time that there is available micro-architectural
resource to do so.

> Wouldn't it
> at least be worthwhile to have list_for_each_prefetch() retaining
> prior behavior, and use it in places where prefetching can be
> deemed to help?

No, I don't think so.  The repetitive pattern of a loop is easy for
hardware to spot.

The cases where prefetching helps in practice are the one-off totally
unpredictable accesses which are suddenly going to block all other
instructions in flight, *and* you are not going to incur a TLB miss in
the short term.

This is why I made the prefetch() suggestion for your svm_load_segs()
code.  The memory operand is used once per context switch, so very
likely to have fallen out of the cache and TLB, and VMLOAD is
microcoded, so a stalling black box as far as forward speculation goes. 
As the code leading up to it is operating in hot TLB mappings, the
pagewalker is free ahead of time to complete the fill.

There are cases where prefetch() really makes a difference, but they are
rare and the hardware vendors have already optimised the common data
access patterns in programs.

It is also highly telling that in nearly a decade, Linux still hasn't
found a case warranting the re-introduction of prefetches on the loop
entry metadata.

Of course, if someone does find a case, we can reconsider, but I doubt
it will ever come up, and misuse of such a list iterator can easily do
more damage than good.

~Andrew

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

Re: [Xen-devel] [PATCH] xen/list: Remove prefetching

Posted by Roger Pau Monné 36 weeks ago
On Tue, Jan 14, 2020 at 08:35:45PM +0000, Andrew Cooper wrote:
> Xen inherited its list infrastructure from Linux.  One area where has fallen
> behind is that of prefetching, which as it turns out is a performance penalty
> in most cases.
> 
> Prefetch of NULL on x86 is now widely measured to have glacial performance
> properties, and will unconditionally hit on every hlist use due to the
> termination condition.
> 
> Cross-port the following Linux patches:
> 
>   75d65a425c (2011) "hlist: remove software prefetching in hlist iterators"
>   e66eed651f (2011) "list: remove prefetching from regular list iterators"
>   c0d15cc7ee (2013) "linked-list: Remove __list_for_each"
> 
> to Xen, which results in the following net diffstat on x86:
> 
>   add/remove: 0/1 grow/shrink: 27/83 up/down: 576/-1648 (-1072)
> 
> (The code additions comes from a few now-inlined functions, and slightly
> different basic block padding.)
> 
> No functional change.
> 
> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>

Reviewed-by: Roger Pau Monné <roger.pau@citrix.com>

Has this gone through some XenRT performance testing to assert there
are not regressions performance wise?

Thanks, Roger.

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

Re: [Xen-devel] [PATCH] xen/list: Remove prefetching

Posted by Andrew Cooper 36 weeks ago
On 15/01/2020 10:39, Roger Pau Monné wrote:
> On Tue, Jan 14, 2020 at 08:35:45PM +0000, Andrew Cooper wrote:
>> Xen inherited its list infrastructure from Linux.  One area where has fallen
>> behind is that of prefetching, which as it turns out is a performance penalty
>> in most cases.
>>
>> Prefetch of NULL on x86 is now widely measured to have glacial performance
>> properties, and will unconditionally hit on every hlist use due to the
>> termination condition.
>>
>> Cross-port the following Linux patches:
>>
>>   75d65a425c (2011) "hlist: remove software prefetching in hlist iterators"
>>   e66eed651f (2011) "list: remove prefetching from regular list iterators"
>>   c0d15cc7ee (2013) "linked-list: Remove __list_for_each"
>>
>> to Xen, which results in the following net diffstat on x86:
>>
>>   add/remove: 0/1 grow/shrink: 27/83 up/down: 576/-1648 (-1072)
>>
>> (The code additions comes from a few now-inlined functions, and slightly
>> different basic block padding.)
>>
>> No functional change.
>>
>> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
> Reviewed-by: Roger Pau Monné <roger.pau@citrix.com>
>
> Has this gone through some XenRT performance testing to assert there
> are not regressions performance wise?

No.  The Linux measurements are still valid observations.

~Andrew

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

Re: [Xen-devel] [PATCH] xen/list: Remove prefetching

Posted by Julien Grall 36 weeks ago

On 14/01/2020 20:35, Andrew Cooper wrote:
> Xen inherited its list infrastructure from Linux.  One area where has fallen
> behind is that of prefetching, which as it turns out is a performance penalty
> in most cases.
> 
> Prefetch of NULL on x86 is now widely measured to have glacial performance
> properties, and will unconditionally hit on every hlist use due to the
> termination condition.
> 
> Cross-port the following Linux patches:
> 
>    75d65a425c (2011) "hlist: remove software prefetching in hlist iterators"
>    e66eed651f (2011) "list: remove prefetching from regular list iterators"
>    c0d15cc7ee (2013) "linked-list: Remove __list_for_each"
> 
> to Xen, which results in the following net diffstat on x86:
> 
>    add/remove: 0/1 grow/shrink: 27/83 up/down: 576/-1648 (-1072)
> 
> (The code additions comes from a few now-inlined functions, and slightly
> different basic block padding.)
> 
> No functional change.
> 
> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>

Acked-by: Julien Grall <julien@xen.org>

Cheers,

-- 
Julien Grall

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel