Con referencia a la implementación de Ktor Pool , que alguien explique el concepto detrás de esta implementación de pop y push. Traté de recorrer el código, pero aún no soy más sabio después de estudiar el código.
A continuación se muestra el fragmento de código que me cuesta entender:
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 } }¿Se puede escribir esto de una forma más sencilla?
Hay dos cosas que hacen que este código parezca un poco inusual. La primera es que está diseñado para ser accedido por múltiples subprocesos sin usar bloqueos. La segunda es que usa un solo valor de 64 bits para almacenar dos números enteros de 32 bits.
Esto parece una variación de una pila sin bloqueo . Está diseñado para ser accedido por múltiples subprocesos al mismo tiempo. El algoritmo aproximado funciona así:
Los algoritmos sin bloqueo como este pueden ser preferibles para el rendimiento en algunos tipos de aplicaciones. La alternativa sería bloquear toda la pila para que mientras un subproceso esté usando la pila, todos los demás subprocesos tengan que esperar.
La otra cosa que hace que este código parezca más complicado es que parece estar almacenando dos valores en una sola variable. El valor de index pasado a pushTop es un número entero de 32 bits. Luego se combina con un contador incremental de 32 bits, version , antes de almacenarse. Entonces, top es en realidad un valor de 64 bits donde los primeros 32 bits son la 'versión' y los últimos 32 bits son el 'índice' que pasamos. Nuevamente, este formato de almacenamiento compacto es probablemente una optimización del rendimiento.
Si agregamos algunos comentarios al código de pushTop , se ve así:
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 Puede ver que ocurre lo mismo en popTop . Es probable que se incluya el número de versión para que el algoritmo sin bloqueo pueda diferenciar entre diferentes copias del mismo valor, si la pila contiene duplicados.