pbsd

If you insist, you could calculate the log2 as something like

    x |= x >>  1;
    x |= x >>  2;
    x |= x >>  4;
    x |= x >>  8;
    x |= x >> 16;
    return popcount(x-1);

but there isn't really much of an advantage to it. lzcnt/bsr are better.

llvm-mca is highly unreliable when it comes to AVX-512. It thinks 3 512-bit vpaddd, vpsubd can be run per cycle. Adjusting for that you get 622 cycles instead of 528.

On Skylake-SP's AVX-512, instructions that previously were dispatched to port 0 or 1 get instead dispatched to ports 0 _and_ 1. So instructions like vpsrlq get zero net speedup from switching to AVX-512 from AVX2. Instructions that previously ran on ports 0,1,5 will now run on ports 0 and 5, for a speedup of at best 1.33.

Multiplication will depend on whether the chip has one or two FMA units. If so, you can run vpmuludq on ports 0 and 5, which is a 2x speedup compared to AVX2's ports 0 and 1. This 8275CL Xeon does have 2 FMA units.

Looking at the two inner loops, we have

    up:
    vmovdqa64     zmm0,ZMMWORD PTR [rdi+rax*4] # p23
    add           rax,0x10       # p0156 
    vpmuludq      zmm1,zmm0,zmm4 # p05 or only p0
    vpsrlq        zmm2,zmm1,0x20 # p0
    vpsrlq        zmm1,zmm0,0x20 # p0
    vpmuludq      zmm1,zmm1,zmm4 # p05 or only p0
    vpandd        zmm1,zmm6,zmm1 # p05
    vpord         zmm1,zmm1,zmm2 # p05
    vpsubd        zmm0,zmm0,zmm1 # p05
    vpsrld        zmm0,zmm0,0x1  # p0
    vpaddd        zmm0,zmm0,zmm1 # p05
    vpsrld        zmm0,zmm0,xmm5 # p0+p5
    vpaddd        zmm3,zmm0,zmm3 # p05
    cmp           rax,rdx        
    jb            up

    up:
    vmovdqa      ymm0,YMMWORD PTR [rdi+rax*4] # p23
    add          rax,0x8                      # p0156
    vpmuludq     ymm1,ymm0,ymm4               # p01
    vpsrlq       ymm2,ymm1,0x20               # p01
    vpsrlq       ymm1,ymm0,0x20               # p01
    vpmuludq     ymm1,ymm1,ymm4               # p01
    vpand        ymm1,ymm1,ymm6               # p015
    vpor         ymm1,ymm1,ymm2               # p015
    vpsubd       ymm0,ymm0,ymm1               # p015
    vpsrld       ymm0,ymm0,0x1                # p01
    vpaddd       ymm0,ymm0,ymm1               # p015
    vpsrld       ymm0,ymm0,xmm5               # p01+p5
    vpaddd       ymm3,ymm0,ymm3               # p01
    cmp          rax,rdx
    jb           up

All other things being equal, we have on average, and counting only the differing instructions, a throughput of ~2.27 instructions per cycle on the AVX2 loop, whereas it is somewhere around ~1.45-1.60 for AVX-512, depending whether you have 1 or 2 FMA units to run multiplications on port 5.

So based on this approximation, the AVX-512 code should probably run around 2*(1.5/2.27) ~ 1.33 times faster. Add to this that vpmuludq is actually one of the most thermally insensitive instructions around and will reduce your core's frequency by 100-200 MHz, and the small speedup you see is more or less explainable. (I actually do see some more noticeable speedup here when switching to AVX-512; 0.25 vs 0.21).

PS: The Intel Icelake and later chips also manage to achieve a throughput of 1/2 divisions per cycle for 32-bit divisors, and 1/3 divisions per cycle for 64-bit divisors.

