Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

{n} times faster than C

owen.cafe

Post reply on HN
Print view View original

181–190 of 249 posts

Re: {n} times faster than C

#181

Post by EVa5I7bHFq9mnYK »

gpderetta wrote: post #179
EVa5I7bHFq9mnYK wrote: post #167

Earlier quoted context omitted.

I mean, if the innermost loop is something like 3 assembly instructions, two extra instructions cmp and jg do not make any difference, if jg never executes?

If they are not in the critical path, it doesn't matter. There is no instruction cache issues as the loop is tiny. Also as the loop is tiny it will fit in the u-op cache (or even in the loop cache), so decoding is not an issue either. The only problem is potential lack of vectorization, but a good vector ISA can in principle handle the bound checking with masked reads and writes (but now the check is no longer a pred…

I thought I began to understand something, your rant proven me wrong) Thanks, anyway)

Re: {n} times faster than C

#182

Post by Const-me »

xoranth wrote: post #75
Const-me wrote: post #60

I’m probably an optimization expert, and I would solve that problem completely differently. On my computer, the initial C version runs at 389 MB / second. I haven’t tested the assembly versions, but if they deliver the same 6.2x speedup, would result in 2.4 GB/second here. Here’s C++ version which for long buffers exceeds 24 GB/second on my computer: https://gist.github.com/Const-me/3ade77faad47f0fbb0538965ae7... Tha…

Interesting. I think you can vectorize the prologue using movemask + popcnt instead of keeping a counter in the ymm registers (warning: untested code, still need to benchmark it): const __m256i zero = _mm256_setzero_si256(); const __m256i s = _mm256_set1_epi8( 's' ); const __m256i p = _mm256_set1_epi8( 'p' ); const size_t a = (size_t)input; const size_t rem = a % 32; const char* aligned = input - rem; const __m256i v…

Good idea, and it can be used for both prologue and epilogue pieces. Updated that gist.

However, this is only relevant for very small inputs. For longer inputs the vectorized portion of the function gonna dominate the performance.

Re: {n} times faster than C

#183

Post by gpderetta »

nwallin wrote: post #57
eklitzke wrote: post #6

Rearranging branches (and perhaps blocks too?) will definitely be done if you are building using FDO, because without FDO (or PGO) the compiler has no idea how likely each branch is to be taken. Cmov can also be enabled by FDO in some cases. However, whether or not using cmov is effective compared to a regular test/jump is highly dependent on how predictable the branch is, with cmov typically performing better when t…

> 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…

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
edit: other variant

    int run_switches2(const char* s) {
        const char *begin = s;
        int sum = 0;
        while(*s) {
            sum += *s++;
        }
        int count = s-begin;
        int s_count = sum - ('s'*count)/('p'-'s');
        int p_count = count - s_count;
        return p_count - s_count;
   }
which compiles to:

   run_switches2(char const*):
        movsx   eax, BYTE PTR [rdi]
        test    al, al
        je      .L56
        mov     rdx, rdi
        xor     ecx, ecx
   .L55:
        add     rdx, 1
        add     ecx, eax
        movsx   eax, BYTE PTR [rdx]
        test    al, al
        jne     .L55
        sub     rdx, rdi
        imul    esi, edx, 115
        movsx   rax, esi
        sar     esi, 31
        imul    rax, rax, 1431655766
        shr     rax, 32
        sub     eax, esi
        add     ecx, eax
        sub     edx, ecx
        mov     eax, edx
        sub     eax, ecx
        ret
   .L56:
        xor     eax, eax
        ret
None of these will beat the clever blocked SIMD someone showed elsethread.

Re: {n} times faster than C

#184

Post by secondcoming »

arun-mani-j wrote: post #153

