Hacker News Reader

Comment by gnuvince | Hacker News Reader

For people who, like me, thought that this would be slower than repeated division: my crappy benchmark indicates that allocating a new string and taking its length is faster by a factor of 2–2.5x.

Edit: In C, the version that loops is 15 times faster than the version that allocates a new string. Python is weird.

View on HN

It's a common feature of interpreters that they impose a large slowdown on whatever is done in interpreted code; Python's is about 40×, although better interpreters like GhostScript and Lua are more like 10×. It's surprising the difference isn't bigger in this case, but I can mostly confirm your results, getting 3× except for small numbers:

    In [1]: dl = lambda n: 1 if n < 10 else 1 + dl(n // 10)

    In [3]: map(dl, [0, 1, 9, 10, 99, 1000, 15432, 32, 801])
    Out[3]: [1, 1, 1, 2, 2, 4, 5, 2, 3]

    In [4]: %timeit dl(15322)
    100000 loops, best of 3: 4.64 µs per loop

    In [5]: %timeit len(str(15322))
    1000000 loops, best of 3: 1.41 µs per loop

    In [6]: %timeit dl(0)
    1000000 loops, best of 3: 721 ns per loop

    In [7]: %timeit len(str(0))
    1000000 loops, best of 3: 1.24 µs per loop

Upon thinking about this further, I guess it's sort of obvious why this happens. dl(0) does a constant, a function invocation, a comparison, a conditional, and a return of a constant (although if you look at the bytecode you'll see a few more steps in there). len(str(0)) does a constant and two built-in function invocations, which (as it happens) involve lookups in the global namespace at runtime in case you have redefined len or str.

So, basically, it's only interpreting a very small number of interpreter bytecodes either way, so the small number it has to interpret to use the builtins is comparable to the small number it has to interpret to run the recursive definition, and so the interpretive overhead is comparable (and it swamps the overhead of things like allocating a new string).

This machine is kind of slow. This took 54 CPU seconds in LuaJIT:

    > function dl(n) if n < 10 then return 1 else return 1 + dl(n/10) end end
    > for i = 1, 1000*1000*100 do dl(15322) end

That means that approach took 540 ns per invocation rather than Python's 4640 ns --- only about 9× slower instead of the usual 40×. Or maybe this is a case where LuaJIT isn't really coming through the way it usually does.

Having done a fair amount of python, this is exactly the result I'd expect. `len`, `str` are essentially implemented in C, thus avoiding the massive interpreter overhead compared to a simple loop in python.

Python uses a String conversion to implement rounding, so why not? :)

https://github.com/python/cpython/blob/master/Objects/floato...

Yes but performance was not part of the question. Any correct solution would do. I see this a lot that people go an extra mile trying to optimize the solution and introducing bugs along the way instead having a simple certainly correct solution and optimize it later if necessary. It is funny that the string version is faster in Python.

Reply on news.ycombinator.com