My own solution which is ~1ms faster uses some other pattern that was found experimentally, but I cannot seem to get it to go any faster by tuning the parameters, and the #1 spot remains slightly out of reach.
Alexander Monakov has called the attention of the highload Telegram chat to this paper[0], saying:
Haswell is tricky for memory bw tuning, as even at fixed core frequency, uncore frequency is not fixed, and depends on factors such as hardware-measured stall cycles:
> According to the respective patent [15], the uncore frequency depends on the stall cycles of the cores, the EPB of the cores, and c-states
> ... uncore frequencies–in addition to EPB and stall cycles–depend on the core frequency of the fastest active core on the system. Moreover, the uncore frequency is also a target of power limitations.
So one wonders if it's not really a matter of reading the RAM in the right pattern to appease the prefetchers but of using values in the right pattern to create the right pattern of stalls to get the highest frequency.
FYI vien [0] figured out that simply compiling with "-static -fno-pie" and _exit(0)-ing at the end puts the solution presented here to 15000 points and hence #4 on the leaderboard. Pretty funny.
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.
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;
}
If you learn AVX2 programming via highload, my impression is that NEON is quite similar. The main difference is the lack of movemask. You can read these[0] articles[1] about what to do instead.
For SVE, prior to very recent versions of SVE, there was no tblq (pshufb equivalent) so I didn't have much hope for using it for general-purpose programming, though of course it would be fine for stuff like TFA.
I don't think this really helps: It's a trick to drive maximum possible memory bandwidth in service of a single executing thread which can process data as fast as it's being delivered.
A parallel matrix multiply running across every core shouldn't have any trouble maximizing memory bandwidth utilization.
KV-cache based LLM inference is normally significantly memory bound on the matrix-vector multiply. This is (part of) why the quantization-based approaches are so popular.
Yeah, how does the proposed solution solve the problem as stated: "Print the number of bytes whose value equals 127 in a 250MB stream of bytes uniformly sampled from [0, 255] sent to standard input."
The whole problem statement isn't equivalent to the substring of the problem statement that GP quoted? I agree. For example, the whole problem statement includes a part that specifies that stdin is a file stored in hugetlbfs.
Alexander Monakov has called the attention of the highload Telegram chat to this paper[0], saying:
So one wonders if it's not really a matter of reading the RAM in the right pattern to appease the prefetchers but of using values in the right pattern to create the right pattern of stalls to get the highest frequency.[0]: https://tu-dresden.de/zih/forschung/ressourcen/dateien/proje...
[0] https://news.ycombinator.com/user?id=vient
550x gains with some C ++ / mixed gnarly low level assembly vs standard C++ is pretty shocking to me.
Used clang with -Ofast -march=native -static. Funnily, gcc gets only 54000 with the same options, 1.6 times slower.
So you can get 25k with following code, clang -Ofast -std=c++17 -march=native -static
With that in mind, I propose the following solution.
`print(976563)`
For SVE, prior to very recent versions of SVE, there was no tblq (pshufb equivalent) so I didn't have much hope for using it for general-purpose programming, though of course it would be fine for stuff like TFA.
[0]: https://community.arm.com/arm-community-blogs/b/infrastructu...
[1]: https://www.corsix.org/content/whirlwind-tour-aarch64-vector...
A parallel matrix multiply running across every core shouldn't have any trouble maximizing memory bandwidth utilization.