{"action":"created","issue":{"url":"https://api.github.com/repos/scalaz/scalaz-zio/issues/35","repository_url":"https://api.github.com/repos/scalaz/scalaz-zio","labels_url":"https://api.github.com/repos/scalaz/scalaz-zio/issues/35/labels{/name}","comments_url":"https://api.github.com/repos/scalaz/scalaz-zio/issues/35/comments","events_url":"https://api.github.com/repos/scalaz/scalaz-zio/issues/35/events","html_url":"https://github.com/scalaz/scalaz-zio/issues/35","id":331423959,"node_id":"MDU6SXNzdWUzMzE0MjM5NTk=","number":35,"title":"Implement a high-performance ring buffer for RTS built using CAS primitives.","user":{"login":"jdegoes","id":156745,"node_id":"MDQ6VXNlcjE1Njc0NQ==","avatar_url":"https://avatars1.githubusercontent.com/u/156745?v=4","gravatar_id":"","url":"https://api.github.com/users/jdegoes","html_url":"https://github.com/jdegoes","followers_url":"https://api.github.com/users/jdegoes/followers","following_url":"https://api.github.com/users/jdegoes/following{/other_user}","gists_url":"https://api.github.com/users/jdegoes/gists{/gist_id}","starred_url":"https://api.github.com/users/jdegoes/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jdegoes/subscriptions","organizations_url":"https://api.github.com/users/jdegoes/orgs","repos_url":"https://api.github.com/users/jdegoes/repos","events_url":"https://api.github.com/users/jdegoes/events{/privacy}","received_events_url":"https://api.github.com/users/jdegoes/received_events","type":"User","site_admin":false},"labels":[{"id":938355728,"node_id":"MDU6TGFiZWw5MzgzNTU3Mjg=","url":"https://api.github.com/repos/scalaz/scalaz-zio/labels/help%20wanted","name":"help wanted","color":"008672","default":true}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":3,"created_at":"2018-06-12T03:26:10Z","updated_at":"2018-08-22T15:37:44Z","closed_at":null,"author_association":"MEMBER","body":"The ring buffer must provide support for a limited number of readers (equal to thread count), and potentially a higher number of writers. That is, many places in the code will add work to the queue, but few will read them. \r\n\r\nIn addition, metrics are important to create good preemption. Metrics on how many ops per second, metrics on how many work units per queue, and so forth, can all be good to feed into an algorithm that decides whether or not a current thread should cooperatively yield to another fiber."},"comment":{"url":"https://api.github.com/repos/scalaz/scalaz-zio/issues/comments/415077025","html_url":"https://github.com/scalaz/scalaz-zio/issues/35#issuecomment-415077025","issue_url":"https://api.github.com/repos/scalaz/scalaz-zio/issues/35","id":415077025,"node_id":"MDEyOklzc3VlQ29tbWVudDQxNTA3NzAyNQ==","user":{"login":"artempyanykh","id":2338443,"node_id":"MDQ6VXNlcjIzMzg0NDM=","avatar_url":"https://avatars0.githubusercontent.com/u/2338443?v=4","gravatar_id":"","url":"https://api.github.com/users/artempyanykh","html_url":"https://github.com/artempyanykh","followers_url":"https://api.github.com/users/artempyanykh/followers","following_url":"https://api.github.com/users/artempyanykh/following{/other_user}","gists_url":"https://api.github.com/users/artempyanykh/gists{/gist_id}","starred_url":"https://api.github.com/users/artempyanykh/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/artempyanykh/subscriptions","organizations_url":"https://api.github.com/users/artempyanykh/orgs","repos_url":"https://api.github.com/users/artempyanykh/repos","events_url":"https://api.github.com/users/artempyanykh/events{/privacy}","received_events_url":"https://api.github.com/users/artempyanykh/received_events","type":"User","site_admin":false},"created_at":"2018-08-22T15:37:44Z","updated_at":"2018-08-22T15:37:44Z","author_association":"CONTRIBUTOR","body":"I did some additional reading and research on the subject. Below are some of my current thoughts.\r\n\r\n**TL;DR**\r\n\r\nThe interface for a ring buffer:\r\n\r\n```scala\r\nabstract class MPMCQueue(requestedCapacity: Int) {\r\n  val capacity: Int\r\n  def relaxedSize(): Int // not sure if we need accurate size, probably some lag (+/-1) is acceptable\r\n  def processedCount(): Long\r\n\r\n  def offer(a: A): Boolean\r\n\r\n  def unsafePoll(): B // returns null when queue empty\r\n  def poll(): Option[B] = Option(unsafePoll())\r\n}\r\n```\r\n\r\nRough plan:\r\n\r\n1. Write a straightforward but correct implementation based on \"[A Portable Lock-Free Bounded Queue](http://pirkelbauer.com/papers/icapp16.pdf)\".\r\n2. Write benchmarks and establish baseline performance. Measuring performance here could be a bit tricky since interesting benchmarks needs to be multithreaded, asynchronous and the system should be in a stable state during the iteration.\r\n3. Iteratively optimize performance. Things to consider here:\r\n    1. Using `null`s instead of Options for better performance.\r\n    2. Padding fields to avoid false sharing.\r\n    3. Using a power of two capacity to make index calculations faster.\r\n    4. ???\r\n\r\n**Details**\r\n\r\nThere are a couple approaches to designing a lock-free concurrent queue (CoralQueue, LMAX, JCTools, etc.). One difference is in the way elements are added to the queue.\r\n\r\nFirst approach (LMAX, CoralQueue) looks like this:\r\n\r\n```scala\r\nabstract class RingBuffer[A](val size: Int) {\r\n  def nextSequence(): Option[Long]\r\n  def publish(seq: Long): Unit\r\n  def poll(): Option[A]\r\n}\r\nval q = new RingBuffer(???) {...}\r\n\r\n// Thread 1\r\nval reservedSlot = q.nextSequence().get // ignore that queue could be full and we'd need to retry\r\nval el = ...\r\nq(reservedSlot) = el\r\nq.publish(reservedSlot)\r\n\r\n// Thread 2\r\nval nextElOpt = q.poll()\r\n```\r\n\r\nThe phases are: reserve a place in the queue, put an element in the queue and publish it when ready.\r\n\r\nThe big upside of this approach is **zero garbage** when you deal with primitive queue elements or mutable objects comprised of primitives and can pre-allocate queue elements.\r\n\r\nThe downside is publishing items is more involved. Consider two threads. Thread 1 and 2 reserved sequence numbers 1 and 2 respectively. Assume they both put their elements into the queue, but before Thread 1 managed to publish it got descheduled. Thread 2 cannot publish before Thread 1 publishes, so it has to wait. There are ways to avoid spinning (e.g. LMAX v3), but nevertheless extra complexity on the caller's side exists.\r\n\r\nSecond approach (JCTools, Java's `ConcurrentLinkedQueue`) is more standard:\r\n\r\n```scala\r\nabstract class RingBuffer[A] {\r\n  def offer(a: A): Boolean\r\n  def poll(): Option[B]\r\n}\r\nval q = new RingBuffer(???) {...}\r\n\r\n// Thread 1\r\nval el = ...\r\nq.offer(el)\r\n\r\n// Thread 2\r\nval nextElOpt = q.poll()\r\n```\r\n\r\nIn this case `offer` and `poll` are atomic operations on their own and there's no extra complexity on the caller's side. It plays nicely with immutable messages being passed through the queue.\r\n\r\nJCTools has an excellent Java implementation of MPMC queue based on a modified design by D. Vyukov (the original design doesn't have all the lock-free properties, like termination safety and resistance to priority inversion, but is simple and fast).\r\n\r\nIn terms of interface I prefer the second approach. As for the implementation I plan to use the design described in \"[A Portable Lock-Free Bounded Queue](http://pirkelbauer.com/papers/icapp16.pdf)\" [LFBQ] by Pirkelbauer et al. which does have the aforementioned lock-free properties. However, the design is for C++11 memory model, so it's not 100% clear yet whether it can be fully adapted for JVM.\r\n\r\n**RTS**\r\nI didn't think too much about how `RTS` could be using a ring buffer under the hood, but my current feeling is that for every capacity it's possible to construct an IO that would block all the slots in the queue and make further progress impossible. Might not be a real problem though..."}}
{"actor":{"display_login":"artempyanykh"}}