哪个默认池

Question

参考 Ktor Pool implementation，有人可以解释一下这个 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 位整数。

锁定自由

这看起来像是 lock-free stack 的一些变体。它被设计为同时被多个线程访问。大致的算法是这样的：

获取旧值并记录下来
确定新值应该是什么
当且仅当 value 仍然匹配我们在开始时看到的旧值
如果比较并设置失败（即在我们计算新值时其他人更改了值），循环回到开始并重试

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

移位

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

如果我们在 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 中看到很多相同的事情发生。如果堆栈包含重复项，则可能包含版本号，以便无锁算法可以区分同一值的不同副本之间的区别。

哪个默认池

Ktor Default pool

kotlin

pool

ktor

锁定自由

移位