Background

My previous article News Goggles Rules Engine Demo in Scala and Java describes a data parser that processes Article feeds and Subscriber preferences from text files. The parser reads the Prolog predicate syntax in the text files and loads memory list and dictionary structures.

I scaled the same data parser approach to my corporate rules engine prototype with very good results. The automated integration regression tests were able to parse more than 2 megabytes of text and process the matching rules in just over 3 seconds.

This was on my home workstation. I loaded my rules engine project onto my netbook and ran the tests there. The run took about 5 minutes! At the time, I assumed the netbook was running in power-conserving slowdown mode.

I loaded the project on the 8-core Intel-powered workstation at my desk at the office and saw the same horribly slow performance. My home workstation is a 4-core AMD-powered workstation about the same age as my work computer. I started to wonder if the AMD architecture could really be that much more efficient for my code base.

I started comparing the machine environments and realized I was running different versions of the Java Virtual Machine in each environment. My home workstation was running JDK 1.6 and the netbook and office machine were running recent updates of JDK 1.7.

I installed JDK 1.7u5 on both the netbook and my office machine as an alternate Java version and re-ran the tests. The tests ran in 3 seconds just like my home workstation.

The Culprit

A Google search for “scala parser performance java 7” included this page in its results: Performance of JavaTokenParsers with java7..

It turns out that between JDK 1.7u5 and JD 1.7u6 the internal String implementation for the substring function changed significantly. Previously the returned String variable actually referenced the appropriate portion of the original String’s character array memory. Starting with JDK 1.7u6 the substring text is copied to a completely new character array on the memory heap.

The revision was made to solve a memory leak problem that plagued many long-running server applications. When a substring result references a portion of a very large source string, the substring’s reference prevents garbage collection of the entire source string. For relatively small substrings, the JDK implementors decided that copying the relevant text to a new heap object was inexpensive enough to justify the ability to reclaim the original source string’s memory.

How Does This Affect Our Parser?

Inside the scala.util.parsing.combinator package in the Scala 2.9 libraries the RegexParsers trait class contains logic similar to this in several places:

  protected def handleWhiteSpace(source: java.lang.CharSequence, offset: Int): Int =
    if (skipWhitespace)
      (whiteSpace findPrefixMatchOf (source.subSequence(offset, source.length))) match {
        case Some(matched) => offset + matched.end
        case None => offset
      }
    else
      offset

The source.subSequence(offset, source.length) function call represents the vulnerable operation affected by the new JDK 1.7u6 String memory revision. With JDK 1.7u5 and earlier (including all versions of JDK 1.6), this operation merely allocates a pair of (start, end) character pointers in memory. Starting with JDK 1.7u6 and later, this operation copies all of the string after the offset position to a new memory object.

The parser invokes this subSequence operation repeatedly as it gobbles its way thru the text being parsed. As small tokens are recognized and retrieved from the head of the text, the remaining tail of the text gets copied again and again.

The memory-copy performance hit is on the order of the square of the original text length. Twice the text will take four times as long to parse. 100 times the text will take 10,000 times as long. One thousand times the text will take one million times as long! (Cue up Dr. Evil …)

Where’s The Promised Polymorphism?

The saving grace comes from the observation by Richard Searle that “The Scala parser fortunately uses CharSequence”. (See his posting Java 7u6 String performance regression.)

That declaration source: java.lang.CharSequence in the handleWhiteSpace method signature refers to an interface rather than the concrete String class. This makes the world of difference as it opens up the chance to implement a polymorphic stand-in for the String class when passing text to our parser.

Mr. Searle has kindly provided a class using the decorator pattern to wrap a normal Java String and provide the shared-memory behavior our parser’s performance requires. Note that a decorated String is still immutable thanks to the final declarations on the internal properties:

package com.live.rrutt.newsgoggles.lib;

//Reference: http://cognitiveentity.wordpress.com/2012/09/13/java-7u6-string-performance-regression/

public class StringDecorator implements CharSequence {

  private final String contents;
  private final int offset;
  private final int length;

  public StringDecorator(String contents) {
    this.contents = contents;
    this.offset = 0;
    this.length = contents.length();
  }

  private StringDecorator(String contents, int offset, int length) {
    this.contents = contents;
    this.offset = offset;
    this.length = length;
  }

  public int length() {
    return length;
  }

  public char charAt(int index) {
    return contents.charAt(index + offset);
  }

  public CharSequence subSequence(int start, int end) {
    return new StringDecorator(contents, offset + start, end - start);
  }

  public String toString() {
    return contents.substring(offset, offset + length);
  }

}

Putting It In Practice

Within our RulesEngine.scala class file we simply need to replace this logic

  def loadData(rulesDataText: String): Boolean = {
    val p = new RulesDataParser
    val parseResult = p.parseAll(p.rulesList, rulesDataText) 

with this logic

  def loadData(rulesDataText: String): Boolean = {
    val p = new RulesDataParser
    val rulesDataCharSequence = new com.live.rrutt.newsgoggles.lib.StringDecorator(rulesDataText)
    val parseResult = p.parseAll(p.rulesList, rulesDataCharSequence) 

The revised logic in my corporate prototype now finishes the integration tests in 3 seconds rather than 5 minutes even when running with a recent JDK 1.7u21 update. (The Eclipse IDE has a nice feature in the main Preferences | Java | Installed JREs dialog that allows registering any number of different JDKs or JREs and quickly switching between them.)

Lessons Learned

When designing a library of functions and methods, code to interfaces rather than concrete classes.

Interface Polymorphism is much more powerful and flexible than Subclass Polymorphism.

Just because your software’s version update supports the same functions and methods and yields the same results as the prior version does not guarantee your customers won’t be impacted by upgrading to it.

Prior to installing supplier version updates onto production systems, perform functional regression and performance testing in a controlled and measurable environment.

Advertisements