<meta content="https://your-image-url.jpg" property="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh9HS-x-dS4oIQSAyvQoXlWlwO1W37v5h5a__vVR-FebAvk6RbMsaUoYrVGb5StXntTWUxnpdOoKiSJoDaiJLywZ2Nzs9cA9sUFYePmZRapVre5ZpS1dG433g-gEIFsj83u6hvly1OMWc7oNGMSv-Kh7XdxsrfnsVn7YcggG4cRjRNlPUcjkLvuU9sNBCY/s2469/Android%2017's%20Lock-Free%20Message%20Queue%20_Meta.png"></meta><i>
Posted by Shai Barack, Android Platform Performance Lead and Charles Munger, Principal Software Engineer</i><p><span id="docs-internal-guid-4d74092e-7fff-8903-bcc8-0a5e5a3ec2fa"></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"></p><div class="separator" style="clear: both;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhbF0aLhQt_qbYhTnODAOPjkVe_oX0gD1YcEGWy8oxv2dE705ei3plig3iKmoOZf6sd8c4x5VmrMNIOyIEy-dmFlaepcN-rz3B6_SSBqa_7VyEJ5FHR2eYcm-QDuYLOormMWbifm2x_X9_4-loSbaW1EQ4H8PKwDLBiIdvcfNNtNp1JeHacykoeTsS0TUk/s16000/Android%2017's%20Lock-Free%20Message%20Queue%20_Blog.png" /></div><span style="font-family: inherit;"><span style="color: #1f1f1f; font-family: inherit; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="color: #1f1f1f; font-family: inherit; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><br /></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="color: #1f1f1f; font-family: inherit; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">In Android 17, apps targeting SDK 37 or higher will receive a new implementation of MessageQueue where the implementation is lock-free. The new implementation improves performance and reduces missed frames, but may break clients that reflect on MessageQueue private fields and methods. To learn more about the behavior change and how you can mitigate impact, </span><a href="http://developer.android.com/about/versions/17/changes/messagequeue" style="font-family: inherit; text-decoration-line: none;" target="_blank"><span style="color: #1155cc; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; text-decoration-line: underline; text-decoration-skip-ink: none; vertical-align: baseline;">check out the MessageQueue behavior change documentation</span></a><span style="color: #1f1f1f; font-family: inherit; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">. This technical blog post provides an overview of the MessageQueue rearchitecture and how you can analyze lock contention issues using Perfetto.</span></p></span></span><p></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span id="docs-internal-guid-cb816bbb-7fff-c2c6-b98c-600b61b50e52"><span style="font-family: inherit;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;">The </span><a href="https://developer.android.com/reference/android/os/Looper" style="text-decoration-line: none;" target="_blank"><span style="color: #1155cc; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; text-decoration-line: underline; text-decoration-skip-ink: none; vertical-align: baseline; white-space-collapse: preserve;">Looper</span></a><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"> drives the UI thread of every Android application. It pulls work from a </span><a href="https://developer.android.com/reference/android/os/MessageQueue" style="text-decoration-line: none;" target="_blank"><span style="color: #1155cc; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; text-decoration-line: underline; text-decoration-skip-ink: none; vertical-align: baseline; white-space-collapse: preserve;">MessageQueue</span></a><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;">, dispatches it to a </span><a href="https://developer.android.com/reference/android/os/Handler" style="text-decoration-line: none;" target="_blank"><span style="color: #1155cc; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; text-decoration-line: underline; text-decoration-skip-ink: none; vertical-align: baseline; white-space-collapse: preserve;">Handler</span></a><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;">, and repeats. For two decades, </span></span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;">MessageQueue</span><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"> used a single monitor lock (i.e. a </span></span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;">synchronized</span><span face=""Google Sans Text", sans-serif" style="color: #1f1f1f; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"> </span><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;">code block) to protect its state.</span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="font-family: inherit;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Android 17 introduces a significant update to this component: a lock-free implementation named </span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 700; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">DeliQueue</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="font-family: inherit;"><span id="docs-internal-guid-b30d8de1-7fff-4a32-cf5d-80cf540e6227"></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">This post explains how locks affect UI performance, how to analyze these issues with Perfetto, and the specific algorithms and optimizations used to improve the Android main thread.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span id="docs-internal-guid-d608e40a-7fff-aa7d-5000-bff3d09fe2fe"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit; font-size: x-large;">The problem: Lock Contention and Priority Inversion</span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;">The legacy </span></span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;">MessageQueue</span><span face=""Google Sans Text", sans-serif" style="color: #1f1f1f; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"> </span><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;">functioned as a priority queue protected by a single lock. If a background thread posts a message while the main thread performs queue maintenance, the background thread blocks the main thread.</span></span></p><span id="docs-internal-guid-fb0fbba7-7fff-7e05-79e8-768946a417ef"><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="font-family: inherit;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;">When two or more threads are competing for exclusive use of the same lock, this is called </span><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline; white-space-collapse: preserve;">Lock contention</span><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;">. This contention can cause </span><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline; white-space-collapse: preserve;">Priority Inversion</span><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;">, leading to UI jank and other performance problems.</span></span></p></span><span><p dir="ltr" style="line-height: 1.38; margin-bottom: 6pt; margin-top: 0pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;">Priority inversion can happen when a high-priority thread (like the UI thread) is made to wait for a low-priority thread. Consider this sequence:</span></span></p><ol style="margin-bottom: 0px; margin-top: 0px; padding-inline-start: 48px;"><li aria-level="1" dir="ltr" style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: decimal; margin-left: -12pt; vertical-align: baseline; white-space: pre;"><p dir="ltr" role="presentation" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="font-family: inherit;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; text-wrap-mode: wrap; vertical-align: baseline;">A </span><span style="color: #1f1f1f; font-style: italic; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; text-wrap-mode: wrap; vertical-align: baseline;">low priority</span><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; text-wrap-mode: wrap; vertical-align: baseline;"> background thread acquires the</span></span><span face=""Google Sans Text", sans-serif" style="color: #1f1f1f; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; text-wrap-mode: wrap; vertical-align: baseline;"> </span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; text-wrap-mode: wrap; vertical-align: baseline;">MessageQueue</span><span face=""Google Sans Text", sans-serif" style="color: #1f1f1f; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; text-wrap-mode: wrap; vertical-align: baseline;"> </span><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; text-wrap-mode: wrap; vertical-align: baseline;"><span style="font-family: inherit;">lock to post the result of work that it did.</span></span></p></li><li aria-level="1" dir="ltr" style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: decimal; margin-left: -12pt; vertical-align: baseline; white-space: pre;"><p dir="ltr" role="presentation" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="font-family: inherit;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; text-wrap-mode: wrap; vertical-align: baseline;">A </span><span style="color: #1f1f1f; font-style: italic; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; text-wrap-mode: wrap; vertical-align: baseline;">medium priority</span><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; text-wrap-mode: wrap; vertical-align: baseline;"> thread becomes runnable and the Kernel's scheduler allocates it CPU time, preempting the low priority thread.</span></span></p></li><li aria-level="1" dir="ltr" style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: decimal; margin-left: -12pt; vertical-align: baseline; white-space: pre;"><p dir="ltr" role="presentation" style="line-height: 1.38; margin-bottom: 6pt; margin-top: 0pt;"><span style="font-family: inherit;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; text-wrap-mode: wrap; vertical-align: baseline;">The </span><span style="color: #1f1f1f; font-style: italic; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; text-wrap-mode: wrap; vertical-align: baseline;">high priority</span><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; text-wrap-mode: wrap; vertical-align: baseline;"> UI thread finishes its current task and attempts to read from the queue, but is blocked because the low priority thread holds the lock.</span></span></p></li></ol><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;">The low-priority thread blocks the UI thread, and the medium-priority work delays it further.</span></span></p><div class="separator" style="clear: both; text-align: center;"><span id="docs-internal-guid-ff649ce9-7fff-0f0a-57eb-a7a10ef70f5b"><span face="Arial, sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="border: none; display: inline-block; height: 213px; overflow: hidden; width: 610px;"><img alt="A visual representation of priority inversion. It shows 'Task L' (Low) holding a lock, blocking 'Task H' (High). 'Task M' (Medium) then preempts 'Task L', effectively delaying 'Task H' for the duration of 'Task M's' execution." src="https://blogger.googleusercontent.com/img/a/AVvXsEi5lpXcJrA3CKIi_DnPnYtJ8bfc3vCrdPHToFuPs6CBRpRCjILPIoTP8Z7m_tpfjLWByWLM1I0UlgacedkHg6iAhlj4Ls7v-EmmRAGvcj9WDB_j095S0SECKZkuU89Bb70vDw-B3CiOWkSuu1KAH6-Z-RLN7zjVJgtqitER1Gl6pMgGEnrWtLp9ebS36JY=s16000" style="margin-left: 0px; margin-top: 0px;" /></span></span></span></div><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span id="docs-internal-guid-e1a4c6c0-7fff-16d2-5e17-ffef6fc3dd8c"><span face="Arial, sans-serif" style="color: black; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit; font-size: large;"><span id="docs-internal-guid-187ea446-7fff-79b9-edff-f48938fe69c4"><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline;">Analyzing contention with Perfetto</span></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="font-family: inherit;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">You can diagnose these issues using </span><a href="https://perfetto.dev/" style="text-decoration: none;" target="_blank"><span style="background-color: transparent; color: #0b57d0; font-style: normal; font-variant: normal; font-weight: 400; text-decoration-skip-ink: none; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap;">Perfetto</span></a><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">. In a standard trace, a thread blocked on a monitor lock enters the sleeping state, and Perfetto shows a slice indicating the lock owner.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span id="docs-internal-guid-cf70a937-7fff-d85c-1d12-1030a3ef6c4c"></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">When you query trace data, look for slices named “monitor contention with …” followed by the name of the thread that owns the lock and the code site where the lock was acquired.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit; font-size: large;"><span id="docs-internal-guid-800d4400-7fff-1521-47b3-09d8c8a6b964"><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline;">Case study: Launcher jank</span></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span id="docs-internal-guid-2473b6a3-7fff-411f-4eaa-574bb03b77aa"></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 6pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">To illustrate, let’s analyze a trace where a user experienced jank while navigating home on a Pixel phone immediately after taking a photo in the camera app. Below we see a screenshot of Perfetto showing the events leading up to the missed frame:</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 6pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"></span></p></span><div class="separator" style="clear: both;"><span style="text-decoration-color: initial; text-decoration-style: initial; text-decoration-thickness: initial;"><br /><img alt="A Perfetto trace screenshot diagnosing the Launcher jank. The 'Actual Timeline' shows a red missed frame. Coinciding with this, the main thread track contains a large green slice labeled 'monitor contention with owner BackgroundExecutor,' indicating that the UI thread was blocked because a background thread held the MessageQueue lock." border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEivHqJIUgTNsk5JKoL8qpiO3vjFfZp-78mTBYD6zWLWbIpQih5o2P-1YdJU57ZEQ2zT959seF1rPzzAmdOFUcMhZqUr67u3YFk5UlqR7UdgVMYpnGU-oFcpEhMtOzaD-8KxTGtaQyL1FpkUqsluy4-cz40e4yzqmiUvG06qmXYd66QnODo-IZJ0tdfps0Q/s16000/cTMPgSaPAotGcAJ.png" /></span><span><span style="color: #1f1f1f;"></span></span></div><span><p></p><div class="separator" style="clear: both; text-align: center;"><br /></div><ul style="margin-bottom: 0px; margin-top: 0px; padding-inline-start: 48px;"><li aria-level="1" dir="ltr" style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; list-style-type: disc; margin-left: -12.75pt; text-decoration: none; vertical-align: baseline; white-space: pre;"><p dir="ltr" role="presentation" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="font-family: inherit;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 700; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Symptom:</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> The Launcher main thread missed its frame deadline. It blocked for 18ms, which exceeds the 16ms deadline required for 60Hz rendering.</span></span></p></li><li aria-level="1" dir="ltr" style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; list-style-type: disc; margin-left: -12.75pt; text-decoration: none; vertical-align: baseline; white-space: pre;"><p dir="ltr" role="presentation" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="font-family: inherit;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 700; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Diagnosis:</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> Perfetto showed the main thread blocked on the</span></span><span face=""Google Sans Text", sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> </span><span style="background-color: transparent; color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">MessageQueue</span><span style="font-family: inherit;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> </span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">lock. A “BackgroundExecutor” thread owned the lock.</span></span></p></li><li aria-level="1" dir="ltr" style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; list-style-type: disc; margin-left: -12.75pt; text-decoration: none; vertical-align: baseline; white-space: pre;"><p dir="ltr" role="presentation" style="line-height: 1.38; margin-bottom: 6pt; margin-top: 0pt;"><span style="font-family: inherit;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 700; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Root Cause:</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> The BackgroundExecutor runs at </span><a href="https://developer.android.com/reference/android/os/Process#THREAD_PRIORITY_BACKGROUND" style="text-decoration: none;" target="_blank"><span style="background-color: transparent; color: #1155cc; font-style: normal; font-variant: normal; font-weight: 400; text-decoration-skip-ink: none; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap;">Process.THREAD_PRIORITY_BACKGROUND</span></a><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> (very low priority). It performed a non-urgent task (checking </span><a href="https://www.android.com/digital-wellbeing/" style="text-decoration: none;" target="_blank"><span style="background-color: transparent; color: #1155cc; font-style: normal; font-variant: normal; font-weight: 400; text-decoration-skip-ink: none; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap;">app usage limits</span></a><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">). Simultaneously, medium priority threads were using CPU time to process data from the camera. The OS scheduler preempted the BackgroundExecutor thread to run the camera threads.</span></span></p></li></ul><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span id="docs-internal-guid-f545b923-7fff-37c6-c64a-6d96c5d01b8b"></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">This sequence caused the Launcher’s UI thread (high priority) to become indirectly blocked by the camera worker thread (medium priority), which was keeping the Launcher’s background thread (low priority) from releasing the lock.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span id="docs-internal-guid-88ee6413-7fff-8ea9-af00-483f1856b732"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit; font-size: large;">Querying traces with PerfettoSQL</span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="font-family: inherit;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">You can use </span><a href="https://perfetto.dev/docs/analysis/perfetto-sql-getting-started" style="text-decoration: none;" target="_blank"><span style="background-color: transparent; color: #1155cc; font-style: normal; font-variant: normal; font-weight: 400; text-decoration-skip-ink: none; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap;">PerfettoSQL</span></a><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> to </span><a href="https://perfetto.dev/docs/analysis/batch-trace-processor" style="text-decoration: none;" target="_blank"><span style="background-color: transparent; color: #1155cc; font-style: normal; font-variant: normal; font-weight: 400; text-decoration-skip-ink: none; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap;">query trace data</span></a><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> for specific patterns. This is useful if you have a large bank of traces from user devices or tests, and you’re searching for specific traces that demonstrate a problem.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span id="docs-internal-guid-009e7aa8-7fff-d370-99b0-84fdc6676791"><span style="font-family: inherit;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;">For example, this query finds </span></span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 14.6667px; white-space-collapse: preserve;">MessageQueue</span><span style="font-family: inherit;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"> contention coincident with dropped frames (jank):</span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"></span></span></p><pre style="color: #333333; line-height: 16.25px; margin: 0px;">INCLUDE PERFETTO MODULE android.monitor_contention;
INCLUDE PERFETTO MODULE android.frames.jank_type;
<span style="color: blue;">SELECT</span>
process_name,
<span style="color: green;">-- Convert duration from nanoseconds to milliseconds</span>
<span style="color: blue;">SUM</span>(dur) / 1000000 <span style="color: blue;">AS</span> sum_dur_ms,
<span style="color: blue;">COUNT</span>(*) <span style="color: blue;">AS</span> count_contention
<span style="color: blue;">FROM</span> android_monitor_contention
<span style="color: blue;">WHERE</span> is_blocked_thread_main
<span style="color: blue;">AND</span> short_blocked_method <span style="color: blue;">LIKE</span> <span style="color: #a31515;">"%MessageQueue%"</span>
<span style="color: green;">-- Only look at app processes that had jank</span>
<span style="color: blue;">AND</span> upid <span style="color: blue;">IN</span> (
<span style="color: blue;">SELECT</span> <span style="color: blue;">DISTINCT</span>(upid)
<span style="color: blue;">FROM</span> actual_frame_timeline_slice
<span style="color: blue;">WHERE</span> android_is_app_jank_type(jank_type) = <span style="color: blue;">TRUE</span>
)
<span style="color: blue;">GROUP</span> <span style="color: blue;">BY</span> process_name
<span style="color: blue;">ORDER</span> <span style="color: blue;">BY</span> <span style="color: blue;">SUM</span>(dur) <span style="color: blue;">DESC</span>;</pre><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span id="docs-internal-guid-cd23b24d-7fff-511d-91a4-3bfaf9572d06"><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;">In this more complex example, join trace data that spans multiple tables to identify </span></span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">MessageQueue</span><span face=""Google Sans Text", sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> </span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;">contention during app startup:</span></span></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"></span></span></p><pre style="color: #333333; line-height: 16.25px; margin: 0px;">INCLUDE PERFETTO MODULE android.monitor_contention;
INCLUDE PERFETTO MODULE android.startup.startups;
<span style="color: green;">-- Join package and process information for startups</span>
<span style="color: blue;">DROP</span> <span style="color: blue;">VIEW</span> <span style="color: blue;">IF</span> <span style="color: blue;">EXISTS</span> startups;
<span style="color: blue;">CREATE</span> <span style="color: blue;">VIEW</span> startups <span style="color: blue;">AS</span>
<span style="color: blue;">SELECT</span> startup_id, ts, dur, upid
<span style="color: blue;">FROM</span> android_startups
<span style="color: blue;">JOIN</span> android_startup_processes <span style="color: blue;">USING</span>(startup_id);
<span style="color: green;">-- Intersect monitor contention with startups in the same process.</span>
<span style="color: blue;">DROP</span> <span style="color: blue;">TABLE</span> <span style="color: blue;">IF</span> <span style="color: blue;">EXISTS</span> monitor_contention_during_startup;
<span style="color: blue;">CREATE</span> VIRTUAL <span style="color: blue;">TABLE</span> monitor_contention_during_startup
<span style="color: blue;">USING</span> SPAN_JOIN(android_monitor_contention PARTITIONED upid, startups PARTITIONED upid);
<span style="color: blue;">SELECT</span>
process_name,
<span style="color: blue;">SUM</span>(dur) / 1000000 <span style="color: blue;">AS</span> sum_dur_ms,
<span style="color: blue;">COUNT</span>(*) <span style="color: blue;">AS</span> count_contention
<span style="color: blue;">FROM</span> monitor_contention_during_startup
<span style="color: blue;">WHERE</span> is_blocked_thread_main
<span style="color: blue;">AND</span> short_blocked_method <span style="color: blue;">LIKE</span> <span style="color: #a31515;">"%MessageQueue%"</span>
<span style="color: blue;">GROUP</span> <span style="color: blue;">BY</span> process_name
<span style="color: blue;">ORDER</span> <span style="color: blue;">BY</span> <span style="color: blue;">SUM</span>(dur) <span style="color: blue;">DESC</span>;</pre><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-family: inherit; white-space-collapse: preserve;">You can use your favorite LLM to write PerfettoSQL queries to find other patterns.</span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span id="docs-internal-guid-096d9a48-7fff-80bf-ddd0-2d17c7081362"></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="font-family: inherit;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">At Google, we use </span><a href="https://perfetto.dev/docs/deployment/deploying-bigtrace-on-a-single-machine" style="text-decoration: none;" target="_blank"><span style="background-color: transparent; color: #1155cc; font-style: normal; font-variant: normal; font-weight: 400; text-decoration-skip-ink: none; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap;">BigTrace</span></a><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> to run PerfettoSQL queries across millions of traces. In doing so, we confirmed that what we saw anecdotally was, in fact, a systemic issue. The data revealed that </span></span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">MessageQueue</span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">lock contention impacts users across the entire ecosystem, substantiating the need for a fundamental architectural change.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit; font-size: x-large;"><span id="docs-internal-guid-caadd956-7fff-a29d-5997-34cb35714195"><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline;">Solution: lock-free concurrency</span></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span id="docs-internal-guid-7c4e1ceb-7fff-d28b-b090-f03cebcd5def"><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;">We addressed the</span></span><span face=""Google Sans Text", sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> </span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">MessageQueue</span><span face=""Google Sans Text", sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> </span><span style="font-family: inherit;"><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">contention problem by implementing a </span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline;">lock-free data structure</span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">, using atomic memory operations rather than exclusive locks to synchronize access to shared state. A data structure or algorithm is lock-free if at least one thread can always make progress regardless of the scheduling behavior of the other threads. This property is generally hard to achieve, and is </span><a href="https://abseil.io/docs/cpp/atomic_danger" style="text-decoration-line: none;" target="_blank"><span style="color: #1155cc; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; text-decoration-line: underline; text-decoration-skip-ink: none; vertical-align: baseline;">usually not worth pursuing for most code</span></a><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">.</span></span></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit; font-size: large;"><span id="docs-internal-guid-297cca04-7fff-13f2-d589-739510c50dee"><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline;">The atomic primitives</span></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">Lock-free software often relies on atomic Read-Modify-Write primitives that the hardware provides.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span id="docs-internal-guid-2a9f5f30-7fff-3bd9-b65d-16481bbb7ee9"></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">On older generation ARM64 CPUs, atomics used a Load-Link/Store-Conditional (LL/SC) loop. The CPU loads a value and marks the address. If another thread writes to that address, the store fails, and the loop retries. Because the threads can keep trying and succeed without waiting for another thread, this operation is lock-free.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"></span></span></p><pre style="color: #333333; line-height: 16.25px; margin: 0px;">ARM64 LL/SC loop example
retry:
ldxr x0, [x1] // <span style="color: blue;">Load</span> <span style="color: blue;">exclusive</span> <span style="color: blue;">from</span> address x1 <span style="color: blue;">to</span> x0
<span style="color: blue;">add</span> x0, x0, #1 // <span style="color: blue;">Increment</span> value <span style="color: blue;">by</span> 1
stxr w2, x0, [x1] // Store <span style="color: blue;">exclusive</span>.
// w2 gets 0 <span style="color: blue;">on</span> success, 1 <span style="color: blue;">on</span> failure
cbnz w2, retry // <span style="color: blue;">If</span> w2 <span style="color: blue;">is</span> non-zero (failed), branch <span style="color: blue;">to</span> retr</pre><p dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;"><br /></span></span></p><p dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;"><span style="font-family: inherit;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">(</span><a href="https://godbolt.org/z/GPs9GeGhG" style="text-decoration: none;"><span style="background-color: transparent; color: #1155cc; font-style: normal; font-variant: normal; font-weight: 400; text-decoration-skip-ink: none; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap;">view in Compiler Explorer</span></a><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">)</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span id="docs-internal-guid-5d564034-7fff-04d5-b5ed-235d2cce6df9"><span style="font-family: inherit;"><br /><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;">Newer ARM architectures (ARMv8.1) support </span><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline; white-space-collapse: preserve;">Large System Extensions (LSE)</span><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"> which include instructions in the form of Compare-And-Swap (CAS) or Load-And-Add (demonstrated below). In Android 17 we added support to the Android Runtime (ART) compiler to detect when LSE is supported and emit optimized instructions:</span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"></span></span></p><pre style="color: #333333; line-height: 16.25px; margin: 0px;">/ ARMv8.1 LSE <span style="color: blue;">atomic</span> example
ldadd x0, x1, [x2] // <span style="color: blue;">Atomic</span> <span style="color: blue;">load</span>-<span style="color: blue;">add</span>.
// Faster, <span style="color: blue;">no</span> loop required.</pre><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="color: #1f1f1f; font-family: inherit; white-space-collapse: preserve;">In our benchmarks, high-contention code that uses CAS achieves a ~3x speedup over the LL/SC variant.</span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span id="docs-internal-guid-655bf206-7fff-a055-5c56-2334602de691"></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">The Java programming language offers atomic primitives via</span></span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><a href="https://developer.android.com/reference/java/util/concurrent/atomic/package-summary" style="text-decoration: none;" target="_blank"><span style="-webkit-text-decoration-skip: none; background-color: transparent; color: #1155cc; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration-skip-ink: none; text-decoration: underline; vertical-align: baseline; white-space: pre;">java.util.concurrent.atomic</span></a><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">that rely on these and other specialized CPU instructions.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span id="docs-internal-guid-495eb21d-7fff-02a9-25c4-6546f5af6e15"><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline;"><span style="font-family: inherit; font-size: x-large;">The Data Structure: DeliQueue</span></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 6pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">To remove lock contention from </span></span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">MessageQueue</span><span style="font-family: inherit;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">, our engineers designed a novel data structure called </span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 700; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">DeliQueue</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">. DeliQueue separates </span><span style="background-color: transparent; color: #188038; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Message</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> insertion from</span></span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Message</span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">processing:</span></span></p><ol style="margin-bottom: 0px; margin-top: 0px; padding-inline-start: 48px;"><li aria-level="1" dir="ltr" style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; list-style-type: decimal; margin-left: -12pt; text-decoration: none; vertical-align: baseline; white-space: pre;"><p dir="ltr" role="presentation" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 700; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">The list of </span></span><span style="background-color: transparent; color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 700; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Message</span><span style="font-family: inherit;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 700; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">s (Treiber stack):</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> A lock-free stack. Any thread can push new </span></span><span style="background-color: transparent; color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Message</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">s here without contention.</span></span></p></li><li aria-level="1" dir="ltr" style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; list-style-type: decimal; margin-left: -12pt; text-decoration: none; vertical-align: baseline; white-space: pre;"><p dir="ltr" role="presentation" style="line-height: 1.38; margin-bottom: 6pt; margin-top: 0pt;"><span style="font-family: inherit;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 700; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">The priority queue (Min-heap):</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> A heap of</span></span><span face=""Google Sans Text", sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> </span><span style="background-color: transparent; color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Message</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">s to handle, exclusively owned by the Looper thread (hence no synchronization or locks are needed to access).</span></span></p></li></ol><h3 dir="ltr" style="line-height: 1.38; margin-bottom: 6pt; margin-top: 6pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 700; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit; font-size: large;">Enqueue: pushing to a Treiber stack</span></span></h3><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span id="docs-internal-guid-5c2da1f3-7fff-2f23-1a57-b87c8ed8680e"></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">The list of</span></span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Message</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">s is kept in a Treiber stack [1], a lock-free stack that uses a CAS loop to update the head pointer.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"></span></p><pre style="color: #333333; line-height: 16.25px; margin: 0px;"><span style="color: blue;">public</span> <span style="color: blue;">class</span> <span style="color: #2b91af;">TreiberStack</span> <E> {
AtomicReference<Node<E>> top =
<span style="color: blue;">new</span> AtomicReference<Node<E>>();
<span style="color: blue;">public</span> <span style="color: #2b91af;">void</span> push(E item) {
Node<E> newHead = <span style="color: blue;">new</span> Node<E>(item);
Node<E> oldHead;
<span style="color: blue;">do</span> {
oldHead = top.get();
newHead.next = oldHead;
} <span style="color: blue;">while</span> (!top.compareAndSet(oldHead, newHead));
}
<span style="color: blue;">public</span> E pop() {
Node<E> oldHead;
Node<E> newHead;
<span style="color: blue;">do</span> {
oldHead = top.get();
<span style="color: blue;">if</span> (oldHead == <span style="color: blue;">null</span>) <span style="color: blue;">return</span> <span style="color: blue;">null</span>;
newHead = oldHead.next;
} <span style="color: blue;">while</span> (!top.compareAndSet(oldHead, newHead));
<span style="color: blue;">return</span> oldHead.item;
}
}</pre><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span id="docs-internal-guid-86bfc1f0-7fff-7ba3-667b-6338b7f6e2d2"><span style="font-family: inherit;"><span style="font-style: italic; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;">Source code based on Java Concurrency in Practice [2], </span><a href="https://jcip.net/listings/ConcurrentStack.java" style="text-decoration-line: none;"><span style="color: #1155cc; font-style: italic; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; text-decoration-line: underline; text-decoration-skip-ink: none; vertical-align: baseline; white-space-collapse: preserve;">available online</span></a><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"> and released to the public domain</span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">Any producer can push new</span></span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Message</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">s to the stack at any time. This is like pulling a ticket at a deli counter - your number is determined by when you showed up, but the order you get your food in doesn't have to match. Because it's a linked stack, ever</span></span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">y</span></span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Message</span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">is a sub-stack - you can see what the </span></span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Message</span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">queue was like at any point in time by tracking the head and iterating forwards - you won't see any new</span></span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Message</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">s pushed on top, even if they're being added during your traversal.</span></span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"><br /><br /></span></p><h3 dir="ltr" style="line-height: 1.38; margin-bottom: 6pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 700; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit; font-size: large;">Dequeue: bulk transfer to a min-heap</span></span></h3><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span id="docs-internal-guid-6fc7a392-7fff-b027-8b25-639abfd4a25c"></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">To find the next </span></span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Message</span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">to handle, the</span></span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Looper</span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">processes new</span></span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Message</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">s</span></span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">from the Treiber stack by walking the stack starting from the top and iterating until it finds the last</span></span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Message</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;"> that it previously processed. As the</span></span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Looper</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;"> traverses down the stack, it inserts </span></span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Message</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">s into the deadline-ordered min-heap. Since the Looper exclusively owns the heap, it orders and processes</span></span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Message</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">s without locks or atomics.</span></span></p><div class="separator" style="clear: both; text-align: center;"><span style="border: none; display: inline-block; height: 91px; margin-left: 1em; margin-right: 1em; overflow: hidden; width: 610px;"><img alt="A system diagram illustrating the DeliQueue architecture. Concurrent producer threads (left) push messages onto a shared 'Lock-Free Treiber Stack' using atomic CAS operations. The single consumer 'Looper Thread' (right) claims these messages via an atomic swap, merges them into a private 'Local Min-heap' sorted by timestamp, and then executes them." src="https://blogger.googleusercontent.com/img/a/AVvXsEhknkVSDfMX-ZahCjfG4tSxzMtW4QHU0mzm_9vw2wXNMM1DY3oOy-sHeejjN-huSAGJAjVJzl47NUlVlVKNswK4KHkW0dTCEoeIZqYspMEI6KIy56S9d0AQWUMa1amuWA6WAWr1naU4_5SrqSr1GYzMsekgmJgjcs43lb4C5YGznm6g3AC3uwAQDFZJnLk=s16000" style="margin-left: 0px; margin-top: 0px;" /></span></div><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span id="docs-internal-guid-d33f0623-7fff-4d5e-99b0-5e91595e38cb"><span face="Arial, sans-serif" style="color: black; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><br /></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;">In walking down the stack, the </span></span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;">Looper</span><span face=""Google Sans Text", sans-serif" style="color: #1f1f1f; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"> </span><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;">also creates links from stacked</span></span><span face=""Google Sans Text", sans-serif" style="color: #1f1f1f; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"> </span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;">Message</span><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;">s back to their predecessors, thus forming a doubly-linked list. Creating the linked list is safe because links pointing down the stack are added via the Treiber stack algorithm with CAS, and links up the stack are only ever read and modified by the</span></span><span face=""Google Sans Text", sans-serif" style="color: #1f1f1f; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"> </span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;">Looper</span><span face=""Google Sans Text", sans-serif" style="color: #1f1f1f; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"> </span><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;">thread. These back links are then used to remove</span></span><span face=""Google Sans Text", sans-serif" style="color: #1f1f1f; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"> </span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;">Message</span><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;">s from arbitrary points in the stack in O(1) time.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">This design provides<span style="font-family: inherit;"> </span></span></span><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><i>O</i>(1)</span></span><span face=""Google Sans Text", sans-serif" style="color: #1f1f1f; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"> </span><span style="font-family: inherit;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;">insertion for producers (threads posting work to the queue) and amortized </span><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><i>O</i>(log </span><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;">N)</span><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"> processing for the consumer (the</span></span><span face=""Google Sans Text", sans-serif" style="color: #1f1f1f; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"> </span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;">Looper</span><span face=""Google Sans Text", sans-serif" style="color: #1f1f1f; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;">).</span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;"><span id="docs-internal-guid-a01eb2dc-7fff-e868-f53e-1d021f344afa"></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">Using a min-heap to order </span></span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Message</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">s also addresses a fundamental flaw in the legacy </span></span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">MessageQueue</span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">, </span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">where</span></span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Message</span><span style="font-family: inherit;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">s were kept in a singly-linked list (rooted at the top). In the legacy implementation, removal from the head was </span><span style="background-color: transparent; color: #1f1f1f; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><i>O</i></span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">(1)</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">, but insertion had a worst case of </span><span style="background-color: transparent; color: #1f1f1f; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><i>O(N)</i></span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> – scaling poorly for overloaded queues! Conversely, insertion to and removal from the min-heap scale logarithmically, delivering competitive average performance but really excelling in tail latencies.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"><span id="docs-internal-guid-1e82bf04-7fff-ce44-b440-809493782717"></span></span></span></span></span></span></p><div align="center" dir="ltr" style="margin-left: 0pt;"><table style="border-collapse: collapse; border: none;"><colgroup><col width="233"></col><col width="233"></col><col width="233"></col></colgroup><tbody><tr style="height: 0pt;"><td style="border-bottom: solid #000000 1pt; border-color: rgb(0, 0, 0); border-left: solid #000000 1pt; border-right: solid #000000 1pt; border-style: solid; border-top: solid #000000 1pt; border-width: 1pt; overflow-wrap: break-word; overflow: hidden; padding: 5pt; vertical-align: top;"><span style="font-family: inherit;"><br /></span></td><td style="border-bottom: solid #000000 1pt; border-color: rgb(0, 0, 0); border-left: solid #000000 1pt; border-right: solid #000000 1pt; border-style: solid; border-top: solid #000000 1pt; border-width: 1pt; overflow-wrap: break-word; overflow: hidden; padding: 5pt; vertical-align: top;"><p dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;"><span style="font-family: inherit;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Legacy (locked) </span><span style="background-color: transparent; color: #188038; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">MessageQueue</span></span></p></td><td style="border-bottom: solid #000000 1pt; border-color: rgb(0, 0, 0); border-left: solid #000000 1pt; border-right: solid #000000 1pt; border-style: solid; border-top: solid #000000 1pt; border-width: 1pt; overflow-wrap: break-word; overflow: hidden; padding: 5pt; vertical-align: top;"><p dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">DeliQueue</span></span></p></td></tr><tr style="height: 0pt;"><td style="border-bottom: solid #000000 1pt; border-color: rgb(0, 0, 0); border-left: solid #000000 1pt; border-right: solid #000000 1pt; border-style: solid; border-top: solid #000000 1pt; border-width: 1pt; overflow-wrap: break-word; overflow: hidden; padding: 5pt; vertical-align: top;"><p dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">Insert</span></span></p></td><td style="border-bottom: solid #000000 1pt; border-color: rgb(0, 0, 0); border-left: solid #000000 1pt; border-right: solid #000000 1pt; border-style: solid; border-top: solid #000000 1pt; border-width: 1pt; overflow-wrap: break-word; overflow: hidden; padding: 5pt; vertical-align: top;"><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><i><span style="font-family: inherit;">O(N)</span></i></span></p></td><td style="border-bottom: solid #000000 1pt; border-color: rgb(0, 0, 0); border-left: solid #000000 1pt; border-right: solid #000000 1pt; border-style: solid; border-top: solid #000000 1pt; border-width: 1pt; overflow-wrap: break-word; overflow: hidden; padding: 5pt; vertical-align: top;"><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="font-family: inherit;"><span style="background-color: transparent; color: #1f1f1f; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><i>O</i></span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">(1)</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> for calling thread</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="font-family: inherit;"><span style="background-color: transparent; color: #1f1f1f; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><i>O(logN)</i></span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> for </span><span style="background-color: transparent; color: #188038; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Looper</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> thread</span></span></p></td></tr><tr style="height: 0pt;"><td style="border-bottom: solid #000000 1pt; border-color: rgb(0, 0, 0); border-left: solid #000000 1pt; border-right: solid #000000 1pt; border-style: solid; border-top: solid #000000 1pt; border-width: 1pt; overflow-wrap: break-word; overflow: hidden; padding: 5pt; vertical-align: top;"><p dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">Remove from head</span></span></p></td><td style="border-bottom: solid #000000 1pt; border-color: rgb(0, 0, 0); border-left: solid #000000 1pt; border-right: solid #000000 1pt; border-style: solid; border-top: solid #000000 1pt; border-width: 1pt; overflow-wrap: break-word; overflow: hidden; padding: 5pt; vertical-align: top;"><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;"><i>O</i>(1)</span></span></p></td><td style="border-bottom: solid #000000 1pt; border-color: rgb(0, 0, 0); border-left: solid #000000 1pt; border-right: solid #000000 1pt; border-style: solid; border-top: solid #000000 1pt; border-width: 1pt; overflow-wrap: break-word; overflow: hidden; padding: 5pt; vertical-align: top;"><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;"><i>O(logN)</i></span></span></p></td></tr></tbody></table></div><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span id="docs-internal-guid-d43a699a-7fff-648e-1c4d-cb8001b51340"></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">In the legacy queue implementation, producers and the consumer used a lock to coordinate exclusive access to the underlying singly-linked list. In DeliQueue, the Treiber stack handles concurrent access, and the single consumer handles ordering its work queue.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span id="docs-internal-guid-7066d0a0-7fff-996d-8718-93fca15b620f"><span style="color: black; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline;"><span style="font-family: inherit; font-size: large;">Removal: consistency via tombstones</span></span></span></span></p><p dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">DeliQueue is a hybrid data structure, joining a lock-free Treiber stack with a single-threaded min-heap. Keeping these two structures in sync without a global lock presents a unique challenge: a message might be physically present in the stack but logically removed from the queue.</span></span></p><p dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">To solve this, DeliQueue uses a technique called “tombstoning.” Each </span></span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Message</span><span face="Arial,sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">tracks its position in the stack via the backwards and forwards pointers, its index in the heap’s array, and a boolean flag indicating whether it has been removed. When a</span></span><span face="Arial,sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Message</span><span face="Arial,sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">is ready to run, the</span></span><span face="Arial,sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Looper</span><span face="Arial,sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">thread will CAS its removed flag, then remove it from the heap and stack.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;">When another thread needs to remove a </span></span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;">Message</span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;">, it doesn't immediately extract it from the data structure. Instead, it performs the following steps:</span></span></p><ol style="margin-bottom: 0px; margin-top: 0px; padding-inline-start: 48px;"><li aria-level="1" dir="ltr" style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; list-style-type: decimal; text-decoration: none; vertical-align: baseline; white-space: pre;"><p dir="ltr" role="presentation" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">Logical removal: the thread uses a CAS to atomically set the </span></span><span style="background-color: transparent; color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Message</span><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">’s removal flag from false to true. The</span></span><span face="Arial, sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> </span><span style="background-color: transparent; color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Message</span><span face="Arial, sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> </span><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">remains in the data structure as evidence of its pending removal, a so-called “tombstone”. Once a</span></span><span face="Arial, sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> </span><span style="background-color: transparent; color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Message</span><span face="Arial, sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> </span><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">is flagged for removal, DeliQueue treats it as if it no longer exists in the queue whenever it’s found.</span></span></p></li><li aria-level="1" dir="ltr" style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; list-style-type: decimal; text-decoration: none; vertical-align: baseline; white-space: pre;"><p dir="ltr" role="presentation" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">Deferred cleanup: The actual removal from the data structure is the responsibility of the </span></span><span style="background-color: transparent; color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Looper</span><span face="Arial, sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> </span><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">thread, and is deferred until later. Rather than modifying the stack or heap, the remover thread adds the</span></span><span face="Arial, sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> </span><span style="background-color: transparent; color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Message</span><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;"> to another lock-free freelist stack.</span></span></p></li><li aria-level="1" dir="ltr" style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; list-style-type: decimal; text-decoration: none; vertical-align: baseline; white-space: pre;"><p dir="ltr" role="presentation" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">Structural removal: Only the </span></span><span style="background-color: transparent; color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Looper</span><span face="Arial, sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> </span><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">can interact with the heap or remove elements from the stack. When it wakes up, it clears the freelist and processes the </span></span><span style="background-color: transparent; color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Messages</span><span face="Arial, sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> </span><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">it contained. Each </span></span><span style="background-color: transparent; color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Message</span><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;"> is then unlinked from the stack and removed from the heap. </span></span></p></li></ol><div><span style="white-space-collapse: preserve;"><br /></span></div><p dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">This approach keeps all management of the heap single-threaded. It minimizes the number of concurrent operations and memory barriers required, making the critical path faster and simpler.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span id="docs-internal-guid-0f44709f-7fff-3016-7a35-94f3ec565c5e"></span></p><h3 dir="ltr" style="line-height: 1.2; margin-bottom: 12pt; margin-top: 12pt;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 700; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit; font-size: x-large;">Traversal: benign Java memory model data races</span></span></h3><div><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 700; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span id="docs-internal-guid-7b3bd3a2-7fff-efe7-f706-1d994d79f9ed" style="font-weight: normal;"><p dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;"><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;">Most concurrency APIs, such as</span></span><span face="Arial, sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> </span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">Future</span><span face="Arial, sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> </span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;">in the Java standard library, or Kotlin’s </span></span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">Job</span><span face="Arial, sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> </span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;">and</span></span><span face="Arial, sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> </span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">Deferred</span><span face="Arial, sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">, i</span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;">nclude a mechanism to cancel work before it completes. An instance of one of these classes matches 1:1 with a unit of underlying work, and calling</span></span><span face="Arial, sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> </span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">cancel</span><span face="Arial, sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> </span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;">on an object cancels the specific operations associated with them.</span></span></p><span style="font-family: inherit;"><br /></span><p dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;"><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;">Today’s Android devices have multi-core CPUs and concurrent, generational garbage collection. But when Android was first developed, it was too expensive to allocate one object for each unit of work. Consequently, Android’s </span></span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">Handler</span><span face="Arial, sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> </span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;">supports cancellation via numerous overloads of </span></span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">removeMessages</span><span face="Arial, sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> -</span><span style="font-family: inherit;"><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> rather than removing a </span><span style="font-style: italic; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">specific</span></span><span face="Arial, sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> </span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">Message</span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;">, it removes all</span></span><span face="Arial, sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> </span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">Message</span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;">s that match the specified criteria. In practice, this requires iterating through all</span></span><span face="Arial, sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> </span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">Message</span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;">s inserted before</span></span><span face="Arial, sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> </span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">removeMessages</span><span face="Arial, sans-serif" style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-size: 11pt;"> </span><span style="font-family: inherit;">w</span></span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;">as called and removing the ones that match.</span></span></p><span style="font-family: inherit;"><br /><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">When iterating forward, a thread only requires one ordered atomic operation, to read the current head of the stack. After that, ordinary field reads are used to find the next</span></span><span face="Arial, sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> </span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">Message</span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;">. If the</span></span><span face="Arial, sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> </span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">Looper</span><span face="Arial, sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> </span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;">thread modifies the</span></span><span face="Arial, sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> </span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">next</span><span face="Arial, sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> </span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;">fields while removing</span></span><span face="Arial, sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> </span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">Message</span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;">s, the</span></span><span face="Arial, sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> </span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">Looper</span><span style="font-family: inherit;"><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">’s write and another thread’s read are unsynchronized - this is a </span><span style="font-style: italic; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">data race</span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">. Normally, a data race is a serious bug that can cause huge problems in your app - leaks, infinite loops, crashes, freezes, and more. However, under certain narrow conditions, data races can be benign within the Java Memory Model. Suppose we start with a stack of:</span></span></span></span></div></span><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"></p><div class="separator" style="clear: both; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><img alt="A diagram showing the initial state of the message stack as a linked list. The 'Head' points to 'Message A', which links sequentially to 'Message B', 'Message C', and 'Message D'." border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgD58rsF7QpfHdZD0-4Y4YT4yn7pyFUvRU8ngHUs2T748AcOKAPQYJ_rn_dUg28-Q_Rc0XH3O7qlD9dGwMdoURapme0STqflbdfgUFqz9xBIjkx1Mn0GW_2H357NtAjHDiFGMEsv-GxLQTTN8qq8UycW_l-liJ6EliM76rUdhX0kMU15DjTMbT60I0-d1w/s16000/graphviz_linked.png" /><span><span style="color: #1f1f1f;"><span style="font-family: inherit;"><span><span></span></span></span></span></span></div><span><span style="color: #1f1f1f;"><span style="font-family: inherit;"><span><span><br /><span style="font-family: inherit; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span id="docs-internal-guid-d19b183b-7fff-69c0-a5e3-ff92ce37f956"></span></span></span></span></span></span></span><p></p><p dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">We perform an atomic read of the head, and see A. A’s </span></span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">next</span><span face="Arial,sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">pointer points to B. At the same time as we process B, the looper might remove B and C, by updating A to point to C and then D.</span></span></p><span><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"><span id="docs-internal-guid-da0e0bca-7fff-aea9-7d44-3ba98b9d79ec"><span face="Arial, sans-serif" style="color: black; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="border: none; display: inline-block; height: 176px; overflow: hidden; width: 610px;"><img alt="A diagram illustrating a benign data race during list traversal. The Looper thread has updated 'Message A' to point directly to 'Message D', effectively removing 'Message B' and 'Message C'. Simultaneously, a concurrent thread reads a stale 'next' pointer from A, traverses through the logically removed messages B and C, and eventually rejoins the live list at 'Message D'." src="https://blogger.googleusercontent.com/img/a/AVvXsEiBEhPBhBTaFMF-1L8t05OMQMm08iWVMG_HGWmCLG9gjEJN87ScZLxovnX8VrbO4RFbRi_Ctw1_0U_BeQVIqAZ3emlxkPhvzXIg3WB3ijOOHRnkqJnnqo43l4G7P1WVU-y8IfENFunduyHnfUewRh2yf_4EM7sbo7BIZDPG1wsDWoN6WbHEePS39mwq1ZE=s16000" style="margin-left: 0px; margin-top: 0px;" /></span></span></span></span></span></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"><br /></span></span></span></span></span></p><p dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">Even though</span></span><span face="Arial,sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">B</span><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;"> and </span></span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">C</span><span face="Arial,sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="font-family: inherit;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">are logically removed, </span><span style="background-color: transparent; color: #188038; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">B</span><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> retains its next pointer to</span></span><span face="Arial,sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">C</span><span face="Arial,sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">,</span><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;"> and</span></span><span face="Arial,sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">C</span><span face="Arial,sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">to </span></span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">D</span><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">. The reading thread continues traversing through the detached removed nodes and eventually rejoins the live stack at </span></span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">D</span><span face="Arial,sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">.</span></p><p dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;"><span face="Arial,sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"><br /></span></p><p dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">By designing DeliQueue to handle races between traversal and removal, we allow for safe, lock-free iteration.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit; font-size: x-large;"><span id="docs-internal-guid-b6b28ebe-7fff-e906-929e-1c17c3e00167"><span style="color: black; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline;">Quitting: Native refcount</span></span></span></span></span></span></span></p><p dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Looper</span><span face="Arial,sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">is backed by a native allocation that must be manually freed once the </span></span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Looper</span><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;"> has quit. If some other thread is adding </span></span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Message</span><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">s while the</span></span><span face="Arial,sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Looper</span><span face="Arial,sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="font-family: inherit;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">is quitting, it could use the native allocation after it’s freed, a memory safety violation. We prevent this using a </span><span style="background-color: transparent; color: black; font-style: italic; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">tagged refcount</span><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">, where one bit of the atomic is used to indicate whether the </span></span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Looper</span><span face="Arial,sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">is quitting.</span></span></p><p dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;"><span face="Arial,sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"><br /></span></p><p dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">Before using the native allocation, a thread reads the refcount atomic. If the quitting bit is set, it returns that the</span></span><span face="Arial,sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Looper</span><span face="Arial,sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">is quitting and the native allocation must not be used. If not, it attempts a CAS to increment the number of active threads using the native allocation. After doing what it needs to, it decrements the count. If the quitting bit was set after its increment but before the decrement, and the count is now zero, then it wakes up the </span></span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Looper</span><span face="Arial,sans-serif" style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">thread.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"><span style="color: black; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;">When the</span></span><span face="Arial, sans-serif" style="color: black; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> </span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">Looper</span><span face="Arial, sans-serif" style="color: black; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> </span><span style="color: black; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;">thread is ready to quit, it uses CAS to set the quitting bit in the atomic. If the refcount was 0, it can proceed to free its native allocation. Otherwise, it parks itself, knowing that it will be woken up when the last user of the native allocation decrements the refcount. This approach does mean that the </span></span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">Looper</span><span style="color: black; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"> thread waits for the progress of other threads, but only when it’s quitting. That only happens once and is not performance sensitive, and it keeps the other code for using the native allocation fully lock-free.</span></span></span></span></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"><span id="docs-internal-guid-852f4e36-7fff-947e-9e8f-7e83afeba2c0"><span face="Arial, sans-serif" style="color: black; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="border: none; display: inline-block; height: 165px; overflow: hidden; width: 610px;"><img alt="A state diagram illustrating the tagged refcount mechanism for safe termination. It defines three states based on the atomic value's layout (Bit 63 for teardown, Bits 0-62 for refcount): Active (Green): The teardown bit is 0. Workers successfully increment and decrement the reference count. Draining (Yellow): The Looper has set the teardown bit to 1. New worker increments fail, but existing workers continue to decrement. Terminated (Red): Occurs when the reference count reaches 0 while draining. The Looper is signaled that it is safe to destroy the native allocation." src="https://blogger.googleusercontent.com/img/a/AVvXsEhnTvDsIwwQfH8V_jK3KwyjtRolyycTjQqqezIEVYspluGZCVNIWpEJA7bFV2iEYXFpTF7XFfdoYaWVamWAre916Uv8nPhRJ7hOddqT2nEymLewlKXvRffzgYRneFMuxflq8GnPyaTf3-gMx-JDf3Jk6YIxP4fUAJ8TcSmGkcI82Pubf6R3YvSlcjoSd-U=s16000" style="margin-left: 0px; margin-top: -1.9174px;" /></span></span></span></span></span></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"><br /></span></span></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"><br /></span></span></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"><span id="docs-internal-guid-7955d30f-7fff-1736-b4c3-4b22e234107c"></span></span></span></span></span></span></p></span><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span><span style="font-family: inherit;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">There’s a lot of other tricks and complexity in the implementation. You can learn more about DeliQueue by reviewing the </span></span></span><span style="font-family: inherit;">source code.</span></p><span><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit; font-size: x-large;"><span id="docs-internal-guid-3b24281c-7fff-389c-3612-edc3b2f073fb"><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline;">Optimization: branchless programming</span></span></span></span></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="font-family: inherit;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">While developing and testing DeliQueue, the team ran many benchmarks and carefully profiled the new code. One issue identified using the </span><a href="https://developer.android.com/ndk/guides/simpleperf" style="text-decoration: none;" target="_blank"><span style="background-color: transparent; color: #1155cc; font-style: normal; font-variant: normal; font-weight: 400; text-decoration-skip-ink: none; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap;">simpleperf tool</span></a><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> was pipeline flushes caused by the</span></span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Message</span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">comparator code.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"><span id="docs-internal-guid-d54d4939-7fff-59af-c65d-7f66993a98bb"><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;">A standard comparator uses conditional jumps, with the condition for deciding which</span></span><span face=""Google Sans Text", sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> </span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">Message</span><span face=""Google Sans Text", sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> </span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;">comes first simplified below:</span></span></span></span></span></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"></span></span></span></span></span></p><pre style="color: #333333; line-height: 16.25px; margin: 0px;"><span style="color: blue;">static</span> <span style="color: #2b91af;">int</span> compareMessages(@NonNull Message m1, @NonNull Message m2) {
<span style="color: blue;">if</span> (m1 == m2) {
<span style="color: blue;">return</span> 0;
}
<span style="color: green;">// Primary queue order is by when.</span>
<span style="color: green;">// Messages with an earlier when should come first in the queue.</span>
<span style="color: blue;">final</span> <span style="color: #2b91af;">long</span> whenDiff = m1.when - m2.when;
<span style="color: blue;">if</span> (whenDiff > 0) <span style="color: blue;">return</span> 1;
<span style="color: blue;">if</span> (whenDiff < 0) <span style="color: blue;">return</span> -1;
<span style="color: green;">// Secondary queue order is by insert sequence.</span>
<span style="color: green;">// If two messages were inserted with the same `when`, the one inserted</span>
<span style="color: green;">// first should come first in the queue.</span>
<span style="color: blue;">final</span> <span style="color: #2b91af;">long</span> insertSeqDiff = m1.insertSeq - m2.insertSeq;
<span style="color: blue;">if</span> (insertSeqDiff > 0) <span style="color: blue;">return</span> 1;
<span style="color: blue;">if</span> (insertSeqDiff < 0) <span style="color: blue;">return</span> -1;
<span style="color: blue;">return</span> 0;
}</pre><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"><br /></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">This code compiles to conditional jumps (</span></span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">b.le</span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">and </span></span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">cbnz</span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="font-family: inherit;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">instructions). When the CPU encounters a conditional branch, it can’t know whether the branch is taken until the condition is computed, so it doesn’t know which instruction to read next, and has to guess, using a technique called </span><span style="background-color: transparent; color: #1f1f1f; font-style: italic; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">branch prediction</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">. In a case like binary search, the branch direction will be unpredictably different at each step, so it’s likely that half the predictions will be wrong. Branch prediction is often ineffective in searching and sorting algorithms (such as the one used in a min-heap), because the cost of guessing wrong is larger than the improvement from guessing correctly. When the branch predictor guesses wrong, it must throw away the work it did after assuming the predicted value, and start again from the path that was actually taken - this is called a </span><span style="background-color: transparent; color: #1f1f1f; font-style: italic; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">pipeline flush</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"><span id="docs-internal-guid-86182231-7fff-da72-96d9-6b96aba5000f"></span></span></span></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">To find this issue, we profiled our benchmarks using the</span></span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">branch-misses</span><span style="font-family: inherit;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> performance counter, which records stack traces where the branch predictor guesses wrong. We then visualized the results with </span><a href="https://github.com/google/pprof" style="text-decoration: none;" target="_blank"><span style="background-color: transparent; color: #1155cc; font-style: normal; font-variant: normal; font-weight: 400; text-decoration-skip-ink: none; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap;">Google pprof</span></a><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">, as shown below:</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"><span id="docs-internal-guid-514a00fc-7fff-6f2a-7a9a-dd53920fe6a1"><span face=""Google Sans Text", sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="border: none; display: inline-block; height: 293px; overflow: hidden; width: 610px;"><img alt="A screenshot from the pprof web UI showing branch misses in MessageQueue code to compare Message instances while performing heap operations." src="https://blogger.googleusercontent.com/img/a/AVvXsEhWzEoCloyBTPrjN-l1Z_g9erTzvYdJSAN_Kl03J5BqreA5Tdb_T9HG0LfenFzE2BkN5GTaeiIqAtQNqmcGjhTsu7vfEj2D-51hUjLaQssZo6pV8jiv8FtLFOmEnqZdfanKNYQ1oOWDAaKEzfSZbV9NVcxVYkXW_dw663Z5DDPUaS8NJwrXzSgTrxtT13k=s16000" style="margin-left: -6.78561e-14px; margin-top: 0px;" /></span></span></span></span></span></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;">Recall that the original </span></span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;">MessageQueue</span><span face=""Google Sans Text", sans-serif" style="color: #1f1f1f; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"> </span><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;">code used a singly-linked list for the ordered queue. Insertion would traverse the list in sorted order as a linear search, stopping at the first element that’s past the point of insertion and linking the new </span></span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;">Message</span><span face=""Google Sans Text", sans-serif" style="color: #1f1f1f; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"> </span><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;">ahead of it. Removal from the head simply required unlinking the head. Whereas DeliQueue uses a min-heap, where mutations require reordering some elements (sifting up or down) with logarithmic complexity in a balanced data structure, where any comparison has an even chance of directing the traversal to a left child or to a right child. The new algorithm is asymptotically faster, but exposes a new bottleneck as the search code stalls on branch misses half the time.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"><span id="docs-internal-guid-fd635632-7fff-cd6b-4491-00a8cba98612"><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">Realizing that branch misses were slowing down our heap code, we optimized the code using </span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline;">branch-free programming</span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">:</span></span></span></span></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"></span></span></span></span></span></p><pre style="color: #333333; line-height: 16.25px; margin: 0px;"><span style="color: green;">// Branchless Logic</span>
<span style="color: blue;">static</span> <span style="color: #2b91af;">int</span> compareMessages(@NonNull Message m1, @NonNull Message m2) {
<span style="color: blue;">final</span> <span style="color: #2b91af;">long</span> when1 = m1.when;
<span style="color: blue;">final</span> <span style="color: #2b91af;">long</span> when2 = m2.when;
<span style="color: blue;">final</span> <span style="color: #2b91af;">long</span> insertSeq1 = m1.insertSeq;
<span style="color: blue;">final</span> <span style="color: #2b91af;">long</span> insertSeq2 = m2.insertSeq;
<span style="color: green;">// signum returns the sign (-1, 0, 1) of the argument,</span>
<span style="color: green;">// and is implemented as pure arithmetic:</span>
<span style="color: green;">// ((num >> 63) | (-num >>> 63))</span>
<span style="color: blue;">final</span> <span style="color: #2b91af;">int</span> whenSign = Long.signum(when1 - when2);
<span style="color: blue;">final</span> <span style="color: #2b91af;">int</span> insertSeqSign = Long.signum(insertSeq1 - insertSeq2);
<span style="color: green;">// whenSign takes precedence over insertSeqSign,</span>
<span style="color: green;">// so the formula below is such that insertSeqSign only matters</span>
<span style="color: green;">// as a tie-breaker if whenSign is 0.</span>
<span style="color: blue;">return</span> whenSign * 2 + insertSeqSign;
}</pre><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"><span id="docs-internal-guid-9074ac10-7fff-96c8-aade-ddfd0a0b56fb"></span></span></span></span></span></span></p><p dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;"><span style="font-family: inherit;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">To understand the optimization, </span><a href="https://godbolt.org/z/bvGh7aadG" style="text-decoration: none;"><span style="background-color: transparent; color: #1155cc; font-style: normal; font-variant: normal; font-weight: 400; text-decoration-skip-ink: none; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap;">disassemble the two examples in Compiler Explorer</span></a><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> and use </span><a href="https://llvm.org/docs/CommandGuide/llvm-mca.html" style="text-decoration: none;"><span style="background-color: transparent; color: #1155cc; font-style: normal; font-variant: normal; font-weight: 400; text-decoration-skip-ink: none; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap;">LLVM-MCA</span></a><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">, a CPU simulator that can generate an </span><a href="https://godbolt.org/z/EYxn6MasE" style="text-decoration: none;"><span style="background-color: transparent; color: #1155cc; font-style: normal; font-variant: normal; font-weight: 400; text-decoration-skip-ink: none; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap;">estimated timeline of CPU cycles</span></a><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"></span></span></span></span></span></p><pre style="color: #333333; line-height: 16.25px; margin: 0px;">The original code:
<span style="color: blue;">Index</span> 01234567890123
[0,0] DeER . . . sub x0, x2, x3
[0,1] D=eER. . . cmp x0, #0
[0,2] D==eER . . cset w0, ne
[0,3] .D==eER . . cneg w0, w0, lt
[0,4] .D===eER . . cmp w0, #0
[0,5] .D====eER . . b.le #12
[0,6] . DeE<span style="color: green;">---R . . mov w1, #1</span>
[0,7] . DeE<span style="color: green;">---R . . b #48</span>
[0,8] . D==eE-R . . tbz w0, #31, #12
[0,9] . DeE<span style="color: green;">--R . . mov w1, #-1</span>
[0,10] . DeE<span style="color: green;">--R . . b #36</span>
[0,11] . D=eE-R . . sub x0, x4, x5
[0,12] . D=eER . . cmp x0, #0
[0,13] . D==eER. . cset w0, ne
[0,14] . D===eER . cneg w0, w0, lt
[0,15] . D===eER . cmp w0, #0
[0,16] . D====eER. csetm w1, lt
[0,17] . D===eE-R. cmp w0, #0
[0,18] . .D===eER. csinc w1, w1, wzr, le
[0,19] . .D====eER mov x0, x1
[0,20] . .DeE<span style="color: green;">----R ret</span></pre><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"><span id="docs-internal-guid-32bdaff2-7fff-460b-89b2-ff05a7840904"><span style="color: black; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;">Note the one conditional branch, </span></span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">b.le</span><span face="Arial, sans-serif" style="color: black; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">, </span><span style="color: black; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;">which avoids comparing the</span></span><span face="Arial, sans-serif" style="color: black; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> </span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">insertSeq </span><span style="color: black; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;">fields if the result is already known from comparing the </span></span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">when</span><span style="color: black; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"> fields.</span></span></span></span></span></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"></span></span></span></span></span></p><pre style="color: #333333; line-height: 16.25px; margin: 0px;">The branchless code:
<span style="color: blue;">Index</span> 012345678
[0,0] DeER . . sub x0, x2, x3
[0,1] DeER . . sub x1, x4, x5
[0,2] D=eER. . cmp x0, #0
[0,3] .D=eER . cset w0, ne
[0,4] .D==eER . cneg w0, w0, lt
[0,5] .DeE<span style="color: green;">--R . cmp x1, #0</span>
[0,6] . DeE-R . cset w1, ne
[0,7] . D=eER . cneg w1, w1, lt
[0,8] . D==eeER <span style="color: blue;">add</span> w0, w1, w0, lsl #1
[0,9] . DeE<span style="color: green;">--R ret</span></pre><p dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;"><br /></span></span></p><p dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">Here, the branchless implementation takes fewer cycles and instructions than even the shortest path through the branchy code - it’s better in all cases. The faster implementation plus the elimination of mispredicted branches resulted in a 5x improvement in some of our benchmarks!</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"><br /><span style="color: black; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">However, this technique is not always applicable. Branchless approaches generally require doing work that will be thrown away, and if the branch is predictable most of the time, that wasted work can slow your code down. In addition, removing a branch often introduces a </span><span style="color: black; font-style: italic; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">data dependency</span><span style="color: black; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">. Modern CPUs execute multiple operations per cycle, but they can’t execute an instruction until its inputs from a previous instruction are ready. In contrast, a CPU can </span><span style="color: black; font-style: italic; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;">speculate</span><span style="color: black; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"> about data in branches, and work ahead if a branch is predicted correctly.</span></span></span></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"><span id="docs-internal-guid-e3d6b84f-7fff-6a01-6407-3e8247547a87"></span></span></span></span></span></span></p><h2 dir="ltr" style="line-height: 1.38; margin-bottom: 6pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 700; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit; font-size: x-large;">Testing and Validation</span></span></h2><p dir="ltr" style="line-height: 1.38; margin-bottom: 6pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">Validating the correctness of lock-free algorithms is notoriously difficult!</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 6pt; margin-top: 0pt;"><span style="font-family: inherit;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">In addition to standard unit tests for continuous validation during development, we also wrote rigorous </span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 700; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">stress tests</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> to verify queue invariants and to attempt to induce data races if they existed. In our test labs we could run millions of test instances on emulated devices and on real hardware.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 6pt; margin-top: 0pt;"><span style="font-family: inherit;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">With </span><a href="https://github.com/google/java-thread-sanitizer" style="text-decoration: none;" target="_blank"><span style="background-color: transparent; color: #1155cc; font-style: normal; font-variant: normal; font-weight: 700; text-decoration-skip-ink: none; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap;">Java ThreadSanitizer</span></a><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> (JTSan) instrumentation, we could use the same tests to also detect some data races in our code. JTSan did not find any problematic data races in DeliQueue, but - surprisingly -actually detected two concurrency bugs in the Robolectric framework, which we promptly fixed.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"><span id="docs-internal-guid-340bb8b1-7fff-ad8d-a726-461114d9db30"></span></span></span></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 6pt; margin-top: 6pt;"><span style="font-family: inherit;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">To improve our debugging capabilities, we built new </span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 700; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">analysis tools</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">. Below is an example showing an issue in Android platform code where one thread is overloading another thread with </span></span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">Message</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">s, causing a large backlog, visible in Perfetto thanks to the</span></span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">MessageQueue</span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">instrumentation feature that we added.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"><span id="docs-internal-guid-90c3fbfa-7fff-1a60-444e-9414aa435c50"><span face=""Google Sans Text", sans-serif" style="font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="border: none; display: inline-block; height: 471px; overflow: hidden; width: 610px;"><img alt="A screenshot of Perfetto UI, demonstrating flows and metadata for Messages being posted to a MessageQueue and delivered to a worker thread." src="https://blogger.googleusercontent.com/img/a/AVvXsEj6PDjipHRYCZTdaA0a9JAXFqW98l1DBKt1sJGKzSgxpYI9oevK5sjG7sdBHDCjwFyK9VZfTbmHmA5NK9Z5cJ5dLxFb7FP7Lw_07AmtaBT4yKs9Gsyz3QeeifZghO09Qk0ZTsbTIMVKmRrT34-VLQmB47qTTKPSm6BeSPiBSASooYIR5yR7AcoRV7utUKc=s16000" style="margin-left: 0px; margin-top: 0px;" /></span></span></span></span></span></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;">To enable </span></span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;">MessageQueue</span><span face=""Google Sans Text", sans-serif" style="color: #1f1f1f; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"> </span><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;">tracing in the</span></span><span face=""Google Sans Text", sans-serif" style="color: #1f1f1f; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"> </span><span style="color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;">system_server</span><span face=""Google Sans Text", sans-serif" style="color: #1f1f1f; font-size: 11pt; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"> </span><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;">process, include the following in your Perfetto configuration:</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"></span></span></span></span></span></p><pre style="color: #333333; line-height: 16.25px; margin: 0px;">data_sources {
config {
name: <span style="color: #a31515;">"track_event"</span>
target_buffer: 0 <span style="color: green;"># Change this per your buffers configuration</span>
track_event_config {
enabled_categories: <span style="color: #a31515;">"mq"</span>
}
}
}</pre><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit; font-size: x-large;"><span id="docs-internal-guid-9d707054-7fff-6660-7d56-bf741066320f"><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline;">Impact</span></span></span></span></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 6pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">DeliQueue improves system and app performance by eliminating locks from </span></span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">MessageQueue</span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">.</span></p><ul style="margin-bottom: 0px; margin-top: 0px; padding-inline-start: 48px;"><li aria-level="1" dir="ltr" style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: 400; list-style-type: disc; margin-left: -12.75pt; text-decoration: none; vertical-align: baseline; white-space: pre;"><p dir="ltr" role="presentation" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="font-family: inherit;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 700; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Synthetic benchmarks:</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> multi-threaded insertions into busy queues is up to </span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 700; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">5,000x faster</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> than the legacy</span></span><span face=""Google Sans Text", sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> </span><span style="background-color: transparent; color: #188038; font-family: "Roboto Mono", monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">MessageQueue</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">, thanks to improved concurrency (the Treiber stack) and faster insertions (the min-heap).</span></span></p></li><li aria-level="1" dir="ltr" style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; list-style-type: disc; margin-left: -12.75pt; text-decoration: none; vertical-align: baseline; white-space: pre;"><p dir="ltr" role="presentation" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="font-family: inherit;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">In </span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 700; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Perfetto traces acquired from internal beta testers</span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">, we see a reduction of 15% in app main thread time spent in lock contention.</span></span></p></li><li aria-level="1" dir="ltr" style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; list-style-type: disc; margin-left: -12.75pt; text-decoration: none; vertical-align: baseline; white-space: pre;"><p dir="ltr" role="presentation" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">On the same test devices, the reduced lock contention leads to significant improvements to the user experience, such as:</span></span></p></li><ul style="margin-bottom: 0px; margin-top: 0px; padding-inline-start: 48px;"><li aria-level="2" dir="ltr" style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; list-style-type: circle; text-decoration: none; vertical-align: baseline; white-space: pre;"><p dir="ltr" role="presentation" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">-4% missed frames in apps.</span></span></p></li><li aria-level="2" dir="ltr" style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; list-style-type: circle; text-decoration: none; vertical-align: baseline; white-space: pre;"><p dir="ltr" role="presentation" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">-7.7% missed frames in System UI and Launcher interactions.</span></span></p></li><li aria-level="2" dir="ltr" style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; list-style-type: circle; text-decoration: none; vertical-align: baseline; white-space: pre;"><p dir="ltr" role="presentation" style="line-height: 1.38; margin-bottom: 6pt; margin-top: 0pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">-9.1% in time from app startup to the first frame drawn, at the 95%ile.</span></span></p></li></ul></ul><h2 dir="ltr" style="line-height: 1.38; margin-bottom: 6pt; margin-top: 6pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 700; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit; font-size: large;">Next steps</span></span></h2><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">DeliQueue is rolling out to apps in Android 17. App developers should review preparing your app for the new lock-free </span></span><span style="background-color: transparent; color: #188038; font-family: 'Roboto Mono',monospace; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">MessageQueue</span><span face="'Google Sans Text',sans-serif" style="background-color: transparent; color: #1f1f1f; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;"> </span><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">on the Android Developers blog to learn how to test their apps.</span></span></p><h2 dir="ltr" style="line-height: 1.38; margin-bottom: 6pt; margin-top: 6pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 700; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit; font-size: large;">References</span></span></h2><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">[1] Treiber, R.K., 1986. Systems programming: Coping with parallelism. International Business Machines Incorporated, Thomas J. Watson Research Center.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"><span id="docs-internal-guid-fb570c95-7fff-a409-09f2-8f8855c4aabc"></span></span></span></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="background-color: transparent; color: #1f1f1f; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span style="font-family: inherit;">[2] Goetz, B., Peierls, T., Bloch, J., Bowbeer, J., Holmes, D., & Lea, D. (2006). Java Concurrency in Practice. Addison-Wesley Professional.</span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"><br /></span></span></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"><br /></span></span></span></span></span></p><p dir="ltr" style="line-height: 1.38; margin-bottom: 12pt; margin-top: 6pt;"><span style="color: #1f1f1f; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space-collapse: preserve;"><span style="font-family: inherit;"><span><span style="font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-emoji: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline;"><span style="font-family: inherit;"><br /></span></span></span></span></span></p></span>