[
https://issues.apache.org/jira/browse/TINKERPOP-1372?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15625594#comment-15625594
]
ASF GitHub Bot commented on TINKERPOP-1372:
-------------------------------------------
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.
----
> ImmutablePath should not use Java recursion (call stacks are wack)
> ------------------------------------------------------------------
>
> Key: TINKERPOP-1372
> URL: https://issues.apache.org/jira/browse/TINKERPOP-1372
> Project: TinkerPop
> Issue Type: Improvement
> Components: process
> Affects Versions: 3.2.0-incubating
> Reporter: Marko A. Rodriguez
> Assignee: Marko A. Rodriguez
>
> {{ImmutablePath}} sucks for a few reasons:
> 1. It has {{ImmutablePathImpl}} interface to combine {{Tail}} and
> {{ImmutablePath}}. Lame.
> 2. It uses recurssion to find data. Lame.
> For 3.2.1, I have done a lot to use {{while()}}-based recursion and I suspect
> I can gut {{ImmutablePathImpl}} and few other kooky things.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
