3 ms·

> That's one of the constraints of the challenge: it has to be able to work on a stream. I cannot find any stream constraint in either the article or the count

by cb321 6y ago

> That's one of the constraints of the challenge: it has to be able to work on a stream. I cannot find any stream constraint in either the article or the countwords repo. He just says "standard input" and his "test.sh" uses "<kjvbible_x10.txt". You can mmap stdin/fd 0 after an `fstat(0,..)` no problemo. Can it fail and should you check errors? Sure (as can accessing stdin in any way, actually). He even mentions memory-mapped IO as a further way to go in the article in the C part.

burntsushi 6y ago
From the OP: > Memory: don’t read whole file into memory. Buffering it line-by-line is okay, or in chunks with a maximum buffer size of 64KB. That said, it’s okay to keep the whole word-count map in memory (we’re assuming the input is text in a real language, not full of randomized unique words). A shorter but less precise way of saying that is, "make the program work on streams." > You can mmap stdin/fd 0 after an `fstat(0,..)` no problemo. Can it fail and should you check errors? Sure (as can accessing stdin in any way, actually). Of course. And when it fails, what do you do? You defer to something that can handle a stream! Which is exactly the problem in the OP.
- cb321 6y ago
  I disagree. mmap will demand page into memory - typically reading 4K at a time off storage (though really the buffer cache in all these timings). Much less than 64K. Were the file bigger than RAM/were there competition, it would also evict earlier pages. It's really just another way to "buffer" without worrying about all the fuss in user space, and I don't think you're going to convince me otherwise. I mean, MAP_POPULATE might violate the idea, but that is a very special case of mmap. Honestly, I think the author himself saying memory-mapped IO is a forward direction but "enough for now!" is pretty conclusive that he didn't think it was a forbidden optimization direction. I think you are over interpreting his early step-by-step style language explaining finite memory as a strict spec, or perhaps he shared an earlier draft of the article with you before he wrote that. It's fine to fail over to a stream, but often mmap is faster, as I know you know.
  - burntsushi 6y ago
    If you mmap'd a file, how do you keep its maximum memory usage to 64KB? I actually don't know the answer to that question. It's definitely not the default. You don't get to control it. The OS does. > It's fine to fail over to a stream, but often mmap is faster, as I know you know. But that's exactly the point. You literally cannot use mmap in all cases, either because you just can't or because it's actually slower. And in those cases, you need to fail over to a streaming implementation. And that streaming implementation needs to be fast too. And that's what this benchmark is. If you submitted a program that only used mmaps, and I sent a stream into that program, it would fail. So then you would need to modify the program to handle streams. And your strategy for dealing with mmaps couldn't be used. So then you'd need to optimize your handling of streams. Which is exactly what the programs in the OP are doing. So in the end, mmaps are a distraction for a benchmark like this, and I suspect that's why the OP didn't bother with them.
    - cb321 6y ago
      You keep ignoring the author literally opening it up as an avenue in: >I’m sure there’s further you could go with the C version: investigate memory-mapped I/O, avoid processing byte-at-a-time, use a fancier data structure for counting, etc. But this is quite enough for now! This subthread started with bluetomcat talking about the optimized C and what experienced C devs might do. That strikes me as fair game to open up discussion of alternative IO anyway even if the author hadn't already (which he clearly did, as quoted). So, that's two reasons it's worth bringing up, and I was never criticizing your program! If what you are on about is "Who wins what scorecard against what arbitrary constraints" or "My hands were tied, really!" or whatever, then, sorry, but this benchmark is too uncontrolled for great answers even on its own terms. Various stdio-using things would be "out of constraints" if a system was configured with bigger than 64K default buffers anyway which is certainly possible, if unlikely, today. None of the sample programs or the test harness "check" for that. Some of the languages may not be able to ensure it. Using that to leapfrog to "only streams" is a stretch. Is CPU freq scaling controlled? Min of N trials to filter background noise/get repeatability? Even simple mean+-sdev? No, no, and no. And probably four more things. Beyond all of that, I also don't think that's what this subthread was ever about. bluetomcat's opening was literally the opposite - equivalent to "real devs would do xyz implicitly independent of the arbitrary constraints posed if performance is paramount"..seemingly a follow up on my quote from the author. He can of course chime in if I misread that. Presumably, the author would have had to relax that already problematic 64K constraint when moving on to mmap (which moving on he might have done if the article were fewer languages or if he had just done it that way first in his open coded C). The positions you seem dug into here seems to me "don't mention mmap to people questioning the posing of the contest even though the author did" or "you cannot default to mmap and fail over like fstat||mmap||do_streams||aiie_noStdInEven". Yes, which is faster varies by OS/situation. So? Maybe "experienced" C/whatever devs know their situation. (You use mmap in ripgrep...). Maybe these are all honest communication errors, but I don't think your positions are very tenable. As I mentioned in a few places, performance conclusions here are harder than they might look. As for "distractions", one might say that about literally all the optimized variants, including their numbers in the table since the numbers are likely to change more. The article might be stronger to focus on only the simple variants of all the rest, leaving the optimized ones for the github repo and weird "contest rule" debates on the github issues. Anyway, to add a little more actual information for passersby less dug in to defending some weird position like "", Nim's stdlib has a trie in critbits module. So, that test is "in bounds" and an easy experiment someone might enjoy. Have a nice day.

