4 ms·

> Considering the computer has to read 40 GB of data from disk, map it to physical memory and then let the CPU has a rip of it No it doesn't? Maybe it needs to

by lmm 3y ago

> Considering the computer has to read 40 GB of data from disk, map it to physical memory and then let the CPU has a rip of it No it doesn't? Maybe it needs to set up page tables for 40GB, but it doesn't need to read the parts you're not using into memory, that's part of the point of memory-mapping like this - it sets up a page fault handler to load the page into memory when accessed, rather than needing to do it all up-front.

DHowett 3y ago
Given that the entire linear chain of comparisons (therefore, every instruction) needs to be evaluated for 2^32-1, it would indeed need to read and execute the entire 40GB file. The fact that it does so by faulting in each page before instructions in it can be executed doesn’t materially avoid having to read every byte. Clearly the author should have checked the larger numbers first to prevent this (:
- Centigonal 3y ago
  Software development needs to be driven by user needs. Clearly the best action in this scenario is to bundle in telemetry code that reports back which numbers are used with this program, assemble a ranking of the most frequently compared numbers in the real world, and use that to order the comparisons in v2 of the program.
  - satiric 3y ago
    Of course the modern "scaleable" solution is to ask ChatGPT if the number is even or odd, and then print ChatGPT's response.
    - constantly 3y ago
      Using selenium and chrome webdriver under the hood to do so, as well.
  - chrismorgan 3y ago
    It’s worth noting that good compilers can actually do a version of this: it’s called profile-guided optimisation <https://en.wikipedia.org/wiki/Profile-guided_optimization https://en.wikipedia.org/wiki/Profile-guided_optimization>. Not many projects use it, because it’s generally a bit of a bother (build a special version, run your profiling, then build everything all over again), but Firefox gets good mileage out of it. My vague recollection is a typical sort of speedup of 5%.
  - eviks 3y ago
    Don't forget to remove the least used 1% of the numbers to make it leaner!
- lmm 3y ago
  > Given that the entire linear chain of comparisons (therefore, every instruction) needs to be evaluated for 2^32-1, it would indeed need to read and execute the entire 40GB file. It does, but not step by step the way the part I quoted described - the reading from memory can be pipelined with the execution. (And it's an ideal access pattern - reading linearly once - so it wouldn't surprise me if other optimisations kicked in)
slabity 3y ago
Did you ignore this part that came a bit before that? > I decided to map the file into the address space instead of reading all of it. By doing this, we can just pretend that the entire file is already in memory and let the poor OS deal with fitting a 40 GB blob into virtual memory. Why take a vaguely rhetorical statement and then complain it contradicts a more concretely accurate statement before it?
- lmm 3y ago
  > Did you ignore this part that came a bit before that? No, just the opposite - I read that and that's exactly why I'm saying there was no need to read the whole thing into memory before starting to execute it. > Why take a vaguely rhetorical statement and then complain it contradicts a more concretely accurate statement before it? Because it's a contradiction in what they've written?
  - rocqua 3y ago
    The article doesn't state the entire program has to be read into memory before it starts executing. Instead the article states that during execution, for the highest inputs, the entire program needs to pass through memory for execution to finish.
rocqua 3y ago
For the highest possible input, all of the program needs to be read into memory. Just not all of it at the same time. I guess technically most of the RET instructions are jumped over, and so they don't need to be in memory. But that isn't how cache-lines (let alone pages) work.

by lmm 3y ago

DHowett 3y ago

Given that the entire linear chain of comparisons (therefore, every instruction) needs to be evaluated for 2^32-1, it would indeed need to read and execute the entire 40GB file. The fact that it does so by faulting in each page before instructions in it can be executed doesn’t materially avoid having to read every byte. Clearly the author should have checked the larger numbers first to prevent this (:

Centigonal 3y ago
Software development needs to be driven by user needs. Clearly the best action in this scenario is to bundle in telemetry code that reports back which numbers are used with this program, assemble a ranking of the most frequently compared numbers in the real world, and use that to order the comparisons in v2 of the program.
- satiric 3y ago
  Of course the modern "scaleable" solution is to ask ChatGPT if the number is even or odd, and then print ChatGPT's response.
  - constantly 3y ago
    Using selenium and chrome webdriver under the hood to do so, as well.
- chrismorgan 3y ago
  It’s worth noting that good compilers can actually do a version of this: it’s called profile-guided optimisation <https://en.wikipedia.org/wiki/Profile-guided_optimization https://en.wikipedia.org/wiki/Profile-guided_optimization>. Not many projects use it, because it’s generally a bit of a bother (build a special version, run your profiling, then build everything all over again), but Firefox gets good mileage out of it. My vague recollection is a typical sort of speedup of 5%.
- eviks 3y ago
  Don't forget to remove the least used 1% of the numbers to make it leaner!
lmm 3y ago
> Given that the entire linear chain of comparisons (therefore, every instruction) needs to be evaluated for 2^32-1, it would indeed need to read and execute the entire 40GB file. It does, but not step by step the way the part I quoted described - the reading from memory can be pipelined with the execution. (And it's an ideal access pattern - reading linearly once - so it wouldn't surprise me if other optimisations kicked in)

slabity 3y ago

Did you ignore this part that came a bit before that? > I decided to map the file into the address space instead of reading all of it. By doing this, we can just pretend that the entire file is already in memory and let the poor OS deal with fitting a 40 GB blob into virtual memory. Why take a vaguely rhetorical statement and then complain it contradicts a more concretely accurate statement before it?

lmm 3y ago
> Did you ignore this part that came a bit before that? No, just the opposite - I read that and that's exactly why I'm saying there was no need to read the whole thing into memory before starting to execute it. > Why take a vaguely rhetorical statement and then complain it contradicts a more concretely accurate statement before it? Because it's a contradiction in what they've written?
- rocqua 3y ago
  The article doesn't state the entire program has to be read into memory before it starts executing. Instead the article states that during execution, for the highest inputs, the entire program needs to pass through memory for execution to finish.

rocqua 3y ago

For the highest possible input, all of the program needs to be read into memory. Just not all of it at the same time. I guess technically most of the RET instructions are jumped over, and so they don't need to be in memory. But that isn't how cache-lines (let alone pages) work.