RFR: 8263131: reduce unnecessary downwards search when using linear search to find method

[Ioi Lam]

On Mon, 8 Mar 2021 19:49:47 GMT, Lois Foltan <lfoltan at openjdk.org> wrote:

> I would like to clarify your statement in the bug description that, "So there no needs to search downwards because there no other method with the same name before it since the method found is the first matched method." Actually there can be more than one entry in the array that contain the same name. Test case "TestConflictingDefaultsAndStaticMethod" in vmTestbase/vm/runtime/StaticMethodsTest.java test demonstrates a situation where an overpass method named "m" and a static method named "m" exist simultaneously in the array. See JDK-8067480 for a full explanation.
> 
> So I am concerned that we should never disable the downwards binary search through overloaded methods. Can you please run the test cases under test/hotspot/jtreg/vmTestbase/vm/runtime/defmeth?
> 
> Thanks,
> Lois

Hmm, I changed my mind about this PR. I think it shouldn't be integrated. The method array is grouped by name. When _disable_method_binary_search is true, quick_search(name) always returns the lowest index of a method with that name, so the caller of quick_search doesn't need to search downwards.

However, as I mentioned in the bug report, _disable_method_binary_search is used only when dumping the CDS archive. The reason is this:

inline int InstanceKlass::quick_search(const Array<Method*>* methods, const Symbol* name) {
  if (_disable_method_binary_search) {
    assert(DynamicDumpSharedSpaces, "must be");
    // At the final stage of dynamic dumping, the methods array may not be sorted
    // by ascending addresses of their names, so we can't use binary search anymore.
    // However, methods with the same name are still laid out consecutively inside the
    // methods array, so let's look for the first one that matches.
    return linear_search(methods, name);
  }

Performance of InstanceKlass::find_method doesn't really matter during CDS dump, and we are already paying a performance penalty by doing a linear search. And if we go into the download search loop:

  const int hit = quick_search(methods, name);
  if (hit != -1) {
    ...
    // search downwards through overloaded methods
    int i;
    for (i = hit - 1; i >= 0; --i) {
        const Method* const m = methods->at(i);
        assert(m->is_method(), "must be method");
        if (m->name() != name) {
          break;   /// <<<<<<< HERE
        }

the loop will end on its first iteration. So this PR won't save that much time anyway.

Adding this extra check will slow down our main use case (when CDS is not dumping) where performance is important. It also makes the code harder to understand. So I think we shouldn't do it.

-------------

PR: https://git.openjdk.java.net/jdk/pull/2857