Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

use maps for rule search, add benchmark #302

Open
wants to merge 1 commit into
base: main
Choose a base branch
from

Conversation

gugu
Copy link

@gugu gugu commented Aug 11, 2022

Problem:

There are 9000 rules and to check domain validity we need to iterate over them. It is hard to use map because we need to search by substring, performance O(domainsCount * ruleCount)

Solution:

  1. Added benchmark.js checks to get observability
  2. During module load we process punySuffix for every domain. It is a very cheap operation O(ruleCount)
  3. During module load we create a map suffix => [rule1, rule2, ..], which usually has 1 element O(ruleCount)
  4. During search we split the domain by dots and search in the map. O(1)

E.g. for mysubdomain.google.co.uk:

  1. search rule map for mysubdomain.google.co.uk => nothing
  2. search rule map for google.co.uk => nothing
  3. searching rule map for .co.uk => found
  4. returting rule for .co.uk

Fixes #301

@gugu gugu changed the title use maps for rule search, add benchmark use maps for rule search, add benchmark, fixes #301 Aug 11, 2022
@gugu gugu changed the title use maps for rule search, add benchmark, fixes #301 use maps for rule search, add benchmark Aug 11, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Performance issues - iterating over 9k rules for every domain
1 participant