RFR: 8261954: Dependencies: Improve iteration over class hierarchy under context class

classic Classic list List threaded Threaded
17 messages Options
Reply | Threaded
Open this post in threaded view
|

RFR: 8261954: Dependencies: Improve iteration over class hierarchy under context class

Vladimir Ivanov-2
Simplify `ClassHierarchyWalker::find_witness_anywhere()` which iterates over class hierarchy under context class searching for witnesses.

Current implementation traverses the hierarchy in a breadth-first manner and keeps a stack-allocated array to keep a worklist.
But all the subclasses are already part of a singly linked list formed by `Klass::subklass()`/`next_sibling()`/`superklass()`.

Proposed refactoring gets rid of the explicit worklist and switches to the traversal over the linked list (encapsulated into `ClassHierarchyIterator`). It performs depth-first pre-order hierarchy traversal.

(There are some other minor refactorings applied in `ClassHierarchyWalker` along the way.)

Testing:
- [x] hs-tier1 - hs-tier8
- [x] additional verification that CHA decisions aren't affected

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

Commit messages:
 - Refactor ClassHierarchyIterator
 - Revert verification
 - Verification
 - Cleanups in ClassHierarchyWalker::is_witness()
 - Migrate ClassHierarchyWalker::find_witness_in to ClassHierarchyIterator
 - ClassHierarchyIterator

Changes: https://git.openjdk.java.net/jdk/pull/2630/files
 Webrev: https://webrevs.openjdk.java.net/?repo=jdk&pr=2630&range=00
  Issue: https://bugs.openjdk.java.net/browse/JDK-8261954
  Stats: 169 lines in 2 files changed: 64 ins; 69 del; 36 mod
  Patch: https://git.openjdk.java.net/jdk/pull/2630.diff
  Fetch: git fetch https://git.openjdk.java.net/jdk pull/2630/head:pull/2630

PR: https://git.openjdk.java.net/jdk/pull/2630
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8261954: Dependencies: Improve iteration over class hierarchy under context class

Vladimir Kozlov-2
On Thu, 18 Feb 2021 17:05:08 GMT, Vladimir Ivanov <[hidden email]> wrote:

> Simplify `ClassHierarchyWalker::find_witness_anywhere()` which iterates over class hierarchy under context class searching for witnesses.
>
> Current implementation traverses the hierarchy in a breadth-first manner and keeps a stack-allocated array to keep a worklist.
> But all the subclasses are already part of a singly linked list formed by `Klass::subklass()`/`next_sibling()`/`superklass()`.
>
> Proposed refactoring gets rid of the explicit worklist and switches to the traversal over the linked list (encapsulated into `ClassHierarchyIterator`). It performs depth-first pre-order hierarchy traversal.
>
> (There are some other minor refactorings applied in `ClassHierarchyWalker` along the way.)
>
> Testing:
> - [x] hs-tier1 - hs-tier8
> - [x] additional verification that CHA decisions aren't affected

Except `do_counts` changes seem fine to me.

src/hotspot/share/code/dependencies.cpp line 1329:

> 1327:   assert_locked_or_safepoint(Compile_lock);
> 1328:
> 1329:   bool do_counts = count_find_witness_calls();

Does count_find_witness_calls() have side effects and required to be called here in product? If not,
`do_counts` is used only for not_product code, so consider enclose it into  NOT_PRODUCT() here and where it is used.

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

PR: https://git.openjdk.java.net/jdk/pull/2630
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8261954: Dependencies: Improve iteration over class hierarchy under context class

Vladimir Ivanov-2
On Thu, 18 Feb 2021 17:53:41 GMT, Vladimir Kozlov <[hidden email]> wrote:

>> Simplify `ClassHierarchyWalker::find_witness_anywhere()` which iterates over class hierarchy under context class searching for witnesses.
>>
>> Current implementation traverses the hierarchy in a breadth-first manner and keeps a stack-allocated array to keep a worklist.
>> But all the subclasses are already part of a singly linked list formed by `Klass::subklass()`/`next_sibling()`/`superklass()`.
>>
>> Proposed refactoring gets rid of the explicit worklist and switches to the traversal over the linked list (encapsulated into `ClassHierarchyIterator`). It performs depth-first pre-order hierarchy traversal.
>>
>> (There are some other minor refactorings applied in `ClassHierarchyWalker` along the way.)
>>
>> Testing:
>> - [x] hs-tier1 - hs-tier8
>> - [x] additional verification that CHA decisions aren't affected
>
> src/hotspot/share/code/dependencies.cpp line 1329:
>
>> 1327:   assert_locked_or_safepoint(Compile_lock);
>> 1328:
>> 1329:   bool do_counts = count_find_witness_calls();
>
> Does count_find_witness_calls() have side effects and required to be called here in product? If not,
> `do_counts` is used only for not_product code, so consider enclose it into  NOT_PRODUCT() here and where it is used.

`count_find_witness_calls()` is a no-op in product binaries:
#ifndef PRODUCT
...
static bool count_find_witness_calls() {
...
#else
#define count_find_witness_calls() (0)
#endif //PRODUCT

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

PR: https://git.openjdk.java.net/jdk/pull/2630
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8261954: Dependencies: Improve iteration over class hierarchy under context class

Coleen Phillimore-3
In reply to this post by Vladimir Ivanov-2
On Thu, 18 Feb 2021 17:05:08 GMT, Vladimir Ivanov <[hidden email]> wrote:

> Simplify `ClassHierarchyWalker::find_witness_anywhere()` which iterates over class hierarchy under context class searching for witnesses.
>
> Current implementation traverses the hierarchy in a breadth-first manner and keeps a stack-allocated array to keep a worklist.
> But all the subclasses are already part of a singly linked list formed by `Klass::subklass()`/`next_sibling()`/`superklass()`.
>
> Proposed refactoring gets rid of the explicit worklist and switches to the traversal over the linked list (encapsulated into `ClassHierarchyIterator`). It performs depth-first pre-order hierarchy traversal.
>
> (There are some other minor refactorings applied in `ClassHierarchyWalker` along the way.)
>
> Testing:
> - [x] hs-tier1 - hs-tier8
> - [x] additional verification that CHA decisions aren't affected

This seems like a nice change.  Some questions.

src/hotspot/share/oops/instanceKlass.hpp line 1486:

> 1484:   }
> 1485: };
> 1486:

The _subklass and _next_sibling fields and implementation are in Klass (klass.hpp/cpp) but I always wonder why they are not in InstanceKlass (instanceKlass.hpp/cpp).  If this new class is in instanceKlass.hpp, these fields should be in the same.  If you agree, we should file an RFE and I will move them.  If the fields truly belong in klass.hpp, then this should be there too. ie. they should match.

src/hotspot/share/code/dependencies.cpp line 1345:

> 1343:     } else if (nof_impls == 1) { // unique implementor
> 1344:       assert(context_type != context_type->implementor(), "not unique");
> 1345:       context_type = InstanceKlass::cast(context_type->implementor());

There's no reason that implementor() should return Klass* rather than InstanceKlass* ? We can clean that up also later to reduce casts. (I thought I already tried to do this once).

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

Marked as reviewed by coleenp (Reviewer).

PR: https://git.openjdk.java.net/jdk/pull/2630
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8261954: Dependencies: Improve iteration over class hierarchy under context class

Vladimir Ivanov-2
On Thu, 18 Feb 2021 22:36:37 GMT, Coleen Phillimore <[hidden email]> wrote:

>> Simplify `ClassHierarchyWalker::find_witness_anywhere()` which iterates over class hierarchy under context class searching for witnesses.
>>
>> Current implementation traverses the hierarchy in a breadth-first manner and keeps a stack-allocated array to keep a worklist.
>> But all the subclasses are already part of a singly linked list formed by `Klass::subklass()`/`next_sibling()`/`superklass()`.
>>
>> Proposed refactoring gets rid of the explicit worklist and switches to the traversal over the linked list (encapsulated into `ClassHierarchyIterator`). It performs depth-first pre-order hierarchy traversal.
>>
>> (There are some other minor refactorings applied in `ClassHierarchyWalker` along the way.)
>>
>> Testing:
>> - [x] hs-tier1 - hs-tier8
>> - [x] additional verification that CHA decisions aren't affected
>
> src/hotspot/share/oops/instanceKlass.hpp line 1486:
>
>> 1484:   }
>> 1485: };
>> 1486:
>
> The _subklass and _next_sibling fields and implementation are in Klass (klass.hpp/cpp) but I always wonder why they are not in InstanceKlass (instanceKlass.hpp/cpp).  If this new class is in instanceKlass.hpp, these fields should be in the same.  If you agree, we should file an RFE and I will move them.  If the fields truly belong in klass.hpp, then this should be there too. ie. they should match.

