Watson-Crick-Complement Performance

httpdigest

Top Contributor
Und wenn man die Fallunterscheidung (im Idealfall ja ein switch, welches von javac als tableswitch fuer Binaersuche uebersetzt wird) noch durch eine kleine char[] lookup table ersetzt, welche bis 'T' geht und als Eintraege fuer die vier Buchstaben das jeweilige Ersetzungszeichen hat, ist es auch noch recht flott.

EDIT: Das hat jetzt zwar überhaupt nichts mehr mit der eigentlichen Aufgabenstellung zu tun, aber das Problem ist ein guter Kandidat für "Bit-level Parallelisierung":
Wenn man wirklich performant sein möchte, dann wählt man für die Repräsentation der vier Basen auch keine Zeichen in einer Zeichenkette/String, sondern Bitmuster, wie etwa:
A = 00
T = 01
G = 10
C = 11
Die Kette ATGC wäre dann also das Byte 00011011.
Die Berechnung des Watson-Crick-Komplements kann dann mittels Bit-level Parallelisierung innerhalb eines Clock-Cycles für 4 Zeichen gleichzeitig ausgeführt werden per XOR mit dem Muster 01010101.
Und, wenn long verwendet wird (also quasi beliebig lange "Strings" als long[] Array repräsentiert werden), kann man mit nur einem einzigen Clock-Cycle sogar 32 Zeichen gleichzeitig ersetzen (Lesen und Schreiben des longs von/zum Array nicht mitgerechnet).
 
Zuletzt bearbeitet:

Bible Man

Mitglied
Hab mich an httpdigest's Version (Bit-Level-Parallelisierung) versucht. Was denkt ihr?
[CODE lang="java" title="Elemente Tauschen"]
// Watson-Crick-Komplements
public class WCKomplement {
/*
* Lookup-Tabelle:
* bin(0) = 00000000
* bin(1) = 00000001
* bin(2) = 00000010
* bin(3) = 00000011
*/
private static String lookUp = "ATCG";
/*
* Wandelt die Byte-Kodierung (Sequenz) in einen String um.
* 1 Byte repräsentiert 4 Zeichen.
*/
public static String byteToSeq(byte b) {
String s = "";
// 4 Durchläufe, da 4 Zeichen
for (int i = 0; i < 4; ++i) {
/*
* bin(3) = 00000011
* Die UND-Verknüpfung liefert die Stelle des Zeichens in der Lookup-Tabelle.
*/
s += lookUp.charAt(b & 3);
// Shift, um die nächsten 2 Bits nach vorne zu bringen
b >>= 2;
}
// Das Ergebnis wäre ohne reverse Spiegelverkehrt.
return new StringBuffer(s).reverse().toString();
}
public static byte komplement(byte b) {
/*
* bin(85) = 01010101
* Die XOR-Verknüpfung wandelt alle 4 repräsentierten Zeichen auf einmal um.
*/
return b ^= 85;
}
/*
* Die Methode kodiert ein Byte entsprechend der Sequenz.
* Die Sequenz darf nicht > 4 sein!
* seq = String s, |s| <= 4
*/
public static byte seqToByte(String s) {
byte b = 0;
// Durchlaufe jedes (4) Zeichen im String
for (int i = 0; i < 4; ++i) {
// Shift, um Platz für das nächste Zeichen zu machen
b <<= 2;
// Die niedersten 2 Bits anhand der LookUp-Tabelle kodieren
b ^= lookUp.indexOf(s.charAt(i));
}
return b;
}
public static void main(String[] args) {
System.out.println(byteToSeq(komplement(seqToByte("ACTG"))));
}
}
[/CODE]
 
Zuletzt bearbeitet:
K

kneitzel

Gast
Hab mich an httpdigest's Version (Bit-Level-Parallelisierung) versucht. Was denkt ihr?
Also irgendwie kann ich so einer Lösung nichts abgewinnen. Es erscheint mir einfach viel zu kompliziert. Wenn man drauf schaut, dann ist die Funktionalität nicht auf Anhieb erkennbar. Das scheinst selbst Du erkannt zu haben, was Du durch Kommentare im Code auszugleichen versucht hast....

