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 -
Replying to @ArvidGerstmann
Two-way and SMOA are the ones I had in mind. A great resource on string matching algorithms is here: http://www-igm.univ-mlv.fr/~lecroq/string/index.html …
2 replies 0 retweets 1 like -
Replying to @RichFelker @ArvidGerstmann
What they all seem to have in common is utilizing an order relation on the alphabet/charset/code units.
1 reply 0 retweets 0 likes
This makes it difficult (likely impossible) to adapt them to matching fnmatch/glob/wildcard type search patterns, even without *.
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.