Re:Show HN: Adblock Fast
by chrisseaton on Wednesday September 09, 2015 @01:01PM
(#10192593)
So what if they aren't? I haven't read the expressions in depth but they look like on a quick glance like they could be checked in linear time. It may have a high degree of branching, but so what when you are checking a single linear path through it for each URL?
[ Parent
| on HN ]
Re:Show HN: Adblock Fast
by stygiansonic on Wednesday September 09, 2015 @01:09PM
(#10192629)
This is correct. According to this article[0], posted in another comment[1], iOS 9's content blocker regular expressions are limited to a subset of regex for which matching can be done in linear time:
"Extremely powerful, regular expressions can surprisingly be done in linear time if you use a strict set of regular expression characters through Thompson’s NFA algorithm. Safari’s Content Blocker implementation in fact imposes this strict regular expression limitation ..."
0. http://blog.appgrounds.com/content-blockers-beat-adblocking/