5 ms·

Isn't this simply bound by the speed of the disk? Surely none of the suggested optimizations (SIMD, multi-threading) are relevant. It would also depend of how

Isn't this simply bound by the speed of the disk? Surely none of the suggested optimizations (SIMD, multi-threading) are relevant. It would also depend of how many different stations there are and what they are for the hash lookup, but seriously I doubt this will be anything measurable compared to I/O.

deleted 3y ago
[deleted]
rockwotj 3y ago
A few things: Disk access can certainly be parallelized, and NVMe is blazing fast, so the bottleneck is more the CPU than disk. There are systems that are built around around modern hardware that realize this (redpanda.com, where I work is one such example) Parsing is a lot of the compute time and some SIMD tricks like SWAR for finding delimiters can be helpful. Stringzilla is a cool library if you want to see a clean implementation of these algorithms: https://github.com/ashvardanian/StringZilla https://github.com/ashvardanian/StringZilla See my reply here about the file being cached completely in memory after the first run: https://news.ycombinator.com/item?id=38864034 https://news.ycombinator.com/item?id=38864034
- londons_explore 3y ago
  I would hope that any reasonably performant implementation would be faster not only than NVMe, but also faster than CPU to RAM data transfers. The AMD EPYC-Milan in the test server supports memory reads at 150 gigabytes/sec, but thats a 32 core machine, and our test only gets 8 of those cores, so we probably can't expect more than 37 gigabytes per second of read bandwidth. The total file is ~12 gigabytes, so we should expect to be able to get the task done in 0.3 seconds or so. There are only ~400 weather stations, so all the results fit in cache. It's unclear if it might be faster to avoid converting ascii to a float - it might be faster to add up all the ascii numbers, and figure out how to convert to a float only when you have the total.
  - anonymoushn 3y ago
    It looks like all existing solutions are too slow by a huge factor then :)
  - vintermann 3y ago
    Are you sure that would give the same result? The first thing that struck me about this challenge is that there's going to be floating point precision issues.
    - londons_explore 3y ago
      All the data is only to one decimal place. You can shift the decimal place and do the whole thing with int's and get a 100% precise result.
      - vintermann 3y ago
        You can, but will it be the same result? :) binary floating point can't represent 0.1 or 0.2 exactly. To be fair, with only additions, and only a billion of them, you're probably fine working in floating point and rounding to one decimal in the end.
        bmicraft 3y ago
        Just x10 it and count in integers?
        vintermann 3y ago
        I said that works here. The point is that floating point may give a different answer.
  - codeflo 3y ago
    > any reasonably performant implementation would be faster not only than NVMe Saturating NVMe bandwidth is wicked hard if you don't know what you're doing. Most people think they're I/O bound because profiling hinted at some read() function somewhere, when in fact they're CPU bound in a runtime layer they don't understand.
NavinF 3y ago
Totally depends on your workload and hardware. I have a normal consumer SSD in my desktop and it can easily sustain 7GB/s (56gbps) as long as I only use 700GB of the 2TB available. A normal server has enough PCIe lanes for 15 SSDs like mine so a normal server's IO bandwidth is comparable to its memory bandwidth. More expensive servers have faster lanes (PCIe 5.0) and more of those lanes. Anyway the OP's file only has 1B rows so it'll be ~1GB compressed which fits in memory after the first discarded run. IO bandwidth shouldn't matter in this scenario: > All submissions will be evaluated by running the program on a Hetzner Cloud CCX33 instance (8 dedicated vCPU, 32 GB RAM). The time program is used for measuring execution times, i.e. end-to-end times are measured. Each contender will be run five times in a row. The slowest and the fastest runs are discarded Edit: The github repo says it's 12 GB uncompressed. That confirms that IO bandwidth doesn't matter
D4ckard 3y ago
Daniel Lemire has an interesting talk on this: https://www.youtube.com/watch?v=wlvKAT7SZIQ https://www.youtube.com/watch?v=wlvKAT7SZIQ. They key takeaway is that the disk is rarely the bottleneck.
- codeflo 3y ago
  It's an old bit of wisdom that's hard to stamp out. That's partly because anything that you don't understand below you in the runtime stack looks like "I/O" during profiling, so the misunderstanding perpetuates even among people who attempt to take a closer look, but don't know enough.
lessbergstein 3y ago
Yes, this is an extremely trivial problem. Anybody who knows how to program in more than one language is going to find this silly. awk or perl would finish it before jit compilation gets started.
- viraptor 3y ago
  It's a trivial problem to implement, but not trivial to implement faster than others. Awk won't beat solutions that are clever about multiple read queues and parallel processing.
- Jaxan 3y ago
  Please try it out in awk. It would be interesting to see whether awk can do this in a few seconds.
