Archive for August, 2008

soc is over, khtml is not

August 25, 2008

GSoC is over for quite a while now, but that was a great time and it really helps if you want to join any open source community like KDE.

So, several days ago I was having discussion about multi-pattern search algorithm with SadEagle that could be used with adblock filtering. And I like the topic of high-performant algorithm. The same day I was reading several articles on that, the next day I was hacking on modified Rabin-Karp’s algorithm. Then I tried several more approaches, like Aho-Corasick.

A bit of testing, debugging, profiling and voila: several days after you could see the commit with numbers in it “7.6x improvement”. And us usual for practice approach (especially, with relatively short strings) algorithm shouldn’t be too complex but I enjoyed my little research anyway.

Big thanks for SadEagle, cause he did great job with it too. As well as performance improvement you could see ad block is now more compatible with adblock plus. and it supports whitelisting too.