21–30 of 41 posts
Earlier quoted context omitted.
1) if you set BATCH_SIZE > 14 sums_acc may overflow 2) chunks with too many small numbers cannot be processed with just 2 shuffle-adds 3) (not mentioned in the post) HighLoad limits the size of the source code you can submit, so you can't put all possible values in the look-up table
For 1, can you raise that to 28 with unsigned accumulators?
Earlier quoted context omitted.
Why? So long as you know the probabilities and they are tolerable, why?
The challenge is to get the right answer. It's much less interesting if you relax the challenge to no longer require the right answer. Here's a really fast approximate answer: 50000000*(2^31-1)/2
Earlier quoted context omitted.
To be clear, it’s not dereferencing unmapped memory, I just haven’t shown how it’s being mapped, because it’s a little complex. As I note in the post, you can imagine as if I mmap all the necessary addresses at the start of the program.
Given that the input is "integers uniformly sampled from [0, 2³¹−1]" couldn't you use a LUT for the 99.99% case of just 10/9/8 digit numbers instead and have a cold branch the handle the very rare smaller numbers.
Is there an explanation of why it sometimes gives the wrong answer?
> will only produce correct results with probability That's terrifying
Earlier quoted context omitted.
For 1, can you raise that to 28 with unsigned accumulators?
14 already assumes unsigned accumulator! 255 [accumulator capacity] / (2 [shuffle-adds] * 9 [highest digit value]) ~= 14
Is there an explanation of why it sometimes gives the wrong answer?
1) if you set BATCH_SIZE > 14 sums_acc may overflow 2) chunks with too many small numbers cannot be processed with just 2 shuffle-adds 3) (not mentioned in the post) HighLoad limits the size of the source code you can submit, so you can't put all possible values in the look-up table
Earlier quoted context omitted.
1) if you set BATCH_SIZE > 14 sums_acc may overflow 2) chunks with too many small numbers cannot be processed with just 2 shuffle-adds 3) (not mentioned in the post) HighLoad limits the size of the source code you can submit, so you can't put all possible values in the look-up table
Couldn't you organize the accumulators in 8 byte chunks, and leave the upper byte unused. Then you map consecutive digits to those chunks and use 64 bit addition for the accumulation. Then overflow between the bytes would keep the correct result if you do the shuffles correctly, and you have a full byte of overflow buffer.
Earlier quoted context omitted.
Couldn't you organize the accumulators in 8 byte chunks, and leave the upper byte unused. Then you map consecutive digits to those chunks and use 64 bit addition for the accumulation. Then overflow between the bytes would keep the correct result if you do the shuffles correctly, and you have a full byte of overflow buffer.
Gaps in the numbers are often enough to do some kind of "SIMD" even on ordinary 32-bit processors.
First time I hear about HighLoad. Seems really interesting to me on the first glance. I personally find SIMD and ISA/μarch-specific optimizations more rewarding than pure algorithmic challenges (codeforces and such). Though Haswell seems like a pretty obsolete platform to optimize for at this point. Even Skylake will be a decade old next year.
Realistically beyond Haswell there hasn’t been a ton of advancement in SIMD. Hawell introduced AVX2, which is what this blog post uses. AVX512 is certainly more powerful, but that’s not even available in the majority of Intel CPUs, even brand new ones.
Earlier quoted context omitted.
Realistically beyond Haswell there hasn’t been a ton of advancement in SIMD. Hawell introduced AVX2, which is what this blog post uses. AVX512 is certainly more powerful, but that’s not even available in the majority of Intel CPUs, even brand new ones.
AVX-512 has been ubiquitous on Intel server CPUs for a long time. Most people don't run high-performance throughput-oriented codes on consumer-grade CPUs with no ECC, which is the primary application for AVX-512. AVX-512 is a markedly better ISA than AVX2, aside from being wider.
AVX-512 is no longer ubiquitous on Intel servers, but only on new AMD servers.
Even earlier, there were cheap Intel servers with CPUs using Atom cores, for example the Denverton, Snow Ridge, Denverton Refresh, Snow Ridge Refresh, Parker Ridge and Arizona Beach series of server CPUs. None of these supported AVX-512 and many did not support even AVX.
However, now, after the launch of the Sierra Forest server CPUs, which will be followed next year by the Clearwater Forest server CPUs, the Atom cores have expanded up to the biggest Intel server CPUs. While such server CPUs are intended for applications where computations using array operations are less important, like Web servers or the hosting of many small virtual machines, the fragmentation of the Intel ISA is extremely annoying, especially when AMD demonstrates how they can implement the same ISA, but at different levels of performance (by varying the number of vector pipelines and the maximum achievable clock frequency) both in laptop CPUs and in desktop/server CPUs and both in compact cores with low clock frequency and in big cores with high clock frequency.
At least for me, the lack of AVX-512 support is the reason that made me stop buying Intel CPUs already some years ago, even if there are some features of the Intel CPUs that I prefer over the AMD CPUs (like TSC deadline), but none of those can compensate the lack of AVX-512 support.
The greater width of AVX-512 is not its greater advantage, but the mask registers and a more complete set of instructions, which simplify many algorithms. Therefore when Intel will support AVX10/256 across all their CPUs, that will partially restore the competitivity of the Intel CPUs, but that is not likely to happen before 2026.