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

Jump to bottom

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

Closed
davezarzycki opened this issue Nov 12, 2019 · 8 comments
Closed

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

davezarzycki opened this issue Nov 12, 2019 · 8 comments
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. code completion Area → source tooling: code completion performance source tooling Area: IDE support, SourceKit, and other source tooling

Comments

@davezarzycki
Copy link
Collaborator

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).
@beccadax
Copy link
Contributor

@swift-ci create

@benlangmuir
Copy link
Member

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.

@davezarzycki
Copy link
Collaborator Author

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;
       │     }
       │     }

@benlangmuir
Copy link
Member

Thanks! This looks like it is happening in the new serialized location code proposed here https://forums.swift.org/t/proposal-emitting-source-information-file-during-compilation/28794.

@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?

@akyrtzi
Copy link
Member

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.

@nkcsgexi
Copy link
Member

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

@akyrtzi
Copy link
Member

akyrtzi commented Nov 14, 2019

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

@akyrtzi
Copy link
Member

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
@AnthonyLatsis AnthonyLatsis added the source tooling Area: IDE support, SourceKit, and other source tooling label Feb 6, 2023
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. code completion Area → source tooling: code completion performance source tooling Area: IDE support, SourceKit, and other source tooling
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
6 participants
@akyrtzi @beccadax @davezarzycki @nkcsgexi @benlangmuir @AnthonyLatsis