Thread-safe large text buffer

Question

This is part of one of my projects called largetext, which actually stemmed from a question on Stack Overflow. The goal is to provide access to a very large text file as a CharSequence so that it be usable with not only java.util.regex but also grappa.

In the next version, I want to provide a thread safe version of the main class, LargeText. I have written and tested a thread safe implementation, but now I'd like to know whether it can be done faster... I have a worst case loss of performance of 40% in calls to .charAt().

---

To give an idea of the impact of this method, looking for all lines more than 10 characters long with a Matcher and the simple Pattern ^.{10,}$ (in multiline mode) will make one call to .charAt() for each character in the file; and the problem is even worse if you use lookarounds, of course. As such this method is pretty critical! On my machine, this method is called more than 80 million times per second with the non thread safe variant below

---

Some explanation on how this all works:

The text file is divided into "text ranges" by a decoding process, mapping one byte range (into the file) to one character range; therefore only the needed text is loaded. This class also handles callers to .charAt() having required a number of characters greater than what has been decoded at a given moment, waking them up when appropriate etc.

The LargeText class uses the principle of locality: when a caller calls .charAt(), it is very likely that the next call to .charAt() will hit the same character range, therefore it keeps the current CharBuffer and text range at hand, and only loads a new one if .charAt() gets out of range.

Note: copyright header and imports omitted for "brevity".

Here is the non thread safe version (link):

/**
 * A large text file as a {@link CharSequence}: non thread safe version
 *
 * <p>Despite the not really reassuring name, this is the class you will use the
 * most often.</p>
 *
 * <p>This class's {@code .charAt()} uses regular instance variables to store
 * the current text range and text buffer.</p>
 *
 * @see LargeTextFactory#load(Path)
 */
@NotThreadSafe
@ParametersAreNonnullByDefault
public final class NotThreadSafeLargeText
    extends LargeText
{
    private IntRange range = EMPTY_RANGE;
    private CharBuffer buffer = EMPTY_BUFFER;

    NotThreadSafeLargeText(final FileChannel channel, final Charset charset,
        final int quantity, final SizeUnit sizeUnit)
        throws IOException
    {
        super(channel, charset, quantity, sizeUnit);
    }

    @Override
    public char charAt(final int index)
    {
        if (!range.contains(index)) {
            final TextRange textRange = decoder.getRange(index);
            range = textRange.getCharRange();
            buffer = loader.load(textRange);
        }
        return buffer.charAt(index - range.getLowerBound());
    }
}

And here is the source to the thread safe version (link):

/**
 * A large text file as a {@link CharSequence}: thread safe version
 *
 * <p>You will need to use an instance of this class, and not the non thread
 * safe one, if your {@code LargeText} instance can potentially be used by
 * several threads concurrently.</p>
 *
 * <p>In order to be thread safe, this implementation uses instances of an inner
 * class holding both the current text range and buffer in a {@link ThreadLocal}
 * variable.</p>
 *
 * @see LargeTextFactory#loadThreadSafe(Path)
 */
@ThreadSafe
@ParametersAreNonnullByDefault
public final class ThreadSafeLargeText
    extends LargeText
{
    private static final ThreadLocal<CurrentBuffer> CURRENT
        = new ThreadLocal<>();
    private static final CurrentBuffer EMPTY_BUF
        = new CurrentBuffer(EMPTY_RANGE, EMPTY_BUFFER);

    ThreadSafeLargeText(final FileChannel channel, final Charset charset,
        final int quantity, final SizeUnit sizeUnit)
        throws IOException
    {
        super(channel, charset, quantity, sizeUnit);
    }

    @Override
    public char charAt(final int index)
    {
        final CurrentBuffer buf = Optional.fromNullable(CURRENT.get())
            .or(EMPTY_BUF);
        if (buf.containsIndex(index))
            return buf.charAt(index);
        final TextRange textRange = decoder.getRange(index);
        final IntRange range = textRange.getCharRange();
        final CharBuffer buffer = loader.load(textRange);
        CURRENT.set(new CurrentBuffer(range, buffer));
        return buffer.charAt(index - range.getLowerBound());
    }

    private static final class CurrentBuffer
    {
        private final IntRange range;
        private final CharBuffer buffer;

        private CurrentBuffer(final IntRange range, final CharBuffer buffer)
        {
            this.range = range;
            this.buffer = buffer;
        }

        private boolean containsIndex(final int index)
        {
            return range.contains(index);
        }

        private char charAt(final int index)
        {
            return buffer.charAt(index - range.getLowerBound());
        }
    }
}

Here's a complete example to illustrate the difference. The tested file here is "only" 800 MiB and I have chosen on purpose a small window of 256 KiB.

You can change four things:

• Path to the tested file (you'll have to, and generate a sufficiently large file, of course)
• Window size
• The call within the try-with-resources block: this example loads the thread safe version; replace with .load() for a non thread safe version
• The tested regex

public final class Foo { private static final Pattern PATTERN = Pattern.compile("^.{10,}$", Pattern.MULTILINE);

 public static void main(final String... args)
    throws IOException
{
    final LargeTextFactory factory = LargeTextFactory.newBuilder()
        .setWindowSize(256, SizeUnit.KiB).build();
    final Path path 
        = Paths.get("/home/fge/tmp/jsr203/docs/BIGFILE.txt");
    final Stopwatch stopwatch = Stopwatch.createUnstarted();

    try (
        final LargeText largeText = factory.loadThreadSafe(path);
    ) {
        int count = 0;
        final Matcher m = PATTERN.matcher(largeText);
        stopwatch.start();
        while (m.find())
            count++;
        stopwatch.stop();
        System.out.println(count + " matches");
        System.out.println(stopwatch);
    }
}
}

You'll have to:

git clone https://github.com/fge/largetext.git

then:

./gradlew compileJava
# if Windows:
gradlew.bat compileJava

Or use your IDE. It requires a JDK, nothing else, but version 7 or higher.

So, as you can see, in the thread safe variant, I use an internal class storing both the current range and buffer, and use a ThreadLocal to store it.

Also, the initial values of EMPTY_RANGE and EMPTY_BUFFER are respectively new IntRange(0, 0) and CharBuffer.allocate(0). The IntRange class is here.

Is there a way to improve the thread safe performance?

Answer 1

How large buffer size are you using? What is the hit/miss frequency on your buffer in charAt()?

If the hit frequency is less than 90% and you're doing as you say 80E6 charAt() per second that means you have 8 million buffer allocations per second which is going to cause the GC significant head aches. AFAIR the JVM can stall all threads while doing GC under certain circumstances (I had a similar problem developing a high-performance parallel java application).

So I would change:

    CURRENT.set(new CurrentBuffer(range, buffer));

to:

    buf.range = range;
    buf.buffer = buffer;

and change the visibility in CurrentBuffer, it's a private nested class so you're not breaking encapsulation any way. This will put less strain on the GC.

Also, if there is any reason to believe that charAt() is progressing even roughly linearly through the indices, a pre-fetch running in the background would speed things up.

Edit:

So with the stats from the comments, the lines executed 99% of the time is:

Not thread safe:

    if (!range.contains(index)) {
        // Branch not taken
    }
    return buffer.charAt(index - range.getLowerBound());

Thread safe:

    final CurrentBuffer buf = CURRENT_BUFFER.get();
    if (buf.containsIndex(index)) // Branch taken
        return buf.charAt(index);
    ... stuff on the stack ...

Set speculation hat: On

The JIT should inline expand the function calls to buf.containsIndex() and buf.charAt, it should also not do anything with the stack variables (not even initializing). So the remaining difference is CURRENT_BUFFER.get() and the book keeping associated with the buf variable which could make or break here as you're only doing a few instructions to fetch the data every time. Adding a few book keeping instructions on the buf variable could have a big impact in your case. I would investigate if I could get rid of it somehow, maybe encapsulate it somehow so the same instance is used in all calls.

Now if you doubt your JVM is good, you can try to inline the two function calls manually and restructure the thread safe variant like this:

    final CurrentBuffer buf = CURRENT_BUFFER.get();
    if (!buf.containsIndex(index)){
        final TextRange textRange = decoder.getRange(index);
        final IntRange range = textRange.getCharRange();
        final CharBuffer buffer = loader.load(textRange);
        CURRENT.set(new CurrentBuffer(range, buffer));
        return buffer.charAt(index - range.getLowerBound());
    }
    return buf.charAt(index);

just in case the JVM is unable to deduce that those stack variables shouldn't be initialized unless you actually get there.

Answer 2

I'll freely admit that my following suggestions are hunches. I hope they make some difference, but they may be negligible.

• Override ThreadLocal.initialValue(). This will eliminate calls to Optional.fromNullable: you will always have a non-null value.

  private static final ThreadLocal<CurrentBuffer> CURRENT = new ThreadLocal<>() {
      protected CurrentBuffer initialValue() {
          return EMPTY_BUF;
      }
  };
  

• Cache single last buffer [?]. This may eliminate some calls to CURRENT.get(), but I don't know if the added complexity is worth it. It won't help if there are enough cores to run all threads, but it may improve throughput if there are many more threads. Worth a shot if all else fails?

  static class ThreadStash {
      final CurrentBuffer buf;
      final Thread t;
  
      ThreadStash(CurrentBuffer buf, Thread t) {
          this.buf = buf;
          this.t = t;
      }
  }
  
  volatile ThreadStash stash = new ThreadStash(EMPTY_BUF, Thread.currentThread());
  
  @Override
  public char charAt(final int index)
  {
      final Thread curThread = Thread.currentThread();
      CurrentBuffer buf;
      ThreadStash stash = this.stash;
      if ( stash.t == curThread ) {
          buf = stash.buf;
      } else {
          buf = CURRENT.get();
          stash = new ThreadStash(buf, curThread);
      }
      if (buf.containsIndex(index))
          return buf.charAt(index);
      final TextRange textRange = decoder.getRange(index);
      final IntRange range = textRange.getCharRange();
      final CharBuffer buffer = loader.load(textRange);
      buf = new CurrentBuffer(range, buffer);
      CURRENT.set(buf);
      stash = new ThreadStash(buf, curThread);
      return buffer.charAt(index - range.getLowerBound());
  }