intuit / intuit/Traverser

Post-order traversal on a medium-size and large graph

Open
#27 0 comments 0 reactions 1 assignee Claimed by @gkesler View on GitHub
help wanted
Dominant language
Java
Stars
60
Forks
21
PR merge metrics
No merged PRs in 30d

Description

Traverser context builder defines a context strategy (see TraverseContextBuilder.[ContextStrategy](https://github.com/intuit/Traverser/blob/4ad80b64ca4cfb5492bb822b9363ec5cafc209c2/src/main/java/com/intuit/commons/traverser/TraverseContextBuilder.java#L173)), which helps to control result during traversal.

In case of post order traversal, the action to set result is invoked once traversal of a current node is complete (hence the name).
On a medium and large graphs this final termination could happen very far from start/root node, the path from start to this node could easily include thousands of intermediate nodes.

Current implementation of [NORMAL_STRATEGY](https://github.com/intuit/Traverser/blob/4ad80b64ca4cfb5492bb822b9363ec5cafc209c2/src/main/java/com/intuit/commons/traverser/TraverseContextBuilder.java#L210) propagates result from current context to parent, and then from parent to grandparent, which utilize application call stack.

On a JVM with standard configuration (512K), this could generate _StackOverflowError_ once call stack is exceeded.
In my case, it took 14-15K nodes in a path to cause the error.

There are several ways to mitigate it.

### Increase JVM stack size
Use configuration to increase stack size with `java -Xss1M` (10M, etc). This is usually enough to enable traversal on a graph with millions nodes.

### Create custom context strategy

Another way to avoid stack overflow is to handle result differently by utilizing custom context strategy.

This example is for illustration purposes, it assumes default configuration and expects custom strategy. It gives up ability to call strategy per every result, therefore it is not general enough.

```java
private static final ContextStrategy CUSTOM_NORMAL_STRATEGY = new ContextStrategy() {
@Override
public void setResult(TraverseContextBuilder outer, U result) {
outer.result = result;
rootContext(outer).setResult(result);
}

@Override
public U getResult(TraverseContextBuilder outer) {
return rootContext(outer).getResult();
}

private TraverseContextBuilder rootContext(TraverseContextBuilder outer) {
TraverseContextBuilder parent = outer.parentContext;
while(parent.contextStrategy == CUSTOM_NORMAL_STRATEGY) { // walk till ROOT
parent = parent.parentContext;
}
return parent;
}

@Override
public U getVar(TraverseContextBuilder outer, Class key) {
U value;
return ((value = (U)outer.vars.get(key)) != null || outer.vars.containsKey(key))
? value
: outer.parentContext.getVar(key);
}

@Override
public U setVar(TraverseContextBuilder outer, Class key, U newValue) {
return outer.vars.containsKey(key)
? (U)outer.vars.put(key, newValue)
: outer.parentContext.setVar(key, newValue);
}

@Override
public String toString() {
return "CUSTOM_NORMAL_STRATEGY";
}
};
```

Find very unit test to illustrate above in [my private gist](https://gist.github.com/amatiushkin/7909ee3c249fd5b213ea60dbd5c0d6d8).

## Question to the community
**Traverser** is designed as a general-purpose library and some limitations and tradeoffs needs to be made.

What is more important for default configuration: ability to traverse large graphs or functionality set? Shall it strive to have both?

PS
This is practical question for anyone, who operates with linked and connected data on a scale of [wikidata](https://www.wikidata.org/wiki/Wikidata:Main_Page) (~100M "entities").

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.