Skip to content

GitLab

  • Projects
  • Groups
  • Snippets
  • Help
    • Loading...
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
    • Contribute to GitLab
  • Sign in / Register
Knot DNS
Knot DNS
  • Project overview
    • Project overview
    • Details
    • Activity
    • Releases
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
  • Issues 22
    • Issues 22
    • List
    • Boards
    • Labels
    • Service Desk
    • Milestones
  • Merge Requests 17
    • Merge Requests 17
  • CI / CD
    • CI / CD
    • Pipelines
    • Jobs
    • Schedules
  • Operations
    • Operations
    • Incidents
    • Environments
  • Packages & Registries
    • Packages & Registries
    • Container Registry
  • Analytics
    • Analytics
    • CI / CD
    • Repository
    • Value Stream
  • Wiki
    • Wiki
  • Snippets
    • Snippets
  • Members
    • Members
  • Collapse sidebar
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
  • Knot projects
  • Knot DNSKnot DNS
  • Merge Requests
  • !574

Closed
Opened Aug 10, 2016 by Vladimír Čunát@vcunatMaintainer
  • Report abuse
Report abuse

QP trie

  • Overview 4
  • Commits 1
  • Changes 8

It's probably better to read just the total diff instead of the individual commits. Maybe it will be best to squash.

Highlights

  • Switchability: currently the tries are used through hat-trie API, and the implementations can be switched by a define.
  • Portability: the code focuses on x86_64, also performance-wise; details are in code: 1 2. Running make check without -DNDEBUG on every platform should be enough to check for related problems.
  • Licensing: I used copyright usual for the rest of knot. The original qp sources were almost all rewritten and they were under CC0 anyway.
  • Simplicity: I'm not convinced qp-trie is significantly simpler than hat-trie if disregarding dependence on hash tables, but I tried hard to make the code understandable and to explain in comments a lot.
  • Speed (UPDATED): I haven't done much benchmarking yet, as our infrastructure seems to be currently suffering from some new bottleneck anyway. Still, it seems that dnssec queries got a little faster and non-dnssec a little slower, i.e. it seems to move closer to NSD speed. (I think the name lookup speed could be improved significantly, but that would be for another time and lookup takes typically only 5–10% of total time anyway, IIRC.) The ddns test shows significant speedup on updating large zones, measuring roughly halved time in comparison to master (the parent commit). Startup time is shown unchanged (measured in the memory tests).
  • Memory (NEW & UPDATED): there seem to be huge savings if the zones are small – in the hosting-100k scenario the total RSS of knot drops to 28 % of original and 37 % with dnssec. I re-tried each in another round to guard against random mistakes, as I didn't know the tries themselves were taking such a large relative portion of all memory. However, with large zones the memory requirements seem to grow slightly by ~1–2 % with the current malloc() implementation we use. (I tried with tcmalloc, causing memory usage to drop by ~ 15 % and the slight difference between QP and HAT gets reversed.)
  • Testing (UPDATED): ./tests-extra/runtests.py is OK on x86_64. Jenkins seems OK, and basic testing on a big-endian machine as well.
Assignee
Assign to
Reviewer
Request review from
None
Milestone
None
Assign milestone
Time tracking
Reference: knot/knot-dns!574
Source branch: trie-qp