How to make Python run as fast (or faster) than Julia

[bartc]

On 26/02/2018 15:09, Chris Angelico wrote:
> On Tue, Feb 27, 2018 at 2:02 AM, bartc <bc at freeuk.com> wrote:
>> On 26/02/2018 14:04, bartc wrote:
>>>
>>> On 26/02/2018 13:42, Ned Batchelder wrote:
>>
>>
>>>    Well, once you notice that the
>>>>
>>>> Python code had N=1e5, and the C code had N=1e9 :)   If you want to
>>>> experiment, with N=1e5, the final number should be 5255210926702073855.
>>>
>>>
>>> OK, I'll try that.
>>
>>
>> I have that Python version working now. It's necessary to apply that masking
>> function to wherever numbers can get bigger.
>>
>> I don't know how long a 1-billion loop will take, but a 10-million loop took
>> 46 seconds on Python 3.6, and 21 seconds on PyPy 2.7 from a couple of years
>> ago. (And on Windows, which has a somewhat slower CPython than Linux.)
> 
> You're still reimplementing the C code in Python, which is
> inefficient. Have you considered going back to the *actual algorithm*
> and implementing that idiomatically in Python? I think you'll find
> that (a) the code is more readable, and (b) the run time is much
> lower.

Do you really think that?

The algorithm seems to require this sequence of calculations to be gone 
through. Otherwise anything more efficient can also be done in any language.

So how would idiomatic Python help, by seeing if such a routine already 
exists in some library? That wouldn't be playing the game.

If it helps, I remember playing with a version in Algol 68 Genie 
(interpreted). Still buggy as the output is different, it does about the 
same amount of work.

A 10-million loop would take an estimated 1000 seconds, on the same 
machine that CPython took 46 seconds. So four magnitudes slower than C.

-- 
bartc