HIVE-1626: stop using java.util.Stack

[pudidic]

We currently use Stack as part of the generic node walking library. Stack should not be used for this since its inheritance from Vector incurs superfluous synchronization overhead. ArrayStack is implemented to replace Stack.

What changes were proposed in this pull request?

• Stack<Node> calls were replaced with ArrayStack<Node>.
• ArrayStack has same pop, push, peek methods as Stack without synchronization.
• LevelOrderWalker uses an extended ArrayStack that allows add(0, element) and remove(0).
• Stack#empty was replaced with ArrayStack#isEmpty.

Why are the changes needed?

• Stack was used in query planning, but it's very slow because of synchronization overhead.

Does this PR introduce any user-facing change?

No.

How was this patch tested?

• All existing tests passed on http://ci.hive.apache.org/blue/organizations/jenkins/hive-precommit/detail/PR-3434/4/pipeline/628/.
• ArrayStackTest was added to test whether ArrayStack work same as Stack.

[pudidic]

retest this please

[pudidic]

The only failing test, TestCleanupService passes on my PC. It seems like unstable test. So I triggered a retest.

[pudidic]

Close/open to trigger a rebuild.

[pudidic]

@cmunkey

I tried to minimize indexed accessors of Stack, exposing push/pop/peek only. Because there already are several use cases of Stack#get(int), I implemented ArrayStack#get(int) also.

However, LevelOrderWalker has a unique usage of Stack. LevelOrderWalker calls stack.add(0, element) and stack.remove(0) to add/remove elements at the start of the stack. They are inverse of stack.pop/push, which add/remove at the end. The rest of part still calls Stack.pop/push, as not inverse. I tried to replace stack.add(0, element) with stack.push and stack.remove(0) with stack.pop, but it behaved very differently. The inverse push/pop is not I wanted to expose. So I implemented a subclass in LevelOrderWalker to isolate its use from others. Maybe I need to document to make its purpose clear.

I'll replace == with equals in indexOf(). Thank you for advice.

[cmunkey]

Maybe call it RandomUpdateStack instead of MyArrayStack.

[cmunkey]

java.util.Stack uses equals() for search, so maybe it is appropriate to use equals here for indexOf().

public synchronized int search(Object o)

[pudidic]

Close/reopen to retrigger the tests.

[github-actions[bot]]

This pull request has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Feel free to reach out on the [email protected] list if the patch is in need of reviews.