Ich finde da solche Methoden doch etwas lesbarer:
Umwandeln eines einzelnen Zeichens:

Java:
    protected static char komplement(final char orgDNA) {
        switch (orgDNA) {
            case 'A' : return 'T';
            case 'T' : return 'A';
            case 'G' : return 'C';
            case 'C' : return 'G';
            default: throw new IllegalArgumentException("Character " + orgDNA + " is not a valid character.")
        }
    }
(Mit aktuellen Java Version wird es durch die switch expression noch etwas besser. Sollten hier mehr wie 4 Werte kommen, dann würde ich eine map in Betracht ziehen statt eben einer Switch Anweisung. Wobei mich an der Aufgabe bereits stört, dass es hier keine Organisation in Objekten gibt. Da wäre das ja keine Zeichenkette sondern Elemente aus einem Enum. Und das Enum wüsste dann, wer das Komplementär ist..... Und dann hätte man eine DNAKette als Klasse und die könnte dann gewisse Dinge direkt ... Das wäre deutlich einläuchtender ... Aber egal - zurück zu der reichen Zeichenkette...

Dann hat man auch eine einfache Möglichkeit, die Zeichenkette umzuwandeln. Da bietet sich ein Stream geradezu an, den man auch schön einfach halten kann:
Java:
    public static String komplement(final String orgDNA) {
        StringBuilder resultBuilder = new StringBuilder();
        orgDNA.chars().mapToObj(ch -> komplement((char)ch)).forEach(resultBuilder::append);
        return resultBuilder.toString();
    }

Das wäre hier wohl meine bevorzugte Lösung. Den StringBuilder kann man natürlich auch direkt über ein .collect nutzen um dann ein toString() aufzurufen...:
Java:
        return orgDNA.chars()
                .map(ch -> komplement((char)ch))
                .collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append).toString();

Aber das ist dann ein Einzeiler, der etwas viel beinhaltet. Daher hätte ich den eher raus gezogen.

Das wäre wohl ein Weg, den ich eingeschlagen hätte ..

Aber auch die 08/15 Schleife würde ich hier als vernünftige Lösung ansehen:
Java:
    public static String komplement(final String orgDNA) {
        char[] result = orgDNA.toCharArray();
        for (int index=0; index<result.length; index++)
            result[index] = komplement(result[index]);
        return new String(result);
    }

In meinen Augen hat die Lesbarkeit einen sehr hohen Stellenwert. Daher wären dies so meine Ansätze.

Und das mit dem replace geht natürlich auch und ist auch schön kurz und übersichtlich:
Java:
    public static String komplement(final String orgDNA) {
        String result = orgDNA.replace('A', 't');
        result = result.replace('T', 'a');
        result = result.replace('G', 'c');
        result = result.replace('C', 'g');
        return result.toUpperCase();
    }
 

httpdigest

Top Contributor
Hängt halt wie immer von den Anforderungen ab. Wenn der Code gerne 10x langsamer laufen darf (was hier ja auch sicherlich der Fall sein wird), dann kann man auch lesbareren Streams-Code schreiben.

Wenn es auf Performance ankommt (wie z.B. bei einem wirklichen Gen-Sequencing Programm oder so), dann - ja - wird Code etwas unleserlicher. Aber Code muss auch nicht immer lesbar sein. _Was_ der Code tut, sollte immer noch durch gute und ausführliche Tests gezeigt werden. Und wenn einem der Code nicht gefällt, kann man ihn immer umschreiben, und kann durch funktionale Tests und Performancetests Regression vermeiden.
Und die hier umgesetzte Funktionalität ist ja nun wirklich so dermassen klein/zentral, dass jeder das innerhalb von 5 Minuten erneut umsetzen könnte.