PPS: Some of your functions could use blends. For example,

    __m256i libdivide_mullhi_u32_vec256_(__m256i a, __m256i b) {
      __m256i hi_product_0Z2Z = _mm256_srli_epi64(_mm256_mul_epu32(a, b), 32);
      __m256i a1X3X = _mm256_srli_epi64(a, 32);
      __m256i hi_product_Z1Z3 = _mm256_mul_epu32(a1X3X, b);
      return _mm256_blend_epi32(hi_product_0Z2Z, hi_product_Z1Z3, 0xAA);
    }

    __m512i libdivide_mullhi_u32_vec512_(__m512i a, __m512i b) {
        __m512i hi_product_0Z2Z = _mm512_srli_epi64(_mm512_mul_epu32(a, b), 32);
        __m512i a1X3X = _mm512_srli_epi64(a, 32);
        __m512i hi_product_Z1Z3 = _mm512_mul_epu32(a1X3X, b);
        return _mm512_mask_blend_epi32((__mmask16)0xAAAA, hi_product_0Z2Z, hi_product_Z1Z3);
    }

Intel greatly improved their divider implementation between Skylake and Icelake. The measurements in the OP are on Skylake-SP, prior to these improvements.

I agree; compiler-type code will miss the cache most of the time. A simple test with clang++ compiling some nontrivial piece of C++:

                 0      lsd_uops                                                    
     1,092,318,746      idq_dsb_uops                                                  ( +-  0.49% )
     4,045,959,682      idq_mite_uops                                                 ( +-  0.06% )

The LSD is disabled in this chip (Skylake) due to errata, but we can see only 1/5th of the uops come from the uops cache. However, the more relevant experiment in terms of power is how many cycles is the cache active instead of the decoders:

                 0      lsd_cycles_active                                           
       378,993,057      idq_dsb_cycles                                                ( +-  0.18% )
     1,616,999,501      idq_mite_cycles                                               ( +-  0.07% )

The ratio is similar: the regular decoders are not active only around 1/5th of the time.

In comparison, gzipping a 20M file looks a lot better:

                 0      lsd_cycles_active                                           
     2,900,847,992      idq_dsb_cycles                                                ( +-  0.07% )
       407,705,985      idq_mite_cycles                                               ( +-  0.33% )

The x86 decoder is not running all the time; the uops cache and the LSD exist precisely to avoid this. With instructions fed from the decoders you can only sustain 4 instructions per cycle, while to get to 5 or 6 your instructions need to be coming from either the uops cache or the LSD. In the case of the Zen 3, the cache can deliver 8 uops per cycle to the pipeline (but the overall thoughput is limited elsewhere at 6)!

Furthermore, the high-performance ARM designs, starting with the Cortex-A77, started using the same trick---the 6-wide execution happens only when instructions are being fed from the decoded macro-op cache.

True, but it's entirely voluntary:

- clamp(a, b, c), where a, b, c are all l-values would copy everything. Not destructive by default (but wasteful on "big" types).

- clamp(a, std::move(b), c) would potentially destroy b, but that's something the caller explicitly opted into.

- clamp(a, T{ something }, T{ something else }) would be an implicit move, but nobody is going to accidentally use those r-values anywhere else.

The non-const ref version returning is not something I quite like either; it would make more sense to me to have `void clamp(T& x, T const& l, T const& h)`, where the semantics would be more like `x.clamp(l, h);`. But to retain the same API I returned the reference.

Having everything be const references is in a sense optimal, but is so prone to misuse that I wouldn't want it in the standard library.

One option is to pass everything by value. Move semantics does the rest. Like:

    template<typename T>
    T clamp(T v, T lo, T hi) {
        if(v < lo) v = std::move(lo);
        if(v > hi) v = std::move(hi);
        return std::move(v);
    }

For fundamental types, this is the same or better than before (including __int128_t and such). For bigint types with heap allocation, i.e., GMP wrappers and such, moving is fairly inexpensive (but for constant lo, hi, they need to be created/copied each time...). For fixed-width bigint types, moving is no different from copying and the cost is higher. In any case, the 99-percentile usage of these functions is with fundamental types, where pass-by-value is clearly the better choice.

Alternatively, you could have

    template<typename T>
    T& clamp(T& v, T const& lo, T const& hi) {
        if(v < lo) v = lo;
        if(v > hi) v = hi;
        return v;
    }

