Fast alternative for String.split by whitespace

Question

After profiling of one project I've found a bottleneck in the code, specifically the line:

String columns[] = line.split("\\s+");

I've tried to find a workaround, but all ready made solutions, such as StringTokenizer and Scanner seem to be less efficient (for example, look at the answer on SO). So I decided to write a custom function.

private List<String> fastSplitWS(final String text)
{
  final List<String> result = new ArrayList<String>();

  if(text != null)
  {
    final int n = text.length();
    if(n > 0)
    {
      int index1 = 0;
      char x = 0;
      boolean y = false; // "preceding char is separator" flag
      for(int i = 0; i < n; i++)
      {
        x = text.charAt(i);

        if(x == '\t' || x == ' ') // if((x >= 9 && x <= 13) || x == ' ')
        {
          if(!y)
          {
            String token = text.substring(index1, i);
            result.add(token);
          }
          index1 = i + 1;
          y = true;
        }
        else
        {
          y = false;
        }
      }

      if(index1 < n - 1)
      {
        result.add(text.substring(index1));
      }
    }
  }

  return result;
}

The problem is that the code performs even worse than String.split() although I don't see how to improve it. According to profiler, most problematic parts are:

• self (lines of the plain code in this method) - 58%
• String.charAt - 21%
• String.subString - 12%
• ArrayList.add - 7%

Could someone suggest how to optimize the self code?

Answer 1

Bug #1

You have an off-by-one error here:

  if(index1 < n - 1)
  {
    result.add(text.substring(index1));
  }

The consequence of this is that "a b c" will be split to ["a", "b"], poor "c" is left out.

Bug #2

I would expect the same output for these calls:

fastSplitWS("");
fastSplitWS("   ");

But that's not the case. The first returns an empty list, the second a list with a single empty string in it. This behavior is also inconsistent with String.split.

This is caused by this:

if(!y)

One way to fix:

if(!y && i > 0)

