In the course of what finally is a major effort at rewriting MMC for multiple promotions, i found a small optimization left for current MMC version.
It is simple to explain : when i know that there is no more better element in the chain, i should stop searching.
I always wanted to implement it but failed up to now, producing some missed opportunities in the pack. This is now correctly solved, with a trick called "early end".
Here are some results :
Calgary 64K Searches 5.54M 5.52M
Firefox 64K Searches 41.9M 41.8M
Enwik8 64K Searches 187M 186M
Calgary 512K Searches 10.9M 10.9M
Firefox 512K Searches 92.1M 91.7M
Enwik8 512K Searches 434M 432M
Calgary 4M Searches 14.2M 14.2M
Firefox 4M Searches 182M 181M
Enwik8 4M Searches 751M 749M
Benefits are disappointingly low.
There must be an explanation though. If there is no possible better opportunity, we are quite likely near the end of the chain anyway, if not already at its end. With these results, it seems this was already the case most of the time.
The only good news is that this small benefit comes at no cost at all.