8000 Add Materialize Iterator by barakmich · Pull Request #101 · cayleygraph/cayley · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Add Materialize Iterator #101

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 7 commits into from
Aug 6, 2014
Merged

Add Materialize Iterator #101

merged 7 commits into from
Aug 6, 2014

Conversation

barakmich
Copy link
Member

Introducing the materialize iterator -- if it seems reasonable to just materialize a set instead of checking paths that might lead back, the And iterator can now add this layer as an optimization. It bails if used on sets that are too large, and is still ripe for cost/benefit tweaks, but in general will make deep queries a lot faster.

To wit, the benchmarks are now almost all short:

$ benchcmp master.txt aftermaterialize.txt
benchmark                                   old ns/op        new ns/op       delta
BenchmarkNamePredicate                      904393           898317          -0.67%
BenchmarkLargeSetsNoIntersection            150923975        54921214        -63.61%
BenchmarkVeryLargeSetsSmallIntersection     174235833178     463987963       -99.73%
BenchmarkHelplessContainsChecker            18569994238      15828325039     -14.76%
BenchmarkNetAndSpeed                        32027611         16516696        -48.43%
BenchmarkKeanuAndNet                        13430475         12509101        -6.86%
BenchmarkKeanuAndSpeed                      15260371         14882936        -2.47%
BenchmarkKeanuOther                         1133568511       74794130        -93.40%
BenchmarkKeanuBullockOther                  124273081626     84608986        -99.93%

/cc @pbnjay @kortschak

@kortschak
Copy link
Contributor

LGTM with comment above. Nice work.

pbnjay
pbnjay reviewed Aug 6, 2014
View reviewed changes
graph/iterator/materialize_iterator.go
}

func (it *Materialize) Clone() graph.Iterator {
out := NewMaterialize(it.subIt.Clone())
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

if it.hasRun, you can copy it.values and it.containsMap here. Since these aren't changed after they are populated you can even save the allocations and just copy the refs too.

@pbnjay
Copy link
Contributor
pbnjay commented Aug 6, 2014

LGTM!

barakmich added a commit that referenced this pull request Aug 6, 2014
@barakmich
Merge pull request #101 from barakmich/materializer_iterator
7e7371c 
Add Materialize Iterator
@barakmich barakmich merged commit 7e7371c into cayleygraph:master Aug 6, 2014
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
3 participants
@barakmich @kortschak @pbnjay
0