Brave ad-blocker gives 69x better performance with its new engine written in Rust

Looks like Brave has also jumped on the bandwagon of writing or rewriting its components in the Rust programming language. Yesterday, its team announced that they have reimplemented its ad-blocker in Rust that was previously written in C++. As a result, the ad-blocker is now 69x faster as compared to the current engine.

The team chose Rust as it is a memory-safe and performant language. The new ad-blocker implementation can be compiled to native code and run within the native browser core. It can also be packaged in a standalone Node.js module. This reimplemented version is available on Brave’s Dev channel and Nightly channel.

How does this new ad-blocking algorithm work?

The previous ad-blocking algorithm relied on the observation that most of the requests were passed through without blocking. It used the Bloom filter data structure that tracks fragments of requests that may match and rules out those that do not.

The new implementation is based on uBlock Origin and Ghostery’s ad-blocking approach, which is tokenization specific to add-block rule matching against URLs and rule evaluation optimized to the different kinds of rules.

What makes this new algorithm faster is that it quickly eliminates any rules that are not likely to match a request from search. “To organize filters in a way that speeds up their matching, we observe that any alphanumeric (letters and numbers) substring that is part of a filter needs to be contained in any matching URL as well,” the team explained.

All these substrings are hashed to a single number that results in a number of tokens. The tokens make matching much easier and faster when a URL is tokenized in the same way. The team further wrote, “Even though by nature of hashing algorithms multiple different strings could hash to the same number (a hash collision), we use them to limit rule evaluation to only those that could possibly match.” If a rule has a specific hostname, it is tokenized too. If a rule contains a single domain option, the entire domain is hashed as another token.

Performance gains made by the reimplementation

For the performance evaluation, the team has used the dataset published with the Ghostery ad-blocker performance study that includes 242,945 requests across 500 popular websites. The new ad-blocker was tested against this dataset with different ad-block rule lists including the biggest one: EasyList and EasyPrivacy combined.

The team performed all the benchmarks on the adblock-rust 0.1.21 library. They used a 2018 MacBook Pro laptop with 2.6 GHz Intel Core i7 CPU and 32GB RAM.

Following are performance gains this new ad-blocker showed:

The new algorithm with its optimized set of rules is 69x faster on average as compared to the current engine.

When tested with the popular filter list combination of EasyList and EasyPrivacy, it gave a “class-leading performance of spending only 5.7μs on average per request.”

It already supports most of the filter rule syntax that has evolved beyond the original specification. This will enable the team to handle web compatibility issues better and faster.

The browser does some of the work that can be helpful to the ad-blocker. This further reduces the overheads resulting in an ad-blocker with the best in class performance.