Dug up this historic example from glibc of why optimizing compilers are a necessary mitigation against hideous code: https://sourceware.org/git/?p=glibc.git;a=blob;f=string/strstr.c;hb=0ecb606cb6cf65de1d9fc8a919bceb4be476c602 …
-
-
Replying to @RichFelker
Rich Felker Retweeted Rich Felker
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 …
Rich Felker added,
5 replies 1 retweet 4 likes -
Replying to @RichFelker
Is that still faster than a modern properly optimized boyer-moore impl? BM should be linear.
1 reply 0 retweets 0 likes -
Replying to @ArvidGerstmann
No, it's much slower. BM isn't constant-space, but there are at least two known, very good constant-space and linear-time algorithms.
1 reply 0 retweets 0 likes -
Replying to @RichFelker
Doesn't BM become linear time with Galil's addition? What are the two known alternative algorithms?
2 replies 0 retweets 0 likes
The problem is failure to be constant-space. strstr needs ability to run in constant-space because it does not admit errors.
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.