Câu hỏi Haskell: Nguyên tắc cấu trúc dữ liệu đồng thời


Tôi đã cố gắng tìm hiểu về đồng thời, và tôi đã cố gắng tìm ra cái gì tốt hơn, một cái lớn IORef khóa hoặc nhiều TVarS. Tôi đã đi đến các hướng dẫn sau đây, ý kiến ​​sẽ được đánh giá cao, liên quan đến việc đây là gần đúng hay tôi đã bỏ lỡ điểm.


Giả sử cấu trúc dữ liệu đồng thời của chúng ta là một bản đồ m, được truy cập như m[i]. Cũng cho phép chúng ta có hai hàm, f_easy và f_hard. Các f_easy nhanh, f_hard mất một thời gian dài. Chúng tôi sẽ giả định các đối số f_easy/f_hard là yếu tố của m.

(1) Nếu giao dịch của bạn trông gần như thế này m[f_easy(...)] = f_hard(...), sử dụng IORef với atomicModifyIORef. Sự lười biếng sẽ đảm bảo rằng m chỉ bị khóa trong một thời gian ngắn vì nó được cập nhật với một đoạn. Tính toán chỉ mục khóa cấu trúc một cách hiệu quả (như một cái gì đó sẽ được cập nhật, nhưng chúng ta chưa biết cái gì), nhưng một khi nó được biết phần tử đó là gì, thì thunk trên toàn bộ cấu trúc sẽ di chuyển đến một phần tử chỉ trên phần tử cụ thể đó , và sau đó chỉ có yếu tố cụ thể đó là "bị khóa".

(2) Nếu giao dịch của bạn trông gần như thế này m[f_hard(...)] = f_easy(...)và không xung đột quá nhiều, sử dụng rất nhiều TVarS. Sử dụng một IORef trong trường hợp này sẽ có hiệu quả làm cho các ứng dụng đơn luồng, vì bạn không thể tính toán hai chỉ mục cùng một lúc (vì sẽ có một thunk chưa được giải quyết trên toàn bộ cấu trúc). TVars cho phép bạn làm việc cùng lúc hai chỉ mục, tuy nhiên, số âm là nếu hai giao dịch đồng thời đều truy cập cùng một phần tử, và một trong số chúng là ghi, thì một giao dịch phải được loại bỏ, sẽ lãng phí thời gian (có thể là được sử dụng ở nơi khác). Nếu điều này xảy ra rất nhiều, bạn có thể tốt hơn với ổ khóa đến (thông qua blackholing) từ IORef, nhưng nếu nó không xảy ra nhiều, bạn sẽ có được sự tương đương tốt hơn với TVarS.

Về cơ bản trong trường hợp (2), với IORef bạn có thể nhận được hiệu quả 100% (không lãng phí công việc) nhưng chỉ sử dụng 1,1 chủ đề, nhưng với TVar nếu bạn có số lượng xung đột thấp, bạn có thể nhận được hiệu quả 80% nhưng sử dụng 10 luồng, vì vậy bạn vẫn nhanh hơn gấp 7 lần ngay cả với công việc bị lãng phí.


7
2018-04-19 01:56


gốc


Có câu hỏi nào ở đây không? Và tôi ngạc nhiên MVar hoàn toàn vắng mặt. - Louis Wasserman
Một cách khác để có được các biến "an toàn" sau đó có nhiều luồng là sử dụng các kênh (haskell.org/ghc/docs/latest/html/libraries/base/…) và có một chuỗi giám sát tất cả các giá trị và các chủ đề khác phải liên hệ với chuỗi đó để nhận được giá trị - nist


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


Hướng dẫn của bạn hơi giống với kết quả của [1] (Phần 6), nơi phân tích hiệu suất của Haskell STM:

"Đặc biệt, đối với các chương trình không thực hiện nhiều công việc bên trong các giao dịch, chi phí cam kết dường như rất cao. Để tiếp tục quan sát chi phí này, cần phải tiến hành phân tích về hiệu suất của ngũ cốc và hạt mịn Cơ chế khóa STM. "