Also, um der Lesbarkeit wegen würde ich mir bei sowas absolut winzigem hier absolut keine Gedanken machen. Es geht hier ja nicht um ein "System" mit 2000 Compilation Units und 100K Zeilen Code.

Und, ob eine "OO"-Lösung mit Enums, Klassen, Factories, Builder-Factories und Factory-Builders (ja, ich überspitze und übertreibe) das ganze lesbarer macht, wage ich bei so ziemlich 99% von "OO"-Code zu bezweifeln.
 
K

kneitzel

Gast
Ich kann Dir gerade nicht folgen:

Performance: Bei der Performance sollte man schon von Anfang an auf eine gute und korrekte Darstellung achten. Da wird hoffentlich NICHT mit Buchstaben gearbeitet wie es hier der Fall ist. Der Versuch, hier dann "zu optimieren" ist ein super Beispiel für genau diese Vorgabe: Nicht optimieren! https://clean-code-developer.de/die-grade/roter-grad/#Vorsicht_vor_Optimierungen
Wenn die Performance nicht stimmig ist / problematisch ist, dann gehört das von Anfang in das Design. Und da sind dann viele Dinge wie z.B. Parallele Abarbeitung wichtig. Oder eine vernünftige Datenhaltung ...Und damit sind wir automatisch auch wieder bei dem Thema OO. Denn ich muss alles, was ich brauche, entsprechend so aufbauen, dass es auch performant läuft (so dass eine Anforderung ist).

Und Streams sollen um Faktor 10 langsamer sein? Oder generell langsamer? Wie kommst Du auf diese Idee? Das hatte Tobias schon vor einigen Monaten angebracht, ohne es belegen zu wollen ... Und wenn ich suche, dann finde ich dazu keine Belege sondern eher andere Aussagen ... wie z.B. https://jaxenter.com/java-performance-tutorial-how-fast-are-the-java-8-streams-118830.html mit "The ultimate conclusion to draw from this benchmark experiment is NOT that streams are always slower than loops. Yes, streams are sometimes slower than loops, but they can also be equally fast; it depends on the circumstances." - aber Du bringst das als Fakt generell gegen Streams und das gleich mit einem Faktor 10x ...

Und was lesbaren Code angeht:
Hier geht es um Anfänger im Bereich Java. Da ist die Lesbarkeit existenziell! Jemand, der etwas lernt, der soll es gleich richtig lernen! Zumal das viele Probleme direkt löst, denn wir sehen hier doch regelmäßig, wie Anfänger dann Variablen vertauschen oder sonst so Dinge machen. Darauf wird viel zu wenig Wert gelegt. Die, die Stoff vermitteln, haben da maximal theoretisches Wissen aber machen es nicht. Ansonsten würden Schüler und Studenten nicht ständig so blöde Namen vergeben sondern direkt vernünftige Namen verwenden. Und in der IDE die Umbenenn-Funktion kennen und nutzen. Das kostet keine Zeit und der Code ist nun einmal lesbarer. Und spätestens dann, wenn ich Code schreibe, dessen einziger Zweck ist, dass Andere sich diesen anschauen und verstehen, dann ist das eine der großen Anforderungen. Und Lehrer / Dozenten haben schlicht fachlich versagt, wenn sie unleserlichen Code ihren Schülern und Studenten vorsetzen.

Das wäre einfach mal meine Meinung. Und vielleicht kannst Du bezüglich der Performance von Streams deinen Punkt etwas ausführen.
 
K

kneitzel

Gast
Plottwist: Ich bin Tobias... döööm döööm DÖÖM!
Du magst ein Tobias sein ... aber nicht der Tobias ... :)

Daher gehe ich auch davon aus, dass du (bezüglich der Inhalte oben) etwas weißt, das ich nicht weiß. Auch wenn ich ggf. meine Position stark vertreten habe: Ich bin da durchaus sehr interessiert, denn man lernt nie aus und ich liege ja auch von Zeit zu Zeit daneben... (Davon abgesehen muss es nicht zwingend ein richtig/falsch geben.) Daher sorry, wenn ich zu energisch gewesen sein sollte ... Ich versuche noch an mir zu arbeiten diesbezüglich ....
 

