Situation: the Firefox immunization slows down Firefox noticable.

Suspected: the algorithm used in Firefox to look up entries in the hosts file could be linear or otherwise not very performant.

Task: write a test application that simulates N lookups inside the blacklist files (assuming one website does, including pictures, have to look up various urls; maybe N = 50?). Once using linear lookup, once using an optimized search trie. Use a hostperm.1 size of M = 25000 entries.
Determine difference in lookup speed.

When finished: go through Firefox source, find out how Firefox looks up this table, and if it is just linear, propose to use an optimized blacklist lookup.

Test results so far:
00:00.063 Blacklist created.
00:01.922 Trie built from blacklist.
00:05.109 10 pages with 50 URLs each look up, linear method.
00:00.031 10 pages with 50 URLs each look up, using Aho-Corasick.Example parameters:
average length of domain in blacklist: 20 characters
number of domains in blacklist: 25000
number of domains to look up per page: 50
number of pages tested: 10
That I repeated the test 10 times was more or less to even see a number in the Aho Corasick test.
The test itself clearly shows that even if the Trie was to be rebuilt for each page, it would work more than twice as fast. In fact though, it has to be built only once, on application start, and then only if the hostperm.1 file has been changed. In real browsing, an Aho-Corasick lookup would be more than 100 times faster than a linear lookup.

Now, before we can put this information to use, I have to download the Firefox source and find out which algorithm they use (if it really is a slow linear lookup as could be suspected by comparing these numbers to the FF slowdown) ;)

With the current sourcecode tarball offering 220 MB of code, I think someone knowing the Firefox code should look this up, for someone not knowing it, it probably would take days (the file "hostperm.1" seems only referenced in the profile migration and cookie extensions).