Efektywne połączenie ciągów w Scali

Question

JVM optymalizuje Łączy ciąg z + i zastępuje go StringBuilder. To powinno być takie samo w Scali. Ale co się dzieje, jeśli łańcuchy są łączone z ++=?

var x = "x" 
x ++= "y" 
x ++= "z" 

O ile wiem, to metody traktuje ciągi jak seqences char, więc nawet jeśli JVM stworzyłoby StringBuilder prowadziłoby to do wielu wywołań metod, prawda? Czy lepiej byłoby zamiast tego użyć StringBuilder?

Do jakiego typu ciąg jest konwertowany niejawnie?

Answer 1

Faktycznie, niewygodna prawda jest StringOps zwykle pozostaje alokacja:

scala> :pa 
// Entering paste mode (ctrl-D to finish) 

class Concat { 
    var x = "x" 
    x ++= "y" 
    x ++= "z" 
} 

// Exiting paste mode, now interpreting. 

defined class Concat 

scala> :javap -prv Concat 
Binary file Concat contains $line3.$read$$iw$$iw$Concat 
    Size 1211 bytes 
    MD5 checksum 1900522728cbb0ed0b1d3f8b962667ad 
    Compiled from "<console>" 
public class $line3.$read$$iw$$iw$Concat 
    SourceFile: "<console>" 
[snip] 


    public $line3.$read$$iw$$iw$Concat(); 
    descriptor:()V 
    flags: ACC_PUBLIC 
    Code: 
     stack=6, locals=1, args_size=1 
     0: aload_0  
     1: invokespecial #19     // Method java/lang/Object."<init>":()V 
     4: aload_0  
     5: ldc   #20     // String x 
     7: putfield  #10     // Field x:Ljava/lang/String; 
     10: aload_0  
     11: new   #22     // class scala/collection/immutable/StringOps 
     14: dup   
     15: getstatic  #28     // Field scala/Predef$.MODULE$:Lscala/Predef$; 
     18: aload_0  
     19: invokevirtual #30     // Method x:()Ljava/lang/String; 
     22: invokevirtual #34     // Method scala/Predef$.augmentString:(Ljava/lang/String;)Ljava/lang/String; 
     25: invokespecial #36     // Method scala/collection/immutable/StringOps."<init>":(Ljava/lang/String;)V 
     28: new   #22     // class scala/collection/immutable/StringOps 
     31: dup   
     32: getstatic  #28     // Field scala/Predef$.MODULE$:Lscala/Predef$; 
     35: ldc   #38     // String y 
     37: invokevirtual #34     // Method scala/Predef$.augmentString:(Ljava/lang/String;)Ljava/lang/String; 
     40: invokespecial #36     // Method scala/collection/immutable/StringOps."<init>":(Ljava/lang/String;)V 
     43: getstatic  #28     // Field scala/Predef$.MODULE$:Lscala/Predef$; 
     46: invokevirtual #42     // Method scala/Predef$.StringCanBuildFrom:()Lscala/collection/generic/CanBuildFrom; 
     49: invokevirtual #46     // Method scala/collection/immutable/StringOps.$plus$plus:(Lscala/collection/GenTraversableOnce;Lscala/collection/generic/CanBuildFrom;)Ljava/lang/Object; 
     52: checkcast  #48     // class java/lang/String 
     55: invokevirtual #50     // Method x_$eq:(Ljava/lang/String;)V 

Zobacz więcej demonstracji w this answer.

Edycja: aby powiedzieć więcej, budujesz ciąg przy każdej zmianie przypisania, więc nie używasz pojedynczego StringBuilder.

Jednak optymalizacja odbywa się poprzez javac a nie kompilator JIT, tak aby porównać owoców tego samego rodzaju:

public class Strcat { 
    public String strcat(String s) { 
     String t = " hi "; 
     String u = " by "; 
     return s + t + u; // OK 
    } 
    public String strcat2(String s) { 
     String t = s + " hi "; 
     String u = t + " by "; 
     return u;   // bad 
    } 
} 

natomiast

$ scala 
Welcome to Scala version 2.11.2 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_11). 
Type in expressions to have them evaluated. 
Type :help for more information. 

scala> :se -Xprint:typer 

scala> class K { def f(s: String, t: String, u: String) = s ++ t ++ u } 
[[syntax trees at end of      typer]] // <console> 
def f(s: String, t: String, u: String): String = scala.this.Predef.augmentString(scala.this.Predef.augmentString(s).++[Char, String](scala.this.Predef.augmentString(t))(scala.this.Predef.StringCanBuildFrom)).++[Char, String](scala.this.Predef.augmentString(u))(scala.this.Predef.StringCanBuildFrom) 

jest złe. Albo, co gorsza, aby rozwinąć Rex za wyjaśnienie:

