overviewer/Minecraft-Overviewer — pull request #533 by brownan (2011-11-13 15:14:01+00:00)
Title: Chunkscanning ready!

The chunk-scanning branch brings massive speed improvements to the process of determining which tiles need to be rendered.

Before, the code would enumerate every possible tile at the highest level, calculating the 32 chunks that touch that tile, checking if those chunks exist, and comparing mtimes on them. This is a lot of wasted effort as all blank tiles are re-checked every render, and even the biggest maps have lots of blank tiles around the edges (as maps aren't perfectly square)

This branch turns the scanning around: chunks are scanned, the tiles they touch are calculated (5 or 10 tiles per chunk), mtimes compared, and the tiles that need to be rendered are held in a memory-efficient tree data-structure. This scans only the chunks that actually exist and performs mtime checks only on tiles that ought to exist, cutting way down on the effort spent in areas of the map that don't exist.

Along with this branch is also a massive amount of cleanups, code rearrangements, and comments explaining various parts of the code. I believe these changes are for the better. Most of the commits are separated: either cleanup or chunk scanning related.

## CAVEATS / THINGS THAT STILL NEED TO BE DONE:
* --regionlist has not been re-implemented. I think this may have been broken before-hand anyways, but still needs to be done at some point
* --changelist has not been re-implemented. This should be easy. Should this be done before merging?
* Due to the new scanning algorithm, If parts of the map are deleted manually (MCEdit) and a previously existing tile should no longer exist, Overviewer won't notice because that tile is never touched or scanned. This wasn't a problem before because every tile was enumerated and scanned; now only tiles that should exist are considered for update. Since shrinking maps are a "corner" case (only happens with manual intervention with external tools) and the chunk-scanning is such an improvement, I propose a new option be added: --prune-tiles. This invokes the old tile-scanning behavior with the sole intent of finding tiles that should no longer exist and deleting them.
* Still to do for even more speed improvements is to change the inner-tile rendering to use the chunk-scan results. Since the results are stored in a tree with the exact same structure as the tiles on disk, it should be trivial to query the tree to see what inner-tiles need rendering, instead of exhaustive enumeration like it is (still) now.
* Chunk scanning is single threaded right now and each rendermode happens in serial. I don't think it would be too hard to do chunk scanning in parallel and then combine/merge the trees at the end. It almost certainly wouldn't be hard to do each rendermode's scan in parallel. However, none of this has been done. My feeling is the chunk scanning is quick enough to not be necessary. Even on the largest maps (aheadley's) it only takes 300-400 seconds per rendermode for a full scan.

## THINGS THAT NEED TO BE TESTED / I NEED YOUR HELP
* The whole thing really. Everything seems to work but I haven't done extensive testing on it
* stochastic option has been re-implemented but hasn't been tested
* Speed tests in comparison with the old code. I actually haven't tested the speed in comparison with the old branch, just speed / profiling tests on the chunk scanning algorithm itself (which even for the largest maps, aheadley's, only takes 300-400 seconds per rendermode on my machine for a full render). I suspect, and preliminary tests confirm, that full renders will be marginally faster while incremental renders will be loads faster (since after the chunk scan, only tiles that need updating are rendered).