Skip to content
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

3x speedup: Hoist "allowed" check in OverlappingModel#propagate #17

Merged
merged 1 commit into from
Oct 3, 2016
Merged

3x speedup: Hoist "allowed" check in OverlappingModel#propagate #17

merged 1 commit into from
Oct 3, 2016

Conversation

nanodeath
Copy link
Contributor

@nanodeath nanodeath commented Oct 2, 2016 •
edited
Loading

The "allowed" check in the innermost-loop of OverlappingModel#propagate can be safely hoisted to the top of the loop and doing so provides a massive speedup.

Performance numbers:
(I added some basic instrumentation with Stopwatch)

City

<overlapping name="City" N="3" symmetry="2" foundation="-1" periodic="True"/>

Before:

< City
> DONE in 10.6412399s
> DONE in 10.2346078s

After:

< City
> DONE in 3.4074682s
> DONE in 3.2315486s

Roughly 3x speedup.

All + Platformer + 3Bricks

Before:

TOTAL TIME (all `<overlapping>`): 298.2288456s

< Platformer (N=3)
> DONE in 3.6201797s
> DONE in 6.1962286s

< 3Bricks
> CONTRADICTION
> DONE in 73.8861201s
> DONE in 75.184608s

After:

TOTAL TIME (all `<overlapping>`): 183.6418427s

< Platformer (N=3)
> DONE in 2.1512673s
> DONE in 1.8658939s

< 3Bricks
> CONTRADICTION
> CONTRADICTION
> DONE in 19.6964029s
> CONTRADICTION
> CONTRADICTION
> CONTRADICTION
> DONE in 16.5563298s

Of course the total times vary wildly depending on...well, how many contradictions 3Bricks runs into, really.

Second run

More favorable, so...why not include.

TOTAL TIME (all `<overlapping>`): 108.0454612s

< Platformer (N=3)
> DONE in 3.0047066s
> DONE in 2.3627346s

< 3Bricks
> DONE in 21.5364856s
> DONE in 18.892922s

@nanodeath
Hoist "allowed" check in OverlappingModel#propagate
60f6e08 
The "allowed" check in the innermost-loop of OverlappingModel#propagate can be safely hoisted to the top of the loop and doing so provides a massive speedup.
@mxgmn
Copy link
Owner

mxgmn commented Oct 3, 2016

Aaaa! Super!!!

@mxgmn mxgmn merged commit 7b8357f into mxgmn:master Oct 3, 2016
kchapelier added a commit to kchapelier/wavefunctioncollapse that referenced this pull request Oct 6, 2016
@kchapelier
integrate optimization from mxgmn/WaveFunctionCollapse#17
7f58337
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.
2 participants
@nanodeath @mxgmn