3 ms·
The blog post is effectively implementing memmem() or strstr() that searches a short string in a long string. If we are allowed to use GNU extensions, the clean
by attractivechaos 4y ago
The blog post is effectively implementing memmem() or strstr() that searches a short string in a long string. If we are allowed to use GNU extensions, the cleanest solution is to call memmem(). Without memmem(), I would implement Boyer–Moore or Knuth–Morris–Pratt, which will be more scalable than the O(MN) implementation in the blog post. Time complexity matters.
- wk_end 4y agoYes, this was my takeaway - it was a very poor choice of example, because a known faster algorithm will crush the sort of micro-optimizations done here and be more readable. Or perhaps it was actually an incredibly good example, despite itself: a great illustration of precisely why jumping to micro-optimization isn't always the right solution.
- pclmulqdq 4y agoThis is also a problem where the algorithmically fastest solutions are also pretty much guaranteed to be faster, since they are equally cache-friendly and will almost always work out to fewer instructions. That is not always the case, but this is one of the times when it is.
- mlajtos 4y agoYou seem like you know a thing about C++, would you please take a look at this garbage? https://mlajtos.mu/posts/no-code-clean-performance https://mlajtos.mu/posts/no-code-clean-performance
- verall 4y ago> I really hate reading C++ so I really haven't checked any of the produced snippets for correctness. So they're almost certainly wrong...