3 ms·

The article provides profiling data of the optimised Python solution. If I'm reading it right, 90% of the time (1148 milliseconds out of a total of 1280) is spe

The article provides profiling data of the optimised Python solution. If I'm reading it right, 90% of the time (1148 milliseconds out of a total of 1280) is spent executing the _collections._count_elements and str.split methods, both of which are Python standard-library methods presumably implemented in optimized C. Of course, they're right to optimize this way, and it's to Python's credit that it's possible to leverage this approach so successfully using only the standard-library, but I think my earlier point stands.

oefrha 6y ago
I practically linked to _collections._count_elements already (linked Counter.update instead because I thought linking to the call site is clearer), but here it is: https://github.com/python/cpython/blob/2fe408497e6838b6fb761e42e8f8ffc70bd6f3b1/Lib/collections/__init__.py#L519-L523 https://github.com/python/cpython/blob/2fe408497e6838b6fb761... Again, very straightforward, based on dict. Python itself does not function at all without the dict implementation since it's the underpinning of the object model. str is a builtin type. Calling str.split() a standard library method is... okay.
- MaxBarraclough 6y ago
  Thanks for the link, interesting that _count_elements is written in Python. At a glance it looks like the kind of thing that might benefit from being written in C, but presumably that's not the case. Perhaps because of the dynamic typing of both arguments? > Python itself does not function at all without the dict implementation since it's the underpinning of the object model. Sure, but I don't see the point here. > Calling str.split() a standard library method is... okay. For our purposes there's no reason to draw a distinction between standard-library functionality closely integrated into the language, and standard-library functionality that isn't. The relevant point is that computational work is being handed off to optimised C code. Again, if you're optimising Python, the smart move is indeed to make maximal use of the optimised machinery in the standard-library (or for that matter some other dependable library). My point still stands: it would be interesting to look at a problem that isn't amenable to this approach, where the performance of the Python interpreter itself would be brought to the fore by necessity. How easy it is to find such a problem will be a function of how good a job Python does of providing applicable optimised functionality in its standard-library. Perhaps something like computing matrix determinants? I don't know enough Python to say.
  - heavyset_go 6y ago
    > Perhaps because of the dynamic typing of both arguments? It wouldn't matter, you'd be dealing with PyObject pointers in C anyway.
    - MaxBarraclough 6y ago
      Right, that's what I meant. If the C code has to cope with dynamic typing anyway, there might be little scope to speed things up. The same isn't true for, say, string operations, where there might be plenty of opportunity to move tight loops from Python to C and speed things up considerably.
      - heavyset_go 6y ago
        Truthfully, I don't think optimization was a motivation for writing _count_elements() in Python or not. The CPython project doesn't prioritize optimization of the language or standard library unless there are clear performance gains to be made in the face of slow code. What most likely happened is someone wrote some code on a mailing list or bug report, and a maintainer included it as is. Reading the bug report that introduced Counter[1], the author states it is the simplest implementation they came up with, and Guido and other maintainers prioritized simplicity. [1] https://bugs.python.org/issue1696199 https://bugs.python.org/issue1696199
        MaxBarraclough 6y ago
        Interesting, thanks.
  - acdha 6y ago
    It can be interesting – especially if you also compare it to something like the PyPy JIT – but it runs afoul of the idiomatic angle since Python has had decades of recommended practice being to write code in Python and optimize the hotspots in C, which has led to very popular libraries like NumPy, PIL/Pillow, etc. becoming almost universal in community recommendations.
- benhoyt 6y ago
  That link shows that yes, "_count_elements" is implemented in Python, but right after it pulls in the C version if available (which it presumably is in CPython): try: # Load C helper function if available from _collections import _count_elements except ImportError: pass Here is the C version (with a comment a little way down describing the "fast path advantages": https://github.com/python/cpython/blob/93d33b47af70ede473f82d7953509a0607259c31/Modules/_collectionsmodule.c#L2277 https://github.com/python/cpython/blob/93d33b47af70ede473f82...
  - MaxBarraclough 6y ago
    Well spotted, thanks.

oefrha 6y ago

I practically linked to _collections._count_elements already (linked Counter.update instead because I thought linking to the call site is clearer), but here it is: https://github.com/python/cpython/blob/2fe408497e6838b6fb761e42e8f8ffc70bd6f3b1/Lib/collections/__init__.py#L519-L523 https://github.com/python/cpython/blob/2fe408497e6838b6fb761... Again, very straightforward, based on dict. Python itself does not function at all without the dict implementation since it's the underpinning of the object model. str is a builtin type. Calling str.split() a standard library method is... okay.

MaxBarraclough 6y ago
Thanks for the link, interesting that _count_elements is written in Python. At a glance it looks like the kind of thing that might benefit from being written in C, but presumably that's not the case. Perhaps because of the dynamic typing of both arguments? > Python itself does not function at all without the dict implementation since it's the underpinning of the object model. Sure, but I don't see the point here. > Calling str.split() a standard library method is... okay. For our purposes there's no reason to draw a distinction between standard-library functionality closely integrated into the language, and standard-library functionality that isn't. The relevant point is that computational work is being handed off to optimised C code. Again, if you're optimising Python, the smart move is indeed to make maximal use of the optimised machinery in the standard-library (or for that matter some other dependable library). My point still stands: it would be interesting to look at a problem that isn't amenable to this approach, where the performance of the Python interpreter itself would be brought to the fore by necessity. How easy it is to find such a problem will be a function of how good a job Python does of providing applicable optimised functionality in its standard-library. Perhaps something like computing matrix determinants? I don't know enough Python to say.
- heavyset_go 6y ago
  > Perhaps because of the dynamic typing of both arguments? It wouldn't matter, you'd be dealing with PyObject pointers in C anyway.
  - MaxBarraclough 6y ago
    Right, that's what I meant. If the C code has to cope with dynamic typing anyway, there might be little scope to speed things up. The same isn't true for, say, string operations, where there might be plenty of opportunity to move tight loops from Python to C and speed things up considerably.
    - heavyset_go 6y ago
      Truthfully, I don't think optimization was a motivation for writing _count_elements() in Python or not. The CPython project doesn't prioritize optimization of the language or standard library unless there are clear performance gains to be made in the face of slow code. What most likely happened is someone wrote some code on a mailing list or bug report, and a maintainer included it as is. Reading the bug report that introduced Counter[1], the author states it is the simplest implementation they came up with, and Guido and other maintainers prioritized simplicity. [1] https://bugs.python.org/issue1696199 https://bugs.python.org/issue1696199
      - MaxBarraclough 6y ago
        Interesting, thanks.
- acdha 6y ago
  It can be interesting – especially if you also compare it to something like the PyPy JIT – but it runs afoul of the idiomatic angle since Python has had decades of recommended practice being to write code in Python and optimize the hotspots in C, which has led to very popular libraries like NumPy, PIL/Pillow, etc. becoming almost universal in community recommendations.
benhoyt 6y ago
That link shows that yes, "_count_elements" is implemented in Python, but right after it pulls in the C version if available (which it presumably is in CPython): try: # Load C helper function if available from _collections import _count_elements except ImportError: pass Here is the C version (with a comment a little way down describing the "fast path advantages": https://github.com/python/cpython/blob/93d33b47af70ede473f82d7953509a0607259c31/Modules/_collectionsmodule.c#L2277 https://github.com/python/cpython/blob/93d33b47af70ede473f82...
- MaxBarraclough 6y ago
  Well spotted, thanks.