5 ms·

It seems like the built in heapq.merge() should be as fast as the implementation here. I mean if it's really just merging sorted lists, why wouldn't it be as fa

It seems like the built in heapq.merge() should be as fast as the implementation here. I mean if it's really just merging sorted lists, why wouldn't it be as fast as this implementation? edit: Okay one reason is that heapq.merge is written in python: https://github.com/python/cpython/blob/6252670732c68420c2a8b3f0259559e45eed7610/Lib/heapq.py#L314-L392 https://github.com/python/cpython/blob/6252670732c68420c2a8b... It might also be since the python version has more options (like arbitrarily many iterables), but I presume it's the fact that the extension is written in C.

typon 5y ago
Because it's written in python
- CogitoCogito 5y ago
  Re-writing it in C wouldn't automatically make much of a difference. Of course a C implementation wouldn't be slower (at minimum you could flatten out the byte-code sequence and use the generated C api calls), but it wouldn't necessarily be noticeably faster. Given the features of the python version, it might very well be the case that writing the same code in C wouldn't speed things up if the same use-cases were supported. Though I would be curious to know if it actually would speed up significantly.
  - masklinn 5y ago
    > Re-writing it in C wouldn't automatically make much of a difference. It probably would even with a line-for-line translation: you’d save all the interpreter overhead, function calls if there are any (I did not look), and most refcount traffic.
    - CogitoCogito 5y ago
      Maybe. It's true you would save a certain amount of interpreter overhead and some refcount. How much that would help is not clear to me. So really I just see any speedups pure speculation honestly. Besides the interesting question isn't really whether it speeds up or not (it obviously will speed up at least a little bit with any non-sane implementation), but how _much_ it speeds up. If you gain 1% honestly who cares. If you gain 30%, then that's more interesting. And how close can you get with this more general version in C to the version in the blog post that is using a simplified implementation without all the extra features. Anyway I am curious to know the answer, but I don't personally feel like writing out the implementation. If you do, I'd be interested in seeing the results.
      - CogitoCogito 5y ago
        I'm a bit amazed I've received downvotes for this post. I'm saying (1) you don't know how much this will speed up by going to C without trying it and (2) you don't know how much of the speed up in this case comes from the OP having written it in C and how much comes from the fact that it's a different algorithm. The fact that anyone would disagree with these (obviously true) statements is kind of incredible to me.
nightpool 5y ago
TFA explains this, although they never actually links the StackOverflow answer that they quote from. > CPython’s list.sort is implemented in C (avoiding interpreter overhead), while heapq.merge is mostly implemented in Python, and optimizes for the “many iterables” case in a way that slows the “two iterables” case. Going to the original StackOverflow answer, we can see the same user (ShadowRanger) expanding on this in a comment: https://stackoverflow.com/questions/464342/combining-two-sorted-lists-in-python https://stackoverflow.com/questions/464342/combining-two-sor... > The selling point for heapq.merge is that it doesn't require either the inputs or the outputs to be list; it can consume iterators/generators and produces a generator, so huge inputs/outputs (not stored in RAM at once) can be combined without swap thrashing. It also handles merging an arbitrary number of input iterables with lower overhead than might be expected (it uses a heap to coordinate the merging, so the overhead scales with the log of the number of iterables, not linearly, but as noted, that doesn't matter for the "two iterable" case).
- CogitoCogito 5y ago
  Yeah looking at the all the features of the heapq.merge() version, I kind of doubt implementing it in C would speed it up much at all. edit: Yeah I now see where the author mentioned the design philosophy of the python version. It was a bit burried, but it answers my question like you say. I personally find that to be the most interesting part.
deleted 5y ago
[deleted]

typon 5y ago

Because it's written in python

CogitoCogito 5y ago
Re-writing it in C wouldn't automatically make much of a difference. Of course a C implementation wouldn't be slower (at minimum you could flatten out the byte-code sequence and use the generated C api calls), but it wouldn't necessarily be noticeably faster. Given the features of the python version, it might very well be the case that writing the same code in C wouldn't speed things up if the same use-cases were supported. Though I would be curious to know if it actually would speed up significantly.
- masklinn 5y ago
  > Re-writing it in C wouldn't automatically make much of a difference. It probably would even with a line-for-line translation: you’d save all the interpreter overhead, function calls if there are any (I did not look), and most refcount traffic.
  - CogitoCogito 5y ago
    Maybe. It's true you would save a certain amount of interpreter overhead and some refcount. How much that would help is not clear to me. So really I just see any speedups pure speculation honestly. Besides the interesting question isn't really whether it speeds up or not (it obviously will speed up at least a little bit with any non-sane implementation), but how _much_ it speeds up. If you gain 1% honestly who cares. If you gain 30%, then that's more interesting. And how close can you get with this more general version in C to the version in the blog post that is using a simplified implementation without all the extra features. Anyway I am curious to know the answer, but I don't personally feel like writing out the implementation. If you do, I'd be interested in seeing the results.
    - CogitoCogito 5y ago
      I'm a bit amazed I've received downvotes for this post. I'm saying (1) you don't know how much this will speed up by going to C without trying it and (2) you don't know how much of the speed up in this case comes from the OP having written it in C and how much comes from the fact that it's a different algorithm. The fact that anyone would disagree with these (obviously true) statements is kind of incredible to me.

nightpool 5y ago

TFA explains this, although they never actually links the StackOverflow answer that they quote from. > CPython’s list.sort is implemented in C (avoiding interpreter overhead), while heapq.merge is mostly implemented in Python, and optimizes for the “many iterables” case in a way that slows the “two iterables” case. Going to the original StackOverflow answer, we can see the same user (ShadowRanger) expanding on this in a comment: https://stackoverflow.com/questions/464342/combining-two-sorted-lists-in-python https://stackoverflow.com/questions/464342/combining-two-sor... > The selling point for heapq.merge is that it doesn't require either the inputs or the outputs to be list; it can consume iterators/generators and produces a generator, so huge inputs/outputs (not stored in RAM at once) can be combined without swap thrashing. It also handles merging an arbitrary number of input iterables with lower overhead than might be expected (it uses a heap to coordinate the merging, so the overhead scales with the log of the number of iterables, not linearly, but as noted, that doesn't matter for the "two iterable" case).

CogitoCogito 5y ago
Yeah looking at the all the features of the heapq.merge() version, I kind of doubt implementing it in C would speed it up much at all. edit: Yeah I now see where the author mentioned the design philosophy of the python version. It was a bit burried, but it answers my question like you say. I personally find that to be the most interesting part.

deleted 5y ago

[deleted]