Trong 3 phương pháp này để đọc danh sách được liên kết từ bộ nhớ dùng chung, tại sao lại là 3 nhanh nhất?

Question

Tôi có chương trình 'máy chủ' cập nhật nhiều danh sách được liên kết trong bộ nhớ dùng chung để phản hồi các sự kiện bên ngoài. Tôi muốn các chương trình khách hàng nhận thấy một bản cập nhật trên bất kỳ danh sách nào càng nhanh càng tốt (độ trễ thấp nhất). Máy chủ đánh dấu nút của một danh sách liên kết là state_ là FILLED khi dữ liệu của nó được điền và con trỏ tiếp theo của nó đã được đặt thành vị trí hợp lệ. Cho đến lúc đó, state_ của nó là NOT_FILLED_YET. Tôi đang sử dụng các rào cản bộ nhớ để đảm bảo rằng khách hàng không thấy state_ là FILLED trước khi dữ liệu bên trong thực sự sẵn sàng (và có vẻ như nó hoạt động, tôi không bao giờ thấy dữ liệu bị hỏng). Ngoài ra, state_ là dễ bay hơi để đảm bảo trình biên dịch không nâng kiểm tra của khách hàng của nó ra khỏi vòng lặp.

Giữ mã máy chủ giống hệt nhau, tôi đã đưa ra 3 phương pháp khác nhau để khách hàng quét danh sách được liên kết để thay đổi. Câu hỏi đặt ra là: Tại sao phương pháp thứ 3 nhanh nhất?

Phương pháp 1: robin tròn trên tất cả các danh sách liên kết (gọi là 'kênh') liên tục, tìm kiếm để xem nếu có các nút đã thay đổi để 'ĐIỀN':

void method_one() 
{ 
    std::vector<Data*> channel_cursors; 
    for(ChannelList::iterator i = channel_list.begin(); i != channel_list.end(); ++i) 
    { 
     Data* current_item = static_cast<Data*>(i->get(segment)->tail_.get(segment)); 
     channel_cursors.push_back(current_item); 
    } 

    while(true) 
    { 
     for(std::size_t i = 0; i < channel_list.size(); ++i) 
     { 
      Data* current_item = channel_cursors[i]; 

      ACQUIRE_MEMORY_BARRIER; 
      if(current_item->state_ == NOT_FILLED_YET) { 
       continue; 
      } 

      log_latency(current_item->tv_sec_, current_item->tv_usec_); 

      channel_cursors[i] = static_cast<Data*>(current_item->next_.get(segment)); 
     } 
    } 
} 

Phương pháp 1 cho độ trễ rất thấp khi sau đó số lượng kênh nhỏ. Nhưng khi số lượng kênh tăng lên (250K +) thì nó trở nên rất chậm vì lặp lại tất cả các kênh. Vì vậy, tôi đã thử ...

Cách 2: Cung cấp cho mỗi danh sách liên kết một ID. Giữ một 'danh sách cập nhật' riêng biệt sang một bên. Mỗi khi một trong các danh sách liên kết được cập nhật, hãy đẩy ID của nó vào danh sách cập nhật. Bây giờ chúng ta chỉ cần theo dõi danh sách cập nhật duy nhất, và kiểm tra các ID chúng ta nhận được từ nó.

void method_two() 
{ 
    std::vector<Data*> channel_cursors; 
    for(ChannelList::iterator i = channel_list.begin(); i != channel_list.end(); ++i) 
    { 
     Data* current_item = static_cast<Data*>(i->get(segment)->tail_.get(segment)); 
     channel_cursors.push_back(current_item); 
    } 

    UpdateID* update_cursor = static_cast<UpdateID*>(update_channel.tail_.get(segment)); 

    while(true) 
    { 
      ACQUIRE_MEMORY_BARRIER; 
     if(update_cursor->state_ == NOT_FILLED_YET) { 
      continue; 
     } 

     ::uint32_t update_id = update_cursor->list_id_; 

     Data* current_item = channel_cursors[update_id]; 

     if(current_item->state_ == NOT_FILLED_YET) { 
      std::cerr << "This should never print." << std::endl; // it doesn't 
      continue; 
     } 

     log_latency(current_item->tv_sec_, current_item->tv_usec_); 

     channel_cursors[update_id] = static_cast<Data*>(current_item->next_.get(segment)); 
     update_cursor = static_cast<UpdateID*>(update_cursor->next_.get(segment)); 
    } 
} 

Phương pháp 2 cho độ trễ TERRIBLE. Trong khi Phương pháp 1 có thể cho độ trễ dưới 10us, Phương pháp 2 sẽ không thể giải thích thường xuyên về độ trễ 8ms! Sử dụng gettimeofday nó xuất hiện rằng sự thay đổi trong update_cursor-> state_ rất chậm để chuyển từ chế độ xem của máy chủ sang máy khách (tôi đang ở trên một hộp đa lõi, vì vậy tôi cho rằng sự chậm trễ là do bộ nhớ cache). Vì vậy, tôi đã thử một cách tiếp cận lai ...