Bible Man

Mitglied
Hab mich an httpdigest's Version (Bit-Level-Parallelisierung) versucht. Was denkt ihr?
[CODE lang="java" title="Elemente Tauschen"]
// Watson-Crick-Komplements
public class WCKomplement {
/*
* Lookup-Tabelle:
* bin(0) = 00000000
* bin(1) = 00000001
* bin(2) = 00000010
* bin(3) = 00000011
*/
private static String lookUp = "ATCG";
/*
* Wandelt die Byte-Kodierung (Sequenz) in einen String um.
* 1 Byte repräsentiert 4 Zeichen.
*/
public static String byteToSeq(byte b) {
String s = "";
// 4 Durchläufe, da 4 Zeichen
for (int i = 0; i < 4; ++i) {
/*
* bin(3) = 00000011
* Die UND-Verknüpfung liefert die Stelle des Zeichens in der Lookup-Tabelle.
*/
s += lookUp.charAt(b & 3);
// Shift, um die nächsten 2 Bits nach vorne zu bringen
b >>= 2;
}
// Das Ergebnis wäre ohne reverse Spiegelverkehrt.
return new StringBuffer(s).reverse().toString();
}
public static byte komplement(byte b) {
/*
* bin(85) = 01010101
* Die XOR-Verknüpfung wandelt alle 4 repräsentierten Zeichen auf einmal um.
*/
return b ^= 85;
}
/*
* Die Methode kodiert ein Byte entsprechend der Sequenz.
* Die Sequenz darf nicht > 4 sein!
* seq = String s, |s| <= 4
*/
public static byte seqToByte(String s) {
byte b = 0;
// Durchlaufe jedes (4) Zeichen im String
for (int i = 0; i < 4; ++i) {
// Shift, um Platz für das nächste Zeichen zu machen
b <<= 2;
// Die niedersten 2 Bits anhand der LookUp-Tabelle kodieren
b ^= lookUp.indexOf(s.charAt(i));
}
return b;
}
public static void main(String[] args) {
System.out.println(byteToSeq(komplement(seqToByte("ACTG"))));
}
}
[/CODE]
Hi, hab noch ein bisschen optimiert. Auch, wenn der Code sich nicht so selbstverständlich verstehen lässt, so macht es dennoch Spaß kompliziertere Lösungsansätze auszuprobieren.
Optimierung:
- StringBuffer().reverse entfernt
[CODE lang="java" title="WCKomplement"]public class WCKomplement {
private static String lookUp = "ATCG";
public static String byteToSeq(byte b) {
String s = "";
for (int i = 0; i < 4; ++i) {
s += lookUp.charAt((b & 192) >> 6);
b <<= 2;
}
return s;
}
public static byte komplement(byte b) {
return b ^= 85;
}
public static byte seqToByte(String s) {
byte b = 0;
for (int i = 0; i < 4; ++i) {
b <<= 2;
b ^= lookUp.indexOf(s.charAt(i));
}
return b;
}
public static void main(String[] args) {
// output: "TGAC"
System.out.println(byteToSeq(komplement(seqToByte("ACTG"))));
}
}[/CODE]
 

Bible Man

Mitglied
Dann hab ich mal einen Performance-Test durchgeführt. Das Ergebnis für 1 Mio Zeichen:

WCKomplementKneitzel: 26 ms
WCKomplementBibleMan: 45 ms

Tja, schade
 

httpdigest

Top Contributor
Daher gehe ich auch davon aus, dass du (bezüglich der Inhalte oben) etwas weißt, das ich nicht weiß
Nein nein, das ist nicht der Fall. :D Ich wollte nur ein bisschen pöbeln... hach mensch, darf man das nicht auch mal tun. :D