by cb321 6y ago

burntsushi 6y ago

From the OP: > Memory: don’t read whole file into memory. Buffering it line-by-line is okay, or in chunks with a maximum buffer size of 64KB. That said, it’s okay to keep the whole word-count map in memory (we’re assuming the input is text in a real language, not full of randomized unique words). A shorter but less precise way of saying that is, "make the program work on streams." > You can mmap stdin/fd 0 after an `fstat(0,..)` no problemo. Can it fail and should you check errors? Sure (as can accessing stdin in any way, actually). Of course. And when it fails, what do you do? You defer to something that can handle a stream! Which is exactly the problem in the OP.

cb321 6y ago
I disagree. mmap will demand page into memory - typically reading 4K at a time off storage (though really the buffer cache in all these timings). Much less than 64K. Were the file bigger than RAM/were there competition, it would also evict earlier pages. It's really just another way to "buffer" without worrying about all the fuss in user space, and I don't think you're going to convince me otherwise. I mean, MAP_POPULATE might violate the idea, but that is a very special case of mmap. Honestly, I think the author himself saying memory-mapped IO is a forward direction but "enough for now!" is pretty conclusive that he didn't think it was a forbidden optimization direction. I think you are over interpreting his early step-by-step style language explaining finite memory as a strict spec, or perhaps he shared an earlier draft of the article with you before he wrote that. It's fine to fail over to a stream, but often mmap is faster, as I know you know.
- burntsushi 6y ago
  If you mmap'd a file, how do you keep its maximum memory usage to 64KB? I actually don't know the answer to that question. It's definitely not the default. You don't get to control it. The OS does. > It's fine to fail over to a stream, but often mmap is faster, as I know you know. But that's exactly the point. You literally cannot use mmap in all cases, either because you just can't or because it's actually slower. And in those cases, you need to fail over to a streaming implementation. And that streaming implementation needs to be fast too. And that's what this benchmark is. If you submitted a program that only used mmaps, and I sent a stream into that program, it would fail. So then you would need to modify the program to handle streams. And your strategy for dealing with mmaps couldn't be used. So then you'd need to optimize your handling of streams. Which is exactly what the programs in the OP are doing. So in the end, mmaps are a distraction for a benchmark like this, and I suspect that's why the OP didn't bother with them.
  - cb321 6y ago
    You keep ignoring the author literally opening it up as an avenue in: >I’m sure there’s further you could go with the C version: investigate memory-mapped I/O, avoid processing byte-at-a-time, use a fancier data structure for counting, etc. But this is quite enough for now! This subthread started with bluetomcat talking about the optimized C and what experienced C devs might do. That strikes me as fair game to open up discussion of alternative IO anyway even if the author hadn't already (which he clearly did, as quoted). So, that's two reasons it's worth bringing up, and I was never criticizing your program! If what you are on about is "Who wins what scorecard against what arbitrary constraints" or "My hands were tied, really!" or whatever, then, sorry, but this benchmark is too uncontrolled for great answers even on its own terms. Various stdio-using things would be "out of constraints" if a system was configured with bigger than 64K default buffers anyway which is certainly possible, if unlikely, today. None of the sample programs or the test harness "check" for that. Some of the languages may not be able to ensure it. Using that to leapfrog to "only streams" is a stretch. Is CPU freq scaling controlled? Min of N trials to filter background noise/get repeatability? Even simple mean+-sdev? No, no, and no. And probably four more things. Beyond all of that, I also don't think that's what this subthread was ever about. bluetomcat's opening was literally the opposite - equivalent to "real devs would do xyz implicitly independent of the arbitrary constraints posed if performance is paramount"..seemingly a follow up on my quote from the author. He can of course chime in if I misread that. Presumably, the author would have had to relax that already problematic 64K constraint when moving on to mmap (which moving on he might have done if the article were fewer languages or if he had just done it that way first in his open coded C). The positions you seem dug into here seems to me "don't mention mmap to people questioning the posing of the contest even though the author did" or "you cannot default to mmap and fail over like fstat||mmap||do_streams||aiie_noStdInEven". Yes, which is faster varies by OS/situation. So? Maybe "experienced" C/whatever devs know their situation. (You use mmap in ripgrep...). Maybe these are all honest communication errors, but I don't think your positions are very tenable. As I mentioned in a few places, performance conclusions here are harder than they might look. As for "distractions", one might say that about literally all the optimized variants, including their numbers in the table since the numbers are likely to change more. The article might be stronger to focus on only the simple variants of all the rest, leaving the optimized ones for the github repo and weird "contest rule" debates on the github issues. Anyway, to add a little more actual information for passersby less dug in to defending some weird position like "", Nim's stdlib has a trie in critbits module. So, that test is "in bounds" and an easy experiment someone might enjoy. Have a nice day.