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 <okramma...@gmail.com> 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 <okramma...@gmail.com> 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 <okramma...@gmail.com> 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 <okramma...@gmail.com> 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 <okramma...@gmail.com> 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 infrastruct...@apache.org or file a JIRA ticket with INFRA. ---