Ktor默认池

Question

关于Ktor池实现，可以有人解释pop和push实现背后的概念。我试着逐步完成代码，但在研究了代码之后，我仍然不太明智。

下面是我很难理解的代码片段：

   private fun pushTop(index: Int) {
    require(index > 0) { "index should be positive" }
    while (true) { // lock-free loop on top
        val top = this.top // volatile read
        val topVersion = (top shr 32 and 0xffffffffL) + 1L 
        val topIndex = (top and 0xffffffffL).toInt() 
        val newTop = topVersion shl 32 or index.toLong() 
        next[index] = topIndex
        if (Top.compareAndSet(this, top, newTop)) return
    }
}

private fun popTop(): Int {
    // lock-free loop on top
    while (true) {
        // volatile read
        val top = this.top
        if (top == 0L) return 0
        val newVersion = (top shr 32 and 0xffffffffL) + 1L
        val topIndex = (top and 0xffffffffL).toInt()
        if (topIndex == 0) return 0
        val next = next[topIndex]
        val newTop = newVersion shl 32 or next.toLong()
        if (Top.compareAndSet(this, top, newTop)) return topIndex
    }
}

这能写得更简单吗？

Answer 1

有两件事使这段代码看起来有点不寻常。第一种是它被设计成不需要使用锁就可以被多个线程访问。第二种方法是使用单个64位值来存储两个32位整数。

锁自由度

这看起来像是无锁堆栈上的一些变化。它被设计成同时被多个线程访问。粗算法的工作原理如下：

• 得到旧的价值并记下来
• 确定新的值应该是什么
• 执行原子比较和设置来替换值当且仅当该值仍然与我们在开头看到的旧值相匹配时。
• 如果比较集失败(即当我们计算新值时，其他人更改了值)，则循环回开始，然后再试一次。

在某些类型的应用程序中，这样的无锁算法在性能上可能更好。另一种方法是锁定整个堆栈，以便在一个线程使用堆栈时，所有其他线程都必须等待。

位移位

使这段代码看起来更复杂的另一件事是，它似乎将两个值存储在一个变量中。传递给index的pushTop值是32位整数.然后，在存储之前，它将与32位递增计数器( version )结合起来.因此，top实际上是一个64位值，其中前32位是“版本”，最后32位是我们传入的“索引”。同样，这种紧凑的存储格式可能是性能优化。

如果我们在pushTop的代码中添加一些注释，如下所示：

val top = this.top // get the current 64-bit value containing 'version' and 'index'
val topVersion = (top shr 32 and 0xffffffffL) + 1L  // get the 32 high bits (version) and add 1
val topIndex = (top and 0xffffffffL).toInt() // get the 32 low bits (the old index)
val newTop = topVersion shl 32 or index.toLong() // combine version and new index to a new 64-bit value

您可以在popTop中看到很多相同的事情发生。如果堆栈包含重复项，则可能包含版本号，以便无锁算法能够区分相同值的不同副本之间的差异。