Improve performance of the fallback path when a translation is not
found in the fast-cache.
* reduce max loading of the per-sector TT hash tables from 80% to 65%.
This reduces the number of required probes by a factor of 3.
* when searching for a translation, don't visit the sectors in a fixed
order. Instead, use an MTF array in which the most popular sectors
(in terms of most likely to hold the translation we're looking for)
are visited first. This reduces the number of required probes by
another factor of 2.
These improvements have no effect on small programs, but improve
scalability on big apps. For an application comprising 300k
translations, runtime on Memcheck is reduced by 3% and on None by
about 20%. The average number of probes per fast-cache miss is
reduced from around 22 to less than 5.
git-svn-id: svn://svn.valgrind.org/valgrind/trunk@11091 a5019735-40e9-0310-863c-91ae7b9d1cf9
2 files changed