Opened 10 months ago

Closed 10 months ago

Last modified 5 months ago

#7267 closed change (fixed)

Optimize memory layout of filter domain maps in matcher

Reported by: mjethani Assignee: mjethani
Priority: P2 Milestone:
Module: Core Keywords:
Cc: Blocked By:
Blocking: #7000 Platform: Unknown / Cross platform
Ready: yes Confidential: no
Tester: Ross Verified working: yes
Review URL(s):

https://codereview.adblockplus.org/30001564/

Description (last modified by mjethani)

Background

In #7265 we started organizing request blocking filters by domain in lib/matcher.js. We made an optimization: if a domain has only one filter that applies to the domain, we reduce Map { "foo" => Map { "example.com" => Map { filter => true } } } to Map { "foo" => Map { "example.com" => filter } }. This optimization reduced the memory requirements for EasyList by ~10 MB.

Now we can take this a step further:

  1. Out of ~19,000 blocking filters in EasyList that end up in the _filterDomainMapsByKeyword data structure, ~18,000 are pure generic filters that are the only entries for their respective keywords. For such filters, we can reduce the nesting by one more level. In other words, we can reduce Map { "foo" => Map { "" => Map { filter => true } } } all the way to Map { "foo" => filter }.
  2. When a filter is removed, we can similarly readjust the data structure to minimize memory usage. For example, in Map { "foo" => Map { "" => Map { filter => true, filter => true } } }, if one of the filters is removed, the new structure should be Map { "foo" => filter }.

This change reduces the memory footprint of the extension by a further ~5 MB (EasyList only).

What to change

The changes as described above, in lib/matcher.js, in the add and remove methods of the Matcher class.

Also see patch.

Hints for testers

Same as #7265.

Change History (7)

comment:1 Changed 10 months ago by mjethani

  • Description modified (diff)
  • Owner set to mjethani
  • Priority changed from Unknown to P2
  • Ready set
  • Review URL(s) modified (diff)

comment:2 Changed 10 months ago by mjethani

  • Blocking 7000 added

comment:3 Changed 10 months ago by mjethani

  • Status changed from new to reviewing

comment:4 Changed 10 months ago by abpbot

comment:5 Changed 10 months ago by mjethani

  • Description modified (diff)
  • Resolution set to fixed
  • Status changed from reviewing to closed

comment:6 Changed 10 months ago by mjethani

This changed caused a regression. I have filed #7312.

comment:7 Changed 5 months ago by Ross

  • Tester changed from Unknown to Ross
  • Verified working set

Done. Working as described in #7265.

ABP 0.9.15.2340
Microsoft Edge 44.17763.1.0 / Windows 10 1809

ABP 3.5.2.2340
Chrome 49.0.2623.75 / Windows 10 1809
Chrome 75.0.3770.142 / Windows 10 1809
Opera 36.0.2130.65 / Windows 10 1809
Opera 62.0.3331.72 / Windows 10 1809
Firefox 51.0 / Windows 10 1809
Firefox 68.0 / Windows 10 1809
Firefox Mobile 68.0 / Android 7.2.2

Note: See TracTickets for help on using tickets.