WCKomplementKneitzel: 26 ms
WCKomplementBibleMan: 45 ms
Naja, ein möglicher Performancevorteil wird natürlich nur dann ausspielbar sein, wenn du nicht noch extra die 'A', 'T', 'C', 'G' Zeichen selbst umkodieren musst. Für den Bit-parallelen Algorithmus müssen die Zeichen schon in dieser Kodierung vorliegen.
 
K

kneitzel

Gast
Dann hab ich mal einen Performance-Test durchgeführt. Das Ergebnis für 1 Mio Zeichen:

WCKomplementKneitzel: 26 ms
WCKomplementBibleMan: 45 ms

Tja, schade
Wenn Dich das etwas reizt, dann teste doch einmal:
a) die zwei Stream Varianten - die eine mit map und die zweite mit mapToObj - beide nutzen ja unter dem Strich den StringBuilder um das Ergebnis zu sammeln. (Hier erwarte ich eigentlich eine klare Abweichung von der Laufzeit.)
b) Ergänze nach dem .chars() noch ein .parallel() und miss erneut den Zeitbedarf.

Das nur, falls es Dich interessiert, da bezüglich Performance etwas zu spielen.
 

Bible Man

Mitglied
Wenn Dich das etwas reizt, dann teste doch einmal:
a) die zwei Stream Varianten - die eine mit map und die zweite mit mapToObj - beide nutzen ja unter dem Strich den StringBuilder um das Ergebnis zu sammeln. (Hier erwarte ich eigentlich eine klare Abweichung von der Laufzeit.)
b) Ergänze nach dem .chars() noch ein .parallel() und miss erneut den Zeitbedarf.

Das nur, falls es Dich interessiert, da bezüglich Performance etwas zu spielen.
WCKomplementKneitzelMapToObject: 28 ms
WCKomplementKneitzelMap: 13 ms
WCKomplementBibleManByte: 47 ms
WCKomplementBibleManShort: 30 ms
WCKomplementBibleManInt: 25 ms

...jetzt wüsst ich wohl mal gerne, wie man den Bit-Ebenen Algorithmus mit Long implementiert...
 

httpdigest

Top Contributor
Hier ist eine/meine Implementierung für beliebig lange (oder kurze) Strings, die kein Vielfaches eines Faktors (4, 8, 16 oder 32) lang sein müssen.
Java:
public class WCComplement {
  public static class Bits {
    public long[] longs;
    public int numChars;
  }
  private static final byte[] CHAR_TO_BITS = new byte['T' + 1];
  private static final char[] BITS_TO_CHAR = {'A', 'T', 'G', 'C'};
  private static final int DIVIDE_BY_32_SHIFT = 5;
  static {
    CHAR_TO_BITS['T'] = 0b01;
    CHAR_TO_BITS['G'] = 0b10;
    CHAR_TO_BITS['C'] = 0b11;
  }
  private static int numLongsFor(int numChars) {
    return (numChars + 31) >>> DIVIDE_BY_32_SHIFT;
  }
  private static Bits convertStringToBits(String str) {
    long[] longs = new long[numLongsFor(str.length())];
    for (int i = 0; i < str.length(); i++) {
      int shiftForChar = i << 1 & (Long.SIZE - 1);
      int longIndex = i >>> DIVIDE_BY_32_SHIFT;
      longs[longIndex] |= ((long) CHAR_TO_BITS[str.charAt(i)]) << shiftForChar;
    }
    Bits b = new Bits();
    b.longs = longs;
    b.numChars = str.length();
    return b;
  }
  private static Bits complementWC(Bits bits) {
    for (int i = 0; i < bits.longs.length; i++)
      bits.longs[i] ^= 0x5555555555555555L;
    return bits;
  }
  private static String convertBitsToString(Bits bits) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < bits.numChars; i++) {
      int shiftForChar = i << 1 & (Long.SIZE - 1);
      int longIndex = i >>> DIVIDE_BY_32_SHIFT;
      sb.append(BITS_TO_CHAR[(int) (bits.longs[longIndex] >> shiftForChar) & 3]);
    }
    return sb.toString();
  }

  // Test
  public static void main(String[] args) {
    System.out.println(convertBitsToString(complementWC(convertStringToBits("ATGCG"))));
  }
}
Ich garantiere dir aber, dass die auch langsamer sein wird als die einfache Char-Substitution in einem String. :)
 
