This is literally the naive, awful, O(nm) strstr but with the C tweaked until ancient gcc gets x86 reg alloc optimalhttps://twitter.com/RichFelker/status/856498772049891329 …
-
-
-
My point isn't to poke fun at the code, but that this kind of coding is the necessary evolutionary endgame with non-optimizing compilers.
-
You end up stuck in local extrema ("fast" ver of quadratic algo) b/c nobody's qualified to rewrite the linear-time one in "high-level asm".
-
And you end up with code that's impossible to debug/verify/audit because it's not even obvious what it's doing.
- 1 more reply
New conversation -
-
-
Nice digging... I "enjoyed" reading this code. Naïve question, but: who nowadays argues that optimising compilers are unnecessary?
-
Good question. There's a large contingent who think optimizing compilers just harm security (esp. alias-analysis-based optimizations).
-
This would be a reasonable position if you'd be compiling the same code regardless of whether optimizing compilers existed, but you're not.
-
Without optimizing compilers, you'd be compiling hackish code full of even worse UB, written to get particular compiler to produce best asm.
-
Completely take that point. Without disagreeing, I don't believe we have the UX or incentive structures right w.r.t. how to exploit UB.
End of conversation
New conversation -
-
-
should also link to musl strstr so we can really see the comparison. also what is the perf difference at -O1 btw musl and glibc for this?
-
musl's is a linear-time algorithm and is roughly the same # of LoC. Timing is highly dependent on inputs. https://git.musl-libc.org/cgit/musl/tree/src/string/strstr.c …
-
The naive algo performs fine for finding "bxxx" in "[^b]{10000}bxxx", awful for finding "bxxx" in "(bxx){10000}xxx".
End of conversation
New conversation -
-
-
I deliberately chose not to comment it. You should have at least as much fun trying to understand it, as I had to write it :-).
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.