algorithm that change a data structure without inflicting expensive cache misses

algorithm that change a data structure without inflicting expensive cache misses

[Yubin Ruan]

Hi,

This question is raised Quick Quiz 9.23 and I think it is impossible because
any changes on a data structure will inevitably inflict cache miss (on other
CPUs). The only way we can help is to make the reader *ignore* the cache miss,
or do the invalidation proactively.

I cannot think of any existing algorithm. Can anyone provide any references
(if that really exist)?

Thanks,
Yubin

Re: algorithm that change a data structure without inflicting expensive cache misses

[Paul E. McKenney]

On Sun, Oct 29, 2017 at 11:24:55AM +0800, Yubin Ruan wrote:
> Hi,
> 
> This question is raised Quick Quiz 9.23 and I think it is impossible because
> any changes on a data structure will inevitably inflict cache miss (on other
> CPUs). The only way we can help is to make the reader *ignore* the cache miss,
> or do the invalidation proactively.
> 
> I cannot think of any existing algorithm. Can anyone provide any references
> (if that really exist)?

I can give you some "trick" answers:

o	The updater changes some part of the data structure that the
	readers happen not to be referencing at the time of the update.
	But this is a bit useless in real life, because one of the
	strengths of RCU is that the updaters have no idea what the
	readers are doing, and thus don't need expensive invalidations
	just to communicate their activities to each other.

o	The updater and all the readers are hardware threads within
	a single core, and therefore share all levels of cache, so that
	there can be no communications cache misses.  This actually
	works if your workload fits into a single core, but is quite
	useless otherwise.

	With one exception.  You might shard your workload over the
	cores, so that each core deals only with its own portion of
	the data structure, again avoiding communications cache
	misses.  Assuming, of course, that you can shart your data
	in such a way as to avoid load imbalances.

o	Your workload is running on a really old parallel machine that
	doesn't have cache.  But in that case, your performance will
	be truly horrible no matter what you do -- you could easily
	outperform the entirety of one of those old machines with a
	single hardware thread of a modern system.

If you do come up with a generally useful algorithm that manages
a read-write shared data structure without cache misses, I bet a
large number of people would be very interested.  ;-)

							Thanx, Paul