Câu hỏi Cơ chế tối ưu hóa chuỗi ngắn trong libc ++ là gì?


Câu trả lời này đưa ra một cái nhìn tổng quan mức cao về tối ưu hóa chuỗi ngắn (SSO). Tuy nhiên, tôi muốn biết chi tiết hơn về cách nó hoạt động trong thực tế, cụ thể trong việc thực hiện libc ++:

  • Chuỗi phải ngắn bao nhiêu để đủ điều kiện cho SSO? Điều này có phụ thuộc vào kiến ​​trúc đích không?

  • Cách triển khai phân biệt giữa ngắn và dài chuỗi khi truy cập dữ liệu chuỗi? Nó đơn giản như m_size <= 16 hoặc là một lá cờ là một phần của một số biến thành viên khác? (TÔI tưởng tượng rằng m_size hoặc một phần của nó cũng có thể được sử dụng để lưu trữ dữ liệu chuỗi).

Tôi hỏi câu hỏi này đặc biệt cho libc ++ vì tôi biết rằng nó sử dụng SSO, điều này thậm chí còn được đề cập trên trang chủ libc ++.

Dưới đây là một số quan sát sau khi xem xét nguồn:

libc ++ có thể được biên dịch với hai bố trí bộ nhớ hơi khác nhau cho lớp chuỗi, điều này được điều chỉnh bởi _LIBCPP_ALTERNATE_STRING_LAYOUT cờ. Cả hai bố cục này cũng phân biệt giữa các máy nhỏ và cuối lớn, khiến chúng ta có tổng cộng 4 biến thể khác nhau. Tôi sẽ giả định bố cục "bình thường" và một chút ít về những gì sau.

Giả sử thêm rằng size_type là 4 byte và value_type là 1 byte, đây là 4 byte đầu tiên của chuỗi sẽ trông giống như trong bộ nhớ:

// short string: (s)ize and 3 bytes of char (d)ata
sssssss0;dddddddd;dddddddd;dddddddd
       ^- is_long = 0

// long string: (c)apacity
ccccccc1;cccccccc;cccccccc;cccccccc
       ^- is_long = 1

Vì kích thước của chuỗi ngắn nằm trong 7 bit trên, nó cần được dịch chuyển khi truy cập nó:

size_type __get_short_size() const {
    return __r_.first().__s.__size_ >> 1;
}

Tương tự, getter và setter cho khả năng sử dụng chuỗi dài __long_mask để làm việc xung quanh is_long bit.

Tôi vẫn đang tìm câu trả lời cho câu hỏi đầu tiên của tôi, tức là giá trị nào sẽ __min_cap, dung lượng của các chuỗi ngắn, có cho các kiến ​​trúc khác nhau không?

Triển khai thư viện chuẩn khác

Câu trả lời này đưa ra một cái nhìn tổng quan tốt đẹp về std::string bố trí bộ nhớ trong các triển khai thư viện chuẩn khác.


76
2018-02-11 06:01


gốc


libc ++ là mã nguồn mở, bạn có thể tìm thấy nó string tiêu đề đây, Tôi đang kiểm tra nó ra vào lúc này :) - Matthieu M.
Bạn có thể quan tâm Hoạt động tối ưu hóa và di chuyển chuỗi nhỏ - Ali
@ Matthieu M .: Tôi đã thấy điều đó trước đây, không may đó là một tập tin rất lớn, cảm ơn sự giúp đỡ trong việc kiểm tra nó ra. - ValarDohaeris
@Ali: Tôi đã vấp phải điều này trong googling xung quanh. Tuy nhiên, bài đăng trên blog này nói rõ ràng rằng nó chỉ là một minh họa về SSO và không phải là một biến thể được tối ưu hóa cao sẽ được sử dụng trong thực tế. - ValarDohaeris


Các câu trả lời:


Libc ++ basic_string được thiết kế để có sizeof 3 từ trên tất cả các kiến ​​trúc, nơi sizeof(word) == sizeof(void*). Bạn đã cắt chính xác cờ dài / ngắn và trường kích thước ở dạng ngắn.

