Needles in a Haystack

Recently, I was working on some code deep in the storage engine. As I was reviewing the code, it dawned on me that, at the core of it, a logging system is a sophisticated highly scalable “grep”.

With AI agents producing more code and continued growth of infrastructure everywhere, telemetry data volume has also continued to grow enormously. All applications (agentic or otherwise) produce a tremendous amount of logs. When applications don’t behave as expected, developers hop on to their favorite observability platform and searching across logs is one of the first starting points of investigation (dashboards being the other). During an investigation, it’s paramount that searches return results within a reasonable amount of time — typically a few seconds. To achieve this, we have to extract any optimization that we can from the resources available.

For the sake of this post, let’s focus only on “string contains” — a simple question — “show me the logs where a given pattern is contained”, that’s all. I thought it would be interesting to just run through different string matching algorithms and see how they perform — from simplest to most technically involved.

Setup

• Intel Xeon @ 2.60 GHz (n2, Cascade Lake), UseAVX=3
• JDK — Corretto 21.0.8.9.1
• 100k synthetic log lines, mean length of 255 bytes.
• Tested with 25 phrases (needles) with half to none of the log-lines in the corpus.

Let’s keep in mind that the log lines themselves are not on a heap buffer but rather a ByteBuffer that is backed by direct memory. This is important because inside a database, where we have hundreds of billions of rows (in compressed form), it’s common to use direct memory (outside of the purview of the garbage collector).

Methods

Let’s start with the baseline method.

Scan the bytes by hand

To avoid the allocation, we can do a direct byte comparison instead of using Java string contains method.

static int naiveIndexOf(ByteBuffer buf, int off, int len, byte[] needle) {
  int matches = 0;
  int nlen = needle.length;
  if (len < nlen) {
    return matches;
  }
  int max = off + len - nlen;
  byte first = needle[0];
  for (int i = off; i <= max; i++) {
    if (buf.get(i) == first && equalsRange(buf, i, needle, 1, nlen)) {
      matches++;
    }
  }
  return matches;
}

// Confirms needle[from, to) against the buffer at pos. Every method below uses this.
static boolean equalsRange(ByteBuffer buf, int pos, byte[] needle, int from, int to) {
  for (int k = from; k < to; k++) {
    if (buf.get(pos + k) != needle[k]) {
      return false;
    }
  }
  return true;
}

23.28 ms, ranging from 6.77 to 33.61.

We aren’t doing any allocations here. But there is a branch on every byte, a bounds-checked ByteBuffer.get on every byte, and no way to skip ahead. Lots of room for optimizations here.

Let’s try to implement some textbook algorithms for string matching.

Boyer-Moore-Horspool

Line the phrase up, compare from the right, and on a mismatch look at the haystack byte sitting under the phrase’s last position — a precomputed table says how far that byte lets you jump, up to the whole length of the phrase. Built once per phrase, not per value.

// Built once per phrase: how far each possible byte lets you jump.
HorspoolSearcher(byte[] needle) {
  _needle = needle.clone();
  Arrays.fill(_skip, needle.length);
  for (int i = 0; i < needle.length - 1; i++) {
    _skip[needle[i] & 0xFF] = needle.length - 1 - i;
  }
}

int indexOf(ByteBuffer buf, int off, int len) {
  int nlen = _needle.length;
  if (len < nlen) {
    return -1;
  }
  int last = nlen - 1;
  int end = off + len - nlen;
  int i = off;
  while (i <= end) {
    int j = last;
    while (j >= 0 && buf.get(i + j) == _needle[j]) {   // compare right to left
      j--;
    }
    if (j < 0) {
      return i;
    }
    i += _skip[buf.get(i + last) & 0xFF];   // next address depends on the byte just loaded
  }
  return -1;
}

This method gives a median latency of 14.59 ms across benchmark runs. Better but not as fast as I would like.

Knuth-Morris-Pratt

The other textbook answer, and the one with the better guarantee: O(n+m) in the worst case, and it never re-reads a haystack byte. It manages that by carrying a variable between positions — how much of the phrase currently matches.

// failure[i] is the longest proper prefix of needle[0..i] that is also a suffix of it --
// how far to rewind the match state without giving up overlap already proven.
KmpSearcher(byte[] needle) {
  _needle = needle.clone();
  _failure = new int[needle.length];
  int k = 0;
  for (int i = 1; i < needle.length; i++) {
    while (k > 0 && needle[i] != needle[k]) {
      k = _failure[k - 1];
    }
    if (needle[i] == needle[k]) {
      k++;
    }
    _failure[i] = k;
  }
}

int indexOf(ByteBuffer buf, int off, int len) {
  int nlen = _needle.length;
  if (len < nlen) {
    return -1;
  }
  int end = off + len;
  int k = 0;                       // how many needle bytes currently match
  for (int i = off; i < end; i++) {
    byte c = buf.get(i);
    while (k > 0 && c != _needle[k]) {
      k = _failure[k - 1];
    }
    if (c == _needle[k]) {
      k++;
      if (k == nlen) {
        return i - nlen + 1;
      }
    }
  }
  return -1;
}

Median latency: 32.74 ms, which is last place, behind even the naive loop it exists to improve on.

The guarantee is real, it’s just expensive here. That carried k is a loop-carried dependency running through a table lookup, so position i+1 can’t start until i has finished. And never re-reading a byte turns out to be the same thing as never skipping one: KMP touches every byte of the haystack, where Horspool jumps over most of them.

Alright, at this point, let’s dig into the weeds and try to optimize at a lower level and see how far we can push the code to do better.

