3 ms·

Note that "standard C++" solution uses std::cin while optimized one uses mmap - completely different things, a lot of speed comes just from that. Would've been

by vient 2y ago

Note that "standard C++" solution uses std::cin while optimized one uses mmap - completely different things, a lot of speed comes just from that. Would've been nice to compare with solution having optimized input and otherwise standard summing loop.

anonymoushn 2y ago
For a solution that contains this stuff const u8 *file_lo; file_lo = (const u8*)mmap(0,250000000ull,PROT_READ,MAP_PRIVATE|MAP_POPULATE,0,0); const u8 *file_hi = file_lo + 250000000ull; u64 count = 0; while (file_lo < file_hi) { if (*file_lo == 127) { ++count; } file_lo++; } I got a bit under 54ms. The solution in the article runs in a bit under 16ms.
- vient 2y ago
  Nice. Did some quick tests with your code on site, got score of ~34000 - best solution is around 14700, so this one is only 2.3 times slower. Used clang with -Ofast -march=native -static. Funnily, gcc gets only 54000 with the same options, 1.6 times slower.
  - vient 2y ago
    Wow, changing `count` type from uint64_t to uint32_t or int radically changes results - now gcc gets 26500 and clang gets 25000, that's just 1.7 times slower than current best solution. So you can get 25k with following code, clang -Ofast -std=c++17 -march=native -static #include <iostream> #include <cstdint> #include <sys/mman.h> #include <unistd.h> int main() { auto file_lo = (const uint8_t*)mmap(0,250000000ull,PROT_READ,MAP_PRIVATE|MAP_POPULATE,STDIN_FILENO,0); int count = 0; for (uint32_t i = 0; i < 250000000; ++i) { if (file_lo[i] == 127) { ++count; } } std::cout << count << std::endl; _exit(0); return 0; }
    - sYnfo 2y ago
      Neat! I'll add the best solution without explicit SIMD/asm in this thread to the post after I wake up, it's a great datapoint.
- _a_a_a_ 2y ago
  Bit rusty here but what if you replaced if (*file_lo == 127) { ++count; with count += (*file_lo == 127); That might save you the occasional branch mis-prediction, and might possibly open up some hardware-level loop optimisations. Any difference?

by vient 2y ago

anonymoushn 2y ago

For a solution that contains this stuff const u8 *file_lo; file_lo = (const u8*)mmap(0,250000000ull,PROT_READ,MAP_PRIVATE|MAP_POPULATE,0,0); const u8 *file_hi = file_lo + 250000000ull; u64 count = 0; while (file_lo < file_hi) { if (*file_lo == 127) { ++count; } file_lo++; } I got a bit under 54ms. The solution in the article runs in a bit under 16ms.

vient 2y ago
Nice. Did some quick tests with your code on site, got score of ~34000 - best solution is around 14700, so this one is only 2.3 times slower. Used clang with -Ofast -march=native -static. Funnily, gcc gets only 54000 with the same options, 1.6 times slower.
- vient 2y ago
  Wow, changing `count` type from uint64_t to uint32_t or int radically changes results - now gcc gets 26500 and clang gets 25000, that's just 1.7 times slower than current best solution. So you can get 25k with following code, clang -Ofast -std=c++17 -march=native -static #include <iostream> #include <cstdint> #include <sys/mman.h> #include <unistd.h> int main() { auto file_lo = (const uint8_t*)mmap(0,250000000ull,PROT_READ,MAP_PRIVATE|MAP_POPULATE,STDIN_FILENO,0); int count = 0; for (uint32_t i = 0; i < 250000000; ++i) { if (file_lo[i] == 127) { ++count; } } std::cout << count << std::endl; _exit(0); return 0; }
  - sYnfo 2y ago
    Neat! I'll add the best solution without explicit SIMD/asm in this thread to the post after I wake up, it's a great datapoint.
_a_a_a_ 2y ago
Bit rusty here but what if you replaced if (*file_lo == 127) { ++count; with count += (*file_lo == 127); That might save you the occasional branch mis-prediction, and might possibly open up some hardware-level loop optimisations. Any difference?