GitHub user okram opened a pull request:
https://github.com/apache/tinkerpop/pull/473
TINKERPOP-1372: ImmutablePath should not use Java recursion (call stacks
are wack)
https://issues.apache.org/jira/browse/TINKERPOP-1372
`ImmutablePath` used heavy method-recursion which is expensive in Java to
create a new call stack for each recurse. All method-recursion has been
replaced with `while(true)`-recursion. Furthermore, was able to get rid of
`ImmutablePath.TailPath` with a `public static ImmutablePath TAIL_PATH = new
ImmutablePath(null,null,null)`. This makes things much cleaner and we don't
need the package protected `ImmutablePathImpl` interface. Finally, I stole
@pietermartin's trick to use direct reference to `Set<String>` labels as the
labels are immutable.
Here is a benchmark of a bunch of `match()`-traversals on the Grateful Dead
graph where the first two columns are time in milliseconds and the last column
is the number of returned results.
```
PREVIOUS NEW # RESULTS
----------------------------
[12.676, 12.019, 93]
[222.123, 177.596, 2952]
[27.187, 35.787, 6]
[80.917, 77.891, 5421]
[189.354, 176.308, 5096]
[14.644, 14.969, 18]
[2.214, 0.908, 3]
[924.093, 777.707, 314932]
```
VOTE +1.
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/apache/tinkerpop TINKERPOP-1372
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/tinkerpop/pull/473.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #473
----
commit 04fe38a28d3dce2a910c40c49658c083785b6473
Author: Marko A. Rodriguez <[email protected]>
Date: 2016-11-01T12:39:45Z
removed call stack recursion in ImmutablePath. All is while(true) based
with a break on 'tail path.' ImmutablePath.TailPath is no longer required as
the 'tail' is a the path segmanet with currentObject == null. Some preliminary
tests show a significant speed up. Benchmark to follow suit. Added more test
cases to PathTest. Removed TailPath Class.forName() in GryoRegistrator as it is
no longer an existing class.
commit 3caa5c8aa38b108f9548ce345ddd97bd7378f99e
Author: Marko A. Rodriguez <[email protected]>
Date: 2016-11-01T12:41:17Z
removed ImmutablePathImpl. Was initially Deprecated as TailPath is no
longer needed, but since its a package local interface, it is not possible to
implement outside of the package. Thus, if its no longer used in the package,
delete.
commit cd000995d1670170b9b5f3d726f20fb8cf45ffc9
Author: Marko A. Rodriguez <[email protected]>
Date: 2016-11-01T13:09:45Z
removed more method-based recursions in ImmutablePath and inlined the
singleHead() and singleTail() methods as they are no longer interface methods
and are only called in one other method.
commit 3896a981fdfced7b19a830738b2f3ef51f82672a
Author: Marko A. Rodriguez <[email protected]>
Date: 2016-11-01T13:19:54Z
Overrode Path.isSimple() default impl for ImmutablePath that doesn't create
so many objects.
commit deaf38a7ed35f3236614d833eeb0eac2a25334fc
Author: Marko A. Rodriguez <[email protected]>
Date: 2016-11-01T14:27:08Z
added @pietermartin's direct reference to Step.getLabels() optimization to
ImmutablePath. Added JavaDoc to Traverser for the dropLabels()/keepLabels()
method. Fixed a spelling mistake in AbstractTraverser.
----
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at [email protected] or file a JIRA ticket
with INFRA.
---
