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 -- To unsubscribe from this list: send the line "unsubscribe perfbook" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
