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.<p>Alexander Monakov has called the attention of the highload Telegram chat to this paper[0], saying:<p><pre><code> 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.
</code></pre>
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.<p>[0]: <a href="https://tu-dresden.de/zih/forschung/ressourcen/dateien/projekte/firestarter/2015_hackenberg_hppac.pdf?lang=en" rel="nofollow">https://tu-dresden.de/zih/forschung/ressourcen/dateien/proje...</a>
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.<p>[0] <a href="https://news.ycombinator.com/user?id=vient">https://news.ycombinator.com/user?id=vient</a>
Is there a path forward for compilers to eek out these optimization gains eventually? Is there even a path?<p>550x gains with some C ++ / mixed gnarly low level assembly vs standard C++ is pretty shocking to me.
Usually, it's fair game to use all of the information presented in an exam-style question to derive your answer.<p>With that in mind, I propose the following solution.<p>`print(976563)`
"The solution presented here is ~550x faster than the following naive program."<p><pre><code> ... std::cin >> v; ...
</code></pre>
Oh come on! That's I/O for every item, I'm surprised it's not even slower.