Function call fusion.

Or avoiding wasted memory and repeated work.

Apache Arrow project uses regular expression matching to implement the LIKE predicate by translating SQL pattern into a regular expression pattern:

While this approach works it has issues:

• replace function always allocates a new string, even if pat contains neither % nor _ leading to wasted memory and allocation overhead

• each replace invocation results in a full scan of the pat resulting in unnecessary repeated work

It's a fairly common problem, so unsurprisingly it has a generic solution - function call fusion. Thanks to referential transparency this optimization has been available for Haskell developers for a long time. For example, map fusion transforms a composition of maps

is transformed into a map of compositions:

which is more efficient since we iterate over input list and produce the output list only once.

So what does it mean for the original problem with SQL pattern translation? To compare the efficiency, we'll fuse repeated replace invocations in the original implementation

into a single function

It's not the most efficient implementation but is sufficient to deliver significantly better performance for cases when there are and there are not any matches. Benchmarks

show almost 3X improvement for the case without matches and ~25% speed up for the case with matches even for a fairly short input strings, foobarbazz and foo%bar_bazz:

Until your compiler supports fuse optimization, it's an important and useful technique for improving performance and efficiency.