- declaredapple 3y ago
  Bit of an update, the record is now 8 seconds in java. I have tried 2 naive awk implementations and both took 10x the basic java implementation btw (I'm sure it too can be optimized).
  - lessbergstein 3y ago
    Just stick to Java
mikewarot 3y ago
Clearly the fastest way to parse this is to load it all into RAM, and work backwards from the end. That has the advantage of putting the digits in ascending order, and then the delimiter, then the string... until EOF or NL is encountered.
throwaway2037 3y ago
I agree. From here: https://news.ycombinator.com/item?id=38865942 https://news.ycombinator.com/item?id=38865942 << Just clarified this in the README: * Input value ranges are as follows: - Station name: non null UTF-8 string of min length 1 character and max length 100 characters - Temperature value: non null double between -99.9 (inclusive) and 99.9 (inclusive), always with one fractional digit >> If we assume worst case entries: -99.9;<100 char station name> That is 106 chars plus newline (1 or 2 chars). That could be 108 GB of data! And, I want to be so picky here: The README says "UTF-8" and "max length 100 characters". Eh, we could start a holy war here arguing about what does a character mean in UTF-8. Let's be generous and assume it means one (8-bit) byte (like C). I have good faith in the original author! Some Googling tells me that the current fastest PCIe Gen5 NVMe drive is Crucial T700 w/ Sequential read (max., MB/s) @ 12,400. That is 8.7 seconds to read 108 GB of data. A few other comments mentioned that the sample file is only 12 GB, so that is 1 second, and 100% can be cached by Linux kernel for 2nd and later reads. However, if the test file is greater than 32 GB, you are definitely screwed for file system caching. You will have to pay a multi-second "I/O tax" to read the file each time. This seems to far outweigh any computation time. Thoughts? Last, I still think this is a great challenge. I think I just found my next interview question. This question is easy to understand and program a basic implementation. Further discussion can be fractally complex about the myriad of optimizations that could be applied. No trolling: Can you imagine if someone tries this exercise in Python? There are a goofy amount of optimizations to deal with huge data in that language thanks to SciPy, Pandas and other friends. I am sure someone can write an insanely performant solution. (I know, I know: The original challenge says no external dependencies.)
usefulcat 3y ago
> Isn't this simply bound by the speed of the disk? Depends on the OS and filesystem being used. The input file is ~12GB, and it's being run 5 times on a machine with 32GB, so after the first run the file could be cached entirely in memory. For example, Linux using ext2 would probably cache the entire file after the first run, but using ZFS it probably would not.

deleted 3y ago

[deleted]

rockwotj 3y ago

A few things: Disk access can certainly be parallelized, and NVMe is blazing fast, so the bottleneck is more the CPU than disk. There are systems that are built around around modern hardware that realize this (redpanda.com, where I work is one such example) Parsing is a lot of the compute time and some SIMD tricks like SWAR for finding delimiters can be helpful. Stringzilla is a cool library if you want to see a clean implementation of these algorithms: https://github.com/ashvardanian/StringZilla https://github.com/ashvardanian/StringZilla See my reply here about the file being cached completely in memory after the first run: https://news.ycombinator.com/item?id=38864034 https://news.ycombinator.com/item?id=38864034

londons_explore 3y ago
I would hope that any reasonably performant implementation would be faster not only than NVMe, but also faster than CPU to RAM data transfers. The AMD EPYC-Milan in the test server supports memory reads at 150 gigabytes/sec, but thats a 32 core machine, and our test only gets 8 of those cores, so we probably can't expect more than 37 gigabytes per second of read bandwidth. The total file is ~12 gigabytes, so we should expect to be able to get the task done in 0.3 seconds or so. There are only ~400 weather stations, so all the results fit in cache. It's unclear if it might be faster to avoid converting ascii to a float - it might be faster to add up all the ascii numbers, and figure out how to convert to a float only when you have the total.
- anonymoushn 3y ago
  It looks like all existing solutions are too slow by a huge factor then :)
- vintermann 3y ago
  Are you sure that would give the same result? The first thing that struck me about this challenge is that there's going to be floating point precision issues.
  - londons_explore 3y ago
    All the data is only to one decimal place. You can shift the decimal place and do the whole thing with int's and get a 100% precise result.
    - vintermann 3y ago
      You can, but will it be the same result? :) binary floating point can't represent 0.1 or 0.2 exactly. To be fair, with only additions, and only a billion of them, you're probably fine working in floating point and rounding to one decimal in the end.
      - bmicraft 3y ago
        Just x10 it and count in integers?
        vintermann 3y ago
        I said that works here. The point is that floating point may give a different answer.
