Z80Babel: C++, D, Rust, Zig and Fortran

Very interesting numbers, so the hand-coded asm version is 4x of what the C compiler can get, wow!

so this is somewhat close to what my second asm code does, although some things are difficult to translate, and I have no idea what would be better for sdcc (I did just debug and verify it in x86_64 linux):

// globals defined like this;
// #define C4_WORK_SIZE 1024        // same as 2048 work_size for sieve_c_1
// uint16_t g_primes[4000];         // makes sure there's enough room for all results
// uint8_t g_work[C4_WORK_SIZE];    // C4_WORK_SIZE must be >= 2 (to be on par with assumptions used in asm version)

uint16_t sieve_c_4() {
    // using "work" buffer to mark only odd numbers, work[0] belongs to prime 5
    // (work[-1] is prime 3, work[1] is prime 7, work[2] is 9, ...)

    uint16_t* p = g_primes;
    *p++ = 2;                       // hard-code prime 2 into result

    for (uint16_t i = 0; i < C4_WORK_SIZE; ++i) g_work[i] = 0x00;   // reset "work" array

    uint8_t* w = g_work;
    uint8_t* const w_end = g_work + C4_WORK_SIZE;

    // phase 1, search for primes which can mark new fields in sieve, enter directly into marking (for prime 3)
    do {
        // w points at work for i+2 number, and i is prime, mark it in sieve
        uint16_t i = 2 * (w - g_work + 1) + 1;
        *p++ = i;

        uint8_t* mark = w - 1 + i;  // initial mark pointer, check also for 16b overflow on ZX (mark < w) case
        if (w_end <= mark || mark < w) break;   // already outside of work, stop first phase
        while (w < mark && mark < w_end) {      // mark g_work at multiplies of i
            *mark = 1;
            mark += i;
        }
        // search from "w" for next prime
        while (*w++) ;              // and move past the found w[i] == 0
    } while (1);                    // infinite loop breaks when marking would go outside of buffer

    // phase 2, search for remaining large primes, which don't need to mark sieve
    do {
        if (*w++) continue;
        uint16_t i = 2 * (w - g_work + 1) + 1;
        *p++ = i;
    } while (w < w_end);

    return p - g_primes;
}

uint16_t sieve_c_4_end() { return (uint16_t)&sieve_c_4; }

edit: maybe keeping track of actual prime number "i" instead of calculating it would make it easier for compilers, as they will probably run out of registers any way, and the calculation is just extra strain on them, while in asm it's worth it just because keeping track of prime number itself is more costly. Keeping it explicitly would look like this:

uint16_t sieve_c_5() {
    // using "work" buffer to mark only odd numbers, work[0] belongs to prime 5
    // (work[-1] is prime 3, work[1] is prime 7, work[2] is 9, ...)

    uint16_t* p = g_primes;
    *p++ = 2;                       // hard-code prime 2 into result

    for (uint16_t i = 0; i < C4_WORK_SIZE; ++i) g_work[i] = 0x00;   // reset "work" array

    uint8_t* w = g_work;
    uint8_t* const w_end = g_work + C4_WORK_SIZE;
    uint16_t prime = 3;

    // phase 1, search for primes which can mark new fields in sieve, enter directly into marking (for prime 3)
    do {
        // w points at work for i+2 number, and i is prime, mark it in sieve
        *p++ = prime;
        uint8_t* mark = w - 1 + prime;  // initial mark pointer, check also for 16b overflow on ZX (mark < w) case
        if (w_end <= mark || mark < w) break;   // already outside of work, stop first phase
        while (w < mark && mark < w_end) {      // mark g_work at multiplies of i
            *mark = 1;
            mark += prime;
        }
        // search from "w" for next prime
        while (prime += 2, *w++) ;                // and move past the found w[i] == 0
    } while (1);                    // infinite loop breaks when marking would go outside of buffer

    // phase 2, search for remaining large primes, which don't need to mark sieve
    do {
        if (prime += 2, *w++) continue;
        *p++ = prime;
    } while (w < w_end);

    return p - g_primes;
}

uint16_t sieve_c_5_end() { return (uint16_t)&sieve_c_5; }

the stuff which didn't translate well:
- mark in asm is done with high byte of "w" address, as the "work" buffer is not expected to start in $0000..$00FF address region (there's ROM in ZX Spectrum), so not needed explicit "1" in asm
- the overflow while advancing "w" during marking is easier to check in asm, I did add extra condition to source to make it check 16b pointer overflow, but I didn't test it in x64, so I just hope these work also when compiled for Z80.

Been thinking about it more, and it's impossible the Z80 C compilers deal with it by generating fully correct code treating also edge cases, that would bloat the resulting machine code to the point nobody would ever use them.

So I guess taking some shortcuts in asm is just as fine, and just documenting the constraints is then enough and it's still comparable.

So, asm quicksort, didn't think about any constraints and just went after fastest asm I can do (except maybe tampering with stack, but considering the result, it would be difficult to gain anything by that trick) (so I don't think any compiler will ever produce this).
https://gist.github.com/ped7g/0c4e94796b474994ed88d0bdd1bf2f25

@salutte: no pressure, I have fun writing code, and I very appreciate you take your time to incorporate it and measure it under your conditions (with MSX machine I guess? I'm "home" at ZX, so we have slightly different instructions timings), so you are saving me from all the boring stuff. Thank you.

I will skip md5, already spent lot of time on the previous two, and md5 does exist in asm in InterNestor Lite: https://github.com/Konamiman/MSX/blob/master/SRC/INL1/INL-RE...