Tại sao chuỗi nối lại nhanh hơn mảng tham gia?

Question

Hôm nay, tôi đọc this thread về tốc độ nối chuỗi.

Đáng ngạc nhiên, nối chuỗi là người chiến thắng:

http://jsben.ch/#/OJ3vo

Kết quả là ngược lại từ những gì tôi nghĩ. Bên cạnh đó, có rất nhiều bài viết về điều này giải thích tương tự như this hoặc this.

Tôi có thể đoán rằng các trình duyệt được tối ưu hóa thành chuỗi concat trên phiên bản mới nhất, nhưng làm cách nào để thực hiện điều đó? Chúng ta có thể nói rằng tốt hơn là sử dụng + khi nối chuỗi không?

Answer 1

chuỗi trình duyệt tối ưu hóa đã làm thay đổi chuỗi nối hình ảnh.

Firefox là trình duyệt đầu tiên tối ưu hóa nối chuỗi. Bắt đầu với phiên bản 1.0, kỹ thuật mảng thực sự chậm hơn so với sử dụng toán tử cộng trong mọi trường hợp. Các trình duyệt khác cũng đã tối ưu hóa chuỗi nối, vì vậy Safari, Opera, Chrome và Internet Explorer 8 cũng hiển thị hiệu suất tốt hơn bằng cách sử dụng toán tử cộng. Internet Explorer trước phiên bản 8 không có tối ưu hóa như vậy và do đó kỹ thuật mảng luôn nhanh hơn toán tử cộng.

- Writing Efficient JavaScript: Chapter 7 – Even Faster Websites

Các V8 javascript động cơ (sử dụng trong Google Chrome) sử dụng this code để làm nối chuỗi:

// ECMA-262, section 15.5.4.6 
function StringConcat() { 
    if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) { 
    throw MakeTypeError("called_on_null_or_undefined", ["String.prototype.concat"]); 
    } 
    var len = %_ArgumentsLength(); 
    var this_as_string = TO_STRING_INLINE(this); 
    if (len === 1) { 
    return this_as_string + %_Arguments(0); 
    } 
    var parts = new InternalArray(len + 1); 
    parts[0] = this_as_string; 
    for (var i = 0; i < len; i++) { 
    var part = %_Arguments(i); 
    parts[i + 1] = TO_STRING_INLINE(part); 
    } 
    return %StringBuilderConcat(parts, len + 1, ""); 
} 

Vì vậy, trong nội bộ họ tối ưu hóa nó bằng cách tạo ra một InternalArray (biến parts), sau đó được lấp đầy. Hàm StringBuilderConcat được gọi với các phần này. Nó nhanh vì hàm StringBuilderConcat là một số mã C++ được tối ưu hóa rất nhiều. Quá dài để báo giá ở đây, nhưng tìm kiếm trong tệp runtime.cc cho RUNTIME_FUNCTION(MaybeObject*, Runtime_StringBuilderConcat) để xem mã.

Answer 2

Tôi đoán là, trong khi mọi phiên bản đều phải trả chi phí cho nhiều kết nối, các phiên bản nối sẽ tạo mảng cùng với đó.

Answer 3

Tôi sẽ nói rằng với chuỗi dễ dàng hơn để preallocate một bộ đệm lớn hơn. Mỗi phần tử chỉ có 2 byte (nếu UNICODE), vì vậy ngay cả khi bạn bảo thủ, bạn có thể preallocate một bộ đệm khá lớn cho chuỗi. Với arrays mỗi phần tử phức tạp hơn, bởi vì mỗi phần tử là một Object, do đó, việc triển khai bảo thủ sẽ preallocate không gian cho các yếu tố ít hơn.

Nếu bạn cố gắng thêm for(j=0;j<1000;j++) trước mỗi for bạn sẽ thấy rằng (dưới chrome) sự khác biệt về tốc độ sẽ nhỏ hơn. Cuối cùng nó vẫn còn 1,5x cho chuỗi nối, nhưng nhỏ hơn so với 2,6 trước đó.

VÀ phải sao chép các phần tử, ký tự Unicode có thể nhỏ hơn tham chiếu đến đối tượng JS.

Hãy nhận biết rằng có khả năng rằng việc triển khai nhiều động cơ JS có một tối ưu hóa cho các mảng single-loại mà có thể làm tất cả những gì đã viết vô ích :-)

Answer 4

Firefox nhanh vì nó sử dụng thứ gọi là Dây (Ropes: an Alternative to Strings). Một sợi dây cơ bản chỉ là một DAG, trong đó mỗi Node là một chuỗi.

Ví dụ: nếu bạn làm a = 'abc'.concat('def'), đối tượng mới được tạo sẽ trông như thế này. Tất nhiên điều này không chính xác như thế nào này trông giống như trong bộ nhớ, bởi vì bạn vẫn cần phải có một lĩnh vực cho loại chuỗi, chiều dài và có thể khác.

a = { 
nodeA: 'abc', 
nodeB: 'def' 
} 

Và b = a.concat('123')

b = { 
    nodeA: a, /* { 
      nodeA: 'abc', 
      nodeB: 'def' 
      } */ 
    nodeB: '123' 
}   

Vì vậy, trong trường hợp đơn giản VM đã làm gần như không làm việc. Vấn đề duy nhất là điều này làm chậm các hoạt động khác trên chuỗi kết quả một chút. Ngoài ra điều này tất nhiên làm giảm chi phí bộ nhớ.

Mặt khác, ['abc', 'def'].join('') thường chỉ cấp phát bộ nhớ để bố trí chuỗi mới bằng phẳng trong bộ nhớ. (Có lẽ điều này nên được tối ưu hóa)

Answer 5

Điều này rõ ràng phụ thuộc vào việc triển khai công cụ javascript. Ngay cả đối với các phiên bản khác nhau của một công cụ, bạn có thể nhận được các kết quả khác nhau một cách có ý nghĩa. Bạn nên làm điểm chuẩn của riêng bạn để xác minh điều này.

Tôi có thể nói rằng String.concat có hiệu suất tốt hơn trong các phiên bản V8 gần đây. Nhưng đối với Firefox và Opera, Array.join là người chiến thắng.

Answer 6

This test cho biết hình phạt thực sự bằng cách sử dụng chuỗi được tạo bằng cách ghép nối được gán với phương thức array.join. Mặc dù tốc độ tổng thể của bài tập vẫn nhanh gấp đôi trong Chrome v31 nhưng nó không còn lớn như khi không sử dụng chuỗi kết quả.

Answer 7

Điểm chuẩn có tầm thường. Ghép nối ba mục tương tự sẽ được inlined, kết quả sẽ được xác định và ghi nhớ, trình xử lý rác sẽ chỉ vứt bỏ các đối tượng mảng (sẽ không có kích thước) và có lẽ chỉ cần đẩy và bật ra khỏi ngăn xếp do không có các tham chiếu bên ngoài và bởi vì các chuỗi không bao giờ thay đổi. Tôi sẽ ấn tượng hơn nếu thử nghiệm là một số lượng lớn các chuỗi được tạo ngẫu nhiên. Như trong một chuỗi giá trị của một hoặc hai.

Array.join FTW!