transpose next_land_dynamic for greater speed and clarity

[MM1nd]

Here's another one I prepared yesterday.

This uses the fact that only very few coodinates are actually dist away from land. It then iterates over these coordinates and looks if the distance of their neighbours happens to be unknown. Only then an update is made. This is actually the more logical thing to do because it checks for dist directly at the beginning of the loop iterating over dist and it checks next_land[ny,nx] in the inner loop and makes a change to the same coordinate.

The original implementation had this backwards. It checked for unknown distances in the outer loop and for the known distance in the inner loop which makes for a lot more checks because of how the numbers work out.

I think that change in ordering is where the main speedup comes from. Doing the more logical thing also saves two comparisons in the inner loop and is likely to be a tiny bit more cache friendly, but I don't think these things matter too much. Using numpy here makes the code look a bit cleaner but mainly it hides away some of the loops, so I don't think it is a great speedup in and of itself. I didn't measure that in detail though. The code is now reasonably fast and it looks cleaner so that was where I stopped investigating.

Cheers

Alex

[coveralls]

Coverage increased (+0.8%) to 86.108% when pulling 3c3b8a6fc101d345cded2d24ff46a8f1797f2321 on MM1nd:revisit_next_land_dynamic into b5db0c6db7b99636a7490049db4610beb14d5a23 on Mindwerks:master.

[coveralls]

Coverage increased (+0.8%) to 86.108% when pulling 3c3b8a6fc101d345cded2d24ff46a8f1797f2321 on MM1nd:revisit_next_land_dynamic into b5db0c6db7b99636a7490049db4610beb14d5a23 on Mindwerks:master.

[codecov-io]

Codecov Report

Merging #247 into master will increase coverage by 0.68%. The diff coverage is 100%.

@@            Coverage Diff             @@
##           master     #247      +/-   ##
==========================================
+ Coverage    80.4%   81.09%   +0.68%     
==========================================
  Files          28       28              
  Lines        3888     3887       -1     
  Branches      768      766       -2     
==========================================
+ Hits         3126     3152      +26     
+ Misses        572      541      -31     
- Partials      190      194       +4

Impacted Files	Coverage Δ
worldengine/generation.py	91.25% <100%> (-0.06%)	:arrow_down:
worldengine/simulations/erosion.py	70.75% <0%> (+10.67%)	:arrow_up:

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update b5db0c6...3c3b8a6. Read the comment docs.

[psi29a]

Do we have some before and after numbers here? I love numbers. :)

[MM1nd]

Like I said in the other thread, this is the second to last improvement I have prepared in this series, so don't expect wonders. We are clearly reaching a limit here as the remaining slowness increasingly is in foreign code (platec, protobuf, the latter we could maybe use better but shrug). I also get the feeling that times being dominated py protobuf makes timings very unstable.

That being said:

Parameters same as always (1024*512 map).

Current master:

2m 30s, ~12% in next_land_dynamic

This branch merged into current master:

2m 23s ~2.3% in `next_land_dynamic``

But still, it's something and it makes the code more readable. I think it's the latter that counts here.

[psi29a]

Thanks! The changes themselves are great, I like that it has become more readable.