sklar.com/blog

Fast Multiple String Replacement in PHP

sklar@sklar.com (David) — 2010-09-29T12:10:46Z

At work, we added a language filter to Ning Pro last month. It lets Network Creators have naughty words (for the Network Creator's definition of "naughty") replaced with * characters.

A straightforward way to do this in PHP is to pass an array of words to look for and their replacements to a function like str_replace() or str_ireplace(). Or, similarly, use a regular expression that gloms the search terms together (and potentially checks word boundaries.) There are assorted WordPress plugins that work like this.

The problem with this approach is that it's really slow. Especially if you have a lot of words you're looking for. The amount of time it takes to do the search and replace grows in proportion to the number of words you're looking for. This is particularly unfortunate because usually, none of the words are ever found!

For our language filter, we took a different approach. We've packaged it up into a PHP extension called Boxwood and releasing it today as open source. (Find it on github: http://github.com/ning/boxwood.)

With Boxwood, you can have your list of search terms be as long as you like -- the search and replace algorithm doesn't get slower with more words on the list of words to look for. It works by building a trie of all the search terms and then scans your subject text just once, walking down elements of the trie and comparing them to characters in your text. It supports US-ASCII and UTF-8, case-sensitive or insensitive matching, and has some English-centric word boundary checking logic.

Take it for a drive and let us know what you think!

Efficiency is not one-dimensional, part MMDXXI

sklar@sklar.com (David) — 2004-04-28T18:41:05Z

In a discussion of the varying levels of efficiency in different web server configurations, Adam Trachtenberg writes, in part:

We've long since passed the inflection point where hardware resources
are more expensive than business objectives and developer costs, yet
we still persist in undervaluing those two assets. Just because
hardware has a tangible price doesn't mean that it's the only part of
the process with a cost.

Well put. Read Adam's entire message.

PHP Microbenchmarking

sklar@sklar.com (David) — 2010-05-04T13:07:53Z

I just posted on the Ning code blog about the PHP microbenchmarking framework we released:

I'm pleased to announce the release of ub, a PHP microbenchmarking framework. You can download it from http://github.com/ning/ub.

The goal is to make it as easy as possible to compare the runtime of alternative approaches to the same problem, such as different regular expressions, or different methods for string or array manipulation.

The source distribution contains a README with some documentation and a bunch of sample benchmarks.

For normal use, it is rare that two similar, but different approaches produce appreciable differences in runtime. (Inefficient regexes and bloated call stacks aside.) The payoff from this kind of benchmarking is really on operations that happen hundreds or thousands of times in a request, or are happening on hundreds or thousands of servers. At that point, shaving off small amounts of runtime performance can really make a difference.

I am looking forward to beef up the set of included benchmarks -- contributions are welcome!