Zuletzt bearbeitet:

Bible Man

Mitglied
Ok. Last but not least:
WCKomplementKneitzelMapToObject: 31 ms
WCKomplementKneitzelMap: 22 ms
WCKomplementByte: 59 ms
WCKomplementShort: 41 ms
WCKomplementInt: 36 ms
WCComplementHttpdigest: 30 ms

Übrigens, Kneitzel, hat .parallel() zu einem Runtime-Error geführt. Ich hab mir das dann nicht genauer angeschaut.
Danke für den Code http^^
 

httpdigest

Top Contributor
Hab den nochmal angepasst. Der hatte noch einen fiesen Bug... ich schätze das kommt davon, wenn man Code schreibt, den man selber nicht mehr versteht. :D
-> also wie @kneitzel schon richtig schreib: immer schön verständlichen Code schreiben!
 

mrBrown

Super-Moderator
Mitarbeiter
Müsste man das nicht mal mit JMH messen?

Bitteschön :)

Ergebnisse sind jeweils in ns/op, weniger ist also besser:

Benchmark \ Länge String
1.024
32.768
1.048.576
replace
4.204​
129.737​
13.916.666​
kneitzels Schleife
1.899​
236.655​
8.482.951​
kneitzels Stream
6.032​
407.833​
13.175.404​
kneitzels Stream, parallel
40.964​
149.685​
3.387.878​
httpdigest
6.390​
212.192​
5.480.285​
httpdigest, Bits statt String
11​
90​
3.968​

Die Stream-Varianten von @kneitzel sind seine zweite Variante, einmal mit parallel(), einmal ohne.
Die Variante von @Bible Man hab ich weggelassen, da sie aktuell nur für 4-Zeichen lange Strings funktioniert (und in beiden Fällen etwas unperformant wäre, durch StringBuffer bzw das direkte concat mit dem String) – die Variante von @httpdigest ist aber ja grundsätzlich der gleiche Algorithmus.

Das letzte Zeile ist die Variante von @httpdigest, bei der der String vor der Zeitmessung in ein Bits-Objekt überführt wird – den Unterscheid sieht man ja recht deutlich :)

Das ganze läuft übrigens dank Auto-Vectorization nicht nur mit 32 Zeichen gleichzeitig, sondern zumindest in dem Test mit 128 :) Da kann natürlich nichts mithalten, was nur einen Wert auf einmal verarbeitet.
Außerdem arbeitet das, anders als alle anderen, "in place", Kneitzels Schleife braucht zB immer ein char-Array mehr.

Letzteres könnte man in @kneitzels Variante noch optimieren – allzu viel dürfte das aber auch nicht ausmachen.



Mit der neuen Vector-API könnte man die Variante von @httpdigest vielleicht sogar noch etwas optimieren, zumindest das Überführen des Strings in das long-Array. An dem "eigentlichen Algorithmus" lässt sich nicht mehr viel machen, das läuft identisch schnell, wenn man explizit vektorisiert.
 

httpdigest

Top Contributor
Das ganze läuft übrigens dank Auto-Vectorization nicht nur mit 32 Zeichen gleichzeitig, sondern zumindest in dem Test mit 128 :)
Wenn man eine CPU mit AVX512 Unterstützung hat (z.B. im Consumer Bereich alles ab Cannon Lake (Intel)), dann wird das leider von der JVM aktuell nicht automatisch genutzt, sondern man muss mit `-XX:UseAVX=3` manuell einen "opt-in" machen. Das könnte das ganze noch etwas schneller machen, wenn nicht sowieso schon die Speicherbandbreite ausgeschöpft ist.
 

Neue Themen


Oben