Any guide on how a person who uses Python or JavaScript can learn such things? I mean knowing which assembly code would be better, which algorithm makes better usage of processor etc.? :) Also, how is such optimization carried out in a large scale software? Like, do you tweak the generated assembly code manually? (Sorry I'm a very very very beginner to low-level code)

You learn by doing. Compiler Explorer [0] is fantastic for this sort of thing. Typically you would do this sort of optimisation after profiling and then on a per-function level.

[0] godbolt.org

Re: {n} times faster than C

#185

Post by Tuna-Fish »

torstenvl wrote: post #112
Tuna-Fish wrote: post #91

Earlier quoted context omitted.

Because modern CPUs as a rule don't speculate on values to arithmetic, only on control flow, and CMOV acts like arithmetic. That is, if there is an add instruction on rax and rbx, no matter what, the add instruction will not execute until both rbx and rbx are available. If the result went into rax, and there is an another instruction that uses that as a source, no matter what that instruction will not execute until t…

I'm not saying you're wrong — I'm completely ignorant at the microcode level — but it seems to me like between cmp x, y je z and cmp x, y sete z the actual speculative part is the same: speculating as to the result of cmp x, y If that's true, why would it not simply pipeline sete and the following instructions and simply execute (or not execute) sete according to its prediction, and then double check itself and rever…

The two sequences look very similar, and could be implemented the same way, but the actual implementation could not be more different.

> If that's true, why would it not simply pipeline sete and the following instructions and simply execute (or not execute) sete according to its prediction, and then double check itself and reverse (or apply) the operation if the prediction was wrong?

You cannot just reverse or apply one operation. The way speculation works, when the frontend encounters a conditional jump, the entire architectural state of the current thread is stored, and all future memory writes are held in the store buffer and not written out. Then a long time, potentially dozens of cycles later, after the je is executed in the backend either the old state is restored and the pending writes are discarded, or the saved state is discarded and the pending writes are released.

In contrast, in ALUs, the inputs for instructions are always available before the instructions are scheduled to execute. It would be possible to implement sete like je, but this would imply significant changes to how and where it is executed. ALU ops cannot trigger speculation because there is no machinery for storing state at that part of the pipeline.

And no-one is ever going to implement cmov or sete like a jump, because moving the op from being an ALU op to being one that is speculatively executed in the frontend like jmp would make both positive and negative changes, and that would be a significant pessimization of existing software because for decades cmovs have been used for unpredictable values, where sequencing and waiting for the real value is a better idea than speculating and failing half the time. Using a cmov serializes execution when any following operations use the value, but if you can have independent work after it, you can always successfully execute that. Speculating at an unpredictable CMOV would cause that to be thrown away uselessly half the time.

Re: {n} times faster than C

#186

Post by areyousure »

sweetjuly wrote: post #158
romnon wrote: post #135

Earlier quoted context omitted.

ive seen people doing += !!(c=='s')-!!(c=='p') for that

I'm sure people do that (even though it's not necessary per some year C standard) but generally the pattern is actually for converting things which are not already 0 or 1 into 0 or 1. For example, you might want to use it here: int num_empty_strings = !!(strlen(s1)) + !!(strlen(s2)) + !!(strlen(s3)) which is equivalent to: int num_empty_strings = (strlen(s1) != 0) + (strlen(s2) != 0) + (strlen(s3) != 0) Which you use…

Note that your code computes the number of nonempty strings.

Re: {n} times faster than C

#187

Post by Tuna-Fish »

skavi wrote: post #133
nwallin wrote: post #119

Earlier quoted context omitted.

Neat! Although you'll need to make a copy of `n`. The second loop will reduce the value of n to null. Edit: Also, there's an off by one error. should be: #include #include int run_switches(const char *s, const size_t n) { int res = 0; uint8_t tmp = 0; for (int i = n & 127; i--; ++s) tmp += *s == 's'; res += tmp; for (int size = n >> 7; size--;) { tmp = 0; for (int i = 128; i--; ++s) tmp += *s == 's'; res += tmp; } re…

Am I missing something, or does this not really account for alignment? Is the compiler doing smarter loop splitting?

I think it's just reading unaligned. That's just a ~2x loss of throughput from L1, but the second the problem is large enough that the work being done doesn't reliably fit into the L1, that doesn't matter a bit anymore.

In general for x86, unaligned writes are worth doing work to avoid, but reads are in most situations not really an issue.

