search

mxgmn / WaveFunctionCollapse

Bitmap & tilemap generation from a single example with the help of ideas from quantum mechanics
Other
23.18k stars 1.24k forks source link

Speed Improvements #10

Closed giawa closed 7 years ago

giawa commented 7 years ago

I re-ordered the 'propagator' jagged array to optimize for caching, and cache the array when possible. I also sped up the Bitmap writing. This takes the sample suite from 211 seconds on my machine to 155 seconds.

mxgmn commented 7 years ago

Many thanks! This is very useful.

Do you have any ideas how to optimize Propagate() method in the overlapping model by any chance?

giawa commented 7 years ago

@mxgmn Not sure, I'll take a look tonight! Glad to hear this code might be helpful.

giawa commented 7 years ago

I've incorporated the edits made by @kchapelier and also optimized the jagged array caching for the overlapping model. This takes the whole process down to 100s on my machine, which is better than a 2x speed improvement. Hopefully I did this the right way - I've never tried to integrate someone else's pull request before. Let me know if there's something I need to change to do this 'The Right Way'.

mxgmn commented 7 years ago

@giawa @kchapelier Do you mind if I integrate your commits from my local repo, not by accepting them in git. I'm a novice in git and I feel that this project is not the best place to learn it.

giawa commented 7 years ago

No problem. You can close this pull request at your leisure. Thanks again for writing this cool code!

kchapelier commented 7 years ago

@mxgmn Sure, no problem either :)

nanodeath commented 7 years ago

Not a fan of the bit-twiddling 😦 Using the Color class is unlikely to be slowing things down significantly. I also think there are too many things changing in this pull request; how are we to tell which are actually valuable?

giawa commented 7 years ago

@nanodeath Thanks for the comments. Writing out the bitmap took about 5% of the time in my limited tests. By removing calls to SetPixel that reduced the time to something negligible. As you mention, the Color class itself isn't a huge slow-down. The calls to SetPixel are actually where the performance hit occurs. However, since this pull request is titled 'Speed Improvements' I'm going to go for broke and make it faster.

Regarding the complexity of this pull request, fair enough. I continued with optimizations after the author of the code asked for me to look in to the other Propagate method. Perhaps I should have split it across several pull requests. I'm not sure if Git has a particular 'Right Way' to do these things, which is why I made the comment to the effect above.

This all being said, I'm going to just close this pull request because the author is going to merge in his local repo anyways. Since he's aware of these potential speed optimizations I'll just let him merge them as they wish. Cheers

nanodeath commented 7 years ago

@giawa I appreciate the thoughtful response. I'm not sure what the "Right Way" is either, and I don't mean to shut down the entire effort. Really my only issue is that any performance improvements that sacrifice readability (even if only a little...or a lot) should be carefully justified, and it's hard to do that with a multitude of changes. I'd be interested to see them individually, though!

mxgmn commented 7 years ago

@giawa Pushed it. Great improvements, thanks again! And they taught me about cache optimization!