10

原来的问题

我是 STM 的新手。我想在 Haskell 中做的一件事涉及一大块数据，以及大量轻量级线程读取和写入所述大块数据的一小部分。读取和写入的位置基本上可以认为是随机的和小的。STM 似乎很适合这个，但我对如何解决这个问题有一些疑问。我看到了几种可能的方法，每种方法都有一些缺点，有些看起来很愚蠢。对这些或其他替代方案的一些评论将不胜感激。

为简单起见，我们假设大数据是 a Data.Vector a，其中元素本身很小。

  1. 整条数据为一个TVar (Vector a)。我想这会导致大量数据的大量复制，因为 STM 会认为每个单独的写入都可能影响整个共享数据。当然，STM 识别出读取和写入非常本地化，并且不需要跨大数据的一致性的地方没有魔法？

  2. 大量的TVar as，基本上每个元素一个，提供完全本地化的 STM，但基本上复制了整个Vector a. 这似乎很愚蠢。

  3. 通过对数据进行分段，在 1 和 2 之间进行折衷，以便我有合理数量的TVar (Vector a)s 对应于数据的子向量。我觉得这个解决方案过于依赖启发式方法，比如分段应该有多大。

  4. 消息传递。不是每个工作人员都使用 STM 读取和写入数据，而是每个工作人员都通过一些STM 机制（例如TChan. 一个特殊的线程接收这些消息，通过另一个线程传递请求的数据TChan，或者获取接收到的数据并将其写入共享数据结构。这个解决方案似乎没有困扰解决方案 1-3 的问题，但在我看来，它基本上放弃了使用 STM 的细节来保持数据一致。相反，它只是消息传递。当然，消息传递部分是用 STM 实现的，但我真正的问题是通过消息传递解决的。STM 看起来太棒了，消息传递太……嗯。

我是否正确地考虑了这一点？有人有任何提示或其他建议吗？

请记住，我没有使用 STM 的经验，也没有尝试过上述解决方案。我会从扶手椅上站起来，但有时在尝试任何事情之前考虑这些事情可能会很好。

附录：第五种方法来自 Nathan Howell，并使用TArray. 这听起来像我想要的，但文档说：

它目前以 Array ix (TVar e) 的形式实现，但将来可能会被更高效的实现所取代（但接口将保持不变）。

我认为这意味着这TArray只是我穿着更好衣服的方法 2。暗示“更有效”实现的文档很有趣，因为它暗示实际上存在更好的方法。

跟进 Vagif Verdi 的回答

Vagif Verdi 的回答很有趣，所以我做了一个小实验来尝试一下。我现在没有时间精简代码，因此对此感兴趣的人将不得不忍受我的代码，而不仅仅是包含基本要素。我决定使用 10^8Int的可变向量作为“大共享数据”，并让多个读取器/写入器对应于网络套接字上的线程。

请注意，代码甚至不读取或写入共享数据块。它就在那里，每个线程都有一个TVar。

那么会发生什么？我运行该程序，它立即占用了大约 780 MB 的 RAM，这是意料之中的（这大约是 10^8 Ints 所需要的）。现在，如果我使用 netcat 连接几个客户端并编写一些文本，程序只是应该打印出来，甚至不写入共享数据，那么进程的 CPU 使用率会在一秒以上的时间内飙升至 100% ！在显示文本之前有明显的延迟。从好的方面来说，内存使用量保持不变（根据 Vagif Verdi 的回答）。如果我删除向量和TVar，即取出所有 STM 和共享数据，一切都非常快速且响应迅速，并且每当客户端写入内容时都没有明显的 CPU 使用率。

因此，虽然很高兴看到共享数据实际上没有重复（尽管我想我应该实际写入共享数据以完全验证这一点），但维护一致状态会带来非常严重的性能损失。对我来说，我的问题仍然存在：如何在保持 STM 优点的同时正确解决这个问题？

感谢 Vagif Verdi 提出了一些非常有趣的观点。

4

3 回答 3

6

STM 不是魔法。如果您有一个巨人TVar，则必须在任何给定时间阻止除一个之外的所有线程。这相当于“粗粒度锁定”，并且具有易于使用的优点，但 STM 的重点是不要被迫使用粗粒度锁定。使用这种方法，一次只有一个线程可以有效地写入。您的“消息传递”系统也是如此——一个线程是限制可伸缩性的瓶颈。

我认为使用 s 数组没有什么大问题，TVar我不知道您为什么将方法 2 描述为“愚蠢”。这正是 STM 的发明目的。

编辑：我鼓励感兴趣的各方观看这个视频，或者至少是它的开头，以讨论 STM 的一些动机。它已经有几年历史了，关于事务提升的东西并不真正相关，但 Herlihy 很聪明，他是计算机科学家之一，他设法让一个领域变得有趣，即使这不是你的事。

于 2012-03-10T11:27:27.223 回答
3

首先，Vector是一个不可变的数据结构。每当您“修改” 时Vector，您都在创建它的全新副本，这意味着每次修改都需要 O(n) 时间（其中 n 是向量的长度）。

其次，Haskell 中的值是不可变的。每次修改 aTVar时，都会用新值替换旧值。

我认为你想要的是一个支持高效更新的纯函数式数据结构。两个例子：

  • Data.Map：键值字典。这就像std::map在 C++ 中一样。

  • Data.Sequence：像一个可变数组，但更好。

每当您“修改”其中一个数据结构时，实际上都是在构建一个新值，该值在内部指向旧值的一部分。

几个准则：

  • 如果您只修改一个值，atomicModifyIORef可能就足够了。如果除了原子更新之外还需要更复杂的同步，那STM将是一个更好的选择。

  • 使用可变变量时要注意惰性。任何时候你修改共享状态，一定要强制它。这可以使用seq. 更方便的方法是使用bang patterns。例子：

    !x <- atomically $ do
    x <- readTVar shared_state
    writeTVar shared_state (changeSomething x)
    return x

    这将强制x在事务完成后进行评估。如果一个变量（IORef, STRef, TVar, 等）被修改了很多次但从未被强制修改，thunk 将堆积在内存中。评估产生的 thunk 甚至可能产生堆栈溢出。

如果您的程序需要大规模并行（即，让多个内核/CPU 同时访问该变量），那么像这样更新单个值的效率可能会降低，因为计算可能会在处理器之间重复。然而，对于少数核心，重复是非常罕见的。

于 2012-03-10T12:45:18.980 回答
1

Haskell 有几种可变数组/向量的实现。因此，您可以使用最简单的方法 TVar (Vector a) 而不必担心复制开销（可变数组中没有复制）

这是一个这样的库：http ://hackage.haskell.org/package/vector-0.9.1

于 2012-03-03T19:16:46.613 回答