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

klassVTable::initialize_vtable exhibits quadratic time complexity

    Details

      Description

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

      There was a suspicion the HS classloader exhibits quadratic time complexity.
      The profile shows the hot call tree sub-branch here:

        57.991 (66%) InstanceKlass::initialize_impl(instanceKlassHandle,Thread*)
        57.991 (66%) InstanceKlass::link_class_impl(instanceKlassHandle,bool,Thread*)
        50.015 (57%) klassVtable::initialize_vtable(bool,Thread*)
        49.995 (57%) klassVtable::update_inherited_vtable(InstanceKlass*,methodHandle,int,int,bool,Thread*)

      This is what happens. InstanceKlass::link_class_impl calls klassVTable::initialize_vtable:

       if (!this_k()->is_shared()) {
              ResourceMark rm(THREAD);
              this_k->vtable()->initialize_vtable(true, CHECK_false);
              this_k->itable()->initialize_itable(true, CHECK_false);
            }

      klassVTable::initialize_vtable calls klassVtable::update_inherited_vtable for each method:

          // Check each of this class's methods against super;
          // if override, replace in copy of super vtable, otherwise append to end
          for (int i = 0; i < len; i++) {
            // update_inherited_vtable can stop for gc - ensure using handles
            HandleMark hm(THREAD);
            assert(methods->at(i)->is_method(), "must be a Method*");
            methodHandle mh(THREAD, methods->at(i));

            bool needs_new_entry = update_inherited_vtable(ik(), mh, super_vtable_len, -1, checkconstraints, CHECK);
            ...
          }

      And klassVtable::update_inherited_vtable does the loop over super-class methods:

        Symbol* name = target_method()->name();
        Symbol* signature = target_method()->signature();

         ...

        Symbol* target_classname = target_klass->name();
        for(int i = 0; i < super_vtable_len; i++) {
          Method* super_method = method_at(i);
          // Check if method name matches
          if (super_method->name() == name && super_method->signature() == signature) {

      Therefore, we spend (number-of-subclass-methods)*(number-of-superclass-methods) time for classloading, which is O(n^2), and bad.

      I think we really need to start using proper hashtables/maps for storing the vtable metadata. Looking up the matching superclass method will drop the complexity of vtable construction to O(n).

        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                coleenp Coleen Phillimore
                Reporter:
                shade Aleksey Shipilev
              • Votes:
                0 Vote for this issue
                Watchers:
                4 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: