Hi Ingo,
On Mon, 2013-11-04 at 08:36 +0100, Ingo Molnar wrote:
> * Davidlohr Bueso <davidlohr@xxxxxx> wrote:
>
> > I will look into doing the vma cache per thread instead of mm (I hadn't
> > really looked at the problem like this) as well as Ingo's suggestion on
> > the weighted LRU approach. However, having seen that we can cheaply and
> > easily reach around ~70% hit rate in a lot of workloads, makes me wonder
> > how good is good enough?
>
> So I think it all really depends on the hit/miss cost difference. It makes
> little sense to add a more complex scheme if it washes out most of the
> benefits!
>
> Also note the historic context: the _original_ mmap_cache, that I
> implemented 16 years ago, was a front-line cache to a linear list walk
> over all vmas (!).
>
> This is the relevant 2.1.37pre1 code in include/linux/mm.h:
>
> /* Look up the first VMA which satisfies addr < vm_end, NULL if none. */
> static inline struct vm_area_struct * find_vma(struct mm_struct * mm, unsigned long addr)
> {
> struct vm_area_struct *vma = NULL;
>
> if (mm) {
> /* Check the cache first. */
> vma = mm->mmap_cache;
> if(!vma || (vma->vm_end <= addr) || (vma->vm_start > addr)) {
> vma = mm->mmap;
> while(vma && vma->vm_end <= addr)
> vma = vma->vm_next;
> mm->mmap_cache = vma;
> }
> }
> return vma;
> }
>
> See that vma->vm_next iteration? It was awful - but back then most of us
> had at most a couple of megs of RAM with just a few vmas. No RAM, no SMP,
> no worries - the mm was really simple back then.
>
> Today we have the vma rbtree, which is self-balancing and a lot faster
> than your typical linear list walk search ;-)
>
> So I'd _really_ suggest to first examine the assumptions behind the cache,
> it being named 'cache' and it having a hit rate does in itself not
> guarantee that it gives us any worthwile cost savings when put in front of
> an rbtree ...
So having mmap_cache around, in whatever form, is an important
optimization for find_vma() - even to this day. It can save us at least
50% cycles that correspond to this function. I ran a variety of
mmap_cache alternatives over two workloads that are heavy on page faults
(as opposed to Java based ones I had tried previously, which really
don't trigger enough for it to be worthwhile). So we now have a
comparison of 5 different caching schemes -- note that the 4 element
hash table is quite similar to two elements, with a hash function of
(addr % hash_size).
1) Kernel build
+------------------------+----------+------------------+---------+
| mmap_cache type | hit-rate | cycles (billion) | stddev |
+------------------------+----------+------------------+---------+
| no mmap_cache | - | 15.85 | 0.10066 |
| current mmap_cache | 72.32% | 11.03 | 0.01155 |
| mmap_cache+largest VMA | 84.55% | 9.91 | 0.01414 |
| 4 element hash table | 78.38% | 10.52 | 0.01155 |
| per-thread mmap_cache | 78.84% | 10.69 | 0.01325 |
+------------------------+----------+------------------+---------+
In this particular workload the proposed patch benefits the most and
current alternatives, while they do help some, aren't really worth
bothering with as the current implementation already does a nice enough
job.
2) Oracle Data mining (4K pages)
+------------------------+----------+------------------+---------+
| mmap_cache type | hit-rate | cycles (billion) | stddev |
+------------------------+----------+------------------+---------+
| no mmap_cache | - | 63.35 | 0.20207 |
| current mmap_cache | 65.66% | 19.55 | 0.35019 |
| mmap_cache+largest VMA | 71.53% | 15.84 | 0.26764 |
| 4 element hash table | 70.75% | 15.90 | 0.25586 |
| per-thread mmap_cache | 86.42% | 11.57 | 0.29462 |
+------------------------+----------+------------------+---------+
This workload sure makes the point of how much we can benefit of caching
the vma, otherwise find_vma() can cost more than 220% extra cycles. We
clearly win here by having a per-thread cache instead of per address
space. I also tried the same workload with 2Mb hugepages and the results
are much more closer to the kernel build, but with the per-thread vma
still winning over the rest of the alternatives.
All in all I think that we should probably have a per-thread vma cache.
Please let me know if there is some other workload you'd like me to try
out. If folks agree then I can cleanup the patch and send it out.
Thanks,
Davidlohr
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@xxxxxxxxx. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@xxxxxxxxx";> email@xxxxxxxxx </a>