"abc" ++ "def" 

    augmentString("abc").++[Char, String](augmentString("def"))(StringCanBuildFrom) 

    collection.mutable.StringBuilder.newBuilder ++= new WrappedString(augmentString("def")) 

    val b = collection.mutable.StringBuilder.newBuilder 
    new WrappedString(augmentString("def")) foreach b.+= 

Jak wyjaśniono Rex, StringBuilder przesłonięcia ++=(String) lecz nie Growable.++=(Traversable[Char]).

W przypadku kiedykolwiek zastanawialiście się, co jest dla unaugmentString:

28: invokevirtual #40     // Method scala/Predef$.augmentString:(Ljava/lang/String;)Ljava/lang/String; 
    31: invokevirtual #43     // Method scala/Predef$.unaugmentString:(Ljava/lang/String;)Ljava/lang/String; 
    34: invokespecial #46     // Method scala/collection/immutable/WrappedString."<init>":(Ljava/lang/String;)V 

I po prostu pokazać, że ty w końcu nazwać ozdób +=(Char) ale po boksie i unboxing:

public final scala.collection.mutable.StringBuilder apply(char); 
    flags: ACC_PUBLIC, ACC_FINAL 
    Code: 
     stack=2, locals=2, args_size=2 
     0: aload_0  
     1: getfield  #19     // Field b$1:Lscala/collection/mutable/StringBuilder; 
     4: iload_1  
     5: invokevirtual #24     // Method scala/collection/mutable/StringBuilder.$plus$eq:(C)Lscala/collection/mutable/StringBuilder; 
     8: areturn  
     LocalVariableTable: 
     Start Length Slot Name Signature 
       0  9  0 this L$line10/$read$$iw$$iw$$anonfun$1; 
       0  9  1  x C 
     LineNumberTable: 
     line 9: 0 

    public final java.lang.Object apply(java.lang.Object); 
    flags: ACC_PUBLIC, ACC_FINAL, ACC_BRIDGE, ACC_SYNTHETIC 
    Code: 
     stack=2, locals=2, args_size=2 
     0: aload_0  
     1: aload_1  
     2: invokestatic #35     // Method scala/runtime/BoxesRunTime.unboxToChar:(Ljava/lang/Object;)C 
     5: invokevirtual #37     // Method apply:(C)Lscala/collection/mutable/StringBuilder; 
     8: areturn  
     LocalVariableTable: 
     Start Length Slot Name Signature 
       0  9  0 this L$line10/$read$$iw$$iw$$anonfun$1; 
       0  9  1 v1 Ljava/lang/Object; 
     LineNumberTable: 
     line 9: 0 

pośmiać dostaje trochę tlenu do krwioobiegu.

Answer 2

Istnieje ogromna różnica OGROMNY różnica czasu.

Jeśli dodać ciągi wielokrotnie używając += zrobić nie optymalizacji dala koszt O(n^2) tworzenia stopniowo dłuższe ciągi. Aby dodać jedną lub dwie, nie zobaczysz różnicy, ale nie skaluje się; do czasu dodania 100 (krótkich) łańcuchów, użycie StringBuilder jest ponad 20 razy szybsze. (Dokładne dane: 1,3 us vs. 27,1 us, aby dodać ciągi reprezentacji liczb od 0 do 100, taktowania powinny być powtarzalne do około + = 5% i oczywiście są dla mojej maszyny.)

Korzystanie ++= na varString jest daleko, daleko jeszcze gorzej, bo są następnie instruowania Scala traktować ciąg jako zbiór znak po znaku, który następnie wymaga różnego rodzaju opakowania, aby String wyglądać kolekcji (, w tym dodawanie w pudełku dodatku znak po znaku przy użyciu ogólnej wersji ++!). Teraz masz 16 razy więcej woluminów na 100 dodatkach! (Dokładne dane: 428,8 nas na ++= na sznurku var zamiast += „s 26,7 us.)

Jeśli piszesz pojedyncze sprawozdanie z gronem + es następnie kompilator Scala będzie używać StringBuilder i skończyć z Efektywny wynik (Dane: 1,8 us na ciągłych ciągach wyciągniętych z tablicy).

Tak więc, jeśli dodajesz ciągi z niczym innym niż + w linii i zależy Ci na wydajności, użyj StringBuilder. Zdecydowanie nie należy używać ++=, aby dodać kolejne String do varString; po prostu nie ma żadnego powodu, aby to zrobić, i istnieje wielka kara w czasie wykonywania.

(Uwaga - bardzo często nie obchodzi cię, jak wydajne są dodatki do Twojego łańcucha!) Nie zagracaj kodu z dodatkowymi StringBuilder s, chyba że masz powód, by podejrzewać, że ta konkretna ścieżka kodowa jest często nazywana .)