Optimization of python nbody

[dahlend]

Hi there!

I was poking around and figured I could speed this code up a smidge. The base python package math is sometimes slower than you may expect, for example, the sqrt of a number is usually much faster if you use **0.5 instead of sqrt.

Additionally part of the computation was doing an effective x ^ 3/2 in 2 steps, and switching to x**1.5 gets a similar speedup to above ^.

Also, the double for loops over a range with the lookups adds a fair amount of time. This PR switches to using the base python combinations which achieves the same goal a tiny bit faster, and I would argue more read-ably.

I didnt run everything else on my machine, but just running this specific section of code in python I got around a 15% speedup.

Let me know if you want me to put this somewhere else.

[dahlend]

Also I would like to mention, if numpy is allowed I can make this much faster, but honestly that sort of feels like cheating.

[hanabi1224]

Thanks, but could u make it 3.py instead? The performance profile is quite different between multiple implementations, especially with or without JIT and 2.py is only faster than 1.py with JIT, could you also make another version of 1.py for cpython and pyston? If the final result shows new versions are consistently faster, I can make the switch later.

if numpy is allowed I can make this much faster

This falls into non-stdlib ffi usage, which is not allowed, or at least specially marked with ffi suffix in their file names

[dahlend]

Ah, I had not realized JIT was also being run as an option, sorry I haven't dug very deep here. I'm not terribly surprised that 2.py is faster in this case, and I'm pretty sure my change to combinations will be slower than the JIT version as well.

Taking a look at 1.py it looks like the math change I made here was already present, it just isn't using a class to contain the data and it rolls its own definition of combinations, which I am unclear on the perf gains/losses. So basically the only change I would potentially make there would be to use the python library combinations instead.

I'll take a look later at moving this to a 3.py.