In the end, i finally completed a new version of

*SecFull*, an aggressive implementation which tries to promote all characters it meets during its travel across the different levels. The changes required the capability to "move back" by one level, since in some cases, chains were broken and needed repair.

A much simpler version was produced in the process, called

*Sec1*. It just tries to promote the last seen character, and only when a valid gateway is confirmed. This ensures that the changes are minimal and well located, keeping all the rest of the code unmodified.

Complexity difference between Sec1 and SecFull is quite large, and therefore it is not so clear which one will bring better benefit.

Anyway, it is now possible to compare. All search algorithms generate exactly the same references, resulting in the same output. Therefore, all changes affect only the speed of searches.

As usual, let's just start by a simple counter of comparisons :

__Nb of comparisons - Window Search 64K :__File | NoSec | Sec1 | SecFull |

Calgary | 4.87M | 4.31M | 3.70M |

Firefox | 35.2M | 31.2M | 25.7M |

Enwik8 | 166.M | 139.M | 121.M |

__Window Search 512K :__File | NoSec | Sec1 | SecFull |

Calgary | 9.31M | 7.94M | 6.32M |

Firefox | 78.2M | 67.3M | 52.9M |

Enwik8 | 370.M | 285.M | 238.M |

__Window Search 4M :__File | NoSec | Sec1 | SecFull |

Calgary | 12.0M | 10.2M | 7.95M |

Firefox | 161.M | 141.M | 114.M |

Enwik8 | 619.M | 472.M | 357.M |

That's for comparisons. Now, what about speed ?

Surely, the less number of comparisons, the better the speed ?

Well, yes, approximately; but we also have to take in consideration code complexity. If each search is "more costly", then the total may end up being slower.

As can be guessed, Sec 1 is more complex than NoSec, and SecFull is the most complex of all. So, does it pay back ? Here are some results :

__Speed - Window Search 64K :__File | NoSec | Sec1 | SecFull |

Calgary | 32.8 MB/s | 31.5 MB/s | 32.0 MB/s |

Firefox | 40.5 MB/s | 38.9 MB/s | 40.0 MB/s |

Enwik8 | 30.8 MB/s | 29.9 MB/s | 30.1 MB/s |

__Window Search 512K :__File | NoSec | Sec1 | SecFull |

Calgary | 16.6 MB/s | 16.9 MB/s | 17.9 MB/s |

Firefox | 19.4 MB/s | 18.6 MB/s | 19.9 MB/s |

Enwik8 | 13.0 MB/s | 13.2 MB/s | 14.7 MB/s |

__Window Search 4M :__File | NoSec | Sec1 | SecFull |

Calgary | 6.5 MB/s | 6.8 MB/s | 8.1 MB/s |

Firefox | 2.3 MB/s | 2.4 MB/s | 2.7 MB/s |

Enwik8 | 1.9 MB/s | 2.4 MB/s | 3.0 MB/s |

Time for some serious thinking.

Even with less comparisons, the new algorithms are not guaranteed to be faster. This is especially true at 64K, where all Secondary algorithm fail to produce any gain, even though the number of comparisons is well reduced.

We need larger search buffer to make Secondary promotions worthwhile. And this is reached as soon as 512K, and then growing with search size.

Actually, SecFull seems to win over Sec1 in each and every circumstance. So it can be preferred.

But to be fair, results are a bit disappointing. The very large difference in comparison loops would make us believe that the benefit could be larger. But in the end, it is still relatively mild.

No ground-breaking progress this time...

## No comments:

## Post a Comment