tôi sử dụng atomicModifyIORef hoặc một MVar khi tất cả các đồng bộ hóa tôi cần là một cái gì đó mà khóa đơn giản sẽ đảm bảo. Khi xem xét việc truy cập đồng thời vào một cấu trúc dữ liệu, nó cũng phụ thuộc vào cách cấu trúc dữ liệu này được thực hiện như thế nào. Ví dụ: nếu bạn lưu trữ dữ liệu của mình bên trong một IORef Data.Map và thường xuyên thực hiện truy cập đọc / ghi sau đó tôi nghĩ atmoicModifyIORef sẽ làm suy giảm hiệu suất của một chuỗi, như bạn đã phỏng đoán, nhưng điều này cũng đúng với một TVar Data.Map. Quan điểm của tôi là điều quan trọng là sử dụng một cấu trúc dữ liệu phù hợp cho lập trình đồng thời (cây cân bằng không).

Điều đó nói rằng, theo ý kiến ​​của tôi, đối số chiến thắng khi sử dụng STM là tính tổng hợp: bạn có thể kết hợp nhiều thao tác thành một giao dịch đơn lẻ mà không bị đau đầu. Nói chung, điều này là không thể sử dụng IORef hoặc là MVar mà không giới thiệu ổ khóa mới.

[1] Các giới hạn của bộ nhớ giao dịch phần mềm (STM): phân tích các ứng dụng Haskell STM trên môi trường nhiều lõi. http://dx.doi.org/10.1145/1366230.1366241

Trả lời cho bình luận của @ Clinton:

Nếu một Độc thân  IORef chứa đựng tất cả các dữ liệu của bạn, bạn chỉ cần sử dụng atomicModifyIORef cho bố cục. Nhưng nếu bạn cần xử lý nhiều yêu cầu đọc / ghi song song với dữ liệu đó, việc mất hiệu suất có thể trở nên đáng kể, vì mỗi cặp các yêu cầu đọc / ghi song song với dữ liệu đó có thể gây ra xung đột.

Cách tiếp cận mà tôi sẽ thử là sử dụng cấu trúc dữ liệu nơi các mục nhập được lưu trữ bên trong một TVar (vs đưa toàn bộ cấu trúc dữ liệu vào một TVar). Điều đó sẽ làm giảm khả năng của livelocks, vì các giao dịch sẽ không xung đột thường xuyên.

Tất nhiên, bạn vẫn muốn giữ các giao dịch của mình càng nhỏ càng tốt và chỉ sử dụng khả năng tổng hợp nếu nó hoàn toàn cần thiết để đảm bảo tính nhất quán. Cho đến nay tôi đã không gặp phải một kịch bản mà kết hợp nhiều hơn một vài hoạt động chèn / tra cứu vào một giao dịch duy nhất là cần thiết.


5
2018-04-19 02:45



Peter: Tôi nghĩ vấn đề với TVar là khả năng kết hợp? Bạn luôn có thể soạn nhiều thao tác bằng cách sử dụng atomicModifyIORef cách tiếp cận (nếu IORef đó chứa tất cả dữ liệu của bạn). Sử dụng TVarMặc dù, nếu bạn có giao dịch TA1, TA2, ... chạy mỗi giây và mỗi lần tăng X, và giao dịch T2 đọc X, và sau đó làm việc trong 2 giây trước khi viết một cái gì đó, T2 không bao giờ hoàn thành. Bạn không thể soạn TA1, ... và T2 bằng cách sử dụng TVarS. Bạn có thể ngăn chặn livelock bằng cách ưu tiên giao dịch dựa trên thời gian tạo, nhưng TVar dường như không làm điều này. - Clinton
@ Clinton: Tôi đã thêm một câu trả lời cho bình luận của bạn. - Peter


