Re: [Xen-devel] [PATCH] xen/list: Remove prefetching
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
On 15/01/2020 10:39, Roger Pau Monné wrote: > On Tue, Jan 14, 2020 at 08:35:45PM +, 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 > Reviewed-by: Roger Pau Monné > > 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
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
On Tue, Jan 14, 2020 at 08:35:45PM +, 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 Reviewed-by: Roger Pau Monné 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
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 Acked-by: Julien Grall Cheers, -- Julien Grall ___ Xen-devel mailing list Xen-devel@lists.xenproject.org https://lists.xenproject.org/mailman/listinfo/xen-devel