Fix Boyer-Moore searcher with the Rytter correction • Hacker News Board

Re: Fix Boyer-Moore searcher with the Rytter correction

#51

Post by battery_cowboy » Sat, Apr 18, 2020, 2:58 AM UTC

StephanTLavavej wrote: post #49

ahelwer wrote: post #36

Earlier quoted context omitted.

Yeah I wrote that Wikipedia article, as much as a single person can. Used the textbook Strings, Trees, and Sequences by Gusfield; it never made mention of Rytter. I wouldn't say Wikipedia is a "terrible" source, though; compared to what? Papers? Textbooks? During the course of my career I've found major technical errors in about half of CS papers. Now the error is being documented & fixed in the Wikipedia article. My…

> you're guaranteed to have some bugs when implementing BM. Writing your own string search function seems nearly on the same level as implementing your own cryptographic functions, though. And that’s the Curse Of The Standard Library Implementers: we’re the ones that have to implement Boyer-Moore, floating-point string conversions, etc. so everyone else can use them :-)

Why aren't there projects amongst the standard library maintainers to make some standard tests and maybe even APIs? That way you'd know that every library implements each algorithm correctly.

Re: Fix Boyer-Moore searcher with the Rytter correction

#52

Post by fithisux » Sat, Apr 18, 2020, 4:41 PM UTC

Is Dlang affected?

Re: Fix Boyer-Moore searcher with the Rytter correction

#53

Post by StephanTLavavej » Sun, Apr 19, 2020, 5:49 AM UTC

battery_cowboy wrote: post #51

StephanTLavavej wrote: post #49

Earlier quoted context omitted.

> you're guaranteed to have some bugs when implementing BM. Writing your own string search function seems nearly on the same level as implementing your own cryptographic functions, though. And that’s the Curse Of The Standard Library Implementers: we’re the ones that have to implement Boyer-Moore, floating-point string conversions, etc. so everyone else can use them :-)

Why aren't there projects amongst the standard library maintainers to make some standard tests and maybe even APIs? That way you'd know that every library implements each algorithm correctly.

We actually do use libc++'s test suite, which has found several bugs, but not this one (apparently because they don't yet have std::boyer_moore_searcher).

Re: Fix Boyer-Moore searcher with the Rytter correction

#54

Post by rurban » Mon, Apr 20, 2020, 10:17 AM UTC

Nice, but using decade old and overly slow string search algorithms still is questionable. There are hundreds of faster algos, the fastest and most stable currently being epsm (2013). https://www.dmi.unict.it/~faro/smart/algorithms.php?algorith...

Re: Fix Boyer-Moore searcher with the Rytter correction

#55

Post by rurban » Mon, Apr 20, 2020, 10:19 AM UTC

MattPalmer1086 wrote: post #19

skyde wrote: post #8

Any one know why the Turbo Boyer-Moore algorithm is not more popular. Any case when Boyer Moore would be better?

There are literally hundreds of string search algorithms published now (including a large number of Boyer Moore variants). There's a great resource called SMART for those interested in exploring this, with implementations of many of them and a simple benchmarking tool. https://smart-tool.github.io/smart/ Although Boyer Moore is well known, there are generally faster algorithms available these days. For short patterns…

Fastest and best is the latest, EPSM. For all cases, given you are on x86_64 or aarch64 with sse4.2

The cited implementation has only minor problems, which I fixed in my fork.

Re: Fix Boyer-Moore searcher with the Rytter correction

#56

Post by mcbain » Thu, Apr 30, 2020, 3:00 AM UTC

StephanTLavavej wrote: post #27

mcbain wrote: post #9

A while back I filed an issue on the MSVC std::vector implementation as the behaviour of a weird corner case differed from GCC/Clang. The reply I got from STL himself was fantastic, pointing out that it was [paraphrasing here] a wart in the spec, and that neither were actually incorrect. To my lasting regret, I didn't keep an ahem offsite backup of some of those corp emails. Hence I can't recall the exact details.

This sounds like the vector >> fiasco, where a vector contains elements that are movable-only (you can't copy a list >, only move it), yet with throwing move constructors (as MSVC's list, set, and other node-based containers dynamically allocate sentinel nodes when default/move-constructed - this is a behavior difference from GCC's libstdc++ and Clang's libc++, where both dynamically-allocated and container-internal…

I only just noticed this reply - many apologies.

Yes, that's the one! Our fix was explicitly deleting the copy constructor. In essence a one-liner for us, but you can't see the iceberg of an issue beneath the surface.

Thanks once again. :)