Hacker News Reader

Comment by dannypgh | Hacker News Reader

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.

View on HN

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.

strstr assumes null-terminated strings right?

Reply on news.ycombinator.com