Avoid Set object for filters with only one subscription

[mjethani]

Background

Out of ~82,000 filters in the default subscriptions, only 7 filters belong to more than one subscription. We're maintaining a Set object for each of the filters, with all but 7 of them having only one entry. Each such Set object has a shallow size of 32 bytes and retained size of 152 bytes in memory.

If we simply keep a direct reference to the single Subscription object rather than adding the object to a Set instance, this would save at least 2.5 MB. In my tests, this technique saves more than 12 MB on the JS heap (which is >21% of the initial used heap).

Because the subscriptions property of the Filter class is public, it is hard to do this cleanly without first modifying the API to access the subscriptions to better encapsulate the internals. It would be ideal never to expose the internal data structure, be it a Set.<Subscription> object or a direct reference to the single Subscription object, but rather expose it via a clean read-only API, such as a subscriptions ​generator.

What to change

Add the following APIs to the Filter class:

1. function* subscriptions(): Yields Subscription objects
2. function addSubscription(subscription): Adds a Subscription object to the filter
3. function removeSubscription(subscription): Removes a Subscription object from the filter

Make the above APIs operate on an internal _subscriptions property, the type of which may be Subscription? (no subscriptions or a single subscription) or Set.<Subscription> (multiple subscriptions). addSubscription and removeSubscription should move from a direct reference to a Set object and back based on the number of subscriptions.

Throughout lib/* and test/*, update the code to use these new APIs instead of the current subscriptions property.

Things to consider

In addition to the initial memory footprint after the default subscriptions have been loaded, the performance of the loading of subscriptions from disk should also be measured. In theory a direct assignment should be faster than the creation of a Set object containing one entry, but there may be unintended consequences of the API changes.

Integration notes

After changeset ​ba63e1a22903, the subscriptions property of the Filter class has been replaced by a subscriptions generator method (yields Subscription objects), addSubscription and removeSubscription methods, and a subscriptionCount property.

Performance impact

Based on some manual performance testing on Google Chrome 70 (Canary) on macOS 10.12.6, the changes for this memory optimization have the following impact on performance:

1. ​Iteration over the list of subscriptions for a filter appears to be ~25% slower.
2. ​Addition of the first subscription to a filter takes about same time.
3. The overall performance of the loading of subscriptions from disk is unaffected.

Hints for testers

The changes here are already covered by the unit tests.

For testing with the browser extension, try the following:

1. Prepare two filter lists with filters A, B, C, and D in the first list and filters A, C, E, and F in the second list (use any kinds of filters)
2. Subscribe to the first list and make sure filters A, B, C, and D are working
3. Subscribe to the second list and make sure filters A, B, C, D, E, and F are working
4. Unsubscribe from the first list and make sure only filters A, C, E, and F are working
5. Unsubscribe from the second list and make sure none of the filters are working
6. Subscribe to the second list again and make sure filters only filters A, C, E, and F are working
7. Subscribe to the first list again and make sure filters A, B, C, D, E, and F are working

[mjethani]

Added @sebastian and @greiner for heads-up.

[greiner]

I've created #6921 for the necessary changes to adblockplusui.

[abpbot]

A commit referencing this issue has landed:
​Issue 6916 - Encapsulate filter subscriptions

[abpbot]

A commit referencing this issue has landed:
​Issue 6916 - Avoid Set object for filters with only one subscription

[sebastian]

Just an idea, how about removing the reference from filter to subscription altogether? Under which circumstances, do we have a filter and need to know which subscription(s) it belongs to? If it's not a highly common case, I suppose we could just iterate through the subscriptions and see which subscriptions includes this filter.

[mjethani]

Replying to sebastian:

Just an idea, how about removing the reference from filter to subscription altogether? Under which circumstances, do we have a filter and need to know which subscription(s) it belongs to? If it's not a highly common case, I suppose we could just iterate through the subscriptions and see which subscriptions includes this filter.

I have filed #7029.

[Ross]

Done. Unit tests are passing and example using subscriptions above is working as described.

ABP 3.3.2.2175
Firefox 62 / 51 / Windows 10
Chrome 69 / 49 / Windows 10
Opera 56 / 36 / Windows 10