- codeflo 3y ago
  > any reasonably performant implementation would be faster not only than NVMe Saturating NVMe bandwidth is wicked hard if you don't know what you're doing. Most people think they're I/O bound because profiling hinted at some read() function somewhere, when in fact they're CPU bound in a runtime layer they don't understand.

NavinF 3y ago

Totally depends on your workload and hardware. I have a normal consumer SSD in my desktop and it can easily sustain 7GB/s (56gbps) as long as I only use 700GB of the 2TB available. A normal server has enough PCIe lanes for 15 SSDs like mine so a normal server's IO bandwidth is comparable to its memory bandwidth. More expensive servers have faster lanes (PCIe 5.0) and more of those lanes. Anyway the OP's file only has 1B rows so it'll be ~1GB compressed which fits in memory after the first discarded run. IO bandwidth shouldn't matter in this scenario: > All submissions will be evaluated by running the program on a Hetzner Cloud CCX33 instance (8 dedicated vCPU, 32 GB RAM). The time program is used for measuring execution times, i.e. end-to-end times are measured. Each contender will be run five times in a row. The slowest and the fastest runs are discarded Edit: The github repo says it's 12 GB uncompressed. That confirms that IO bandwidth doesn't matter

D4ckard 3y ago

Daniel Lemire has an interesting talk on this: https://www.youtube.com/watch?v=wlvKAT7SZIQ https://www.youtube.com/watch?v=wlvKAT7SZIQ. They key takeaway is that the disk is rarely the bottleneck.

codeflo 3y ago
It's an old bit of wisdom that's hard to stamp out. That's partly because anything that you don't understand below you in the runtime stack looks like "I/O" during profiling, so the misunderstanding perpetuates even among people who attempt to take a closer look, but don't know enough.

lessbergstein 3y ago

Yes, this is an extremely trivial problem. Anybody who knows how to program in more than one language is going to find this silly. awk or perl would finish it before jit compilation gets started.

viraptor 3y ago
It's a trivial problem to implement, but not trivial to implement faster than others. Awk won't beat solutions that are clever about multiple read queues and parallel processing.
Jaxan 3y ago
Please try it out in awk. It would be interesting to see whether awk can do this in a few seconds.
declaredapple 3y ago
Bit of an update, the record is now 8 seconds in java. I have tried 2 naive awk implementations and both took 10x the basic java implementation btw (I'm sure it too can be optimized).
- lessbergstein 3y ago
  Just stick to Java

mikewarot 3y ago

Clearly the fastest way to parse this is to load it all into RAM, and work backwards from the end. That has the advantage of putting the digits in ascending order, and then the delimiter, then the string... until EOF or NL is encountered.

throwaway2037 3y ago

I agree. From here: https://news.ycombinator.com/item?id=38865942 https://news.ycombinator.com/item?id=38865942 << Just clarified this in the README: * Input value ranges are as follows: - Station name: non null UTF-8 string of min length 1 character and max length 100 characters - Temperature value: non null double between -99.9 (inclusive) and 99.9 (inclusive), always with one fractional digit >> If we assume worst case entries: -99.9;<100 char station name> That is 106 chars plus newline (1 or 2 chars). That could be 108 GB of data! And, I want to be so picky here: The README says "UTF-8" and "max length 100 characters". Eh, we could start a holy war here arguing about what does a character mean in UTF-8. Let's be generous and assume it means one (8-bit) byte (like C). I have good faith in the original author! Some Googling tells me that the current fastest PCIe Gen5 NVMe drive is Crucial T700 w/ Sequential read (max., MB/s) @ 12,400. That is 8.7 seconds to read 108 GB of data. A few other comments mentioned that the sample file is only 12 GB, so that is 1 second, and 100% can be cached by Linux kernel for 2nd and later reads. However, if the test file is greater than 32 GB, you are definitely screwed for file system caching. You will have to pay a multi-second "I/O tax" to read the file each time. This seems to far outweigh any computation time. Thoughts? Last, I still think this is a great challenge. I think I just found my next interview question. This question is easy to understand and program a basic implementation. Further discussion can be fractally complex about the myriad of optimizations that could be applied. No trolling: Can you imagine if someone tries this exercise in Python? There are a goofy amount of optimizations to deal with huge data in that language thanks to SciPy, Pandas and other friends. I am sure someone can write an insanely performant solution. (I know, I know: The original challenge says no external dependencies.)

usefulcat 3y ago

> Isn't this simply bound by the speed of the disk? Depends on the OS and filesystem being used. The input file is ~12GB, and it's being run 5 times on a machine with 32GB, so after the first run the file could be cached entirely in memory. For example, Linux using ext2 would probably cache the entire file after the first run, but using ZFS it probably would not.