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

[SR-11767] IDE completion tests have quadratic performance #54174

davezarzycki opened this issue Nov 12, 2019 · 8 comments

[SR-11767] IDE completion tests have quadratic performance #54174

davezarzycki opened this issue Nov 12, 2019 · 8 comments


Copy link

@davezarzycki davezarzycki commented Nov 12, 2019

Previous ID SR-11767
Radar rdar://problem/57135446
Original Reporter @davezarzycki
Type Bug
Status Resolved
Resolution Done
Additional Detail from JIRA
Votes 0
Component/s CodeCompletion
Labels Bug, Performance
Assignee None
Priority Medium

md5: 916052869301b0c69a030ac96fb056bb

Issue Description:

If I'm reading the trace results of `perf` (on Linux) correctly, the IDE completion test cases have quadratic performance. The problem seems to be that nothing caches where the line breaks are in a source file, so every time a line+column pair is translated back to a source location, the source file is rescanned. This is especially true if the line+column lookup fails and `None` is returned. The code also doesn't even call `memchr()` to find the next newline (`memchr` is vector optimized, at least on Linux).

Copy link

@beccadax beccadax commented Nov 13, 2019

@swift-ci create

Copy link

@benlangmuir benlangmuir commented Nov 13, 2019

Hey DaveZ! Could you show us an example of a trace exhibiting this behaviour? I'm not clear where you're seeing the repeated conversions from line+column to offset. I've seen offset -> line+column conversions show up in traces before, but never line+column -> offset, and never in code-completion. The only such translation I can think of for code-completion would be for the `-pos=N:M` command-line argument to the invocation of sourcekitd-test.

Copy link
Collaborator Author

@davezarzycki davezarzycki commented Nov 14, 2019

From perf record/report of the slowest IDE test (complete_value_expr.swift):

Samples: 116K of event 'cycles:u', Event count (approx.): 68330844611, DSO: swift-ide-test
  Overhead  Command         Symbol
-   23.32%  swift-ide-test  [.] swift::SourceManager::resolveFromLineCol                                                                                                         ◆
   - 23.32% swift::SourceManager::resolveFromLineCol                                                                                                                             ▒
        swift::SourceManager::getLocFromExternalSource                                                                                                                           ▒
        swift::Decl::calculateSerializedLocs                                                                                                                                     ▒
      - swift::Decl::getLoc                                                                                                                                                      ▒
         - 23.32% llvm::function_ref<bool (swift::ValueDecl*)>::callback_fn<swift::TypeChecker::resolveDeclRefExpr(swift::UnresolvedDeclRefExpr*, swift::DeclContext*)::$_2>     ▒
              findNonMembers                                                                                                                                                     ▒
            - swift::TypeChecker::resolveDeclRefExpr                                                                                                                             ▒
               - 23.32% swift::TypeChecker::getTypeOfCompletionOperator                                                                                                          ▒
                    swift::getTypeOfCompletionOperator                                                                                                                           ▒
                    (anonymous namespace)::CodeCompletionCallbacksImpl::doneParsing                                                                                              ▒
                    swift::Parser::performCodeCompletionSecondPassImpl                                                                                                           ▒
                    swift::Parser::performCodeCompletionSecondPass                                                                                                               ▒
                    swift::CompilerInstance::parseAndCheckTypesUpTo                                                                                                              ▒
                    swift::CompilerInstance::performSemaUpTo                                                                                                                     ▒
                    main                                                                                                                                                         ▒
                    __libc_start_main                                                                                                                                            ▒
                    0x495641000025db3d                                                                                                                                           ▒
               + 0.00% (anonymous namespace)::PreCheckExpression::walkToExprPre                                                                                                  ▒
         + 0.00% swift::TypeChecker::applyUnboundGenericArguments                                                                                                                ▒
   + 0.00% swift::SourceManager::getLocFromExternalSource                                                                                                                        ▒
+    3.08%  swift-ide-test  [.] llvm::DenseMapBase<llvm::DenseMap<std::__1::pair<swift::Type, void*>, swift::DependentMemberType*, llvm::DenseMapInfo<std::__1::pair<swift::Type,▒
+    2.71%  swift-ide-test  [.] swift::GenericSignatureBuilder::maybeResolveEquivalenceClass                                                                                     ▒
+    1.76%  swift-ide-test  [.] swift::GenericSignatureBuilder::PotentialArchetype::updateNestedTypeForConformance                                                               ▒
+    1.25%  swift-ide-test  [.] swift::DependentMemberType::get                                                                                                                  ▒
+    0.72%  swift-ide-test  [.] swift::AssociatedTypeDecl::getOverriddenDecls                                                                                                    ▒

And the busy code scanning for newlines:

       │     for (; Line && (Ptr < End); ++Ptr) {
       │       dec    %edx
       │       setne  %r8b
       │       mov    %r9,%rax
       │       cmp    %r10,%r9
       │     → jae    31506b0 <swift::SourceManager::resolveFromLineCol(unsigned int, unsigned int, unsigned int) const+0xa0>
       │       test   %edx,%edx
       │     → je     31506b0 <swift::SourceManager::resolveFromLineCol(unsigned int, unsigned int, unsigned int) const+0xa0>
       │       lea    0x1(%r9),%rsi
       │       mov    %r9,%rax
       │       nop
       │     if (*Ptr == '\n') {
 12.80 │       xor    %edi,%edi
 10.45 │       cmpb   $0xa,-0x1(%rsi)
  7.90 │       sete   %dil
 13.20 │       cmove  %rsi,%rax
       │     for (; Line && (Ptr < End); ++Ptr) {
 13.46 │       sub    %edi,%edx
 12.24 │       setne  %r8b
  7.35 │       cmp    %r10,%rsi
       │     → jae    31506b0 <swift::SourceManager::resolveFromLineCol(unsigned int, unsigned int, unsigned int) const+0xa0>
  7.16 │       inc    %rsi
       │       test   %edx,%edx
 15.38 │     → jne    3150690 <swift::SourceManager::resolveFromLineCol(unsigned int, unsigned int, unsigned int) const+0x80>
       │     --Line;
       │     LineStart = Ptr+1;
       │     }
       │     }

Copy link

@benlangmuir benlangmuir commented Nov 14, 2019

Thanks! This looks like it is happening in the new serialized location code proposed here

@nkcsgexi We should make sure this code is efficient in general, but is there a way for us to turn it off completely in code-completion?

Copy link

@akyrtzi akyrtzi commented Nov 14, 2019

@nkcsgexi how about storing the utf8 byte offset instead of line:column, so we don't have to pay the cost of resolving all these line:column locations.

Copy link

@nkcsgexi nkcsgexi commented Nov 14, 2019

Talked with @akyrtzi more about this, we could set `IgnoreSwiftSourceInfo = true` for all code completion invocation. Probably even for all sourcekitd invocations?

Copy link

@akyrtzi akyrtzi commented Nov 14, 2019

It's probably useful to have them available for locations in the emitted diagnostics (live issues).

Copy link

@akyrtzi akyrtzi commented Jan 13, 2020

@nathawes has completely disabled serialized location functionality for code-completion please verify with using latest snapshots from master or swift-5.2 branch.

@swift-ci swift-ci transferred this issue from apple/swift-issues Apr 25, 2022
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
None yet

No branches or pull requests

5 participants