10

I am building a Comparator that provides multi-column sort capability on a delimited String. I am currently using the split method from String class as my preferred choice for splitting the raw String into tokens.

Is this the best performing way to convert the raw String into a String array? I will be sorting millions of rows so I think approach matters.

It seems to run fine and is very easy, but unsure if there's a faster way in java.

Here is how the sort works in my Comparator:

public int compare(String a, String b) {

    String[] aValues = a.split(_delimiter, _columnComparators.length);
    String[] bValues = b.split(_delimiter, _columnComparators.length);
    int result = 0;

    for( int index : _sortColumnIndices ) {
        result = _columnComparators[index].compare(aValues[index], bValues[index]);
        if(result != 0){
            break;
        }
    }
    return result;
}

After benchmarking the various approaches, believe it or not, the split method was the quickest using the latest version of java. You can download my completed comparator here: https://sourceforge.net/projects/multicolumnrowcomparator/

  • 5
    I will point out that the nature of the answer to this question depends on the implementation of the jvm. The behavior of strings (sharing a common backing array in OpenJDK, but not in OracleJDK) differs. This difference can have significant impacts on splitting strings and the creation of substrings, along with garbage collection and memory leaks. How big are these arrays? How are you doing it now? Would you consider an answer that makes for a new Stringish type rather than actual Java Strings? – user40980 Dec 20 '13 at 16:17
  • 1
    In particular look at StringTokenizer nextToken which eventually calls package private String constructor. Compare this to the changes documented in Changes to String internal representation made in Java 1.7.0_06 – user40980 Dec 20 '13 at 16:20
  • or presplit the strings to save the log(n) factor of creating the string arrays – ratchet freak Dec 20 '13 at 16:27
  • 2
    The fastest way to split a string is to get Chuck Norris to karate chop it. – FrustratedWithFormsDesigner Dec 20 '13 at 16:37
  • The array size depends on the number of columns so it is variable. This multi-column Comparator is passed as a parameter like so: ExternalSort.mergeSortedFiles(fileList, new File("BigFile.csv"), _comparator, Charset.defaultCharset(), false ); The External sort routine will sort the whole row string, it is actually the comparator that does the splitting and sorting based on the sort columns – Constantin Dec 20 '13 at 19:52
19

I've written a quick and dirty benchmark test for this. It compares 7 different methods, some of which require specific knowledge of the data being split.

For basic general purpose splitting, Guava Splitter is 3.5x faster than String#split() and I'd recommend using that. Stringtokenizer is slightly faster than that and splitting yourself with indexOf is twice as fast as again.

For the code and more info see http://demeranville.com/battle-of-the-tokenizers-delimited-text-parser-performance/

  • I'm just curious what JDK you were using... and if it was 1.6, I'd be most interested in seeing a recap of your results in 1.7. – user40980 Dec 20 '13 at 17:01
  • 1
    it was 1.6 I think. The code is there as a JUnit test if you want to run it in 1.7. Note String.split performs regex matching, which is always going to be slower than splitting on a single defined character. – tom Dec 20 '13 at 17:04
  • 1
    Yep, however for 1.6, the StringTokenizer (and similar) code calls a String.substring() that does O(1) creation of the new string by using the same backing array. This was changed in 1.7 to make a copy of the necessary part of the backing array rather for O(n). This could have a singicncant impact in your results making the difference between the split and StringTokenizer less (slowing down everything that used substring before). – user40980 Dec 20 '13 at 17:06
  • 1
    Certainly true. The thing is the way that StringTokenizer works has gone from "to create a new string assign 3 integers" to "to create a new string, do an array copy of the data" which will change how fast that part is. The difference between the various approaches may be less now and it would be interesting (if for no other reason than its interesting) to do a followup with Java 1.7. – user40980 Dec 20 '13 at 18:01
  • 1
    Thanks for that article! Very useful and will use to benchmark various approaches. – Constantin Dec 20 '13 at 20:12
5

As @Tom writes, an indexOf type approach is faster than String.split(), since the latter deals with regular expressions and has a lot of extra overhead for them.

