[SERVER-78213] Efficient implementation of reference tracking Created: 19/Jun/23  Updated: 13/Sep/23  Resolved: 13/Sep/23

Status: Closed
Project: Core Server
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Task Priority: Major - P3
Reporter: Timour Katchaounov Assignee: Timour Katchaounov
Resolution: Won't Fix Votes: 0
Labels: M1
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Attachments: File matt-useMap-as-vector.diff     File s-78213-efficient-ref-track-useMap-as-bitset.v1.diff    
Sprint: QO 2023-09-04, QO 2023-09-18
Participants:

 Description   

Reference tracking is one of the major reasons for slower performance of Bonsai vs classic. There are several complimentary ways to approach this problem:

  • Reduce the number of call to functions that use reference tracking (for instance to constant folding).
  • Reduce the number of calls to reference tracking.
  • Make reference tracking faster by itself.

This task is about the latter approach. The main reason why reference tracking is slow is the use of hash-maps and hash-sets, therefore this task is about analysis of the existing code, and replacing hash-based data structures with a custom-designed and more efficient data structures. Since the most efficient way to operate on sets of objects known to us is via bitsets, this is what we will focus on.



 Comments   
Comment by Timour Katchaounov [ 13/Sep/23 ]

This ticket will be implemented by several individual tickets. Currently these are SERVER-80953, and SERVER-80954, but there may be more.

Comment by Timour Katchaounov [ 03/Aug/23 ]

There is a branch with current work on this improvement: https://github.com/10gen/mongo/tree/s-78213-efficient-ref-track

  • As of August 3, 2023:
  • Commit 2a512a55478e442ddd425169b9e6802847a66939 contains a complete set of changes that replace 'useMap' with a better structure, and result in ~25% improvement on a relatively complex query.
  • Subsequent changes are unfinished work in progress that replace 'defs' and 'nodeDefs' with a vector which will be later used to generate the final map.
Generated at Thu Feb 08 06:37:45 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.