Since Decimal is being discussed quite a bit here in the thread, I just wanted to point out that the conversion of base-10 strings to Decimal instances is only O(n) if the _decimal module that is written in C is used. However, import decimal will automatically and transparently fall back to the pure Python implementation if _decimal is not available, and _pydecimal.py has completely different complexities: all the operations are implemented by converting the decimal string to a regular Python int object (O(n^2) as we’ve all been learning) and then converting the result back to a str (again O(n^2)).
Now the C implementation should be available ~always (except on PyPy 
), but if not, the effect is pretty bad, if the application tries to use Decimal for arbitrary precision arithmetic with efficient conversion back and forth to str. I’m not sure whether I am suggesting anything here, should the fallback to _pydecimal.py produce a warning?