6 ms·

This is a bad take. ripgrep, to my knowledge, cannot be written in a higher level language without becoming a lot slower.[1] And yet, if I removed its use of pa

This is a bad take. ripgrep, to my knowledge, cannot be written in a higher level language without becoming a lot slower.[1] And yet, if I removed its use of parallelism by default, there will be a significantly degraded user experience by virtue of it being a lot slower. This isn't an "obsession." It's engineering. [1] - I make this claim loosely. Absence of evidence isn't evidence of absence and all that. But if I saw ripgrep implemented in, say, Python and it matched speed in the majority of cases, I would learn something.

pjmlp 6y ago
Python isn't really something I would even think as possible example, Common Lisp, D, Nim, Swift, most likely.
- cb321 6y ago
  Cython with all the appropriate cdef type declarations can match C and so might also do it. Not sure Cython exactly counts as "Python"..it's more a superset/dialect { and I also doubt such a port would hold many lessons for @burntsushi, but it bore noting. }
- burntsushi 6y ago
  So? I said, "higher level language." I didn't say, "Python specifically." I would guess D could do it. I don't know enough about Nim or Swift. I would learn something if Common Lisp did it. I'd also learn something if Haskell or Go did it.
  - cb321 6y ago
    I am not trying to contradict anyone here, but any language mature enough to have an impl/way to not have arbitrary performance ceilings needs access to inline assembly/SIMD. Cython/Nim/SBCL can all do that..probably Haskell..Not so sure about Go or Swift. Anyway, many languages can respond well to optimization effort. I doubt anyone disagrees. At the point of realizing the above no ceiling bit, the argument devolves to more one about (fairly subjective) high/low levelness of the code itself/the effort applied to optimizing, not about the language the code is written in. So, it's not very informative and tends to go nowhere (EDIT: especially when the focus is on a single, highly optimized tool like `rg` as opposed to "broad demographic traits" of pools of developers, and "levelness" is often somewhat subjective, too).
    - burntsushi 6y ago
      You're missing the context I think. Look at what I was responding to in my initial message in this thread: > If you have an architecture where you can afford real parallelism you can afford higher level languages anyway. My response is, "no you can't, and here's an example." > but any language mature enough to have an impl/way to not have arbitrary performance ceilings needs access to inline assembly/SIMD If you ported ripgrep to Python and the vast majority of it was in C or Assembly, then I would say, "that's consistent with my claim: your port isn't in Python." My claim is likely more subtle than you might imagine. ripgrep has many performance sensitive areas. It isn't enough to, say, implement the regex engine in C and write some glue code around that. It won't be good enough. (Or at least, that's my claim. If I'm proven wrong, then as I said, I'd learn something.) > At the point of realizing the above no ceiling bit, the argument devolves to more one about (fairly subjective) high/low levelness of the code itself/the effort applied to optimizing, not about the language the code is written in. So, it's not very informative and tends to go nowhere. I agree that it's pretty subjective and wishy washy. But when someone goes around talking nonsense like "if parallelism is a benefit then you're fine with a higher level language," you kind of have to work with what you got. A good counter example to that nonsense is to show a program that is written is a "lower" level language that simultaneously benefits from parallelism and wouldn't be appropriate to do in a higher level language. I happen to have one of those in my back-pocket. :-) (xsv is another example. Compare it with csvkit, even though csvkit's CSV parser is written in C, it's still dog slow, because the code around the CSV parser matters.)
      - cb321 6y ago
        Ok. "Afford parallelism => afford high level" with the implication of HL=slow does sound pretty off base. So, fair enough. FWIW, as per your subtle claim, it all seems pretty hot spot optimizable to me, at least if you include the memchr/utf8-regex engine in "hot spot". I do think the entire framing has much measurement vagueness ("hot", "vast majority", "levelness", and others) & is unlikely to be helpful, as explained. In terms of "evidence", I do not know of a competitor who has put the care into such a tool to even try to measure, though. { And I love rg. Many thanks and no offense at all was intended! }
  - eru 6y ago
    I suspect Don Stewart might be able to do it in Haskell. That's basically by knowing enough about GHC to carefully trigger all the relevant optimizations.
    - burntsushi 6y ago
      Hah. I'm highly skeptical. But I suppose if anyone could do it, it'd be him. I would certainly learn something. :-) I've tried optimizing Haskell code myself before. It did not go well. It was an implementation of the Viterbi algorithm actually. We ported it to Standard ML and C and measured performance. mlton did quite well at least. We published a paper about the process of writing Viterbi in Haskell in ICFP a few years back: https://dl.acm.org/doi/pdf/10.1145/2364527.2364560?casa_token=19aYVUM_DGsAAAAA:OpdVjP1Q33EsnlQjk-969AGQN0maJarkEa78xjjsJGWT1ytxMrnNuHdgEkGWAFa3aIj4Hi7BTPEixQ https://dl.acm.org/doi/pdf/10.1145/2364527.2364560?casa_toke... Unfortunately, the performance aspect of it was only a small part, and we didn't talk about the C or mlton ports in the paper.
      - eru 6y ago
        Very interesting! I suspect you could make a very Haskell-like language that's also really fast, but you'd have to base it on linear types from the ground up, and make everything total by default. (Hide non-total parts behind some type 'tag' like we do with IO in current Haskell (and have something like unsafePerformPartial when you know your code is total, but can't convince the compiler).) That way the compiler can be much more aggressive about making things strict.

pjmlp 6y ago

Python isn't really something I would even think as possible example, Common Lisp, D, Nim, Swift, most likely.

cb321 6y ago
Cython with all the appropriate cdef type declarations can match C and so might also do it. Not sure Cython exactly counts as "Python"..it's more a superset/dialect { and I also doubt such a port would hold many lessons for @burntsushi, but it bore noting. }
burntsushi 6y ago
So? I said, "higher level language." I didn't say, "Python specifically." I would guess D could do it. I don't know enough about Nim or Swift. I would learn something if Common Lisp did it. I'd also learn something if Haskell or Go did it.
- cb321 6y ago
  I am not trying to contradict anyone here, but any language mature enough to have an impl/way to not have arbitrary performance ceilings needs access to inline assembly/SIMD. Cython/Nim/SBCL can all do that..probably Haskell..Not so sure about Go or Swift. Anyway, many languages can respond well to optimization effort. I doubt anyone disagrees. At the point of realizing the above no ceiling bit, the argument devolves to more one about (fairly subjective) high/low levelness of the code itself/the effort applied to optimizing, not about the language the code is written in. So, it's not very informative and tends to go nowhere (EDIT: especially when the focus is on a single, highly optimized tool like `rg` as opposed to "broad demographic traits" of pools of developers, and "levelness" is often somewhat subjective, too).
  - burntsushi 6y ago
    You're missing the context I think. Look at what I was responding to in my initial message in this thread: > If you have an architecture where you can afford real parallelism you can afford higher level languages anyway. My response is, "no you can't, and here's an example." > but any language mature enough to have an impl/way to not have arbitrary performance ceilings needs access to inline assembly/SIMD If you ported ripgrep to Python and the vast majority of it was in C or Assembly, then I would say, "that's consistent with my claim: your port isn't in Python." My claim is likely more subtle than you might imagine. ripgrep has many performance sensitive areas. It isn't enough to, say, implement the regex engine in C and write some glue code around that. It won't be good enough. (Or at least, that's my claim. If I'm proven wrong, then as I said, I'd learn something.) > At the point of realizing the above no ceiling bit, the argument devolves to more one about (fairly subjective) high/low levelness of the code itself/the effort applied to optimizing, not about the language the code is written in. So, it's not very informative and tends to go nowhere. I agree that it's pretty subjective and wishy washy. But when someone goes around talking nonsense like "if parallelism is a benefit then you're fine with a higher level language," you kind of have to work with what you got. A good counter example to that nonsense is to show a program that is written is a "lower" level language that simultaneously benefits from parallelism and wouldn't be appropriate to do in a higher level language. I happen to have one of those in my back-pocket. :-) (xsv is another example. Compare it with csvkit, even though csvkit's CSV parser is written in C, it's still dog slow, because the code around the CSV parser matters.)
    - cb321 6y ago
      Ok. "Afford parallelism => afford high level" with the implication of HL=slow does sound pretty off base. So, fair enough. FWIW, as per your subtle claim, it all seems pretty hot spot optimizable to me, at least if you include the memchr/utf8-regex engine in "hot spot". I do think the entire framing has much measurement vagueness ("hot", "vast majority", "levelness", and others) & is unlikely to be helpful, as explained. In terms of "evidence", I do not know of a competitor who has put the care into such a tool to even try to measure, though. { And I love rg. Many thanks and no offense at all was intended! }
- eru 6y ago
  I suspect Don Stewart might be able to do it in Haskell. That's basically by knowing enough about GHC to carefully trigger all the relevant optimizations.
  - burntsushi 6y ago
    Hah. I'm highly skeptical. But I suppose if anyone could do it, it'd be him. I would certainly learn something. :-) I've tried optimizing Haskell code myself before. It did not go well. It was an implementation of the Viterbi algorithm actually. We ported it to Standard ML and C and measured performance. mlton did quite well at least. We published a paper about the process of writing Viterbi in Haskell in ICFP a few years back: https://dl.acm.org/doi/pdf/10.1145/2364527.2364560?casa_token=19aYVUM_DGsAAAAA:OpdVjP1Q33EsnlQjk-969AGQN0maJarkEa78xjjsJGWT1ytxMrnNuHdgEkGWAFa3aIj4Hi7BTPEixQ https://dl.acm.org/doi/pdf/10.1145/2364527.2364560?casa_toke... Unfortunately, the performance aspect of it was only a small part, and we didn't talk about the C or mlton ports in the paper.
    - eru 6y ago
      Very interesting! I suspect you could make a very Haskell-like language that's also really fast, but you'd have to base it on linear types from the ground up, and make everything total by default. (Hide non-total parts behind some type 'tag' like we do with IO in current Haskell (and have something like unsafePerformPartial when you know your code is total, but can't convince the compiler).) That way the compiler can be much more aggressive about making things strict.