Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8230162

ScopeImpl.remove() has O(N) performance

    XMLWordPrintable

    Details

    • Type: Enhancement
    • Status: Resolved
    • Priority: P4
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 14
    • Component/s: tools
    • Labels:
      None
    • Resolved In Build:
      b18

      Description

      ScopeImpl.remove(Symbol) performs an O(N) removal of the given symbol from the list of siblings in the same scope. Currently, the algorithm (essentially) uses a singly-linked hash set, which has O(1) insertion, O(1) lookup, and O(N) removal.

      This can be improved to O(1) by changing the Entry data structure to a doubly-linked hash set. In this case, the previous entry can be accessed directly from the entry to be removed.

      For github.com/google/dagger usage in one of Google's larger projects, we measured a 33.2 second improvement (28%) in annotation processing time (14% overall) on average.

        Attachments

          Activity

            People

            Assignee:
            jlahoda Jan Lahoda
            Reporter:
            ronsh Ron Shapiro
            Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

              Dates

              Created:
              Updated:
              Resolved: