klassVTable::initialize_vtable exhibits quadratic time complexity

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).