Ngoài hiệu suất, tôi thấy một lý do cơ bản hơn để sử dụng TVar- Hệ thống kiểu đảm bảo bạn không thực hiện bất kỳ thao tác "không an toàn" nào như readIORef hoặc là writeIORef. Dữ liệu của bạn được chia sẻ là thuộc tính của loại, không phải của việc triển khai. CHỈNH SỬA: unsafePerformIO luôn luôn là không an toàn. readIORef chỉ là không an toàn nếu bạn cũng đang sử dụng atomicModifyIORef. Ít nhất là bọc IORef của bạn trong một loại mới và chỉ phơi bày một gói atomicModifyIORef

Ngoài ra, không sử dụng IORef, sử dụng MVar hoặc là TVar

  1. Mẫu sử dụng đầu tiên mà bạn mô tả có thể không có đặc điểm hiệu suất tốt. Bạn có thể kết thúc (gần như) hoàn toàn đơn luồng - vì lười biếng không có công việc thực tế xảy ra mỗi khi bạn cập nhật trạng thái được chia sẻ, nhưng bất cứ khi nào bạn cần sử dụng trạng thái chia sẻ này, toàn bộ đống khối tích lũy cần phải bị buộc và có cấu trúc phụ thuộc dữ liệu tuyến tính.
  2. Có hiệu quả 80% nhưng song song cao hơn đáng kể cho phép bạn khai thác số lượng lõi ngày càng tăng. Bạn có thể mong đợi những cải thiện hiệu suất tối thiểu trong những năm tới trên mã chuỗi đơn.
  3. Nhiều từ CAS có khả năng đến một bộ xử lý gần bạn dưới dạng "Bộ nhớ giao dịch phần cứng" cho phép các STM trở nên hiệu quả hơn nhiều.
  4. Mã của bạn sẽ có nhiều mô-đun hơn - mọi đoạn mã phải được thay đổi nếu bạn thêm nhiều trạng thái được chia sẻ hơn khi thiết kế của bạn có tất cả trạng thái được chia sẻ sau một tham chiếu duy nhất. TVars Và ở một mức độ thấp hơn MVars hỗ trợ mô đun tự nhiên.

1
2018-04-19 02:39



Về các hoạt động "không an toàn", luôn có các hoạt động không an toàn, ví dụ: "performUnsafeIO". Nó chỉ là một hoạt động không an toàn khác mà chúng ta biết để tránh trừ khi chúng ta thực sự cẩn thận. - Clinton
Bạn dùng như thế nào MVar? Bằng cách gọi liên tục takeMVar và putMVar? Điều đó không giống với việc sử dụng IORef và atomicModifyIORef dù sao? - Clinton
1. Bạn có thể dễ dàng ngã ba công việc song song, không cần phải chờ đợi cho những thunks buộc phải. tôi tin TVars cũng lười biếng, bạn sẽ không nhận được cùng một vấn đề? - Clinton
Nỗi sợ tôi có TVar là livelock. Cụ thể là tất cả các giao dịch phải mất ít thời gian hơn để hoàn thành hơn khoảng cách tối đa giữa các xung đột với giao dịch đó. Nếu có một giao dịch T1 chạy mỗi giây chạm X, và một giao dịch T2 khác mà đọc X mất 2 giây để hoàn thành, T2 sẽ không bao giờ hoàn thành. Hệ thống kiểu không bảo vệ chống lại điều này. Mã có thể thất bại ngẫu nhiên tùy thuộc vào các mẫu sử dụng. Điều này khó tránh khỏi hơn là không sử dụng "readIORef" và "writeIORef". - Clinton
mặc dù về nguyên tắc livelock là một vấn đề, tôi không chắc chắn nếu có ai có bất kỳ bằng chứng của nó thực sự gây ra các loại vấn đề bạn mô tả với STM hiện tại. Cũng có thể thực hiện STM để đảm bảo mức độ công bằng. - Philip JF