NevermoreEngine
NevermoreEngine copied to clipboard
Major optimization of Octree module
Notably;
- This version of the module is now roughly 0.3x more performant.
- Swapped out t[#t+1] to table.insert
- Removed redundant, 1-time use variables
- No longer calling functions but rather calculating directly (possible issues with ease-of-use in terms of changing function behavior, but this also allows for much faster run times)
- Localization of table indices
A benchmark of current (Octree) versus optimized (PyOctree) shows the following performance improvements:

| Radius | Octree | PyOctree | Improvement |
|---|---|---|---|
| 20 | 26304 | 23169 | 1.13x faster |
| 40 | 47895 | 39960 | 1.19x faster |
| 60 | 82806 | 65281 | 1.26x faster |
| 80 | 132882 | 104087 | 1.27x faster |
| 100 | 192587 | 147095 | 1.30x faster |
| 120 | 277387 | 207931 | 1.33x faster |
| 140 | 374498 | 273656 | 1.36x faster |
| 160 | 519923 | 372003 | 1.39x faster |
| 180 | 661866 | 485274 | 1.36x faster |
| 200 | 834977 | 625786 | 1.33x faster |
| 220 | 1076302 | 838082 | 1.28x faster |
| 240 | 1276984 | 937616 | 1.36x faster |
| 260 | 1595419 | 1068181 | 1.49x faster |
| 280 | 1815949 | 1256723 | 1.44x faster |
| 300 | 2100269 | 1421281 | 1.47x faster |
| 320 | 2346557 | 1710521 | 1.37x faster |
| 340 | 2702164 | 1851038 | 1.45x faster |
| 360 | 2870727 | 2204199 | 1.30x faster |
| 380 | 3182624 | 2275747 | 1.39x faster |
| 400 | 3393377 | 2665696 | 1.27x faster |
| 420 | 3663764 | 2857884 | 1.28x faster |
| 440 | 3909860 | 3156822 | 1.23x faster |
| 460 | 4110152 | 3032455 | 1.35x faster |
| 480 | 4331064 | 3217508 | 1.34x faster |
| 500 | 4342197 | 3453817 | 1.25x faster |
This can be made faster at the cost of the readability.

(I'm not good with Excel so my charts are not very good, sorry)
A benchmark of current (Octree) versus optimized (PyOctree) shows the following performance improvements:
Radius Octree PyOctree Improvement 20 26304 23169 1.13x faster 40 47895 39960 1.19x faster 60 82806 65281 1.26x faster 80 132882 104087 1.27x faster 100 192587 147095 1.30x faster 120 277387 207931 1.33x faster 140 374498 273656 1.36x faster 160 519923 372003 1.39x faster 180 661866 485274 1.36x faster 200 834977 625786 1.33x faster 220 1076302 838082 1.28x faster 240 1276984 937616 1.36x faster 260 1595419 1068181 1.49x faster 280 1815949 1256723 1.44x faster 300 2100269 1421281 1.47x faster 320 2346557 1710521 1.37x faster 340 2702164 1851038 1.45x faster 360 2870727 2204199 1.30x faster 380 3182624 2275747 1.39x faster 400 3393377 2665696 1.27x faster 420 3663764 2857884 1.28x faster 440 3909860 3156822 1.23x faster 460 4110152 3032455 1.35x faster 480 4331064 3217508 1.34x faster 500 4342197 3453817 1.25x faster
Ahh, my bad - my radii search speeds went down from 0.6 to 0.2ms, and I thought it was a 3x improvement since 6/2=3.. forgot you need to do it the other way around.. oops