giá trị nào sẽ __min_cap, dung lượng của các chuỗi ngắn, dùng cho các kiến ​​trúc khác nhau?

Trong dạng ngắn, có 3 từ để làm việc với:

  • 1 bit đi đến lá cờ dài / ngắn.
  • 7 bit đi đến kích thước.
  • Giả định char, 1 byte đi tới dấu null (libc ++ sẽ luôn lưu trữ một dấu null phía sau dữ liệu).

Điều này để lại 3 từ trừ 2 byte để lưu trữ một chuỗi ngắn (tức là lớn nhất capacity() mà không có phân bổ).

Trên một máy 32 bit, 10 ký tự sẽ phù hợp trong chuỗi ngắn. sizeof (chuỗi) là 12.

Trên một máy 64 bit, 22 ký tự sẽ phù hợp trong chuỗi ngắn. sizeof (chuỗi) là 24.

Mục tiêu thiết kế chính là giảm thiểu sizeof(string), trong khi làm cho bộ đệm trong càng lớn càng tốt. Lý do là để tăng tốc độ di chuyển xây dựng và chuyển nhượng. Lớn hơn sizeof, càng có nhiều từ bạn phải di chuyển trong khi xây dựng di chuyển hoặc chuyển nhượng.

Biểu mẫu dài cần tối thiểu 3 từ để lưu trữ con trỏ dữ liệu, kích thước và dung lượng. Vì vậy tôi đã hạn chế hình thức ngắn cho 3 từ đó. Nó đã được gợi ý rằng một sizeof 4 từ có thể có hiệu suất tốt hơn. Tôi chưa thử nghiệm lựa chọn thiết kế đó.

_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT

Có một cờ cấu hình được gọi là _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT sắp xếp lại các thành viên dữ liệu sao cho thay đổi "bố cục dài" từ:

struct __long
{
    size_type __cap_;
    size_type __size_;
    pointer   __data_;
};

đến:

struct __long
{
    pointer   __data_;
    size_type __size_;
    size_type __cap_;
};

Động lực cho sự thay đổi này là niềm tin rằng việc đặt __data_ đầu tiên sẽ có một số lợi thế hiệu suất do sự liên kết tốt hơn. Một nỗ lực đã được thực hiện để đo lường các lợi thế hiệu suất, và rất khó để đo lường. Nó sẽ không làm cho hiệu suất tồi tệ hơn, và nó có thể làm cho nó tốt hơn một chút.

Cờ nên được sử dụng cẩn thận. Nó là một ABI khác, và nếu vô tình trộn lẫn với một libc ++ std::string được biên dịch với một cài đặt khác _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT sẽ tạo ra lỗi thời gian chạy.

Tôi khuyên bạn nên chỉ thay đổi cờ này bởi một nhà cung cấp libc ++.


90
2018-02-11 18:25



Bạn không chắc chắn liệu có tương thích giấy phép giữa libc ++ và Facebook Folly hay không, nhưng FBstring quản lý để lưu trữ thêm một char (tức là 23) bằng cách thay đổi kích thước thành dung lượng còn lại, để nó có thể làm nhiệm vụ gấp đôi như terminator null cho một chuỗi ngắn 23 ký tự. - TemplateRex
@TemplateRex: Đó là thông minh. Tuy nhiên nếu libc ++ chấp nhận nó sẽ yêu cầu libc ++ từ bỏ một đặc tính khác mà tôi thích về chuỗi std :: của nó: string là tất cả 0 bit. Điều đó làm cho xây dựng mặc định siêu hiệu quả. Và nếu bạn sẵn sàng uốn cong các quy tắc, đôi khi thậm chí miễn phí. Ví dụ. bạn có thể callocbộ nhớ và chỉ cần khai báo nó là đầy đủ các chuỗi được xây dựng mặc định. - Howard Hinnant
Ah, 0-init thật sự rất tuyệt! BTW, FBstring có 2 bit cờ, cho biết các chuỗi ngắn, trung bình và lớn. Nó sử dụng SSO cho chuỗi lên đến 23 ký tự, và sau đó sử dụng một vùng bộ nhớ malloc-ed cho chuỗi lên đến 254 ký tự và hơn thế nữa mà chúng làm COW (không còn hợp pháp trong C ++ 11, tôi biết). - TemplateRex
Tại sao không thể lưu trữ kích thước và dung lượng trong ints để lớp có thể được đóng gói chỉ 16 byte trên kiến ​​trúc 64-bit? - phuclv
@ LưuVĩnhPhúc: Tôi muốn cho phép chuỗi lớn hơn 2Gb trên 64 bit. Chi phí được thừa nhận là lớn hơn sizeof. Nhưng đồng thời bộ đệm bên trong cho char đi từ 14 đến 22, đó là một lợi ích khá tốt. - Howard Hinnant


