Hacker News Reader

Comment by robinhoode | Hacker News Reader

Do projects like this ever get included into the mainstream? Would this be an appropriate candidate for inclusion into PHP's standard library?

View on HN

I would have hoped (but have no idea) that PHP simply uses libc's strstr in their implementation of strstr. If this is the case, then this would need to be included in the relevant libc for the platform you're using PHP on.

I was going to have that be my entire comment here, but I figured this was easy enough to check - so I pulled php 5.5.7 source, and because of option parsing complexities strstr ends up being implemented in terms of php_memnstr, which is a macro for zend_memnstr, which in turn calls memchr and memcmp repeatedly in a loop. So, no, libc's strstr doesn't seem to be used.

I'm a little unsure whether or why this has to be so complex, but after a quick dip the water doesn't seem inviting enough for me to follow up.

strstr assumes null-terminated strings right?

With regard to your comment about complexity, the cunning thing here is that these algorithms find a substring in a string very quickly, often without even looking at every character in the string.

For example, Boyer-Moore (http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algor...) starts by looking at the end of the substring. If it finds a match, it searches earlier. If it does not find a match, it can skip ahead by several characters (possibly even the length of the substring, depending on how the match failed). How much to skip ahead is a bit complicated, but can be calculated in advance.

Consider searching for a substring consisting of 1000 'a's. Boyer-Moore starts by looking at the 1000th (1-indexed) character. If it's an 'a', it then walks back and checks the 999th, 998th etc. However, if it's not an 'a', it can immediately skip on to examine the 2000th character, i.e. only looking at 1 in every 1000 characters. As you can imagine, this can be very fast!

The Railgun implementation seems to be a combination of improved Boyer-Moore (Boyer-Moore-Horspool-Sunday) with Rabin-Karp (which uses hashing). My understanding is that these algorithms complement each other, so if you have an input string that is particularly inefficient with one algorithm, it automatically picks the other one.

Since many programs have string-searching in their innermost loops, spending some time optimizing this function can be worthwhile.

I think your parent was referring to why php's implementation is so complex.

Indeed. PHP is often criticized for having inconsistently named or patterned libraries, and the response is usually "PHP is a relatively light wrapper to a bunch of C libraries" -- In fact I saw 3 versions of strstr in PHP core - strstr, mb_strstr, and grapheme_strstr. I guess I would have expected one of them to be a somewhat thin wrapper around libc's strstr.

As another commentator pointed out, libc's strstr assumes NUL-terminated strings. Maybe php's doesn't? Which seems a bit odd to me in light of the explanation of PHP's genesis as having roots in C, but stranger things...

I'm not surprised at all that libc's strstr would be complex.

If you ever maintained anything big enough, you'd know that what is here presented misses almost every precondition to actually be included. It just looks like a lot of mess and trouble for anybody who dares to touch it. Hit: what's signal to noise ratio of the page linked here and the corresponding codeproject page? Well the page about the function optimization with 5 MB irrelevant pngs and a lot of unprocesssed outputs of some code runs is surely very artistic but it looks as the author actually wanted to make it harder to the people to understand what he is doing.

Note the OP often mentions that the algorithm doesn't work for lenght == 1, which is unacceptable for a general library function.

I didn't read every update of the code but it looks like it is written in c only. Critical code is usually implemented with the best algorithm and then converted/optimized manually to/in assembly.

I'm not sure what the negatives of adding length == 1 would be, but I don't think they would decrease performance enough to make it more then strstr.

It really wouldn't do much at all if it's not in the loop.

Reply on news.ycombinator.com