rygorous

// Original; this is straight Kogge-Stone
// the problem is that on Intel Haswell and later, there's only one
// port (port 5) that handles shuffles, including PSLLDQ (_mm_slli_si128).
// This code needs 4 cycles worth of port 5 work, which is not great if
// you want to mix it with other work that is port 5-heavy.
static inline __m128i prefix_sum_u8_orig(__m128i x)
{
    x = _mm_add_epi8(x, _mm_slli_si128(x, 1));
    x = _mm_add_epi8(x, _mm_slli_si128(x, 2));
    x = _mm_add_epi8(x, _mm_slli_si128(x, 4));

rygorous

Core 0:
encode (x1)      : 4.526 seconds, 183.25 ns/B, rate= 5.46 MB/s
decode (x50)     : 132.080 millis, 5.35 ns/B, rate= 187.01 MB/s

Core 4:
encode (x1)      : 7.672 seconds, 310.60 ns/B, rate= 3.22 MB/s
decode (x50)     : 185.233 millis, 7.50 ns/B, rate= 133.35 MB/s

rygorous

BEFORE:

Kraken, Normal, lzt99 :
24,700,820 ->10,146,976 =  3.286 bpb =  2.434 to 1

encode (x1)      : 10.954 seconds, 443.48 c/B, rate= 2.25 MB/s
decode (x30)     : 141.283 millis, 5.72 c/B, rate= 174.83 MB/s 

AFTER:

rygorous

herolte:/ $ cat /proc/cpuinfo
processor       : 0
Features        : fp asimd evtstrm aes pmull sha1 sha2 crc32
CPU implementer : 0x41
CPU architecture: 8
CPU variant     : 0x0
CPU part        : 0xd03
CPU revision    : 4

processor       : 1

rygorous

float baseRadius = 15.0;

vec2 random(vec2 p){
	p = fract(p * vec2(443.897, 441.423));
    p += dot(p, p.yx+19.19);
    return fract((p.xx+p.yx)*p.xy);
}

rygorous

void fancierRotate2(unsigned int *arr, const bool *control, int count, int rot0, int rot1)
{
    for (int i = 0; i < count; ++i)
    {
        int rot = control[i] ? rot1 : rot0;
        arr[i] = (arr[i] << (rot & 31)) | (arr[i] >> (-rot & 31));
    }
}

rygorous

why doesn't radfft support AVX on PC?

So there's two separate issues here: using instructions added in AVX and using 256-bit wide vectors. The former turns out to be much easier than the latter for our use case.

Problem number 1 was that you positively need to put AVX code in a separate file with different compiler settings (/arch:AVX for VC++, -mavx for GCC/Clang) that make all SSE code emitted also use VEX encoding, and at the time radfft was written there was no way in CDep to set compiler flags for just one file, just for the overall build.

[There's the GCC "target" annotations on individual funcs, which in principle fix this, but I ran into nasty problems with this for several compiler versions, and VC++ has no equivalent, so we're not currently using that and just sticking with different compilation units.]

The other issue is to do with CPU power management.

rygorous

#include <stdint.h>

#define BITKNIT_BRANCHLESS_RENORM

// RAD-esque types
typedef size_t UINTa;
typedef uint8_t U8;
typedef uint16_t U16;
typedef uint32_t U32;

rygorous

     $default(TakeCPP,*.h,pre
       $unless($NoAutoInclude,
         $unless($wildcard($file,$NoAutoIncludeMatch),
           $set(tccfile,$extension($file,c))
           $set(tccppfile,$extension($file,cpp))
           $unless($RequiresIfExists($tccfile),
             $RequiresIfExists($tccppfile)
           )
         )
       )

rygorous

A few notes on XBitmanip

Looks fairly good to me; although I like PDEP/PEXT (and accordingly BDEP/BEXT) quite much, I'm a bit worried about the relatively large amount of control circuitry required to set up the butterfly muxes, but that concern is already mentioned in the spec draft so I'm not adding anything new.

I do have a few remarks though.

Problems with shift counts mod XLEN

One recurring issue with bit mask generation and shifts are the corner cases. For example, the usual