String.Ginin vấn đề hiệu suất trong C#

Question

Tôi đã nghiên cứu một câu hỏi đã được trình bày cho tôi: Cách viết một hàm lấy chuỗi làm đầu vào và trả về một chuỗi có dấu cách giữa các ký tự. Hàm này được viết để tối ưu hóa hiệu suất khi nó được gọi là hàng ngàn lần mỗi giây.

1. Tôi biết rằng .net có chức năng được gọi là String.Join, mà tôi có thể chuyển vào ký tự khoảng trắng làm dấu tách cùng với chuỗi gốc.

2. Chặn sử dụng String.Join, tôi có thể sử dụng lớp StringBuilder để nối thêm dấu cách sau mỗi ký tự.

3. Cách khác để thực hiện tác vụ này là khai báo một mảng ký tự với 2 * n-1 ký tự (Bạn phải thêm ký tự n-1 cho dấu cách). Mảng ký tự có thể được điền vào một vòng lặp và sau đó được chuyển đến chuỗi constructor.

Tôi đã viết một số mã .net chạy mỗi thuật toán một triệu lần mỗi tham số "Hello, World" và đo thời gian thực thi. Phương pháp (3) là nhiều, nhanh hơn nhiều so với (1) hoặc (2).

Tôi biết rằng (3) nên rất nhanh vì nó tránh tạo ra bất kỳ tham chiếu chuỗi bổ sung nào để thu gom rác, nhưng có vẻ như với chức năng tích hợp .net như String.Join sẽ mang lại hiệu suất tốt. Tại sao sử dụng String.Join chậm hơn nhiều so với thực hiện công việc bằng tay?

public static class TestClass 
{ 
    // 491 milliseconds for 1 million iterations 
    public static string Space1(string s) 
    {    
     return string.Join(" ", s.AsEnumerable()); 
    } 

    //190 milliseconds for 1 million iterations 
    public static string Space2(string s) 
    { 
     if (s.Length < 2) 
      return s; 
     StringBuilder sb = new StringBuilder(); 
     sb.Append(s[0]); 
     for (int i = 1; i < s.Length; i++) 
     { 
      sb.Append(' '); 
      sb.Append(s[i]); 
     }    
     return sb.ToString(); 
    } 

