为什么ConcurrentWhatever.Count拍摄快照

Question

在关于ConcurrentStack/Concurrent Queue的C#/.NET Little Wonders文章中,提到了关于以下.Count操作的以下内容ConcurrentStack:

Count获取堆栈的快照,然后计算项目.这意味着它是O(n)操作,如果您只想检查空堆栈,请调用IsEmpty而不是O(1).

我在多线程编程方面还不是很有经验,但我明白为什么你不能只是遍历集合中的项目并对它们进行计数,因为集合可能同时被其他线程更改.但是,如果您必须锁定 ConcurrentStack足够长的时间来制作快照,那么只要在锁定项目时对项目进行计数就不会更容易,返回该计数并释放锁定,而不是花费开销和时间成本在释放锁之前生成整个快照？

我可能会遗漏一些关于它是如何工作的基本知识,我将不胜感激您的任何想法或见解.

Answer 1

我不知道它是否像这样实现,但是如果你将它实现为具有不可变节点的单链表,则快照几乎是免费的,不需要锁定.你只需要获得当前的顶级元素.然后按照链接列表开头.

您可以将每个节点的位置保存在节点的堆栈上,但这样可以交换内存以获得性能Count.并且可能通常不会调用count来保证每个节点有额外的内存.

大多数ConcurrentCollection都没有锁定.例如,可以Interlocked.CompareExchange在指向当前节点的字段上构建这种链表列表支持的堆栈.如果你使一些操作无锁,你通常需要使所有这些操作无锁,因为无锁操作不会受到锁定.

Answer 2

我不确定，但这是一个猜测。

堆栈可以实现为单链表，由不可变单元组成，其中每个单元都指向堆栈上其下方的单元。那么“快照”就只是制作堆栈顶部的副本；因为单元格是不可变的，所以这也会拉动当前堆栈的其余部分。

因此，快照将是一个 O(1) 操作，但计算实际项目仍然是 O(n)。