C++中是否有任何线程安全的图形库？

基本上我正在寻找一个图形库，它可以对图形操作进行细密的锁定，以便不同的线程可以同时触及图形的不同部分，并且可以阻止竞争性修改。C++中是否有任何线程安全的图形库？

我搜索了一下，找不到任何东西。也许这对我的需求太具体，但我会想象会有大量的科学应用程序可以在大图上工作。

2009-12-21 drpepper

这里的“图”是计算机科学的抽象东西，还是另一个词的“情节”？ – dmckee 2009-12-21 17:36:34

http://en.wikipedia.org/wiki/Graph_%28mathematics%29 – Yacoby 2009-12-21 17:44:45

@Yacoby：是的，我知道。但该标签还包括像http://stackoverflow.com/questions/1879964/plotting-cartesian-plots-axis-inside-the-figure-possible-annotations和http://stackoverflow.com/questions/1878368/something -to-use-for-graphing-numbers是关于http://en.wikipedia.org/wiki/Graph_of_a_function。 O这是海报的意思吗？ – dmckee 2009-12-21 17:47:37

假设你问关于图的数学实体（例如，GraphBase处理的图的类型） - 那么我认为你不会找到你要找的东西，至少在通用库中。

问题是，“线程安全”在所有上下文中都不是一个明确定义的术语 - 至少它可能意味着程序可能不会在多线程并发处理时爆炸 - 但超出这个要求，即使是像“容易安全”的容器或算法这样的东西，也会有一些额外的语义关于这意味着什么 - 而且通用图库更加复杂，并且需要更加精确的（和可配置的）语义来满足这一点。

例如（简单对象这里讲的 - 比如一个容器）：

并发读访问允许在同一个对象？是否允许对同一个对象进行并发写入访问？读者是否阻止读者？读者是否会阻止作家？做作家阻止作家？更一般地说，什么操作会阻止其他操作？

尽管您可以为简单容器定义合理的语义 - 就像一个并发集合 - 即使您移动到类似地图的地方，您也需要引入像“putIfAbsent”这样的复合操作，以弥补许多应用程序需要超过线程安全 - 他们需要将通常在不同调用（搜索，然后添加）中执行的操作链接到逻辑原子操作中。

我怀疑像图库一样，这个问题变得尖锐起来。您的应用程序需要定义哪些操作可以并行进行 - 哪些操作应该阻止其他操作，无论您是否需要获取图形的一致快照，是否需要图形上操作的完全可串行化，或者是否需要放宽模型是适当的，所以它。

我很难将所有这种通用性建立到图库中，并且也许不可能提前预测实际需求在线程安全性方面的情况（以上只是可能考虑的一小部分），所以我怀疑大多数图形库只会提供有关行为的弱保证（例如，允许并发读取访问）或根本没有明确的安全性，并期望库的使用者在顶层构建更高级别的同步构造。

另一个原因可能是高性能库只能在线程不安全的版本中找到，是为了避免惩罚不需要这种安全性的客户（这可能对大多数给定类的大多数实例而言） - 假设该线程安全性可以由需要它的人在外部添加，但反向转换（移除线程安全性）通常是不可能的。 Java一直在走这条道路，有些早期的线程安全类，如Vector支持ArrayList和StringBuffer与StringBuilder的有效弃用。

另一方面，客户可以以有效的方式在外部向容器添加线程安全性（无法访问内部部件）的假设通常是不正确的 - 这是构建自组合的基础并发包中的线程安全容器。然而，我很怀疑你会在C++中找到与图表操作等价的东西。

更新：鉴于其他答复，我想我应该强调，我不认为你会发现单线程库的一般线程安全扩展 - 但显然有几个显式并行线程库，虽然我怀疑这些实现了更高级别的语义，并在内部执行并行性，而不是面向线程安全的单个图形操作操作。

来源

2009-12-21 21:02:00 BeeOnRope

我明白你的意思了。也许将图显式分割成多个部分并将每个线程单词放在一个部分中会更容易。然后，只有当操作涉及两个部分之间的边界或顶点时，才需要唯一的锁定。我对这个想法的担忧是图表的某些部分可能比其他部分更有趣，这会使一些线程空转。 – drpepper 2009-12-22 13:04:59

您提到的问题在并行算法中很常见，在该算法中，您对工作集进行分区，并且集中的不同分区可能需要大量不同的处理时间，并且确定此时间不可行。我将在下面描述两个（类似的）策略。 – BeeOnRope 2009-12-23 00:21:59

一种策略是将工作集划分为比工作人员更多的部分 - 因此，如果您决定4名工人，则创建20个部分，这会增加作品执行类似工作量的机会（因为一名工作人员可以完成17个工作“无趣的部分”）。然而，很难确定最佳的分区数量。您可以创建的分区数量也可能存在实际限制。 – BeeOnRope 2009-12-23 00:22:44

你可能想看看Parallel Boost Graph Library（也可能是MultiThreaded Graph Library）。我还没有使用过自己，只是偶然发现它们，同时将并行机制作为加速某些BGL代码的选项。（啊...它看起来像Parallel-BGL现在正式in boost！有一个很好的architectural overview，但也许他们的“分布图”的概念是相当粗糙的比你想的）。

来源

2009-12-21 21:29:34 timday

感谢您的链接。并行BGL看起来非常好，但似乎更多的是在没有共享内存的多处理器上进行并行计算。在我的情况下，我认为这将是矫枉过正。至于MTGL，它看起来相当未完成。他们不断提及他们必须稳定他们的“基本API”！但我会密切关注它。 – drpepper 2009-12-22 13:00:30

不幸的是，细粒度锁定的代价可能高于多线程的加速。更不用说死锁的风险，当你的互斥体数量非常少时，锁定管理变得更加困难。

来源

2009-12-21 22:18:29

C++中是否有任何线程安全的图形库？

回答

相关问题