Python 3.3 vs. MSDOS Basic

[Terry Reedy]

On 2/18/2013 4:55 PM, Chris Angelico wrote:

> Running under Python 2.6, both your version and mine take about 90
> seconds to run. But under Python 3.3, where (among other things)
> range() yields values lazily, my version is significantly faster than
> yours. BUT! Both versions, under 3.3, are significantly *slower* than
> under 2.6. My first thought is that it's because Py2 has different
> types for 'int' and 'long', and Py3 doesn't (effectively, everything's
> a long), so I added an L suffix to every number and ran each of them
> under 2.6 again. Seems that was the bulk of the difference, though not
> all.
>
> Pythonistas, does this count as a regression, or is Python
> sufficiently "not a number crunching language" that we don't care?

Both. This brute-force algorithm is almost pure number crunching. This 
is the sort of thing pypy and cython are good at speeding up. (I leave 
out numpy only because it is not an array-oriented problem.)

I put a counter in the inner loop of my improved version the does 
(3*n+1)//2 in one step and got 87 826 478 in 40 seconds (without the 
counter). That is 2 million loops per second and each loop does a 
compare, one or two integer ops, and creates and releases one or two ints.

If I were doing a lot of int crunching like this with CPython and were 
building my own interpreter, I would greatly expand the range of 
pre-allocated 'small' ints to avoid some of the repeated allocation and 
de-allocation. On a multi-gibibyte machine, allocating up to 1000000 
instead of 256 would be feasible.

As Ian noted, an intelligent algorithm in CPython can match pypy and is 
in the ballpark of C, but is much easier to write in Python than C. It 
is possible that Ian's code could be improved further. A pre-allocated 
arrray + dict might be faster. Whenever an odd value is filled in, 
powers of 2 times that value can also be.

-- 
Terry Jan Reedy