Phương pháp 3: Giữ danh sách cập nhật. Nhưng lặp lại tất cả các kênh liên tục và trong mỗi lần kiểm tra lặp lại nếu danh sách cập nhật đã được cập nhật. Nếu nó có, đi với số đẩy lên nó. Nếu chưa, hãy kiểm tra kênh mà chúng tôi hiện đang lặp lại.

void method_three() 
{ 
    std::vector<Data*> channel_cursors; 
    for(ChannelList::iterator i = channel_list.begin(); i != channel_list.end(); ++i) 
    { 
     Data* current_item = static_cast<Data*>(i->get(segment)->tail_.get(segment)); 
     channel_cursors.push_back(current_item); 
    } 

    UpdateID* update_cursor = static_cast<UpdateID*>(update_channel.tail_.get(segment)); 

    while(true) 
    { 
     for(std::size_t i = 0; i < channel_list.size(); ++i) 
     { 
      std::size_t idx = i; 

      ACQUIRE_MEMORY_BARRIER; 
      if(update_cursor->state_ != NOT_FILLED_YET) { 
       //std::cerr << "Found via update" << std::endl; 
       i--; 
       idx = update_cursor->list_id_; 
       update_cursor = static_cast<UpdateID*>(update_cursor->next_.get(segment)); 
      } 

      Data* current_item = channel_cursors[idx]; 

      ACQUIRE_MEMORY_BARRIER; 
      if(current_item->state_ == NOT_FILLED_YET) { 
       continue; 
      } 

      found_an_update = true; 

      log_latency(current_item->tv_sec_, current_item->tv_usec_); 
      channel_cursors[idx] = static_cast<Data*>(current_item->next_.get(segment)); 
     } 
    } 
} 

Độ trễ của phương pháp này tốt như Phương pháp 1, nhưng được chia tỷ lệ thành số lượng lớn kênh. Vấn đề là, tôi không biết tại sao. Chỉ cần ném một cờ lê vào mọi thứ: nếu tôi bỏ ghi chú phần 'tìm thấy thông qua cập nhật', nó sẽ in giữa MỌI LATENCY LOG MESSAGE. Có nghĩa là mọi thứ chỉ được tìm thấy trong danh sách cập nhật! Vì vậy, tôi không hiểu tại sao phương pháp này có thể nhanh hơn so với phương pháp 2.

Các đầy đủ, mã biên dịch được (yêu cầu GCC và tăng-1.41) mà tạo ra chuỗi ngẫu nhiên như dữ liệu thử nghiệm là tại địa chỉ: http://pastebin.com/0kuzm3Uf

Cập nhật: Tất cả 3 phương pháp có hiệu quả spinlocking cho đến khi một cập nhật xảy ra. Sự khác biệt là trong thời gian bao lâu để họ nhận thấy bản cập nhật đã xảy ra. Họ tất cả liên tục đánh thuế bộ vi xử lý, do đó không giải thích được sự khác biệt về tốc độ. Tôi đang thử nghiệm trên một máy tính 4 lõi không có gì khác chạy, vì vậy máy chủ và máy khách không có gì để cạnh tranh. Tôi thậm chí đã thực hiện một phiên bản của mã nơi cập nhật báo hiệu một điều kiện và có khách hàng chờ đợi về điều kiện - nó không giúp độ trễ của bất kỳ phương pháp nào.

Update2: Mặc dù có 3 phương pháp, tôi chỉ thử 1 lần, vì vậy chỉ có 1 máy chủ và 1 máy khách đang cạnh tranh cho thành viên state_.

Answer 1

Câu trả lời là khó để tìm ra, và công bằng sẽ khó với thông tin tôi trình bày mặc dù có ai đó thực sự biên soạn nguồn Tôi đã nói rằng "tìm thấy thông qua danh sách cập nhật" được in sau mỗi thông điệp nhật ký độ trễ, nhưng điều này không thực sự đúng - nó chỉ đúng cho đến mức tôi có thể cuộn lại trong thiết bị đầu cuối của tôi. Ngay từ đầu đã có một loạt các bản cập nhật được tìm thấy mà không cần sử dụng danh sách cập nhật.

Vấn đề là giữa thời điểm tôi đặt điểm xuất phát trong danh sách cập nhật và điểm xuất phát trong mỗi danh sách dữ liệu, sẽ có sự chậm trễ do các thao tác này mất thời gian. Hãy nhớ rằng, các danh sách đang phát triển toàn bộ thời gian này đang xảy ra. Hãy xem xét trường hợp đơn giản nhất mà tôi có 2 danh sách dữ liệu, A và B. Khi tôi đặt điểm bắt đầu trong danh sách cập nhật, có 60 phần tử trong đó, do 30 cập nhật trong danh sách A và 30 cập nhật trong danh sách B. đã được luân phiên:

A 
B 
A 
B 
A // and I start looking at the list here 
B 

