Sunday, December 5, 2010

Early end optimization

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 :

                       Fusion  Early-end 
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.

No comments:

Post a Comment