Java substring() Performance

So 21 Dezember 2014 by Oliver Paetzel
Tags: java substring performance string java.lang charsequence

Für ein aktuelles Projekt betrachte ich eine Textdatei mit einem "moving window". Ich betrachte also immer einen String mit fester Größe, den ich über die Datei wandern lasse. Auf diesen wende ich dann bestimmte Methoden an, um so Daten zu extrahieren. Meine erste Herangehensweise war, das ganze mit einem StringBuilder zu lösen, also die Datei byte für byte einzulesen und dann jeweils an der ersten Stelle einen char zu löschen. Das ganze sah dann folgendermaßen aus:

StringBuilder sb = new StringBuilder();
FileChannel fc = null;
try (RandomAccessFile raf = new RandomAccessFile(file, "r")) {
    fc = raf.getChannel();
    long fileSize = fc.size();
    ByteBuffer buf = ByteBuffer.allocate((int) fileSize);
    fc.read(buf);
    buf.flip();
    for (int i = 0; i < fileSize; i+=5) {
        sb.append((char) buf.get());
        if(i>windowSize) {
            sb.delete(0, 1);
        }
        if(i >= windowSize) {
            retVal =  retVal | FileReader.recognizeWithAll(retVal, sb.toString());
        }
    }
} catch (FileNotFoundException e) {
    //...

Diese Lösung hat schon einiges an Performance-Potential, das mir aber auf den ersten Blick nicht aufgefallen beziehungsweise egal war.

Mit dieser Implementierung brauchte mein Rechner für die 24.000 zu bearbeitenden Dateien über eine Stunde. Als mir das zu lang gedauert hat, habe ich einfach parallelisiert und auf 3 Kernen waren es auch nur noch 20 Minuten.

Dann kam allerdings das Problem auf, dass es für manche "Recognizer" praktisch wäre, das Fenster zu vergrößern und nach vorne oder hinten weiter zu suchen, wenn das Ausgangsfenster schon verdächtig schien. Ich habe das Codestück von oben durch dieses ersetzt:

int retVal = 0;
String longString = new String(Files.readAllBytes(Paths.get(file)), Charset.defaultCharset());
int i=0;
if(longString.length() >= windowSize) {
    for(i=0; i<longString.length()-windowSize; i+=5) {
        retVal |= FileReader.recognizeWithAll(retVal, longString, i, i+windowSize);
    }
    if(i!= longString.length()-windowSize) {
        retVal |= FileReader.recognizeWithAll(retVal, longString, longString.length()-windowSize, longString.length());
    }
} else {
    retVal |= FileReader.recognizeWithAll(retVal, longString, i, longString.length());
}

Ich habe also die ganze Datei in einen String eingelesen und dann mit den "Koordinaten" für das Fenster an die Recognizer geschickt. Die Signatur der Recognizer hat sich dabei auch geändert. Die Methoden sahen dann ungefähr so aus:

public int recognize(int retVal, String longString, int start, int end) {
    String recognizeString = longString.substring(start, end);
    //other code...
    return retVal;
}

Nachdem dies implementiert war, dachte ich mir, dass das ja vielleicht auch die Laufzeit kürzer werden müsste, da ich bei dem sb.delete() ein umkopieren des gesamten internen Arrays vermutet habe. Die Ernüchterung kam aber schon beim ersten Durchlauf: Es dauerte ähnlich lang mit dieser Implementierung. Also habe ich mir den StringBuilder-Sourcecode angeschaut. Doch die Vermutung mit dem umkopieren wurde bestätigt:

public AbstractStringBuilder delete(int start, int end) {
    //checks...
    int len = end - start;
    if (len > 0) {
    System.arraycopy(value, start+len, value, start, count-end);
         count -= len;
    }
    return this;
    }

Es wird also (fast) das ganze interne Array kopiert. Mit der neuen Implementierung sollte das eigentlich nicht geschehen. Wo war also das Problem? Der einzige Punkt, an dem etwas schiefgehen könnte, wäre die substring()-Methode. Also auch hier in den Sourcecode geschaut und in den Zeilen 1913 und 1914 wird nach ein paar checks ein String-Konstruktor aufgerufen:

return ((beginIndex == 0) && (endIndex == value.length)) ? this
                : new String(value, beginIndex, subLen);

Der Konstruktor tut nun folgendes:

public String(char value[], int offset, int count) {
    //checks...
    this.value = Arrays.copyOfRange(value, offset, offset+count);
}

Es wird also wieder das ganze Array kopiert! Als ich schon fast anfangen wollte, das ganze noch einmal in C oder C++ zu implementieren, fiel mir auf, dass die Methdoen in den Recognizern eigentlich keine Strings, sondern nur eine CharSequence als Eingabe benötigen. Lange Rede, kurzer Sinn: Hier ist meine eigene Implementierung von CharSequence ohne Array-Kopiererei.

public class MyCharSequence implements CharSequence {

    private String str;
    private int offset;
    private int end;

    public MyCharSequence(String str, int offset, int end) {
        super();
        if (offset < 0) {
            throw new StringIndexOutOfBoundsException(offset);
        }
        if (end - offset < 0) {
            throw new StringIndexOutOfBoundsException(end - offset);
        }
        if(str.length() - end < 0) {
            throw new StringIndexOutOfBoundsException(end);
        }
        this.str = str;
        this.offset = offset;
        this.end = end;
    }

    @Override
    public char charAt(int index) {
        if(index < 0) {
            throw new StringIndexOutOfBoundsException(index);
        }
        index += offset;
        if (index >= end) {
            throw new StringIndexOutOfBoundsException(index - offset);
        }
        return str.charAt(index);
    }

    @Override
    public int length() {
        return end - offset;
    }

    @Override
    public CharSequence subSequence(int start, int end) {
        if (start < 0) {
            throw new StringIndexOutOfBoundsException(start);
        }
        if (end > length()) {
            throw new StringIndexOutOfBoundsException(end);
        }
        return new MyCharSequence(str, start + offset, end + offset);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for(int i = offset; i<end; i++) {
            sb.append(str.charAt(i));
        }
        return sb.toString();
    }

    public void setEnd(int end) {
        if (end - offset < 0) {
            throw new StringIndexOutOfBoundsException(end - offset);
        }
        if(str.length() - end < 0) {
            throw new StringIndexOutOfBoundsException(end);
        }
        this.end = end;
    }
}

Dann noch folgendes ändern:

public int recognize(int retVal, String longString, int start, int end) {
    String recognizeString = new MyCharSequence(longString, start, end);
    //other code...
    return retVal;
}

Und schon war die Laufzeit bei 5 Minuten!

Categories
Blog