Nhưng sau khi tôi đặt danh sách cập nhật thành đó, có một số cập nhật cho B và không cập nhật A. Sau đó, tôi đặt địa điểm bắt đầu trong mỗi danh sách dữ liệu. Điểm bắt đầu của tôi cho danh sách dữ liệu sẽ là sau khi tăng đột biến, nhưng điểm xuất phát của tôi trong danh sách cập nhật trước khi tăng đột biến, vì vậy bây giờ tôi sẽ kiểm tra một loạt các bản cập nhật mà không tìm thấy chúng. Cách tiếp cận hỗn hợp ở trên hoạt động tốt nhất vì bằng cách lặp qua tất cả các phần tử khi không thể tìm thấy bản cập nhật, nó sẽ nhanh chóng đóng khoảng cách thời gian giữa danh sách cập nhật và vị trí danh sách dữ liệu.

Answer 2

Tôi đã nhận thấy trong cả phương pháp 1 và phương pháp 3 bạn có một dòng, ACQUIRE_MEMORY_BARRIER, mà tôi giả định có liên quan đến điều kiện đa luồng/chủng tộc?

Dù bằng cách nào, phương pháp 2 không có bất cứ ngủ có nghĩa là đoạn mã sau ...

while(true) 
{ 
    if(update_cursor->state_ == NOT_FILLED_YET) { 
     continue; 
    } 

sẽ búa bộ vi xử lý. Cách điển hình để thực hiện tác vụ của nhà sản xuất/người tiêu dùng này là sử dụng một số loại semaphore để báo hiệu cho người đọc rằng danh sách cập nhật đã thay đổi. Một tìm kiếm cho nhà sản xuất/người tiêu dùng đa luồng nên cung cấp cho bạn một số lượng lớn các ví dụ. Ý tưởng chính ở đây là điều này cho phép thread chuyển sang chế độ ngủ trong khi chờ trạng thái update_cursor-> thay đổi. Điều này ngăn chặn chủ đề này từ ăn cắp tất cả các chu kỳ CPU.

Answer 3

Giả thuyết: Phương pháp 2 bằng cách nào đó sẽ chặn bản cập nhật không được máy chủ ghi.

Một trong những điều bạn có thể làm búa, bên cạnh lõi bộ xử lý, là bộ nhớ cache mạch lạc của bạn. Khi bạn đọc một giá trị trên một lõi cụ thể, bộ đệm L1 trên lõi đó phải có quyền truy cập đọc vào dòng bộ đệm đó, điều đó có nghĩa là nó cần phải vô hiệu hóa quyền ghi vào dòng đó mà bất kỳ bộ đệm nào khác có. Và ngược lại để viết một giá trị. Vì vậy, điều này có nghĩa rằng bạn liên tục ping-ponging dòng bộ nhớ cache qua lại giữa một "viết" nhà nước (trên bộ nhớ cache của máy chủ-core) và "đọc" nhà nước (trong bộ nhớ cache của tất cả các lõi khách hàng). Sự phức tạp của hiệu suất bộ nhớ cache x86 không phải là điều tôi hoàn toàn quen thuộc, nhưng có vẻ hoàn toàn chính đáng (ít nhất là về mặt lý thuyết) rằng bạn đang làm gì bằng việc có ba luồng khác nhau. có thể với yêu cầu truy cập đọc là khoảng việc tạo ra một cuộc tấn công từ chối dịch vụ trên máy chủ ngăn không cho nó ghi vào dòng bộ nhớ cache đó trong vài phần nghìn giây.

Bạn có thể thực hiện một thử nghiệm để phát hiện điều này bằng cách xem xét mất bao lâu để máy chủ thực sự ghi giá trị vào danh sách cập nhật và xem có độ trễ tương ứng với độ trễ hay không.

Bạn cũng có thể thử thử xóa bộ nhớ cache khỏi phương trình, bằng cách chạy mọi thứ trên một lõi để đề khách và máy chủ đang kéo mọi thứ ra khỏi cùng một bộ đệm L1.

Answer 4

Tôi không biết liệu bạn đã từng đọc các cột Đồng thời từ Herb Sutter chưa. Chúng khá thú vị, đặc biệt khi bạn gặp vấn đề về bộ nhớ cache.

Thực tế là số Method2 có vẻ tốt hơn vì id nhỏ hơn dữ liệu nói chung có nghĩa là bạn không phải thực hiện các chuyến đi khứ hồi đến bộ nhớ chính quá thường xuyên (đang đánh thuế).

Tuy nhiên, những gì thực sự có thể xảy ra là bạn có một dòng bộ nhớ cache:

Line of cache = [ID1, ID2, ID3, ID4, ...] 
       ^  ^
      client   server 

Mà sau đó tạo ra tranh chấp.

Đây là bài viết của Herb Sutter: Eliminate False Sharing. Ý tưởng cơ bản chỉ đơn giản là giả tạo ID của bạn trong danh sách để nó chiếm một dòng bộ nhớ cache hoàn toàn.

Kiểm tra các bài viết khác trong serie khi bạn đang ở đó. Có lẽ bạn sẽ nhận được một số ý tưởng. Có một bộ đệm tròn không có khóa đẹp, tôi nghĩ rằng có thể giúp cho danh sách cập nhật của bạn :)