This forces the returned reference to be an l-value, and so returning dangling temporaries becomes more difficult. There's the added cost for the assignments, though.

You can also achieve the fix using the arguably more natural

    template<typename T>
    T const& clamp(T const& v, T const& lo, T const& hi) {
        T const& a = v < lo ? lo : v;
        T const& b = a > hi ? hi : a;
        return b;
    }

Either way, the commitee's idea of returning references for the C++ max/min/clamp functions was terrible, and it's a constant source of problems with temporaries and such. Like this: https://godbolt.org/z/j593Mebd6

This is probably the story in page 220 of [1], beginning at "Von Neumann got into trouble at the end of his life because he was really a frog but everyone expected him to fly like a bird.".

[1] http://www.uvm.edu/pdodds/files/papers/others/2009/dyson2009...

Oh yeah, I thought the add r,r,2 was odd but didn't investigate. This brings things back to ~2+ cycles per iteration, which strictly speaking does not require fusion.

It would be easier to test this explicitly instead of inside some unrelated RNG.

Based on the information from [1] we have something like this for both loops:

    .LBB0_2:
            eor     x13, x9, x9, lsr #30     # 2 \* p1-6
            mul     x13, x13, x11            # 1 \* p5-6
            eor     x13, x13, x13, lsr #27   # 2 \* p1-6
            mul     x13, x13, x12            # 1 \* p5-6
            eor     x13, x13, x13, lsr #31   # 2 \* p1-6
            str     x13, [x0, x10, lsl #3]   # 1 \* p7-8
            add     x13, x10, #2             # 1 \* p1-6
            add     x9, x9, x8               # 1 \* p1-6
            mov     x10, x13                 # none
            cmp     x13, x1                  #
            b.lo    .LBB0_2                  # Fused into 1 \* p1-3
                                             # Total: 11 uops

    .LBB1_2:
            mul     x13, x9, x11             # 1 \* p5-6
            umulh   x14, x9, x11             # 1 \* p5-6
            eor     x13, x14, x13            # 1 \* p1-6
            mul     x14, x13, x12            # 1 \* p5-6
            umulh   x13, x13, x12            # 1 \* p5-6
            eor     x13, x13, x14            # 1 \* p1-6
            str     x13, [x0, x10, lsl #3]   # 1 \* p7-8
            add     x13, x10, #2             # 1 \* p1-6
            add     x9, x9, x8               # 1 \* p1-6
            mov     x10, x13                 # none
            cmp     x13, x1                  #
            b.lo    .LBB1_2                  # Fused into 1 \* p1-3
                                             # Total: 10 uops

Purely based on number of uops, there's a slight win for wyhash, all other things being equal. However, I doubt that you're really getting one iteration per second here; there are 6 integer units, and even if you perfectly exploited instruction parallelism you're limited to 6 ALU instructions per cycle, which are less than the extent of either loop. It would be possible if the mul-umulh pairs are getting fused, which would bring it down to 8 uops per iteration.

Taking into account the port distribution, each iteration of wyhash involves 4 uops being dispatched to ports 5 and 6, which means you should be getting at least 2 cycles/iteration purely for the multiplications. If it's much lower than that, the whole multiplication being fused into a single port 5-6 uop might be right.

However I can neither confirm nor deny that the loops behave like that on the M1, as I don't have one.

[1] https://dougallj.github.io/applecpu/firestorm.html

Schnorr got close to making such a claim in a previous version of the paper [1, Section 6]. Namely, that NTRU is close to being broken if a sufficiently short vector (it is not specified how short) is found.

The main claim of Schnorr's, as far as I can gather, is that for lattices where the shortest vector(s) are much shorter than the maximum shortest vector(s) for the same dimension, i.e., low-density lattices, those vectors can be found in heuristic polynomial time with his enumeration approach.

Now, low-density lattices are fairly common in cryptographic settings, where the solution, discoverable by finding shortest vectors, is unusually short/close relatively to what one would expect in a random lattice.

As such, if true, I would expect Schnorr's idea to lead to more breaks than just RSA. But I don't personally think it's true. At the same time, I'm not a lattice expert, so make of that what you will.

[1] https://www.math.uni-frankfurt.de/~dmst/research/papers/SVP2...

GCM is a different type of construction, but the polynomial used there is explainable---it's the irreducible polynomial of the type x^128 + f(x) for which f(x) has the lowest degree (i.e., it's the lexicographically smallest irreducible GF(2) polynomial of degree 128). Any irreducible polynomial picked here would work as well, from a security point of view.

AES is a good case study, because you _cannot_ remove any operation without ending up with a broken cipher:

- If you remove AddRoundKey, there's no key getting mixed and you don't really have a block cipher in the first place; - If you remove SubBytes, the entire thing becomes linear and elementary to break; - If you remove ShiftRows, each column of the 4x4 state is independent of each other, and you could trivially distinguish the cipher from random by observing that only 32 bits change for any single byte change; - If you remove MixColumns, you're removing most of the diffusion of the cipher, and once again it becomes much easier to break because there's no longer any mixing across bytes.

The order itself doesn't matter all that much. You can reorder AddRoundKey, ShiftRows, and Mixcolumns any way you like and you end up with the exact same cipher, since those are all linear operations. Ordering them differently with respect to SubBytes would have no meaningful security impact, but it serves no purpose to start with anything other than adding the key and applying SubBytes, since all the other linear stuff can be trivially canceled out by the attacker until the first nonlinear operation.

The general principle in AES-like ciphers is to iterate rounds of the shape `block = nonlinear_operation(block, key[i])` followed by `block = linear_operation(block)`. You will find many (many!) designs like this if you go looking, trying various choices of nonlinear and linear operations that guarantee various useful properties. In the case of AES, SubBytes guarantees that the differential probability going through any byte is upper bounded by 1/64; MixColumns guarantees that for any two distinct 4-byte inputs, between the input and output there are at the very least 5 changed bytes. When you mix these two together, with the help of ShiftRows you can show that useful differential trails are pretty much gone after 4 rounds.

Constructions like SHA-1 (or more precisely, the block cipher underlying SHA-1) do not generally have such clean rationales. You can view it as a Feistel-like cipher with a linear key schedule, so it's hardly a random mashing of operations, but how the particular sequence of operations of the round function is chosen is a bit of a trial and error process. The same applies to Salsa20, Chacha20, and most other ARX constructions.

The set of operations you have access to as a designer affects immensely what your cipher will look like. If your alien CPUs had a very different instruction set than ours, their ciphers would look very different.

Back in the old days memory lookups were as fast as computation, and S-box based designs were very popular. That is no longer the case, to an extent, both for security (cache-timing side-channels) and performance reasons. S-box designs are still common, but the S-boxes are usually <= 4-bit wide, mostly there to facilitate analysis (counting active S-boxes), and usually implemented as boolean logic instead.

Without S-boxes, the other main approach is to mix operations from incompatible algebraic domains. Like add and xor. When composed many times together, hopefully this results in a very complicated nonlinear expression of very high degree on any of these domains. One of the first popular ciphers to do this was IDEA, which mixed addition, xor, and modular multiplication to pretty good effect. The challenge then is to figure out a set of these operations that is both efficient at eliminating input-output structure (linear, differential, etc characteristics) and efficient at being computed in the widest possible range of machines. This restricts your options to a common set of operations, like add, xor, shift, and so on. Multiplications can be useful, but they don't do very well at the low end, and tend to complicate analysis.

This is only at the very lowest level of the design phase, where you're picking your mixing/diffusion building blocks. You still have to decide on a higher-level structure such as the various Feistel variants, Lai-Massey, SPN, etc, which comes with its own set of tradeoffs.

Presumably https://www.reddit.com/r/crypto/comments/3or80y/i_designed_m...

Not only is it a single uop for the last 10 years of Intel chips, you can also run 2 of them per cycle.

Yes. Between Pollard's rho, SQUFOF, ECM, the various sieves, etc, there is essentially no range at which this one performs better.

Subexponential algorithms in general have long had proven running times. Dixon's method [1], in particular, has had a proven running time since 1980. The number field sieve itself has had some recent progress on that front [2].

However, those algorithms are _probabilistic_, not _deterministic_, which is what sets this linked method apart.

This algorithm, much like Pollard-Strassen before it, is pretty much irrelevant to integer factorization in practice. But it is nevertheless remarkable to see some progress on deterministic factorization after such a long time.

[1] https://doi.org/10.1090/S0025-5718-1981-0595059-1

[2] https://doi.org/10.1016/j.jnt.2017.10.019

If you really want to know, you could cover most of it with [1,2].

[1] https://www.maa.org/sites/default/files/pdf/upload_library/2...

[2] https://www.maa.org/sites/default/files/pdf/upload_library/2...

I don't think that's the case on most CPUs; VPGATHERDD on Skylake, Icelake, etc, all issue the same 4/8/16 port2,3 uops regardless of what the addresses are.

Indeed; I've always known it as the Tenex bug [1], the Tenex being the system designed by BBN prior to being bought by DEC and renamed to TOPS-20.

[1] http://www.bwlampson.site/33-Hints/Acrobat.pdf

What does the effect (or lack thereof) look like when doing xmm stores?

> Otherwise, if msg is short and it gets broken across a block boundary, this can make meet-in-the-middle--style attacks easier.

Can you elaborate? Take SHA-512/256 with some awkward prefix size, let's say 127 bytes. Which attacks, presumably not side-channel based, become possible?

In any case, I am not convinced in the least by this suffix pitch. Handwaving that "prefix-freeness" needs to be checked, when that's something that is constantly gotten wrong and results in real breaks is a bit naïve. On the other hand, I have real trouble thinking of a real break caused by prefixing. The Ed25519 paper you link to does not point to prefixing as the culprit either; that just happened to be where the key was, and the lack of randomness makes power analysis possible. Without randomness, suffixing would suffer a similar fate.

The single-uop FMA instructions beg to differ. As well as ADC, SBB, CMOVcc, etc, since Broadwell: 1 uop, 3 inputs. LEA itself has consisted of 1 uop for a very long time...but the complex 3-input version gets sent to a different place than the simple one.

The PBLENDVB case is interesting: the VEX-encoded variant takes 2 uops in every uarch, but 1 uops (since Skylake) in the non-VEX encoded variant that takes XMM0 as a hardcoded input.

For each input source file, cl.exe creates at least 7 temporary files (with suffixes "gl", "sy", "ex", "in", "db", "md", "lk"). The churn of creating and deleting those, coupled with the slowness of performing checkpointing on a huge empty drive, seem to be the root cause here.

This appears somewhat related to this bug report: https://developercommunity.visualstudio.com/content/problem/...

Marking the temporary files as FILE_ATTRIBUTE_TEMPORARY could improve things, without having to go into significant Windows kernel changes.

I would point out that there _are_ consumer-grade chips with AVX-512 beyond the Xeons and Cannonlake: the Skylake-X chips such as i7-7800X, which even happen to have 2 512-bit FMA units, unlike some of the cheaper Xeons.

I will point out three things that make the Sunny Cove exciting to me, beyond the obvious new instructions (based on the available slides):

- There are now two ports for vector shuffles. For shuffle-heavy applications, which is often the case with bit-manipulation kernels, this is great news. This seems improved from Cannonlake.

- This was already present on the Cannonlake, but integer division is drastically improved, and goes from ~30ish uops to 4. Divisions that could take up to 90 cycles will now take <=18.

- There are now 4 LEA ports, up from 2, which for address calculation and small integer multiplications are quite useful.

A moved-from std::vector<int> will always be empty. However, a moved-from std::vector<int, custom_stateful_allocator> may not be.

Howard Hinnant had a Stack Overflow reply a while back going through the possible corner cases of this precise question: https://stackoverflow.com/a/17735913

Odlyzko, despite having some notable contributions to index calculus algorithms, was not among the first to invent or suggest its use.