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

From: Andrew Cooper <andrew.cooper3@citrix.com>
To: Jan Beulich <jbeulich@suse.com>
Cc: "Stefano Stabellini" <sstabellini@kernel.org>,
	"Julien Grall" <julien@xen.org>, "Wei Liu" <wl@xen.org>,
	Xen-devel <xen-devel@lists.xenproject.org>,
	"Volodymyr Babchuk" <Volodymyr_Babchuk@epam.com>,
	"Roger Pau Monné" <roger.pau@citrix.com>
Subject: Re: [Xen-devel] [PATCH] xen/list: Remove prefetching
Date: Wed, 15 Jan 2020 12:40:19 +0000	[thread overview]
Message-ID: <436c2c07-a1a8-b5b4-5ddb-7d205ba28f3c@citrix.com> (raw)
In-Reply-To: <ad6edefe-a295-d00b-179b-c95efc5f34b0@suse.com>

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