I think it's `java.lang.Object` which complicates things. All array classes are rooted at Object, so neither `_subklass` nor  `_next_sibling` can be changed to `InstanceKlass`. I put `ClassHierarchyIterator` in `instanceKlass.hpp` primarily because it accepts only `InstanceKlass` root class. But I'm fine with putting it into `klass.hpp`.

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

PR: https://git.openjdk.java.net/jdk/pull/2630
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8261954: Dependencies: Improve iteration over class hierarchy under context class

Vladimir Ivanov-2
In reply to this post by Coleen Phillimore-3
On Thu, 18 Feb 2021 22:40:03 GMT, Coleen Phillimore <[hidden email]> wrote:

>> Simplify `ClassHierarchyWalker::find_witness_anywhere()` which iterates over class hierarchy under context class searching for witnesses.
>>
>> Current implementation traverses the hierarchy in a breadth-first manner and keeps a stack-allocated array to keep a worklist.
>> But all the subclasses are already part of a singly linked list formed by `Klass::subklass()`/`next_sibling()`/`superklass()`.
>>
>> Proposed refactoring gets rid of the explicit worklist and switches to the traversal over the linked list (encapsulated into `ClassHierarchyIterator`). It performs depth-first pre-order hierarchy traversal.
>>
>> (There are some other minor refactorings applied in `ClassHierarchyWalker` along the way.)
>>
>> Testing:
>> - [x] hs-tier1 - hs-tier8
>> - [x] additional verification that CHA decisions aren't affected
>
> src/hotspot/share/code/dependencies.cpp line 1345:
>
>> 1343:     } else if (nof_impls == 1) { // unique implementor
>> 1344:       assert(context_type != context_type->implementor(), "not unique");
>> 1345:       context_type = InstanceKlass::cast(context_type->implementor());
>
> There's no reason that implementor() should return Klass* rather than InstanceKlass* ? We can clean that up also later to reduce casts. (I thought I already tried to do this once).

Yes, I don't see a compelling reason for `implementor()` to return `Klass*` instead of `InstanceKlass*`. Would be nice to clean it up. Do you want me to file an RFE?

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

PR: https://git.openjdk.java.net/jdk/pull/2630
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8261954: Dependencies: Improve iteration over class hierarchy under context class

Coleen Phillimore-3
In reply to this post by Vladimir Ivanov-2
On Fri, 19 Feb 2021 12:00:20 GMT, Vladimir Ivanov <[hidden email]> wrote:

>> src/hotspot/share/oops/instanceKlass.hpp line 1486:
>>
>>> 1484:   }
>>> 1485: };
>>> 1486:
>>
>> The _subklass and _next_sibling fields and implementation are in Klass (klass.hpp/cpp) but I always wonder why they are not in InstanceKlass (instanceKlass.hpp/cpp).  If this new class is in instanceKlass.hpp, these fields should be in the same.  If you agree, we should file an RFE and I will move them.  If the fields truly belong in klass.hpp, then this should be there too. ie. they should match.
>
> I think it's `java.lang.Object` which complicates things. All array classes are rooted at Object, so neither `_subklass` nor  `_next_sibling` can be changed to `InstanceKlass`. I put `ClassHierarchyIterator` in `instanceKlass.hpp` primarily because it accepts only `InstanceKlass` root class. But I'm fine with putting it into `klass.hpp`.

Does the compiler dependencies use the _subklass lists for array classes?  The only other use for this is vtable reinitialization.  It is fine to leave ClassHIerarchyIterator in instanceKlass.hpp since that's how it's used in this change. I might investigate this more some later time.

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