However, one algorithm change that might give you a super speedup. Assuming that this Comparator is going to be used to sort your ~100,000 Strings, do not write the Comparator<String>. Because, in the course of your sort, the same String will likely be compared multiple times, so you will split it multiple times, etc...

Split all the Strings once into String[]s, and have a Comparator<String[]> sort the String[]. Then, at the end, you can combine them all together.

Alternatively, you could also use a Map to cache the String -> String[] or vice versa. e.g. (sketchy) Also note, you are trading memory for speed, hope you have lotsa RAM

HashMap<String, String[]> cache = new HashMap();

int compare(String s1, String s2) {
   String[] cached1 = cache.get(s1);
   if (cached1  == null) {
      cached1 = mySuperSplitter(s1):
      cache.put(s1, cached1);
   }
   String[] cached2 = cache.get(s2);
   if (cached2  == null) {
      cached2 = mySuperSplitter(s2):
      cache.put(s2, cached2);
   }

   return compareAsArrays(cached1, cached2);  // real comparison done here
}
  • this is a good point. – tom Dec 21 '13 at 11:39
  • It would require modification to the External Sort code which can be found here: code.google.com/p/externalsortinginjava – Constantin Dec 21 '13 at 14:53
  • 1
    Probably easiest to use a Map then. See edit. – user949300 Dec 21 '13 at 16:15
  • Given that this is part of an external sort engine (to deal with far more data than can possibly fit in available memory), I was really going after an efficient "splitter" (yes, it is wasteful to split same String repeatedly, hence my original need to do this as fast as possible) – Constantin Dec 22 '13 at 0:04
  • Briefly browsing the ExternalSort code, it looks like if you cleared your cache at the end (or start) of every sortAndSave() call then you should not run out of memory due to a huge cache. IMO, the code should have a few extra hooks like firing events or calling do-nothing protected methods that users like you could override. (Also, it should not be all static methods so that they can do this) You might want to contact the authors and file a request. – user949300 Dec 22 '13 at 18:30
2

According to this benchmarks, StringTokenizer is faster for splitting strings but it doesn't return an array which makes it less convenient.

If you need to sort millions of rows I'd recommend using a RDBMS.

  • 3
    That was under JDK 1.6 - things in strings are fundamentally different in 1.7 - see java-performance.info/changes-to-string-java-1-7-0_06 (in particular, creating a substring is not O(1) anymore but rather O(n)). The link notes that in 1.6 Pattern.split used different String creating than String.substring()) - see code linked in comment above to follow the StringTokenizer.nextToken() and the package private constructor it had access to. – user40980 Dec 20 '13 at 16:23
1

This is the method I use for parsing large (1GB+) tab-delimited files. It has far less overhead than String.split(), but is limited to char as a delimiter. If anyone has a faster method, I'd like to see it. This can also be done over CharSequence and CharSequence.subSequence, but that requires implementing CharSequence.indexOf(char) (refer to the package method String.indexOf(char[] source, int sourceOffset, int sourceCount, char[] target, int targetOffset, int targetCount, int fromIndex) if interested).

public static String[] split(final String line, final char delimiter)
{
    CharSequence[] temp = new CharSequence[(line.length() / 2) + 1];
    int wordCount = 0;
    int i = 0;
    int j = line.indexOf(delimiter, 0); // first substring

    while (j >= 0)
    {
        temp[wordCount++] = line.substring(i, j);
        i = j + 1;
        j = line.indexOf(delimiter, i); // rest of substrings
    }

    temp[wordCount++] = line.substring(i); // last substring

    String[] result = new String[wordCount];
    System.arraycopy(temp, 0, result, 0, wordCount);

    return result;
}
  • Have you benchmarked this vs String.split() ? If so, how does it compare? – Jay Elston Aug 31 '17 at 1:02
  • @JayElston On a 900MB file, it reduced the split time from 7.7 seconds to 6.2 seconds, so around 20% faster. It is still the slowest part of my floating-point matrix parsing. I'm guessing that much of the remaining time is array allocation. It might be possible to cut the matrix allocation out by using a tokenizer-based approach with an offset in the method - that would start to look more like the method I cited above the code. – vallismortis Aug 31 '17 at 1:49

protected by gnat Aug 30 '17 at 17:50

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.