Làm cách nào để tối ưu hóa vòng nhận cho hàng nghìn thư trong Erlang?

Question

Trong chương "Lập trình đa lõi CPU" của Lập trình Erlang cuốn sách, Joe Armstrong đưa ra một ví dụ tốt đẹp của song song của một hàm bản đồ:

pmap(F, L) -> 
    S = self(), 
    %% make_ref() returns a unique reference 
    %% we'll match on this later 
    Ref = erlang:make_ref(), 
    Pids = map(fun(I) -> 
     spawn(fun() -> do_f(S, Ref, F, I) end) 
    end, L), 
    %% gather the results 
    gather(Pids, Ref). 

do_f(Parent, Ref, F, I) -> 
    Parent ! {self(), Ref, (catch F(I))}. 

gather([Pid|T], Ref) -> 
    receive 
     {Pid, Ref, Ret} -> [Ret|gather(T, Ref)] 
    end; 

gather([], _) -> 
    []. 

Nó hoạt động độc đáo, nhưng tôi tin rằng có một nút cổ chai trong đó gây ra nó hoạt động rất chậm trên danh sách với hơn 100.000 yếu tố.

Khi chức năng gather() được thực hiện, nó bắt đầu khớp với một Pid đầu tiên từ danh sách Pids với thông báo trong hộp thư chính của quá trình. Nhưng nếu thư cũ nhất trong hộp thư không phải là từ số này rất Pid thì sao? Sau đó, nó cố gắng tất cả các tin nhắn khác cho đến khi nó tìm thấy một trận đấu. Điều đó đang được nói, có một xác suất nhất định, trong khi thực hiện chức năng gather() chúng ta sẽ phải lặp qua tất cả các thông báo hộp thư để tìm một kết quả phù hợp với một Pid mà chúng tôi đã lấy từ danh sách Pids. Đó là N * N trường hợp xấu nhất cho một danh sách các kích thước N.

Tôi thậm chí còn cố gắng chứng minh sự tồn tại của nút cổ chai này:

gather([Pid|T], Ref) -> 
    receive 
     {Pid, Ref, Ret} -> [Ret|gather(T, Ref)]; 
     %% Here it is: 
     Other -> io:format("The oldest message in the mailbox (~w) did not match with Pid ~w~n", [Other,Pid]) 
    end; 

Làm thế nào tôi có thể tránh nút cổ chai này?

Answer 1

Trong trường hợp này, bạn có thể sử dụng dict (từ pid của quá trình sinh sản để lập chỉ mục trong danh sách gốc) làm Pids thay thế.

Answer 2

Vấn đề là nếu bạn muốn có một giải pháp chính xác bạn vẫn phải:

• kiểm tra nếu trả lời được xuất phát từ một trong những quá trình bạn có sinh ra
• đảm bảo kết quả đúng trật tự

Đây là giải pháp sử dụng bộ đếm thay vì danh sách - điều này giúp loại bỏ sự cần thiết để duyệt qua hộp thư đến nhiều lần. Kết hợp của Ref đảm bảo rằng thư chúng tôi nhận được từ con cái của chúng tôi. Trình tự thích hợp được đảm bảo bằng cách phân loại kết quả với lists:keysort/2 ở cuối của pmap, bổ sung thêm một số chi phí, nhưng có thể ít hơn O(n^2).

-module(test). 

-compile(export_all). 

pmap(F, L) -> 
    S = self(), 
    % make_ref() returns a unique reference 
    % we'll match on this later 
    Ref = erlang:make_ref(), 
    Count = lists:foldl(fun(I, C) -> 
           spawn(fun() -> 
               do_f(C, S, Ref, F, I) 
             end), 
           C+1 
         end, 0, L), 
    % gather the results 
    Res = gather(0, Count, Ref), 
    % reorder the results 
    element(2, lists:unzip(lists:keysort(1, Res))). 


do_f(C, Parent, Ref, F, I) -> 
    Parent ! {C, Ref, (catch F(I))}. 


gather(C, C, _) -> 
    []; 
gather(C, Count, Ref) -> 
    receive 
     {C, Ref, Ret} -> [{C, Ret}|gather(C+1, Count, Ref)] 
    end. 

Answer 3

Ví dụ của Joe gọn gàng, nhưng thực tế bạn muốn có giải pháp nặng hơn cho vấn đề của mình. Hãy xem ví dụ http://code.google.com/p/plists/source/browse/trunk/src/plists.erl.

Nói chung, có ba điều bạn muốn làm:

1. Chọn một đơn vị làm việc đó là "đủ lớn". Nếu đơn vị công việc quá nhỏ, bạn chết bằng cách xử lý trên không. Nếu nó quá lớn, bạn chết bởi công nhân đang nhàn rỗi, đặc biệt là nếu công việc của bạn không đồng đều chia cho số phần tử trong danh sách.

2. Giới hạn trên số lượng công nhân đồng thời. Psyeugenic đề xuất chia nhỏ nó bằng cách lên lịch, tôi đề xuất chia nhỏ nó bằng giới hạn số lượng công việc, 100 công việc nói. Nghĩa là, bạn muốn bắt đầu 100 công việc và sau đó đợi cho đến khi một số công việc đó hoàn thành trước khi bạn bắt đầu thêm nhiều công việc.

3. Cân nhắc sắp xếp thứ tự các phần tử nếu có thể.Nó nhanh hơn nhiều nếu bạn không cần phải đưa vào tài khoản. Đối với nhiều vấn đề, điều này là có thể. Nếu đơn đặt hàng quan trọng, hãy sử dụng dict để lưu trữ nội dung như được đề xuất. Nó nhanh hơn cho các danh sách phần tử lớn.

Quy tắc cơ bản là ngay khi bạn muốn song song, bạn hiếm khi muốn đại diện dựa trên danh sách dữ liệu của mình. Danh sách có một tuyến tính cố hữu với nó, mà bạn không muốn. Có một cuộc trò chuyện của Guy Steele về chủ đề: http://vimeo.com/6624203