Re: {n} times faster than C

#188

Post by fefe23 »

First, before optimizing you should consider correctness and security. input should be const and the return value should be ssize_t (so you don't have numeric overflow on 64-bit).

Second, consider this replacement function:

  ssize_t test(const char \*input) {
    ssize_t res = 0;
    size_t l = strlen(input);
    size_t i;
    for (i=0; i
The timings are (using gcc -O3 -march=native): your function 640 cycles, mine 128 cycles. How can that be? I'm reading the memory twice! I have one call to strlen in there, and memory is slow. Shouldn't this be much slower?

No. strlen is a hack that uses vector instructions even though it may technically read beyond the string length. It makes sure not to cross page boundaries so it will not cause adverse reactions, but valgrind needs a suppression exception to not complain about it.

If you know the length beforehand, the compiler can vectorize and unroll the loop, which it happens to do here. To great effect, if I may say so.

The art of writing fast code is usually to get out of the way of the compiler, which will do a perfectly fine job if you let it.

If you really wanted to, you could get rid of the strlen by hacking your logic into what strlen does. That would make the C code much less readable and not actually help that much. My test string is "abcdefghijklmnopqrstuvxyz", so it's all in the l1 cache.

Re: {n} times faster than C

#189

Post by orlp »

I made a variant that is (on my Apple m1 machine) 20x faster than the naive C version in the blog by branchlessly processing the string word-by-word:

    int run_switches(const char* input) {
        int res = 0;

        // Align to word boundary.
        while ((uintptr_t) input % sizeof(size_t)) {
            char c = *input++;
            res += c == 's';
            res -= c == 'p';
            if (c == 0) return res;
        }

        // Process word-by-word.
        const size_t ONES = ((size_t) -1) / 255;  // 0x...01010101
        const size_t HIGH_BITS = ONES > 7;
            p_accum += p_high_bits >> 7;
            if (++iters >= 255 / sizeof(size_t)) {
                // To prevent overflow in our byte-wise accumulators we must flush
                // them every so often. We use a trick by noting that 2^8 = 1 (mod 255)
                // and thus a + 2^8 b + 2^16 c + ... = a + b + c  (mod 255).
                res += s_accum % 255;
                res -= p_accum % 255;
                iters = s_accum = p_accum = 0;
            }
        }
        res += s_accum % 255;
        res -= p_accum % 255;

        // Process tail.
        while (1) {
            char c = *input++;
            res += c == 's';
            res -= c == 'p';
            if (c == 0) break;
        }

        return res;
    }
Fun fact: the above is still 1.6x slower (on my machine) than the naive two-pass algorithm that gets autovectorized by clang:

    int run_switches(const char* input) {
        size_t len = strlen(input);
        int res = 0;
        for (size_t i = 0; i

Re: {n} times faster than C

#190

Post by xoranth »

gpderetta wrote: post #156
xoranth wrote: post #49

I think I managed to improve on both this post, and its sequel, at the cost of specializing the function for the case of a string made only of 's' and 'p'. The benchmark only tests strings made of 's' and 'p', so I think it is fair. The idea is as follow. We want to increase `res` by one when the next character is `s`. Naively, we might try something like this: res += (c - 'r'); // is `res += 1` when c == 's' This do…

Even simpler: just sum all elements of the array. Then at the end subtract 'p'*len from the sum, then divide by ('s'-'p') to get the s count. The 'p' count is len minus the 's' count. The initial sum is easily vectorized as well. If I've not made any mistakes it should work. Only issue is possible overflow on the running sum. Can't be bothered to benchmark it though:). edit: missed the decrement when you see 's'. So…

That's likely the fastest way to do that without vectorization. But you'd need to upcast 's' to an uint64 (or at least an uint32). That means that vectorization would operate on 32/64 bit lanes.

With vectorization, I think the way to go is to have two nested loops, an outer advances by 32 * 255 elements at a time, and an inner one that loads 32 bytes, compares each character to 's', and accumulates on 8 bit lanes.

Then in the outer loop you do an horizontal sum of the 8 bit accumulators.

Post reply on HN