search

EastsidePreparatorySchool / FusorComputationalModeling

Eastside Prep Fusor project electrostatic field modeling and deuteron simulation
2 stars 3 forks source link

Performance: getRandomPoint #33

Closed gunnarmein closed 7 years ago

gunnarmein commented 7 years ago

getRandomPoint does a linear search, in effect, through surface areas, to find the right component to get a point from. This is correct, but needlessly slow. If we import an STL model of the vac chamber, we might have thousands or tens of thousands of parts to traverse. Here are two ways to rewrite this:

a) binary search for the right part 1) When all the parts have been instantiated, create an array with their cumulative surface areas. 2) in getRandom point, implement a custom binary search for the index in the array which contains the random value range (lower bound). That's the index of the part to get the point from.

b) map of parts by area sizes. We have lots of memory, right? This is really only an optimization of a) - we create a big array of object pointers (for 100 parts maybe a million objects). We populate it with pointers to parts proportionally - if parts[0] takes up 13.678% of surface area, then we put parts[0] into the first 13.678% of slots. now, every time we need a random point we can figure out from which part it should come by picking a random object out of the array.

guberti commented 7 years ago

Option B seems clever, but I'm skeptical that it will offer much of a performance upgrade over option A (I could be very wrong, though). Working in implementing option A.

gunnarmein commented 7 years ago

The performance upgrade from log n to constant is not that great, true, compared to the upgrade from n to log n. Actually, the profiler says that getRandomPoint does not even matter. It seems dwarfed by just the time spent in balancing. Unless it was in-lined by the compiler.

guberti commented 7 years ago

Building a fix for this is taking longer than I expected. #30, #31, and #32 are fixed and their fixes are visible in my branch Performance-upgrades-to-point-distribution. I'll send a PR for the branch once #33 is complete.

guberti commented 7 years ago

Fixed! This change majorly affects code performance in a positive way. The test mentioned in #31 previously took 8 seconds (after the repair of #30, #31, #32) now takes 1.