Các triển khai libc ++ là một chút phức tạp, tôi sẽ bỏ qua thiết kế thay thế của nó và giả sử một máy tính cuối nhỏ:

template <...>
class basic_string {
/* many many things */

    struct __long
    {
        size_type __cap_;
        size_type __size_;
        pointer   __data_;
    };

    enum {__short_mask = 0x01};
    enum {__long_mask  = 0x1ul};

    enum {__min_cap = (sizeof(__long) - 1)/sizeof(value_type) > 2 ?
                      (sizeof(__long) - 1)/sizeof(value_type) : 2};

    struct __short
    {
        union
        {
            unsigned char __size_;
            value_type __lx;
        };
        value_type __data_[__min_cap];
    };

    union __ulx{__long __lx; __short __lxx;};

    enum {__n_words = sizeof(__ulx) / sizeof(size_type)};

    struct __raw
    {
        size_type __words[__n_words];
    };

    struct __rep
    {
        union
        {
            __long  __l;
            __short __s;
            __raw   __r;
        };
    };

    __compressed_pair<__rep, allocator_type> __r_;
}; // basic_string

Chú thích: __compressed_pair về cơ bản là một cặp được tối ưu hóa cho Tối ưu hóa cơ sở trống, aka template <T1, T2> struct __compressed_pair: T1, T2 {};; cho tất cả các ý định và mục đích bạn có thể coi nó là một cặp thông thường. Tầm quan trọng của nó chỉ xuất hiện bởi vì std::allocator là vô quốc tịch và do đó trống rỗng.

Được rồi, điều này khá thô, vì vậy hãy kiểm tra cơ chế! Bên trong, nhiều chức năng sẽ gọi __get_pointer() mà chính nó gọi __is_long để xác định xem chuỗi có đang sử dụng __long hoặc là __short đại diện:

bool __is_long() const _NOEXCEPT
    { return bool(__r_.first().__s.__size_ & __short_mask); }

// __r_.first() -> __rep const&
//     .__s     -> __short const&
//     .__size_ -> unsigned char

Thành thật mà nói, tôi không quá chắc chắn đây là Tiêu chuẩn C ++ (Tôi biết điều khoản ban đầu về sau trong union nhưng không biết làm thế nào nó meshes với một liên minh vô danh và aliasing ném lại với nhau), nhưng một thư viện chuẩn được phép tận dụng lợi thế của hành vi thực hiện được xác định anyway.


16
2018-02-11 08:30



Cảm ơn bạn đã trả lời chi tiết này! Mảnh duy nhất tôi thiếu là cái gì __min_cap sẽ đánh giá cho các kiến ​​trúc khác nhau, tôi không chắc chắn sizeof() sẽ quay trở lại và nó bị ảnh hưởng như thế nào bởi răng cưa. - ValarDohaeris
@ValarDohaeris nó được thực hiện xác định. thông thường, bạn sẽ mong đợi 3 * the size of one pointer trong trường hợp này, sẽ là 12 octet trên một vòm 32 bit và 24 octet trên một vòm 64 bit. - justin