Six times faster than C

Re:Six times faster than C by nwallin on Thursday July 06, 2023 @06:31PM (#36624125)

> I assume that their test input (which isn't described in the post, and is also not in their GitHub repo) consists of random strings consisting almost entirely of s and p characters.

test code is here: https://github.com/414owen/blog-code/blob/master/02-the-same... it randomly selects between 's' or 'p'. The characters can't be anything other than 's', 'p', or the terminating null. Knowing that particular fact about our input gives us this ...clever... optimization:

    int run_switches(const char* s) {
        int result = 0;
        while (*s)
            result += (1 | *s++) - 'r';
        return result;
    }

which compiles to:

    run_switches:
            movzx   eax, BYTE PTR [rdi]
            xor     edx, edx
            test    al, al
            je      .L1
    .L3:
            or      eax, 1
            inc     rdi
            movsx   eax, al
            lea     edx, [rdx-114+rax]
            movzx   eax, BYTE PTR [rdi]
            test    al, al
            jne     .L3
    .L1:
            mov     eax, edx
            ret

This is too clever by half, of course, but it perfectly illustrates your point about exploiting properties of the data.

[ Parent | on HN ]

Re:Six times faster than C by gpderetta on Friday July 07, 2023 @06:40AM (#36629761)

You do not even need to subtract 'r'.

    int run_switches(const char* s) {
        int s_count = 0;
        const char *begin = s;
        while(*s) {
            s_count += (1 & *s++);
        }
        int count = s-begin;
        return count - s_count;
    }

which compiles to:

.L49: and edx, 1 add rax, 1 add ecx, edx movzx edx, BYTE PTR [rax] test dl, dl jne .L49

[ Parent | on HN ]