Another way is to initialize y to true. (Notice that with this variable name, it's hard to understand the logical meaning of this.)

Readability

@TopinFrassi was too kind. I find this code extremely hard to read, mostly due to the poor naming throughout. The unconventional indenting and brace placement don't help.

Performance

It's worth nothing the trade-offs of using .charAt and .toCharArray. Take a look at those links, of the implementations in OpenJDK 8:

• toCharArray does an arraycopy, using double the space
• charAt does a boundary check on the index parameter

Which one is more efficient? I've no idea...

Improvement ideas

The indentation levels can be reduced here:

  if(text != null)
  {
    final int n = text.length();
    if(n > 0)
    {

The first one can be reduced using an early return:

if(text == null) return result;
final int n = text.length();
if(n > 0)
{

The second can be reduced by eliminating the if(n > 0) completely, as the loop logic takes care of the n == 0 case automatically.

Suggested implementation

Applying the above suggestions and bugfixes, the implementation becomes:

private List<String> fastSplitWS(final String text) {
    if (text == null) {
        throw new IllegalArgumentException("the text to split should not be null");
    }

    final List<String> result = new ArrayList<String>();

    final int len = text.length();
    int tokenStart = 0;
    boolean prevCharIsSeparator = true;  // "preceding char is separator" flag

    char[] chars = text.toCharArray();

    for (int pos = 0; pos < len; ++pos) {
        char c = chars[pos];

        if (c == '\t' || c == ' ') {
            if (!prevCharIsSeparator) {
                result.add(text.substring(tokenStart, pos));
                prevCharIsSeparator = true;
            }
            tokenStart = pos + 1;
        } else {
            prevCharIsSeparator = false;
        }
    }

    if (tokenStart < len) {
        result.add(text.substring(tokenStart));
    }

    return result;
}

Answer 2

Your indentation is on the limit of being hard to read! :p Usually there's more indentation between two nested things. Ex :

Your code :

if(true)
{
 if(true && 1==1)
 {
 }
}

Usually :

if(true)
{
    if(true && 1==1)
    {
    }
}

It is much easier to read this way! Also, Java conventions point that the bracket's style should be "egyptian" meaning :

if(...) {
}

instead of

if(...)
{
}

You could reduce the nesting (and hence enhance readability) by reversing the logic of your first if. Instead of :

if(text != null) {
}

You should write :

if(text == null) {
    return result;
}

This way there's less code in your if, and well, that's easier to read.

Another way to remove the else code block would be to introduce a variable that checks if the current character is a separator.

Same thing for n > 0. Although you could simply drop this condition. If n==0, then your for loop simply won't be executed and "voilà", you return result.

Look at this : boolean y = false; // "preceding char is separator" flag

If you have a comment explaining what your variable does, then your variable isn't well named. Why wouldn't you name your boolean precedingCharIsSeparator? Is it too long? I don't think so, plus it would mean the comment is now useless, you could remove it. Remember that long variable names aren't longer to compute! :p

The overall naming needs to be reviewed. It won't help for performance, but it will sure as hell help for readability, which is the second biggest concern of your code.

There's something you need to understand about profiling. The final result will always be 100%. The fact that your code takes 58% of the time isn't abnormal. It could be 58% of 1 millisecond or 58% of 10 minutes. If the bottleneck of your application is split, your application is probably fine. Otherwise you maybe need to check if you can replace your split by something else.

Here's the final code, with better named variables, less nesting and the usage of a char[] which I think will speed up a little bit your code. (But I have no proof of what I'm saying! :p)

private static List<String> fastSplitWS(final String text)
{
    final List<String> result = new ArrayList<String>();

    if(text == null) {
        return result;
    }

    final char[] characters = text.toCharArray();
    final int length = characters.length;

    int newWordIndex = 0;
    boolean precedingCharIsSeparator = true;

    for(int i = 0; i < length; i++) {
        char current = characters[i];
        boolean currentCharIsSeparator = current == '\t' || current == ' ';

        if(currentCharIsSeparator && !precedingCharIsSeparator) {
            result.add(new String(characters, newWordIndex, i - newWordIndex + 1));
        } else if(precedingCharIsSeparator) {
            newWordIndex = i;
        }
        precedingCharIsSeparator = currentCharIsSeparator;
    }

    if(newWordIndex < length - 1) {
        result.add(new String(characters, newWordIndex, length - newWordIndex));
    }

    return result;
}

Finally, the method name isn't very good. I guess WS stands for WhiteSpace, well you should write it fully! splitOnWhitespace would be a better name.

Finally (again lol), you should wonder if you really want to return a List<String>? Usually split returns an array, I think it should be the same here.

Answer 3

This is just a short answer about the use of ArrayList. It is almost always a poor option, as it is pretty much an array with helper functions. If you have an ArrayList of 10000 integers, and then add another integer, ArrayList will (if its current array it's storing the values in is of size 10000) create a new array, move all the values of the old array in the new array, then add the integer to the end. Sounds inefficient? Certainly does.

My opinion is to use LinkedList. LinkedList is faster, because it works like this:

• Each value in the list is stored in a Node.
• Each Node points to the next Node.
• Adding something to the end is as simple as creating a new Node and linking it to the Node chain.
• Removing and inserting is as simple as changing some links around.

Worst-case time complexity comparison:

        LinkedList        ArrayList
Get:       O(n)              O(1)
Add:       O(n)              O(n)
Insert:    O(n)              O(n)

Best-case time complexity comparison:

        LinkedList        ArrayList
Get:       O(1)              O(1)
Add:       O(1)              O(1)
Insert:    O(1)              O(n) <- assuming not inserting at end of list

Yes, LinkedList is losing, but in this case, you don't use get often. On the other hand, memory is an issue for ArrayList:

        LinkedList        ArrayList
Get:       O(1)              O(1)
Add:       O(1)              O(n)
Insert:    O(1)              O(n)