Live data from Hacker News

{n} times faster than C

owen.cafe

161–170 of 249 posts

Re: {n} times faster than C

#161

I'm not so sure that the right take-away is "hand-written assembler is 6x faster than C." It's more like "jumps are a lot slower than conditional arithmetic." And that can [edit:often] be achieved easily in C by simply not using switch statements when an if statement or two will work fine. Rewriting the C function as follows got a 5.5x speedup: int run_switches(char *input) { int r = 0; char c; while (1) { c = *input…

Yes, but this will backfire on ARM, where jumps are as roughly fast as conditional arithmetic.

The whole point of using C is not to think about the underlying architecture. As soon as you start taking "jumps are a lot slower than conditional arithmetic on x86" into account, you're not writing in C, you're writing in assembly with extra steps :-)

Re: {n} times faster than C

#162
post #87
post #47

Earlier quoted context omitted.

The version that's friendly to the compiler is described in part two: https://owen.cafe/posts/the-same-speed-as-c/ It achieves 3.88GiB/s I intentionally didn't go down the route of vectorizing. I wanted to keep the scope of the problem small, and show off the assembly tips and tricks in the post, but maybe there's potential for a future post, where I pad the input string and vectorize the algorithm :)

So I downloaded your code. On my desktop, with loop-9 gcc I got ~4.5GB/s, and with loop-7 I got ~4.4GB/s. With the following code: #include int run_switches(const char *s, size_t n) { int res = 0; for (; n--; ++s) res += (*s == 's') - (*s == 'p'); return res; } I got ~31GB/s in GCC and ~33GB/s in Clang. This is without any padding, or SIMD intrinsics, or any such nonsense. This is just untying the compiler's hands an…

Another good reason to write optimization-friendly C (or similar) over assembly code, especially in libraries, is that the compiler will evolve with CPUs, while the assembly code will not.

I've seen plenty of cases where replacing hand-written assembly with C (or similar) lead to a substantial performance increase because the assembly code was written for some old CPU and not the best way of doing things on current CPUs.

Re: {n} times faster than C

#163

Earlier quoted context omitted.

I'd be curious to learn why CPUs don't have conditional move speculation.

Speculative execution is all about control flow. It's about what value is in the instruction pointer at some nebulous point in the future. A conditional jump can put one of two values into the instruction pointer, they will either increment the instruction pointer (jump not taken) or put the immediate value into the instruction pointer. (jump taken) cmov/sete are utterly deterministic; they always increment the instr…

> Speculative execution is all about control flow

It's murkier than that. Speculation also deals with the order in which instructions can be executed. Take for example memory ordering (discussed in a mini essay elsewhere here): we typically speculate that all loads are unrelated to any other older in-flight stores with unresolved addresses so that we can optimistically launch them. This is not a control flow issue but it is something we both speculate and predict (memory dependence predictors!) despite the next PC being essentially deterministic.

Re: {n} times faster than C

#165

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 purpose of control flow speculation is to avoid stalling the pipeline.

If each instruction was executed in one single clock cycle, the cost of executing a branch would be one cycle and that's it.

However since there is a maximum speed at which operations can happen in hardware, the period of such a clock cycle that can execute a whole instruction would be very long and so the amount of "instructions per second" the CPU could execute would be low.

Now, if you can break up each instruction in smaller steps and execute the smaller steps in an overlapping manner, such that while you're executing the second step of the first instruction you're executing the first step of the next instruction and so on (like on an assembly line in a factory) you can have a much shorter clock period for each of these steps, and at the end of each clock tick an instruction would complete execution. The CPU will be still running one instruction per clock cycle, but since each clock period is shorter the overall instruction per second rate will be higher.

But for this to work the next instruction you want to execute must be known in advance so that at each clock cycle the CPU can start step 1 of a new instruction.

That's easy when the program is executing sequentially but when there are branches involved it's more tricky.

And that's tricky also if the branch is not conditional! If the instruction execution is broken into many small steps, it may take one or more steps before figuring out that you have a branch in the first place, let alone decoding where you need to branch to. In the meantime the CPU will have happily started to execute the first "steps" of the next instruction.

This is called a "branch hazard"

Early CPU implementations handled branch hazards by just throwing away the intermediate states if the few instructions that we're half way through the pipeline and call it a day (stalling the pipeline).

Early RISC CPUs attempted to be clever and use a trick called "delay slots": the instruction(s) already in the pipeline will continue to execute as if they were logically before the branch. This puta the onus to the programmer (or the compiler) to make sure that only instructions that are safe to be executed regardless of whether the branch is taken or not, are actually put after the branch instruction (otherwise you can just write nops).

But branch delay slots are not a panacea. As pipelines got deeper it became I practical to have a large number of delay slots and even a small number of delay slots were often just filled with nops anyway.

Improving on UNconditional branches was done by "looking ahead" in the instruction stream for branch instructions. When the instructions are all of the same size it's easy to quickly look a few instructions ahead and tell when you found a branch. You also need an instruction encoding scheme that is relatively fast to decode, at the very least it should be fast to decode branches (the more complicated the logic to decode a branch is, the farther ahead you'd have to look in the instruction stream, which in turn would limit the size of the sequence of instructions you can fill your pipeline with between subsequent branches).

To further complicate the matter, even if you found the branch instruction and you decoded it, it doesn't mean you yet know where it will branch to!

Indirect jumps (where the address is in a register) are similar to conditional jumps in that you don't know the address you're jumping to by merely looking ahead in the instruction stream and noticing the branch instruction. You need to either wait until you execute the branch and stall the pipeline in the meantime, or keep them in the pipeline and flush the pipeline once you know the target of the branch.

The next trick that CPU designers came up way before speculative execution is "branch target prediction".

The CPU keeps a little associative memory that maps addresses of a branch instruction to branch targets. When the lookahead logic spots a branch instruction it looks in this map and gets a guess of the branch target and uses that immediately ad the next instruction so that the pipeline is kept fed with something.

If by the time the branch instruction is executed the guess turned out to be wrong, the pipeline is flushed in the same way it would have to be flushed anyway if we had no clever branch lookahead in the first place. But if the guess was right we paid only one cycle to execute the branch.

This works for indirect unconditional branches and also for conditional branches! The prediction logic can be more subtle and complicated, many many things gave been attempted but this the general idea.

Re: {n} times faster than C

#166

Earlier quoted context omitted.

To a point . A modern C compiler generates mind boggingly fast assembler. However, some languages make it way easier to write sophisticated algorithms more easily. For instance, suppose you're writing a program to find the nth Fibonacci number for whatever reason. In Python, the naive version might look like: def fib(n): if n On my machine, that takes about 12 seconds to find the 40th number. Altering that slightly l…

How many brains has the Fibonacci example broken... You'd unroll it to a loop on both C and Python. Fibonacci doesn't need a cache. It needs K previous values, where K=1.

If for some reason you really wanted to compute Fib(n) for ridiculously large numbers of n, you would probably use that [Fib(n), Fib(n-1)] = A [Fib(n-1), Fib(n-2)] for the transition matrix A = [[1, 1], [1, 0]] and thus [Fib(n+1), Fib(n)] = A^n [Fib(1), Fib(0)] and then use exponentiation by squaring to compute A^n directly and thus Fib(n) in log_2(n) steps.

Re: {n} times faster than C

#167

Earlier quoted context omitted.

Is this the reason I dont usually see any speed up if I eliminate array boundary checking in C#? The jump condition is almost always false, is this what "predictable" means?

Indeed. The cost of bound checking is second order effects like making vectorization harder, slightly higher instruction (and possibly data) cache pressure, or requiring higher decode bandwidth. For the vast majority of programs these bottlenecks do not really matter.

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?

Re: {n} times faster than C

#168

Earlier quoted context omitted.

The inputs here are random which is the problem and why this isn't demonstrating that. Create an input of all 's' and compare it.

Better than random input, but still only ~half as fast as using sete [19:13:34 user@boxer ~/src/looptest] $ diff -u bench.c bench-alls.c --- bench.c 2023-07-06 16:04:16.000000000 -0400 +++ bench-alls.c 2023-07-06 19:13:34.000000000 -0400 @@ -17,7 +17,7 @@ int num_rand_calls = number / CHAR_BIT + 1; unsigned char *buffer = malloc(num_rand_calls * CHAR_BIT); for (int i = 0; i Jumps are slower.

In this benchmark the only loop carried dependency is over the res variable (edit: and of course the index). The jump doesn't break these dependencies, so for this specific problem, the additional latency of the cmov doesn't matter as it is always perfectly pipelined and cmov will always come up on top. But if the input of cmov depended on a previous value, then potentially a branch could be better given an high enough prediciton rate.

Re: {n} times faster than C

#169

Earlier quoted context omitted.

I had an old compilers professor say something like this once. “If you think you can do something better than the C compiler, I promise you you can’t.”

To a point . A modern C compiler generates mind boggingly fast assembler. However, some languages make it way easier to write sophisticated algorithms more easily. For instance, suppose you're writing a program to find the nth Fibonacci number for whatever reason. In Python, the naive version might look like: def fib(n): if n On my machine, that takes about 12 seconds to find the 40th number. Altering that slightly l…

adding @cache meaningfully changes the algorithmic complexity from O(1.8^^N) (iirc - it's obviously exponential) to O(N).

Re: {n} times faster than C

#170
Back-of-the-envelope approach that should eliminate most branching:

  int table[256] = {0};                                                           
                                                                                
  void init() {                                                                   
    table['s'] = 1;                                                             
    table['p'] = -1;                                                            
  }                                                                               
                                                                                
  int run_switches(char *input, int size) {                                                 
    int res = 0;                                                                
    while (size-- >= 0) res += table[input[size]];
    return res;                                                                 
  }
Post reply on HN