SWAR: eight lanes in a long

SWAR is SIMD Within A Register — treat an ordinary long as eight independent byte lanes and operate on all eight with nothing but integer arithmetic.

The trick is turning a question like “which of these bytes equal c?” into “which of these bytes are zero?”, since zero bytes can be found without branching.

// if the variable b = 'c' then bcast is 0x6363...63.
long bcast = (b & 0xFFL) * 0x0101010101010101L;
static long zeroLanes(long x) {
  return ~(((x & 0x7F7F7F7F7F7F7F7FL) + 0x7F7F7F7F7F7F7F7FL) | x) & 0x8080808080808080L;
}

And zeroLanes:

Given these two methods, here is the full implementation.

static int swarIndexOfSingleAnchor(ByteBuffer buf, int off, int len, byte[] needle) {
  int nlen = needle.length;
  if (len < nlen) {
    return -1;
  }
  byte first = needle[0];
  long bcastFirst = (first & 0xFFL) * ONES;
  int max = off + len - nlen;
  int swarEnd = off + len - 8 - (nlen - 1);   // keeps the 8-byte load inside the value
  int i = off;
  while (i <= swarEnd) {
    long hit = zeroLanes(buf.getLong(i) ^ bcastFirst);
    while (hit != 0) {
      int pos = i + (Long.numberOfTrailingZeros(hit) >>> 3);
      if (equalsRange(buf, pos, needle, 1, nlen)) {
        return pos;
      }
      hit &= hit - 1;
    }
    i += 8;
  }
  while (i <= max) {
    if (buf.get(i) == first && equalsRange(buf, i, needle, 1, nlen)) {
      return i;
    }
    i++;
  }
  return -1;
}

The key here is that we are evaluating 8 bytes at a time instead of one byte at a time and we are using bitwise/numeric arithmetic for our matching.

This gives a median of 13.22 ms, range 5.10 to 21.55. But we can do better than eight lanes in a step.

SWAR, anchored at both ends

Same loop as above, but load a second word nlen-1 bytes further on and AND the two masks together. A lane now survives only if the phrase’s first byte sits there and its last byte sits at the right distance beyond it.

static int swarIndexOf(ByteBuffer buf, int off, int len, byte[] needle) {
  int nlen = needle.length;
  if (len < nlen) {
    return -1;
  }
  int last = nlen - 1;
  byte first = needle[0];
  long bcastFirst = (first & 0xFFL) * ONES;
  long bcastLast = (needle[last] & 0xFFL) * ONES;
  int max = off + len - nlen;
  int swarEnd = off + len - 8 - last;   // both loads stay inside the value
  int i = off;
  while (i <= swarEnd) {
    long hit = zeroLanes(buf.getLong(i)        ^ bcastFirst)
             & zeroLanes(buf.getLong(i + last) ^ bcastLast);
    while (hit != 0) {
      int pos = i + (Long.numberOfTrailingZeros(hit) >>> 3);
      // Both end bytes are already proven by the mask, so only the interior needs checking.
      if (equalsRange(buf, pos, needle, 1, last)) {
        return pos;
      }
      hit &= hit - 1;
    }
    i += 8;
  }
  while (i <= max) {
    if (buf.get(i) == first && equalsRange(buf, i, needle, 1, nlen)) {
      return i;
    }
    i++;
  }
  return -1;
}

So now we get a median of 9.15 ms, range 7.84 to 11.84.

Nothing about the step width changed. All that changed is how often the scan stops to confirm a candidate.

The Vector API

The same algorithm again, this time in real SIMD registers. 64 lanes rather than 8, and the compare is a single instruction instead of half a dozen integer ops.

static final VectorSpecies<Byte> SPECIES = ByteVector.SPECIES_PREFERRED;
static final int LANES = SPECIES.length();   // 64 on this machine

static int vectorIndexOf(MemorySegment seg, int off, int len, byte[] needle) {
  int nlen = needle.length;
  if (len < nlen) {
    return -1;
  }
  int end = off + len;
  int last = nlen - 1;
  byte first = needle[0];
  byte lastByte = needle[last];
  int vecEnd = end - LANES - last;
  int i = off;
  while (i <= vecEnd) {
    ByteVector head = ByteVector.fromMemorySegment(SPECIES, seg, i,        ORDER);
    ByteVector tail = ByteVector.fromMemorySegment(SPECIES, seg, i + last, ORDER);
    long hit = head.eq(first).and(tail.eq(lastByte)).toLong();
    while (hit != 0) {
      int pos = i + Long.numberOfTrailingZeros(hit);
      if (equalsRange(seg, pos, needle, 1, last)) {
        return pos;
      }
      hit &= hit - 1;
    }
    i += LANES;
  }
  // Up to 63 bytes left over. Falls through to the 8-byte SWAR scan, then to scalar.
  return swarScan(seg, i, end, needle);
}

This gets us to 6.06 ms (5.24 to 8.49), which is the best number in the benchmark. This comes out to approximately 6ns per logline.

Result summary

Final thoughts

One aspect to understand is that, on top of such matching code, there are multiple indexes that help speed up filtering significantly. Think of this method as the bottom of the stack, and many layers of optimizations on top of this.

If we were scanning+matching over 1 billion log lines, a single thread would take less than 60 seconds. But we have multiple threads/cores and we have smart indexes that reduce the need for this work dramatically as well. All of this combined is why it never takes more than a few seconds for queries to show results in practice.

The thing that stays with me is that, at scale, the simple things matter a lot. What works with less data would not work when the amount of data is multiplied — the number of allocations, the number of memory copies, branching, ordering etc.