Hiệu suất/khóa kém với STM

Question

Tôi đang viết một chương trình có số lượng đại lý lớn lắng nghe các sự kiện và phản ứng trên chúng. Kể từ khi Control.Concurrent.Chan.dupChan không được chấp nhận, tôi đã quyết định sử dụng TChan như được quảng cáo.

Hiệu suất của TChan tồi tệ hơn nhiều so với tôi mong đợi. Tôi có chương trình sau đây minh họa vấn đề này:

{-# LANGUAGE BangPatterns #-} 

module Main where 

import Control.Concurrent.STM 
import Control.Concurrent 
import System.Random(randomRIO) 
import Control.Monad(forever, when) 

allCoords :: [(Int,Int)] 
allCoords = [(x,y) | x <- [0..99], y <- [0..99]] 

randomCoords :: IO (Int,Int) 
randomCoords = do 
    x <- randomRIO (0,99) 
    y <- randomRIO (0,99) 
    return (x,y) 

main = do 
    chan <- newTChanIO :: IO (TChan ((Int,Int),Int)) 

    let watcher p = do 
     chan' <- atomically $ dupTChan chan 
     forkIO $ forever $ do 
        r@(p',_counter) <- atomically $ readTChan chan' 
        when (p == p') (print r) 
     return() 

    mapM_ watcher allCoords 

    let go !cnt = do 
     xy <- randomCoords 
     atomically $ writeTChan chan (xy,cnt) 
     go (cnt+1) 

    go 1 

Khi biên soạn (-O) và chạy một cái gì đó chương trình đầu tiên sẽ ra như thế này:

 
./tchantest 
((0,25),341) 
((0,33),523) 
((0,33),654) 
((0,35),196) 
((0,48),181) 
((0,48),446) 
((1,15),676) 
((1,50),260) 
((1,78),561) 
((2,30),622) 
((2,38),383) 
((2,41),365) 
((2,50),596) 
((2,57),194) 
((3,19),259) 
((3,27),344) 
((3,33),65) 
((3,37),124) 
((3,49),109) 
((3,72),91) 
((3,87),637) 
((3,96),14) 
((4,0),34) 
((4,17),390) 
((4,73),381) 
((4,74),217) 
((4,78),150) 
((5,7),476) 
((5,27),207) 
((5,47),197) 
((5,49),543) 
((5,53),641) 
((5,58),175) 
((5,70),497) 
((5,88),421) 
((5,89),617) 
((6,0),15) 
((6,4),322) 
((6,16),661) 
((6,18),405) 
((6,30),526) 
((6,50),183) 
((6,61),528) 
((7,0),74) 
((7,28),479) 
((7,66),418) 
((7,72),318) 
((7,79),101) 
((7,84),462) 
((7,98),669) 
((8,5),126) 
((8,64),113) 
((8,77),154) 
((8,83),265) 
((9,4),253) 
((9,26),220) 
((9,41),255) 
((9,63),51) 
((9,64),229) 
((9,73),621) 
((9,76),384) 
((9,92),569) 
... 

Và sau đó, tại một số điểm, sẽ ngừng viết bất cứ điều gì, trong khi vẫn tiêu thụ 100% cpu.

 
((20,56),186) 
((20,58),558) 
((20,68),277) 
((20,76),102) 
((21,5),396) 
((21,7),84) 

Khi quá trình này bị khóa nhanh hơn và xảy ra chỉ sau một vài dòng. Nó cũng sẽ tiêu thụ bất kỳ số lõi nào được tạo sẵn thông qua cờ RTS '-N.

Ngoài ra, hiệu suất có vẻ kém - chỉ khoảng 100 sự kiện mỗi giây được xử lý.

Đây có phải là lỗi trong STM hoặc tôi có hiểu nhầm điều gì đó về ngữ nghĩa của STM không?

Answer 1

Chương trình sẽ hoạt động khá kém. Bạn đang sinh ra 10.000 đề tài, tất cả chúng sẽ xếp hàng chờ một TVar được ghi vào. Vì vậy, một khi tất cả chúng đều đang diễn ra, bạn có thể nhận được điều này xảy ra:

1. Mỗi 10.000 chủ đề cố gắng đọc từ kênh, tìm thấy nó trống và tự thêm vào hàng đợi cho TV bên dưới. Vì vậy, bạn sẽ có 10.000 sự kiện xếp hàng và 10.000 quy trình trong hàng chờ đợi cho TVar.
2. Nội dung nào đó được ghi vào kênh. Điều này sẽ unqueue mỗi 10.000 chủ đề và đặt nó trở lại trên run-queue (điều này có thể là O (N) hoặc O (1), tùy thuộc vào cách RTS được viết).
3. Mỗi trong số 10.000 chủ đề sau đó phải xử lý mục để xem liệu nó có quan tâm đến nó hay không.

Vì vậy, mỗi mục sẽ gây xử lý O (10.000). Nếu bạn thấy 100 sự kiện mỗi giây, điều đó có nghĩa là mỗi chuỗi yêu cầu khoảng 1 micro giây để thức dậy, đọc một vài TVars, viết thành một và xếp hàng lại. Điều đó không có vẻ quá bất hợp lý. Tuy nhiên, tôi không hiểu tại sao chương trình này sẽ dừng lại hoàn toàn.

Nói chung, tôi sẽ loại bỏ thiết kế này và thay thế nó như sau:

Có một chủ đề duy nhất đọc kênh sự kiện, trong đó duy trì một bản đồ từ phối hợp để quan tâm-thu-kênh. Sau đó, chuỗi đơn có thể chọn (các) người nhận từ bản đồ trong thời gian O (log N) (tốt hơn nhiều so với O (N), và với một yếu tố liên tục nhỏ hơn nhiều), và gửi sự kiện tới người nhận quan tâm . Vì vậy, bạn thực hiện chỉ một hoặc hai thông tin liên lạc cho bên quan tâm, thay vì 10.000 thông tin liên lạc cho tất cả mọi người. Một hình thức dựa trên danh sách của ý tưởng được viết bằng CHP trong phần 5.4 giấy này: http://chplib.files.wordpress.com/2011/05/chp.pdf

Answer 2

Thêm vào những gì Neil nói, mã của bạn cũng có một lỗ thủng không gian (đáng chú ý với nhỏ n): Sau khi sửa chữa các tuple rõ ràng build-up vấn đề by making tuples strict, tôi bị bỏ lại với cấu hình sau: Điều gì đang xảy ra ở đây, tôi nghĩ, đó là chủ đề chính là ghi dữ liệu đến các chia sẻ TChan nhanh hơn so với các chủ đề công nhân có thể đọc nó (TChan, như Chan, là không bị chặn). Vì vậy, các chủ đề công nhân spend most of their time reexecuting các giao dịch STM tương ứng của họ, trong khi chủ đề chính bận rộn nhồi nhiều dữ liệu hơn vào kênh; điều này giải thích tại sao chương trình của bạn bị treo.

Answer 3

Đây là một trường hợp thử nghiệm tuyệt vời! Tôi nghĩ rằng bạn đã thực sự tạo ra một trường hợp hiếm hoi của livelock/nạn đói chính hãng. Chúng tôi có thể kiểm tra điều này bằng cách biên dịch với -eventlog và chạy với -vst hoặc bằng cách biên dịch với -debug và chạy với -Ds. Chúng tôi thấy rằng ngay cả khi chương trình "treo" thời gian chạy vẫn hoạt động như điên, nhảy giữa các chủ đề bị chặn.

Lý do cấp cao là bạn có một nhà văn (nhanh) và nhiều người đọc (nhanh). Các độc giả và nhà văn cả hai cần truy cập cùng một tvar đại diện cho kết thúc của hàng đợi. Giả sử rằng một chuỗi không thành công một cách thành công và tất cả các chuỗi khác đều thất bại khi điều này xảy ra. Bây giờ, khi chúng ta tăng số lượng các chủ đề trong tranh chấp lên 100 * 100, thì xác suất của người đọc tiến bộ nhanh chóng tiến tới không. Trong khi chờ đợi, người viết thực tế mất dài hơn trong quyền truy cập vào truyền hình đó so với người đọc, điều đó khiến mọi thứ trở nên tồi tệ hơn.

Trong trường hợp này, đặt một ga nhỏ giữa mỗi lần gọi go cho người viết (ví dụ: threadDelay 100) là đủ để khắc phục sự cố. Nó cung cấp cho độc giả đủ thời gian để tất cả các khối giữa viết liền, và do đó loại bỏ các livelock. Tuy nhiên, tôi do nghĩ rằng đó sẽ là một vấn đề thú vị để cải thiện hành vi của trình lập lịch trình thời gian chạy để xử lý các tình huống như thế này.