Opened 5 months ago

Closed 4 months ago

Last modified 4 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: Unknown Verified working: no
Review URL(s):

Description (last modified by mjethani)


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 { "" => Map { filter => true } } } to Map { "foo" => Map { "" => 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 (6)

comment:1 Changed 5 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 5 months ago by mjethani

  • Blocking 7000 added

comment:3 Changed 5 months ago by mjethani

  • Status changed from new to reviewing

comment:4 Changed 5 months ago by abpbot

comment:5 Changed 4 months ago by mjethani

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

comment:6 Changed 4 months ago by mjethani

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

Note: See TracTickets for help on using tickets.