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

Class.getMethods() exhibits quadratic time complexity

    XMLWordPrintable

    Details

    • Type: Enhancement
    • Status: Resolved
    • Priority: P4
    • Resolution: Fixed
    • Affects Version/s: 8u20, 9
    • Fix Version/s: 9
    • Component/s: core-libs
    • Labels:

      Description

      As originally reported by Martin Buchholz here:
       http://mail.openjdk.java.net/pipermail/core-libs-dev/2014-October/029272.html

      The profile shows the hot call tree sub-branch here:

        | | +- 15.981 (18%) java.lang.Class.getMethods()
        | | | +- 15.971 (18%) java.lang.Class.privateGetPublicMethods()
        | | | | +- 15.791 (18%) java.lang.Class$MethodArray.removeByNameAndDescriptor(java.lang.reflect.Method)
        | | | | | +- 10.687 (12%) java.lang.Class$MethodArray.matchesNameAndDescriptor(java.lang.reflect.Method, java.lang.reflect.Method)
        | | | | | | +- 0.020 (0%) java.lang.reflect.Method.getParameterTypes()
        | | | | | | +- 0.010 (0%) java.lang.Object.clone()
        | | | | | +- 0.020 (0%) java.lang.Class$MethodArray.remove(int)
        | | | | +- 0.100 (0%) java.lang.Class.privateGetDeclaredMethods(boolean)
        | | | | +- 0.050 (0%) java.lang.Class.privateGetPublicMethods()
        | | | | +- 0.020 (0%) java.lang.Class$MethodArray.addAllIfNotPresent(java.lang.Class$MethodArray)

      This is what happens. Class.getMethods() ends up calling

          private Method[] privateGetPublicMethods() {
             ...

                      MethodArray supers = new MethodArray();
                      supers.addAll(c.privateGetPublicMethods());
                      // Filter out concrete implementations of any
                      // interface methods
                      for (int i = 0; i < supers.length(); i++) {
                          Method m = supers.get(i);
                          if (m != null &&
                                  !Modifier.isAbstract(m.getModifiers()) &&
                                  !m.isDefault()) {
                              inheritedMethods.removeByNameAndDescriptor(m);
                          }
                      }

             ....

             // Filter out all local methods from inherited ones
              for (int i = 0; i < methods.length(); i++) {
                  Method m = methods.get(i);
                  inheritedMethods.removeByNameAndDescriptor(m);
              }

      ...which tries to filter out the inherited methods for the current class. Unfortunately, the call to removeByNameAndDescriptor yields *another* loop of "inherited" methods:

              void removeByNameAndDescriptor(Method toRemove) {
                  for (int i = 0; i < length; i++) {
                      Method m = methods[i];
                      if (m != null && matchesNameAndDescriptor(m, toRemove)) {
                          remove(i);
                      }
                  }
              }

      ...and this yields quadratic complexity. We should try to do better lookups instead of linear searches here.

        Attachments

          Issue Links

            Activity

              People

              Assignee:
              plevart Peter Levart
              Reporter:
              shade Aleksey Shipilev
              Votes:
              0 Vote for this issue
              Watchers:
              5 Start watching this issue

                Dates

                Created:
                Updated:
                Resolved: