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

241–249 of 249 posts

Re: {n} times faster than C

#241

Post by fuber2018 »

utopcell wrote: post #229
redf1sh wrote: post #225

Earlier quoted context omitted.

I don't understand something. What does n&127 and n>>7 mean here?

127 is 128-1 or 2^7-1, or 1111111b (in binary). It is a faster way to compute n%D when D is known to be a power-of-two. n>>7 is equal to n/(2^7), and is a faster way to divide with a power-of-two.

The code in question has to process a string of variable length.

But the compiler/CPU can process bytes one at a time or much faster in groups. The code is trying to process as much as possible in groups of 128.

But since the caller can pass in a string which is not a mulitple of 128 chars, the first for-loop (& 127) will figure out how much of the string to process such that the remaining string length is a multiple of 128.

The second for-loop (>> 7) calculates divides by 128 (>> 7) to find out how many multiples of 128 there are to process. The inner for-loop processes 128 chars looking for 's' chars.

Now the for-loop within a for-loop doesn't look any faster than the plain single for-loop, but I'd assume that the heuristics of certain compilers can intuit that it can generate code to operate on multiple chars at the same time (SIMD instructions), since the result of one operation are independent of others.

On a compiler that cannot generate SIMD code, the code won't be much faster, if at all, than the naive straightforward manner.

Re: {n} times faster than C

#242

Post by 6510 »

throwaway14356 wrote: post #145
saagarjha wrote: post #130

Earlier quoted context omitted.

You’d need to count both as other characters are ignored.

naïve q2: does that mean most comparisons are no match 3 times? could one do a bitwise operation and fuzzy test for all 3 in one go?

Is it still ASCII? If so p is 01110000 and s is 01110011(?) but I don't know what \0 is, is it 00000000? Is there anything else know about the data? If the rest of the characters are all numbers, those all start with 0011 but that doesn't seem of much use. 4-9 have either the 5th or 6th bit set.

Only if AND with 00001100 yields zero the other 3 tests are needed.

Ofc I have no idea what opcodes the language provides.

Re: {n} times faster than C

#243

Post by moonchild »

bruce343434 wrote: post #239
bruce343434 wrote: post #238

Earlier quoted context omitted.

E-graphs are interesting, but one still has to deal with combinatorial explosions. Are you alluding to some powerful search heuristic? Your example touches on the problems of inflexible ABI, namely caller saved registers and the unknowability of side effects of external functions. Very weird that it can't reorder `r = x+y` despite it having no "observable" side effect until `return r`, since that return dominates the…

I looked at it closer. In C, it is a side effect to assign to a variable. For an extern function not annotated __attribute__((pure)) the compiler has to assume the function call generates side effects. This prevents it from reordering the assignment and function call. Since x86-64 ABI has caller saved registers, in the case where it calls eff() first, it has to save x and y, and after the call, restore them.

The work on e-graphs I refer to is https://egraphs-good.github.io/>—amortised rebuilds.

My example has nothing whatsoever to do with abi, and everything to do with ir. f and g are exactly semantically equivalent, and this equivalence is trivial to show; that the compilers generate different code for each demonstrates redundancies in their ir.

> it is a side effect to assign to a variable

But that variable is not aliased here.

Re: {n} times faster than C

#244

Post by epcoa »

sitkack wrote: post #240
epcoa wrote: post #114

Earlier quoted context omitted.

With all due respect this is quite literally the level of stuff covered in an undergrad EE architecture course and is covered in an elementary text like Patterson and Hennessy.

> With all due respect > quite literally You could have conveyed the close to the same thing by saying, "things like this are covered in Patterson and Hennessy" > elementary text Jesus, do you even lift? The rest of the discussion is amazing.

For those not aware Patterson and Hennessy is elementary (“relating to the basic elements of a subject.”) because it is often used in an introductory course of computer architecture. This isn’t a slight.

Re: {n} times faster than C

#245

Post by throwaway14356 »

6510 wrote: post #242
throwaway14356 wrote: post #145

Earlier quoted context omitted.

naïve q2: does that mean most comparisons are no match 3 times? could one do a bitwise operation and fuzzy test for all 3 in one go?

Is it still ASCII? If so p is 01110000 and s is 01110011(?) but I don't know what \0 is, is it 00000000? Is there anything else know about the data? If the rest of the characters are all numbers, those all start with 0011 but that doesn't seem of much use. 4-9 have either the 5th or 6th bit set. Only if AND with 00001100 yields zero the other 3 tests are needed. Ofc I have no idea what opcodes the language provides.

Here is a perfectly useless idea: AND with 00000010 would give 2 for s an 0 for p. (-1 and you have +1 for s and -1 for p as the article describes) Then you have a number that one could just add in stead of jumping to +1 or -1.

Re: {n} times faster than C

#246

Post by 414owen »

amm wrote: post #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; }

The array lookup approach taken in part two:

https://owen.cafe/posts/the-same-speed-as-c/

But taking the length of the string as a parameter is not, because that changes the problem statement (making the solution vectorizable)

Also note that you'll try to read element -1 of the input. You probably want to change the `>=` to a `>`

Re: {n} times faster than C

#247

Post by 414owen »

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)

This is pretty much `assembly language the game`: https://tomorrowcorporation.com/humanresourcemachine

It's not a useful architecture, but it teaches the thought process really well, and you end up discovering a lot of optimization naturally.

For this article, I'm measuring every step to see what the performance implications of the changes are, which, along with some educated guesses and some googling/reading other articles, was enough for me to figure out what was going on.

In part two (https://owen.cafe/posts/the-same-speed-as-c/) especially, I didn't know what was going on with the benchmarks for a long time. Eventually I got lucky and made a change, which led to a hypothesis, which lead to more tests, which led to a conclusion.

Re: {n} times faster than C

#248

Post by [deleted] »

zaxomi wrote: post #149
torstenvl wrote: post #56

Earlier quoted context omitted.

I haven't run any benchmarks, but jump-if-equal and set-if-equal would seem to have the same level of predictability. My naive, untested intuition is that there's only one meaningful difference: the former has to dump the entire pipeline on a miss, and the latter only has to nop a single instruction on a miss. But maybe I'm missing something. I'll re-read his rant. EDIT: Linus rants a lot, but makes one concrete clai…

Did you test this on a Pentium 4, the processor that Linus is talking about?

[deleted]

Re: {n} times faster than C

#249

Post by red2awn »

I experimented with different optimizations and ended with 128x speedup. The improvement mainly comes from manual SIMD intrinsics, but you can go a long way just by making the code more auto-vectorization friendly as some other comments have mentioned. See:

https://ipthomas.com/blog/2023/07/n-times-faster-than-c-wher...

Post reply on HN