Finding the kth smallest number where all (hexadecimal) digits are different

Question

I'm mostly trying to understand why the simpler char array mask below (to track which digits have been already used) is much faster than the one 16 bit uint mask along with intrinsic ops. On Ryzen 3700x, compiled with "-O3 -march=native", this version takes only 1.02 secs for 10 million calls, whereas the commented out uint16 mask approach takes 2.37 secs.

#include <iostream>
#include <cstdint>
#include <chrono>
#include <x86intrin.h>


unsigned int get_digit(unsigned int i, char *mask){
    unsigned int j = 0;
    while(1){
        while(mask[j] == 0) j++;
        if(i == 0) return j;
        i--;
        j++;
    }
}

inline unsigned nthset(uint16_t x, unsigned n) {
    return _tzcnt_u64(_pdep_u64(1U << n, x));
}

uint64_t foo(int i){
    constexpr uint64_t factorials[16] = {1,1,2,6,24,120,720,5040,40320,362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000};
    uint64_t base = (1ULL<<60);

    // NOTE: Not sure why, but the simpler char array mask below is much faster than the 
    // clever 16 bit mask with intrinsic ops on Ryzen 3700x.

    //uint16_t mask = 0b1111'1111'1111'1111;
    char mask[16] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};

    uint64_t res = 0;
    int n = 15;
    while(n){
        const unsigned int v = factorials[n];
        const unsigned int d = get_digit(i / v, mask);
        //const unsigned int d = nthset(mask, i / v);
        mask[d] = 0;
        //mask = mask & ~(1<<d);

        i = i%v;
        res += d * base;
        base = base >> 4;
        n--;
    }
    //unsigned int d = nthset(mask, 0);
    unsigned int d = get_digit(0, mask);
    res += d;
    return res;
}

Answer 1

std::uint64_t is misspelt throughout as uint64_t (as if we'd written using std::uint64_t; somewhere, but that's not present in the code).

std::uint16_t is similarly misspelt. I don't see a need for exact widths here, so prefer std::uint_fast16_t and std::uint_fast64_t instead as more portable alternatives.

Why is the function called foo()? That's probably the least informative name possible. What are we trying to do here? It needs at least a comment to explain its purpose, but a better name would be helpful.

The other function get_digit() appears to have an informative name, but inspection makes me doubt that it's getting one of the digits of i. What's mask for? Perhaps this would be better named.

Overall impression: this code makes no attempt to show what it's for or how to use it. I would not take on maintenance responsibility for any of it.