    // 50 milliseconds for 1 million iterations 
    public static string Space3(string s) 
    { 
     if (s.Length < 2) 
      return s; 
     char[] array = new char[s.Length * 2 - 1]; 
     array[0] = s[0]; 
     for (int i = 1; i < s.Length; i++) 
     { 
      array[2*i-1] = ' '; 
      array[2*i] = s[i]; 
     } 
     return new string(array); 
    } 

Cập nhật: Tôi đã thay đổi dự án của tôi để "phát hành" chế độ và cập nhật lần trôi qua tôi trong câu hỏi cho phù hợp.

Answer 1

Tại sao sử dụng String.Join chậm hơn rất nhiều so với thực hiện công việc bằng tay?

Lý do String.Join chậm trong trường hợp này là bạn có thể viết một thuật toán có kiến ​​thức trước về bản chất chính xác của IEnumerable<T> của bạn.

String.Join<T>(string, IEnumerable<T>) (quá tải bạn đang sử dụng), mặt khác, được thiết kế để làm việc với bất kỳ loại số lượng tùy ý nào, có nghĩa là nó không thể phân bổ trước đến kích thước phù hợp. Trong trường hợp này, giao dịch linh hoạt cho hiệu năng và tốc độ thuần túy.

Nhiều phương pháp khuôn khổ xử lý các trường hợp nhất định, nơi mọi thứ có thể được tăng tốc bằng cách kiểm tra các điều kiện, nhưng điều này thường chỉ được thực hiện khi "trường hợp đặc biệt" đó là phổ biến.

Trong trường hợp này, bạn đang tạo một trường hợp cạnh có hiệu quả trong đó quy trình viết tay sẽ nhanh hơn, nhưng đây không phải là trường hợp sử dụng phổ biến là String.Join. Trong trường hợp này, vì bạn biết chính xác, trước những gì được yêu cầu, bạn có khả năng tránh tất cả chi phí cần thiết để có thiết kế linh hoạt bằng cách phân bổ trước một mảng chính xác kích thước phù hợp và xây dựng kết quả theo cách thủ công.

Bạn sẽ thấy rằng, thường là có thể để viết một phương pháp sẽ thực hiện một số thói quen khuôn khổ cho dữ liệu đầu vào cụ thể. Điều này là phổ biến, vì các thói quen khuôn khổ phải làm việc với bất kỳ tập dữ liệu nào, có nghĩa là bạn không thể tối ưu hóa cho một kịch bản đầu vào cụ thể.

Answer 2

Vì bạn không sử dụng bản dựng Bản phát hành (nên được tối ưu hóa được kiểm tra theo mặc định) và/hoặc bạn đang gỡ lỗi thông qua studio trực quan thì JITer sẽ bị ngăn không cho tối ưu hóa nó. Bởi vì điều này bạn chỉ không nhận được một hình ảnh tốt về bao lâu mỗi hoạt động thực sự mất. Khi bạn thêm vào các tối ưu hóa, bạn có thể có được bức tranh thực sự về những gì đang xảy ra.

Điều quan trọng là bạn không phải gỡ lỗi trong studio trực quan. Chuyển đến thư mục bin/release và nhấp đúp vào tệp thực thi hoàn toàn bên ngoài studio trực quan.

Answer 3

Ví dụ String.Join của bạn hoạt động trên IEnumerable<char>. Việc đếm IEnumerable<T> với foreach thường chậm hơn so với thực hiện một vòng lặp for (nó phụ thuộc vào loại bộ sưu tập và các trường hợp khác, như Dave Black đã chỉ ra trong một nhận xét). Ngay cả khi Join sử dụng StringBuilder, bộ đệm trong của StringBuilder sẽ phải tăng lên nhiều lần vì số lượng mục cần thêm không được biết trước.

Answer 4

Hiệu suất kém không đến từ String.Join, nhưng từ cách bạn xử lý từng ký tự. Trong trường hợp này, vì các ký tự phải được xử lý riêng lẻ, phương thức đầu tiên của bạn sẽ tạo ra nhiều chuỗi trung gian hơn và phương thức thứ hai bị hai cuộc gọi phương thức .Append cho mỗi ký tự. Phương pháp thứ ba của bạn không liên quan đến nhiều chuỗi trung gian hoặc các cuộc gọi phương thức và đó là lý do tại sao phương pháp thứ ba của bạn là nhanh nhất.

Answer 5

Khi bạn đã vượt qua một số IEnumerable đến String.Join, không có ý tưởng về số lượng bộ nhớ cần phân bổ. Tôi phân bổ một đoạn bộ nhớ, thay đổi kích thước nó nếu nó không đủ và lặp lại quá trình cho đến khi nó đủ bộ nhớ để chứa tất cả các chuỗi.

Phiên bản mảng nhanh hơn vì chúng tôi biết lượng bộ nhớ được cấp phát tốt hơn.

Cũng xin vui lòng không phải là khi bạn đang chạy phiên bản đầu tiên, GC có thể đã xảy ra.

Answer 6

Trong phương pháp đầu tiên của bạn, bạn đang sử dụng quá tải String.Join hoạt động trên Số đếm, yêu cầu phương thức này đi bộ các ký tự của chuỗi bằng cách sử dụng một điều tra viên. Bên trong, điều này sử dụng một số StringBuilder vì số ký tự chính xác không xác định.

Bạn đã cân nhắc sử dụng quá tải String.Join có thay thế chuỗi (hoặc chuỗi ký tự)? Việc thực hiện đó cho phép sử dụng bộ đệm độ dài cố định (tương tự như phương thức thứ ba của bạn) cùng với một số hoạt động chuỗi không an toàn nội bộ cho tốc độ. Cuộc gọi sẽ thay đổi thành - String.Join(" ", s); Nếu không thực sự thực hiện các biện pháp để đo lường, tôi hy vọng điều này sẽ ngang bằng hoặc nhanh hơn phương pháp thứ ba của bạn.

Answer 7

Đọc rất thú vị.Tôi muốn đề cập rằng

string.Join(" ", s.ToCharArray()) 

cải thiện hiệu suất hơi trên

string.Join(" ", s.AsEnumerable()) 

Dưới đây là một trang thử nghiệm tôi đã sử dụng để so sánh lần:

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Diagnostics; 
using System.Text; 
using System.Web.UI; 
public partial class Test : Page 
{ 
    protected void Page_Load(object sender, EventArgs e) 
    { 
     var rankings = new Dictionary<string, double>(); 
     var test = new string('1', 1000000); 
     Response.Write("Testing space separating a string with length: " + test.Length + ". Numbers are total milliseconds.<br/><br/>"); 
     var timer = Stopwatch.StartNew(); 
     Space1(test); 
     timer.Stop(); 
     rankings.Add("string.join", timer.Elapsed.TotalMilliseconds); 
     timer = Stopwatch.StartNew(); 
     Space2(test); 
     timer.Stop(); 
     rankings.Add("stringbuilder", timer.Elapsed.TotalMilliseconds); 
     timer = Stopwatch.StartNew(); 
     Space3(test); 
     timer.Stop(); 
     rankings.Add("char array", timer.Elapsed.TotalMilliseconds); 
     var list = rankings.ToList(); 
     list.Sort((x, y) => x.Value.CompareTo(y.Value)); 
     foreach (var rank in list) 
     { 
      Response.Write(rank + "<br/>"); 
     } 
    } 
    private static string Space1(string s) 
    { 
     //return string.Join(" ", s.AsEnumerable()); 
     return string.Join(" ", s.ToCharArray()); 
    } 
    private static string Space2(string s) 
    { 
     if (s.Length < 2) 
     { 
      return s; 
     } 
     var sb = new StringBuilder(); 
     sb.Append(s[0]); 
     for (var i = 1; i < s.Length; i++) 
     { 
      sb.Append(' '); 
      sb.Append(s[i]); 
     } 
     return sb.ToString(); 
    } 
    private static string Space3(string s) 
    { 
     if (s.Length < 2) 
     { 
      return s; 
     } 
     var array = new char[s.Length * 2 - 1]; 
     array[0] = s[0]; 
     for (var i = 1; i < s.Length; i++) 
     { 
      array[2 * i - 1] = ' '; 
      array[2 * i] = s[i]; 
     } 
     return new string(array); 
    } 
} 

Mẫu đầu ra (hầu như lúc nào cũng là cùng một thứ tự):

Không gian thử nghiệm tách một chuỗi có chiều dài: 1000000. Số là tổng mili giây.

[char mảng, 14,7902]

[StringBuilder, 25,6643]

[String.Join, 61,7402]