PR: https://git.openjdk.java.net/jdk/pull/2630
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8261954: Dependencies: Improve iteration over class hierarchy under context class

Coleen Phillimore-3
In reply to this post by Vladimir Ivanov-2
On Fri, 19 Feb 2021 12:07:47 GMT, Vladimir Ivanov <[hidden email]> wrote:

>> src/hotspot/share/code/dependencies.cpp line 1345:
>>
>>> 1343:     } else if (nof_impls == 1) { // unique implementor
>>> 1344:       assert(context_type != context_type->implementor(), "not unique");
>>> 1345:       context_type = InstanceKlass::cast(context_type->implementor());
>>
>> There's no reason that implementor() should return Klass* rather than InstanceKlass* ? We can clean that up also later to reduce casts. (I thought I already tried to do this once).
>
> Yes, I don't see a compelling reason for `implementor()` to return `Klass*` instead of `InstanceKlass*`. Would be nice to clean it up. Do you want me to file an RFE?

I just filed one.  We've been trying to make metadata types more specific for years and must have missed this one.

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

PR: https://git.openjdk.java.net/jdk/pull/2630
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8261954: Dependencies: Improve iteration over class hierarchy under context class

Vladimir Ivanov-2
In reply to this post by Coleen Phillimore-3
On Fri, 19 Feb 2021 12:57:58 GMT, Coleen Phillimore <[hidden email]> wrote:

> Does the compiler dependencies use the _subklass lists for array classes?

Arrays aren't interesting in the context of CHA (which `Dependencies` implements), so they are handled only because they are encountered during hierarchy traversal under `java.lang.Object`:
  bool is_witness(Klass* k) {
    if (doing_subtype_search()) {
      return Dependencies::is_concrete_klass(k);
    } else if (!k->is_instance_klass()) {
      return false; // no methods to find in an array type
    } else {
      ...

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

PR: https://git.openjdk.java.net/jdk/pull/2630
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8261954: Dependencies: Improve iteration over class hierarchy under context class

Vladimir Ivanov-2
In reply to this post by Coleen Phillimore-3
On Thu, 18 Feb 2021 22:41:22 GMT, Coleen Phillimore <[hidden email]> wrote:

>> Simplify `ClassHierarchyWalker::find_witness_anywhere()` which iterates over class hierarchy under context class searching for witnesses.
>>
>> Current implementation traverses the hierarchy in a breadth-first manner and keeps a stack-allocated array to keep a worklist.
>> But all the subclasses are already part of a singly linked list formed by `Klass::subklass()`/`next_sibling()`/`superklass()`.
>>
>> Proposed refactoring gets rid of the explicit worklist and switches to the traversal over the linked list (encapsulated into `ClassHierarchyIterator`). It performs depth-first pre-order hierarchy traversal.
>>
>> (There are some other minor refactorings applied in `ClassHierarchyWalker` along the way.)
>>
>> Testing:
>> - [x] hs-tier1 - hs-tier8
>> - [x] additional verification that CHA decisions aren't affected
>
> This seems like a nice change.  Some questions.

Thanks for the reviews, Vladimir and Coleen.

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

PR: https://git.openjdk.java.net/jdk/pull/2630
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8261954: Dependencies: Improve iteration over class hierarchy under context class

Erik Österlund-3
In reply to this post by Vladimir Ivanov-2
On Thu, 18 Feb 2021 17:05:08 GMT, Vladimir Ivanov <[hidden email]> wrote:

> Simplify `ClassHierarchyWalker::find_witness_anywhere()` which iterates over class hierarchy under context class searching for witnesses.
>
> Current implementation traverses the hierarchy in a breadth-first manner and keeps a stack-allocated array to keep a worklist.
> But all the subclasses are already part of a singly linked list formed by `Klass::subklass()`/`next_sibling()`/`superklass()`.
>
> Proposed refactoring gets rid of the explicit worklist and switches to the traversal over the linked list (encapsulated into `ClassHierarchyIterator`). It performs depth-first pre-order hierarchy traversal.
>
> (There are some other minor refactorings applied in `ClassHierarchyWalker` along the way.)
>
> Testing:
> - [x] hs-tier1 - hs-tier8
> - [x] additional verification that CHA decisions aren't affected

It looks like there is a traversal bug lurking here, unless I missed something. Looks great otherwise.

src/hotspot/share/oops/instanceKlass.hpp line 1457:

> 1455:   // Make a step iterating over the class hierarchy under the root class.
> 1456:   // Skips subclasses if requested.
> 1457:   void next() {

Since this method is a bit involved, I think it might want to move to the cpp file.

src/hotspot/share/oops/instanceKlass.hpp line 1461:

> 1459:     if (_visit_subclasses && _current->subklass() != NULL) {
> 1460:       _current = _current->subklass();
> 1461:       return; // visit next subclass

_visit_subclasses is initially true in the constructor. That seems to imply that after the first call to next(), we will take this path, just returning the subklass() without walking the siblings. The _visit_subclasses variable is never mutated away from the true state at all if it was already true, until we get to the bottom of the class hierarchy. That seems to imply that the next() iterator won't visit any siblings at all until we get to the bottom of the class hierarchy, essentially breaking the DFS traversal. Therefore, it looks to me like the use of the _visit_subclasses variable needs to be looked over a bit in this function in general, unless I misunderstood something.

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

Changes requested by eosterlund (Reviewer).

PR: https://git.openjdk.java.net/jdk/pull/2630
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8261954: Dependencies: Improve iteration over class hierarchy under context class

Vladimir Ivanov-2
On Fri, 19 Feb 2021 13:52:35 GMT, Erik Österlund <[hidden email]> wrote:

>> Simplify `ClassHierarchyWalker::find_witness_anywhere()` which iterates over class hierarchy under context class searching for witnesses.
>>
>> Current implementation traverses the hierarchy in a breadth-first manner and keeps a stack-allocated array to keep a worklist.
>> But all the subclasses are already part of a singly linked list formed by `Klass::subklass()`/`next_sibling()`/`superklass()`.
>>
>> Proposed refactoring gets rid of the explicit worklist and switches to the traversal over the linked list (encapsulated into `ClassHierarchyIterator`). It performs depth-first pre-order hierarchy traversal.
>>
>> (There are some other minor refactorings applied in `ClassHierarchyWalker` along the way.)
>>
>> Testing:
>> - [x] hs-tier1 - hs-tier8
>> - [x] additional verification that CHA decisions aren't affected
>
> src/hotspot/share/oops/instanceKlass.hpp line 1461:
>
>> 1459:     if (_visit_subclasses && _current->subklass() != NULL) {
>> 1460:       _current = _current->subklass();
>> 1461:       return; // visit next subclass
>
> _visit_subclasses is initially true in the constructor. That seems to imply that after the first call to next(), we will take this path, just returning the subklass() without walking the siblings. The _visit_subclasses variable is never mutated away from the true state at all if it was already true, until we get to the bottom of the class hierarchy. That seems to imply that the next() iterator won't visit any siblings at all until we get to the bottom of the class hierarchy, essentially breaking the DFS traversal. Therefore, it looks to me like the use of the _visit_subclasses variable needs to be looked over a bit in this function in general, unless I misunderstood something.

`_visit_subclasses` is mutated only from the outside (there's `ClassHierarchyIterator::skip_subclasses()` specificlaly for that) when user code needs to ignore subclasses:

https://github.com/openjdk/jdk/blob/ae78e51e4248c2ccfa73c772fb1db1baad2c2903/src/hotspot/share/code/dependencies.cpp#L1359:

  for (ClassHierarchyIterator iter(context_type); !iter.done(); iter.next()) {
    Klass* sub = iter.klass();

    // Do not report participant types.
    if (is_participant(sub)) {
      // Walk beneath a participant only when it doesn't hide witnesses.
      if (participants_hide_witnesses) {
        iter.skip_subclasses();
      }

And `_visit_subclasses` is cleared to the initial state on the very next call to `next()`.

> That seems to imply that the next() iterator won't visit any siblings at all until we get to the bottom of the class hierarchy, essentially breaking the DFS traversal.

Yes, that's the intended behavior. Why do think it doesn't obey depth-first order? `next_sibling()` points to a class on the same level of class hierarchy.

> src/hotspot/share/oops/instanceKlass.hpp line 1457:
>
>> 1455:   // Make a step iterating over the class hierarchy under the root class.
>> 1456:   // Skips subclasses if requested.
>> 1457:   void next() {
>
> Since this method is a bit involved, I think it might want to move to the cpp file.

Good point.

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

PR: https://git.openjdk.java.net/jdk/pull/2630
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8261954: Dependencies: Improve iteration over class hierarchy under context class

Erik Österlund-3
In reply to this post by Vladimir Ivanov-2
On Thu, 18 Feb 2021 17:05:08 GMT, Vladimir Ivanov <[hidden email]> wrote:

> Simplify `ClassHierarchyWalker::find_witness_anywhere()` which iterates over class hierarchy under context class searching for witnesses.
>
> Current implementation traverses the hierarchy in a breadth-first manner and keeps a stack-allocated array to keep a worklist.
> But all the subclasses are already part of a singly linked list formed by `Klass::subklass()`/`next_sibling()`/`superklass()`.
>
> Proposed refactoring gets rid of the explicit worklist and switches to the traversal over the linked list (encapsulated into `ClassHierarchyIterator`). It performs depth-first pre-order hierarchy traversal.
>
> (There are some other minor refactorings applied in `ClassHierarchyWalker` along the way.)
>
> Testing:
> - [x] hs-tier1 - hs-tier8
> - [x] additional verification that CHA decisions aren't affected

Looks good! (move next() to cpp file if you want to)

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

Marked as reviewed by eosterlund (Reviewer).

PR: https://git.openjdk.java.net/jdk/pull/2630
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8261954: Dependencies: Improve iteration over class hierarchy under context class

Erik Österlund-3
In reply to this post by Vladimir Ivanov-2
On Fri, 19 Feb 2021 15:20:50 GMT, Vladimir Ivanov <[hidden email]> wrote:

>> src/hotspot/share/oops/instanceKlass.hpp line 1461:
>>
>>> 1459:     if (_visit_subclasses && _current->subklass() != NULL) {
>>> 1460:       _current = _current->subklass();
>>> 1461:       return; // visit next subclass
>>
>> _visit_subclasses is initially true in the constructor. That seems to imply that after the first call to next(), we will take this path, just returning the subklass() without walking the siblings. The _visit_subclasses variable is never mutated away from the true state at all if it was already true, until we get to the bottom of the class hierarchy. That seems to imply that the next() iterator won't visit any siblings at all until we get to the bottom of the class hierarchy, essentially breaking the DFS traversal. Therefore, it looks to me like the use of the _visit_subclasses variable needs to be looked over a bit in this function in general, unless I misunderstood something.
>
> `_visit_subclasses` is mutated only from the outside (there's `ClassHierarchyIterator::skip_subclasses()` specificlaly for that) when user code needs to ignore subclasses:
>
> https://github.com/openjdk/jdk/blob/ae78e51e4248c2ccfa73c772fb1db1baad2c2903/src/hotspot/share/code/dependencies.cpp#L1359:
>
>   for (ClassHierarchyIterator iter(context_type); !iter.done(); iter.next()) {
>     Klass* sub = iter.klass();
>
>     // Do not report participant types.
>     if (is_participant(sub)) {
>       // Walk beneath a participant only when it doesn't hide witnesses.
>       if (participants_hide_witnesses) {
>         iter.skip_subclasses();
>       }
>
> And `_visit_subclasses` is cleared to the initial state on the very next call to `next()`.
>
>> That seems to imply that the next() iterator won't visit any siblings at all until we get to the bottom of the class hierarchy, essentially breaking the DFS traversal.
>
> Yes, that's the intended behavior. Why do think it doesn't obey depth-first order? `next_sibling()` points to a class on the same level of class hierarchy.

Okay, I see. So you traverse all the way down, following the subclass links until you can't go further, and then traverse the siblings on the way up. That makes sense. Thanks for the explanation.

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

PR: https://git.openjdk.java.net/jdk/pull/2630
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8261954: Dependencies: Improve iteration over class hierarchy under context class [v2]

Vladimir Ivanov-2
In reply to this post by Vladimir Ivanov-2
> Simplify `ClassHierarchyWalker::find_witness_anywhere()` which iterates over class hierarchy under context class searching for witnesses.
>
> Current implementation traverses the hierarchy in a breadth-first manner and keeps a stack-allocated array to keep a worklist.
> But all the subclasses are already part of a singly linked list formed by `Klass::subklass()`/`next_sibling()`/`superklass()`.
>
> Proposed refactoring gets rid of the explicit worklist and switches to the traversal over the linked list (encapsulated into `ClassHierarchyIterator`). It performs depth-first pre-order hierarchy traversal.
>
> (There are some other minor refactorings applied in `ClassHierarchyWalker` along the way.)
>
> Testing:
> - [x] hs-tier1 - hs-tier8
> - [x] additional verification that CHA decisions aren't affected

Vladimir Ivanov has updated the pull request incrementally with one additional commit since the last revision:

  Move ClassHierarchyIterator::next() into CPP file

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

Changes:
  - all: https://git.openjdk.java.net/jdk/pull/2630/files
  - new: https://git.openjdk.java.net/jdk/pull/2630/files/ae78e51e..7237e9c5

Webrevs:
 - full: https://webrevs.openjdk.java.net/?repo=jdk&pr=2630&range=01
 - incr: https://webrevs.openjdk.java.net/?repo=jdk&pr=2630&range=00-01

  Stats: 39 lines in 2 files changed: 21 ins; 17 del; 1 mod
  Patch: https://git.openjdk.java.net/jdk/pull/2630.diff
  Fetch: git fetch https://git.openjdk.java.net/jdk pull/2630/head:pull/2630

PR: https://git.openjdk.java.net/jdk/pull/2630
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8261954: Dependencies: Improve iteration over class hierarchy under context class [v2]

Vladimir Ivanov-2
In reply to this post by Erik Österlund-3
On Fri, 19 Feb 2021 15:52:32 GMT, Erik Österlund <[hidden email]> wrote:

>> Vladimir Ivanov has updated the pull request incrementally with one additional commit since the last revision:
>>
>>   Move ClassHierarchyIterator::next() into CPP file
>
> Looks good! (move next() to cpp file if you want to)

Thanks for the review, Erik.

(Moved ClassHierarchyIterator::next() into CPP file as you suggested.)

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

PR: https://git.openjdk.java.net/jdk/pull/2630
Reply | Threaded
Open this post in threaded view
|

Integrated: 8261954: Dependencies: Improve iteration over class hierarchy under context class

Vladimir Ivanov-2
In reply to this post by Vladimir Ivanov-2
On Thu, 18 Feb 2021 17:05:08 GMT, Vladimir Ivanov <[hidden email]> wrote:

> Simplify `ClassHierarchyWalker::find_witness_anywhere()` which iterates over class hierarchy under context class searching for witnesses.
>
> Current implementation traverses the hierarchy in a breadth-first manner and keeps a stack-allocated array to keep a worklist.
> But all the subclasses are already part of a singly linked list formed by `Klass::subklass()`/`next_sibling()`/`superklass()`.
>
> Proposed refactoring gets rid of the explicit worklist and switches to the traversal over the linked list (encapsulated into `ClassHierarchyIterator`). It performs depth-first pre-order hierarchy traversal.
>
> (There are some other minor refactorings applied in `ClassHierarchyWalker` along the way.)
>
> Testing:
> - [x] hs-tier1 - hs-tier8
> - [x] additional verification that CHA decisions aren't affected

This pull request has now been integrated.

Changeset: 0a4e710f
Author:    Vladimir Ivanov <[hidden email]>
URL:       https://git.openjdk.java.net/jdk/commit/0a4e710f
Stats:     173 lines in 3 files changed: 68 ins; 69 del; 36 mod

8261954: Dependencies: Improve iteration over class hierarchy under context class

Reviewed-by: kvn, coleenp, eosterlund

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

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