[TinkerPop3] Unrolling Loops with UnrollJumpStrategy

[Marko Rodriguez]

Hi,

As you may know from Gremlin2, g.V.out.out.out is cheaper than g.V.out.loop(1){it.loops < 3} in terms of both time and space. There is nearly 5x time difference as you can see in our recommended optimizations section of the Gremlin2 documentation:

https://github.com/tinkerpop/gremlin/wiki/Gremlin-Groovy-Path-Optimizations#using-loops 

One way to avoid this cost is if the "ifPredicate" is of the form "it.loops < x," then unroll your loop. This technique is used extensively in modern language compilers -- http://en.wikipedia.org/wiki/Loop_unwinding. With Gremlin3 and TraversalStrategies, we can now unroll loops by analyzing the Traversal accordingly within the new UnrollJumpStrategy.

https://github.com/tinkerpop/tinkerpop3/blob/master/gremlin-core/src/main/java/com/tinkerpop/gremlin/process/graph/strategy/UnrollJumpStrategy.java

The strategy finds all JumpSteps in the traversal. If the JumpStep is "unrollable" then the … section of as('x')…jump('x') is isolated and cloned and inserted accordingly. Here are some runtimes with the strategy enabled and disabled.

MANUAL UNROLLING

gremlin> t = System.currentTimeMillis(); g.V().out().out().out().iterate(); System.currentTimeMillis() - t

==>841

UNROLL JUMP STRATEGY DISABLED

gremlin> traversal = g.V().as('x').out().jump('x',3); traversal.strategies().unregister(com.tinkerpop.gremlin.process.graph.strategy.UnrollJumpStrategy.class)

==>null

gremlin> t = System.currentTimeMillis(); traversal.iterate(); System.currentTimeMillis() - t

==>3754

UNROLL JUMP STRATEGY ENABLED

gremlin> t = System.currentTimeMillis(); g.V().as('x').out().jump('x',3).iterate(); System.currentTimeMillis() - t

==>866

Pretty nifty eh?

Enjoy!,

Marko.

http://markorodriguez.com

[Stephen Mallette]

The unroll part is nifty, but equally nifty is that the "strategy" abstractions continue to allow things like this without modification to the core of their design.  

--
You received this message because you are subscribed to the Google Groups "Gremlin-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gremlin-user...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Paul Jackson]

I agree. Shouldn't something similar be possible with any loop closure using some combination of optional and filter pipes? Also, I wonder if there is any way to retain the breadth-first behavior of loops.