Skip to content
  • Igor Kushnir's avatar
    Path::operator==: compare segments in reverse order · b13d377c
    Igor Kushnir authored
    Initially this comparison optimization was implemented in
    ProjectFileDataProvider::projectClosing(). Milian suggested moving the
    logic into Path::operator== to speed up Path comparison everywhere.
    
    The current item removal algorithm in
    ProjectFileDataProvider::projectClosing() works perfectly for a single
    project or for several not very large projects. But when there is at
    least one huge project (such as WebKit) and many small projects opened
    at the same time, closing even a tiny project requires iterating over
    all files and comparing each item's projectPath to the path of the
    project that is being closed, which takes a long time if the project
    directories are located in a common parent directory.
    
    Comparing Path segments in reverse order is much faster in this case,
    because project directory names are compared first. The comparison
    practically always ends no later than at the last Path segments (now
    checked first). That's because the project directory names of two
    projects are almost never equal as KDevelop doesn't support opening two
    projects with the same name (BUG 210562). And when the paths are equal,
    Path::operator== returns right away, because in practice all
    ProjectFile::projectPath objects share QVector data with constant
    IProject::path().
    
    For example, consider closing many projects at KDevelop exit, the last
    two of which are WebKit with almost 320 thousand files and kdevelop with
    a little more than 67 thousand files. Without this commit closing a
    project (that may even contain less than a thousand files) located in
    the same directory as WebKit and kdevelop, takes 47 ms on average if its
    files precede the WebKit's files in m_projectFiles and 27 ms on average
    otherwise. Closing a project that has a projectPath with a number of
    segments unequal to that of WebKit and kdevelop takes just 1 ms, because
    QVector::operator== returns early if the container sizes are different.
    Closing the penultimate WebKit project takes 67 ms on average.
    
    At this commit the 47 ms and 27 ms cited above turn into 3.6 ms. The
    1 ms case is unaffected by this optimization. The 67 ms turn into 59 ms.
    
    I have attempted an alternative optimization of projectClosing(), with
    which closing any small project took just 1 ms - several times less than
    at this commit. The idea was to store const IProject* project instead of
    Path projectPath in ProjectFile struct. However, it is difficult to
    ensure that the pointer is not dereferenced after the project is closed
    and destroyed. Doing so requires either:
      * Increasing sizeof(ProjectFile) from 24 bytes to 32 bytes to store
        both the pointer and the path or to store a QPointer. Such a change
        is likely to negatively affect performance of other functions.
      * Synchronously calling QuickOpenDataProviderBase::reset() when a
        project is closed. This has negative performance consequences if a
        project is closed, then opened again before Quick Open line edit is
        activated; or if a project is reopened.
    
    Yet another alternative optimization is to remove files from multiple
    projects in one iteration over m_projectFiles when these projects are
    closed in quick succession (this happens at KDevelop exit). But merging
    successive invocations of projectClosing() and processing them once with
    help of a timer, or introducing an IProjectController::projectsClosing()
    signal, require many code changes and are difficult to get right.
    b13d377c