GalSim-developers / GalSim

The modular galaxy image simulation toolkit. Documentation:
http://galsim-developers.github.io/GalSim/
Other
224 stars 105 forks source link

Speed up combine_wave_lists using new merge_sorted function #1243

Closed rmjarvis closed 1 year ago

rmjarvis commented 1 year ago

@jchiang87 found that a significant amount of time in some recent imSim runs was spend doing the combine_wave_list function when adding the bulge+disk+knots galaxy components. This is partly because the SEDs probably have more wavelengths than we really need. But regardless, this function was not the most efficient bit of code. This PR significantly improves the algorithm. In the typical case, it's more than 3x faster. And when all the inputs are the same (which was the case for imSim in Jim's test) it's almost 5x faster.

The new underlying functionality is a new utility function merge_sorted, which merges two or more numpy arrays when the inputs are all already sorted. This is a pretty simple function (familiar to those who know merge sort), but there is apparently no native numpy function that does this. I did find sortednp who also implements this, but I just went ahead and wrote my own rather than add a new dependency.

The timing script I wrote compares the new version with the old one, and with Jim's suggested change of checking for equality in order to skip the merge entirely. (The new version also includes this check, btw.) Here are the timing results on my laptop:

Time for 10000 iterations of combine_wave_list
old time =  0.6298755840000001
jims time =  0.6358873750000003
new time =  0.18641429200000026
Time for 10000 iterations of combine_wave_list with identical wave_lists
old time =  0.7706999579999998
jims time =  0.1962956250000012
new time =  0.16020912499999973
rmjarvis commented 1 year ago

Good ideas Matt. Thanks. The only tricky one was getting NaNs to work the same way that np.unique treats them (puts them last). The rest were already fine. :)