<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd">
<html lang="en" style="--code-editor-font: var(--default-mono-font, "GitLab Mono"), JetBrains Mono, Menlo, DejaVu Sans Mono, Liberation Mono, Consolas, Ubuntu Mono, Courier New, andale mono, lucida console, monospace;">
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
<title>
GitLab
</title>
<style data-premailer="ignore" type="text/css">
a { color: #1068bf; }
</style>
<style>img {
max-width: 100%; height: auto;
}
body {
font-size: .875rem;
}
body {
-webkit-text-shadow: hsla(0,0%,100%,.01) 0 0 1px;
}
body {
font-family: "GitLab Sans",-apple-system,BlinkMacSystemFont,"Segoe UI",Roboto,"Noto Sans",Ubuntu,Cantarell,"Helvetica Neue",sans-serif,"Apple Color Emoji","Segoe UI Emoji","Segoe UI Symbol","Noto Color Emoji"; font-size: inherit;
}
</style>
</head>
<body style="font-size: inherit; -webkit-text-shadow: hsla(0,0%,100%,.01) 0 0 1px; font-family: "GitLab Sans",-apple-system,BlinkMacSystemFont,"Segoe UI",Roboto,"Noto Sans",Ubuntu,Cantarell,"Helvetica Neue",sans-serif,"Apple Color Emoji","Segoe UI Emoji","Segoe UI Symbol","Noto Color Emoji";">
<div class="content">
<p class="details" style="font-style: italic; color: #626168;">
Issue created by <a href="https://gitlab.rtems.org/sebhub">Sebastian Huber</a>: <a href="https://gitlab.rtems.org/rtems/rtos/rtems/-/work_items/5804">#5804</a>
</p>
<div class="md" style="position: relative; z-index: 1; color: #3a383f; word-wrap: break-word;">
<h2 id="user-content-summary" dir="auto" style="margin-top: 0px; margin-bottom: 10px;" align="initial">Summary<a href="#summary" aria-label="Link to heading 'Summary'" data-heading-content="Summary" class="anchor" style="margin-top: 0px;"></a>
</h2>
<p dir="auto" style="color: #3a383f; margin: 0px 0px 1rem;" align="initial">The red-black tree of the score uses the macros of <code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; margin-top: 0px; font-weight: inherit; overflow-wrap: break-word; white-space: break-spaces; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; word-break: keep-all; padding: 0.125rem 0.25rem;">bsd-tree.h</code>. The
rebalance does more loads and stores than it needs. The table lists the extra
work.</p>
<table dir="auto" style="border-spacing: 0; text-align: initial; color: #3a383f; width: auto; border-collapse: collapse; border-width: 0;">
<thead style="margin-top: 0px;">
<tr style="margin-top: 0px;">
<th style="line-height: 1.25rem; color: #18171d; margin-top: 0px; padding: 10px 16px; border-color: #dcdcde; border-style: solid; border-width: 1px 1px 0;" valign="top">Operation</th>
<th style="line-height: 1.25rem; color: #18171d; padding: 10px 16px; border-color: #dcdcde; border-style: solid; border-width: 1px 1px 0;" valign="top">Extra work</th>
</tr>
</thead>
<tbody>
<tr style="margin-top: 0px;">
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">insert</td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">stores the color of the root after each call</td>
</tr>
<tr>
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">insert</td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">tests the parent again after its last rotation</td>
</tr>
<tr>
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">insert, removal</td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">loads the left child for the side, then the right child</td>
</tr>
<tr>
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">removal</td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">stores the root color after the last rotation</td>
</tr>
<tr>
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">removal</td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">copies the whole node to its successor</td>
</tr>
</tbody>
</table>
<p dir="auto" style="color: #3a383f; margin: 0px 0px 1rem;" align="initial">The store of the root color keeps the tree control live across the loop. Each
call therefore saves and restores registers, also for a black parent. Every
thread queue, every watchdog and every scheduler with a tree pays this cost.</p>
<h2 id="user-content-proposed-change" dir="auto" style="margin-top: 20px; margin-bottom: 10px;" align="initial">Proposed change<a href="#proposed-change" aria-label="Link to heading 'Proposed change'" data-heading-content="Proposed change" class="anchor" style="margin-top: 0px;"></a>
</h2>
<p dir="auto" style="color: #3a383f; margin: 0px 0px 1rem;" align="initial">The series has four commits:</p>
<ol dir="auto" style="text-align: initial; margin: 0px 0px 1rem; padding: 0;">
<li style="margin-top: 0px; line-height: 1.6em; margin-left: 25px; padding-left: 3px;">Add a performance test of the red-black tree. It measures the minimum, the
successor, the replacement, the extraction of the minimum and of a random
node, and the insertion of a random and an ascending key. The tree sizes
are 1, 2, 3, 5, 13, 34, 89 and 233 nodes.</li>
<li style="line-height: 1.6em; margin-left: 25px; padding-left: 3px;">Translate the <code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; margin-top: 0px; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; white-space: pre-wrap; overflow-wrap: break-word; word-break: keep-all; padding: 0.125rem 0.25rem;">bsd-tree.h</code> macros of the red-black tree into static inline
functions and remove the header. The test <code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; white-space: pre-wrap; overflow-wrap: break-word; word-break: keep-all; padding: 0.125rem 0.25rem;">sptree01</code> checked only that the
macros of the header did not clash with <code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; white-space: pre-wrap; overflow-wrap: break-word; word-break: keep-all; padding: 0.125rem 0.25rem;"><sys/tree.h></code>, so it goes with the
header.</li>
<li style="line-height: 1.6em; margin-left: 25px; padding-left: 3px;">Flatten the node of the red-black tree. The fields get the prefix <code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; margin-top: 0px; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; white-space: pre-wrap; overflow-wrap: break-word; word-break: keep-all; padding: 0.125rem 0.25rem;">rbn_</code>.</li>
<li style="line-height: 1.6em; margin-left: 25px; padding-left: 3px;">Restructure the control flow of the rebalance, so that it loads and stores
only what it needs and returns as soon as the tree is balanced. The node
layout and the color values stay, so the watchdog keeps its state in the
color field.</li>
</ol>
<p dir="auto" style="color: #3a383f; margin: 0px 0px 1rem;" align="initial">A Qemu plugin counted the work per call on the Cortex-M7, for random keys and
64 nodes:</p>
<table dir="auto" style="border-spacing: 0; text-align: initial; color: #3a383f; width: auto; border-collapse: collapse; border-width: 0;">
<thead style="margin-top: 0px;">
<tr style="margin-top: 0px;">
<th style="line-height: 1.25rem; color: #18171d; margin-top: 0px; padding: 10px 16px; border-color: #dcdcde; border-style: solid; border-width: 1px 1px 0;" valign="top">Function</th>
<th style="line-height: 1.25rem; color: #18171d; padding: 10px 16px; border-color: #dcdcde; border-style: solid; border-width: 1px 1px 0;" valign="top">Count</th>
<th align="right" style="line-height: 1.25rem; color: #18171d; padding: 10px 16px; border-color: #dcdcde; border-style: solid; border-width: 1px 1px 0;" valign="top">Before</th>
<th align="right" style="line-height: 1.25rem; color: #18171d; padding: 10px 16px; border-color: #dcdcde; border-style: solid; border-width: 1px 1px 0;" valign="top">After</th>
</tr>
</thead>
<tbody>
<tr style="margin-top: 0px;">
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top"><code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; margin-top: 0px; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; white-space: pre-wrap; overflow-wrap: break-word; word-break: keep-all; padding: 0.125rem 0.25rem;">_RBTree_Insert_color()</code></td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">instructions</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">30.1</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">21.9</td>
</tr>
<tr>
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top"></td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">loads</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">10.0</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">5.8</td>
</tr>
<tr>
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top"></td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">stores</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">7.4</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">3.9</td>
</tr>
<tr>
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top"><code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; margin-top: 0px; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; white-space: pre-wrap; overflow-wrap: break-word; word-break: keep-all; padding: 0.125rem 0.25rem;">_RBTree_Extract()</code></td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">instructions</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">41.8</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">37.9</td>
</tr>
<tr>
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top"></td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">loads</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">16.3</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">11.2</td>
</tr>
<tr>
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top"></td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">stores</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">12.1</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">9.0</td>
</tr>
</tbody>
</table>
<h2 id="user-content-ab-measurement-on-hardware" dir="auto" style="margin-top: 20px; margin-bottom: 10px;" align="initial">A/B measurement on hardware<a href="#ab-measurement-on-hardware" aria-label="Link to heading 'A/B measurement on hardware'" data-heading-content="A/B measurement on hardware" class="anchor" style="margin-top: 0px;"></a>
</h2>
<p dir="auto" style="color: #3a383f; margin: 0px 0px 1rem;" align="initial">The A/B test ran the performance test of commit 1 on eight processors. A is commit
3 and B is commit 4. A second run of A, called A2, gives the noise. Each
executable was built with <code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; margin-top: 0px; font-weight: inherit; overflow-wrap: break-word; white-space: break-spaces; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; word-break: keep-all; padding: 0.125rem 0.25rem;">-falign-functions=64</code>, so that a function moves to
no other cache line between A and B.</p>
<table dir="auto" style="border-spacing: 0; text-align: initial; color: #3a383f; width: auto; border-collapse: collapse; border-width: 0;">
<thead style="margin-top: 0px;">
<tr style="margin-top: 0px;">
<th style="line-height: 1.25rem; color: #18171d; margin-top: 0px; padding: 10px 16px; border-color: #dcdcde; border-style: solid; border-width: 1px 1px 0;" valign="top">SoC</th>
<th style="line-height: 1.25rem; color: #18171d; padding: 10px 16px; border-color: #dcdcde; border-style: solid; border-width: 1px 1px 0;" valign="top">BSP</th>
<th style="line-height: 1.25rem; color: #18171d; padding: 10px 16px; border-color: #dcdcde; border-style: solid; border-width: 1px 1px 0;" valign="top">Processor</th>
</tr>
</thead>
<tbody>
<tr style="margin-top: 0px;">
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">Zynq UltraScale+ MPSoC</td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top"><code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; margin-top: 0px; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; white-space: pre-wrap; overflow-wrap: break-word; word-break: keep-all; padding: 0.125rem 0.25rem;">aarch64/zynqmp_apu</code></td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">Cortex-A53, 4 cores</td>
</tr>
<tr>
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">Zynq UltraScale+ MPSoC</td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top"><code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; margin-top: 0px; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; white-space: pre-wrap; overflow-wrap: break-word; word-break: keep-all; padding: 0.125rem 0.25rem;">arm/zynqmp_rpu_lock_step</code></td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">Cortex-R5F</td>
</tr>
<tr>
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">SAMRH71</td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top"><code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; margin-top: 0px; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; white-space: pre-wrap; overflow-wrap: break-word; word-break: keep-all; padding: 0.125rem 0.25rem;">arm/samrh71_flexram</code></td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">Cortex-M7</td>
</tr>
<tr>
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">Zynq-7000</td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top"><code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; margin-top: 0px; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; white-space: pre-wrap; overflow-wrap: break-word; word-break: keep-all; padding: 0.125rem 0.25rem;">arm/xilinx_zynq_zc702</code></td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">Cortex-A9, 2 cores</td>
</tr>
<tr>
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">GR740</td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top"><code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; margin-top: 0px; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; white-space: pre-wrap; overflow-wrap: break-word; word-break: keep-all; padding: 0.125rem 0.25rem;">sparc/gr740</code></td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">LEON4, 4 cores</td>
</tr>
<tr>
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">PolarFire SoC</td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top"><code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; margin-top: 0px; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; white-space: pre-wrap; overflow-wrap: break-word; word-break: keep-all; padding: 0.125rem 0.25rem;">riscv/mpfs_u54</code></td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">U54, 4 cores</td>
</tr>
<tr>
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">PolarFire SoC</td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top"><code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; margin-top: 0px; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; white-space: pre-wrap; overflow-wrap: break-word; word-break: keep-all; padding: 0.125rem 0.25rem;">riscv/mpfs_e51</code></td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">E51</td>
</tr>
<tr>
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">LS1046A</td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">a BSP outside the RTEMS tree</td>
<td style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">Cortex-A72, 4 cores</td>
</tr>
</tbody>
</table>
<p dir="auto" style="color: #3a383f; margin: 0px 0px 1rem;" align="initial">The rows use the median of 100 samples. The counters of the PolarFire SoC
and the LS1046A step by 1 µs and 40 ns. Their rows use the mean instead.</p>
<h3 id="user-content-hot-cache" dir="auto" style="margin-top: 1.5rem; margin-bottom: 1rem; font-weight: 600; font-size: 1.125rem; letter-spacing: inherit; line-height: 1.25; color: #18171d;" align="initial">Hot cache<a href="#hot-cache" aria-label="Link to heading 'Hot cache'" data-heading-content="Hot cache" class="anchor" style="margin-top: 0px;"></a>
</h3>
<p dir="auto" style="color: #3a383f; margin: 0px 0px 1rem;" align="initial"><a class="no-attachment-icon gfm" href="https://gitlab.rtems.org/rtems/rtos/rtems/-/blob/main/rbtree-speed-up-hot-cache.png" target="_blank" rel="noopener noreferrer" style="margin-top: 0px;"><img src="/rtems/rtos/rtems/-/blob/main/rbtree-speed-up-hot-cache.png" alt="Runtime change with a hot cache over the tree size" class="gfm" style="max-width: 100%; height: auto; margin-top: 0px; vertical-align: baseline;"></a></p>
<p dir="auto" style="color: #3a383f; margin: 0px 0px 1rem;" align="initial">Each value is the geometric mean of the B/A ratio over the eight tree sizes.
Negative values are faster.</p>
<table dir="auto" style="border-spacing: 0; text-align: initial; color: #3a383f; width: auto; border-collapse: collapse; border-width: 0;">
<thead style="margin-top: 0px;">
<tr style="margin-top: 0px;">
<th style="line-height: 1.25rem; color: #18171d; margin-top: 0px; padding: 10px 16px; border-color: #dcdcde; border-style: solid; border-width: 1px 1px 0;" valign="top">Board</th>
<th align="right" style="line-height: 1.25rem; color: #18171d; padding: 10px 16px; border-color: #dcdcde; border-style: solid; border-width: 1px 1px 0;" valign="top">Extract minimum</th>
<th align="right" style="line-height: 1.25rem; color: #18171d; padding: 10px 16px; border-color: #dcdcde; border-style: solid; border-width: 1px 1px 0;" valign="top">Extract random node</th>
<th align="right" style="line-height: 1.25rem; color: #18171d; padding: 10px 16px; border-color: #dcdcde; border-style: solid; border-width: 1px 1px 0;" valign="top">Insert random key</th>
<th align="right" style="line-height: 1.25rem; color: #18171d; padding: 10px 16px; border-color: #dcdcde; border-style: solid; border-width: 1px 1px 0;" valign="top">Insert ascending key</th>
</tr>
</thead>
<tbody>
<tr style="margin-top: 0px;">
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">ZynqMP APU, Cortex-A53</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-32.7 %</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-11.6 %</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-4.4 %</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-4.8 %</td>
</tr>
<tr>
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">ZynqMP RPU, Cortex-R5F</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-13.6 %</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-5.5 %</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-3.1 %</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-2.9 %</td>
</tr>
<tr>
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">SAMRH71, Cortex-M7</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-11.8 %</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-6.8 %</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-4.9 %</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-4.3 %</td>
</tr>
<tr>
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">Zynq-7000, Cortex-A9</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-18.0 %</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">+7.0 %</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-3.2 %</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">+0.5 %</td>
</tr>
<tr>
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">GR740, LEON4</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">+0.2 %</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-9.7 %</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-5.4 %</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-3.8 %</td>
</tr>
<tr>
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">PolarFire SoC, U54 (mean)</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-22.1 %</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-9.9 %</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-4.7 %</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">+4.4 %</td>
</tr>
<tr>
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">PolarFire SoC, E51 (mean)</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-12.3 %</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-10.0 %</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-7.5 %</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-5.1 %</td>
</tr>
<tr>
<td style="line-height: 1.25rem; margin-top: 0px; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">LS1046A, Cortex-A72 (mean)</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-26.1 %</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-11.3 %</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">-1.8 %</td>
<td align="right" style="line-height: 1.25rem; padding: 10px 16px; border: 1px solid #dcdcde;" valign="top">+2.4 %</td>
</tr>
</tbody>
</table>
<p dir="auto" style="color: #3a383f; margin: 0px 0px 1rem;" align="initial">For these four operations, A2 differs from A by at most 1.0 %.</p>
<h3 id="user-content-dirty-cache-and-full-load" dir="auto" style="margin-top: 1.5rem; margin-bottom: 1rem; font-weight: 600; font-size: 1.125rem; letter-spacing: inherit; line-height: 1.25; color: #18171d;" align="initial">Dirty cache and full load<a href="#dirty-cache-and-full-load" aria-label="Link to heading 'Dirty cache and full load'" data-heading-content="Dirty cache and full load" class="anchor" style="margin-top: 0px;"></a>
</h3>
<p dir="auto" style="color: #3a383f; margin: 0px 0px 1rem;" align="initial"><a class="no-attachment-icon gfm" href="https://gitlab.rtems.org/rtems/rtos/rtems/-/blob/main/rbtree-speed-up-environments.png" target="_blank" rel="noopener noreferrer" style="margin-top: 0px;"><img src="/rtems/rtos/rtems/-/blob/main/rbtree-speed-up-environments.png" alt="Geometric mean of the runtime change per board and environment" class="gfm" style="max-width: 100%; height: auto; margin-top: 0px; vertical-align: baseline;"></a></p>
<h3 id="user-content-operations-which-the-change-does-not-touch" dir="auto" style="margin-top: 1.5rem; margin-bottom: 1rem; font-weight: 600; font-size: 1.125rem; letter-spacing: inherit; line-height: 1.25; color: #18171d;" align="initial">Operations which the change does not touch<a href="#operations-which-the-change-does-not-touch" aria-label="Link to heading 'Operations which the change does not touch'" data-heading-content="Operations which the change does not touch" class="anchor" style="margin-top: 0px;"></a>
</h3>
<p dir="auto" style="color: #3a383f; margin: 0px 0px 1rem;" align="initial"><a class="no-attachment-icon gfm" href="https://gitlab.rtems.org/rtems/rtos/rtems/-/blob/main/rbtree-speed-up-unchanged.png" target="_blank" rel="noopener noreferrer" style="margin-top: 0px;"><img src="/rtems/rtos/rtems/-/blob/main/rbtree-speed-up-unchanged.png" alt="Runtime change of the unchanged operations and the noise" class="gfm" style="max-width: 100%; height: auto; margin-top: 0px; vertical-align: baseline;"></a></p>
<p dir="auto" style="color: #3a383f; margin: 0px 0px 1rem;" align="initial">The minimum, the successor and the replacement share no code with the
rebalance. Their change shows the effect of the code layout. It ranges from
-2.7 % to +5.1 %. The largest change is the successor on the SAMRH71, whose A2
noise reaches 4.2 %.</p>
<h2 id="user-content-regression-tests" dir="auto" style="margin-top: 20px; margin-bottom: 10px;" align="initial">Regression tests<a href="#regression-tests" aria-label="Link to heading 'Regression tests'" data-heading-content="Regression tests" class="anchor" style="margin-top: 0px;"></a>
</h2>
<p dir="auto" style="color: #3a383f; margin: 0px 0px 1rem;" align="initial">The tests <code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; margin-top: 0px; font-weight: inherit; overflow-wrap: break-word; white-space: break-spaces; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; word-break: keep-all; padding: 0.125rem 0.25rem;">sprbtree01</code> and <code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; font-weight: inherit; overflow-wrap: break-word; white-space: break-spaces; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; word-break: keep-all; padding: 0.125rem 0.25rem;">ts-unit-no-clock-0</code> pass on the boards of all eight
targets, for each of the commits 2 to 4.</p>
<h2 id="user-content-known-regressions" dir="auto" style="margin-top: 20px; margin-bottom: 10px;" align="initial">Known regressions<a href="#known-regressions" aria-label="Link to heading 'Known regressions'" data-heading-content="Known regressions" class="anchor" style="margin-top: 0px;"></a>
</h2>
<p dir="auto" style="color: #3a383f; margin: 0px 0px 1rem;" align="initial">The Zynq-7000 removes a random node 8 % to 20 % slower from three nodes. GCC
merges the side test of the child change with the first test of the
rebalance. The merged branch depends on the side of a random node, so the
branch predictor misses it.</p>
<p dir="auto" style="color: #3a383f; margin: 0px;" align="initial">The GR740 removes the minimum 6.1 % slower from two nodes. The LEON4 predicts
each branch as taken. The removal of a red leaf falls through two branches
directly after their compare, which costs two cycles each.</p>
</div>
</div>
<div class="footer" style="margin-top: 10px;">
<p style="font-size: small; color: #626168;">
—
<br>
<a href="https://gitlab.rtems.org/rtems/rtos/rtems/-/work_items/5804">View it on GitLab</a>.
<br>
You're receiving this email because of your account on <a target="_blank" rel="noopener noreferrer" href="https://gitlab.rtems.org">gitlab.rtems.org</a>. <a href="https://gitlab.rtems.org/-/namespace/49/sent_notifications/6-5f78oniymc0702efsmit50a38-1d/unsubscribe" target="_blank" rel="noopener noreferrer">Unsubscribe</a> from this thread · <a href="https://gitlab.rtems.org/-/profile/notifications" target="_blank" rel="noopener noreferrer" class="mng-notif-link">Manage all notifications</a> · <a href="https://gitlab.rtems.org/help" target="_blank" rel="noopener noreferrer" class="help-link">Help</a>
<span style="color: transparent; font-size: 0; display: none; overflow: hidden; opacity: 0; width: 0; height: 0; max-width: 0; max-height: 0;">
Notification message regarding https://gitlab.rtems.org/rtems/rtos/rtems/-/work_items/5804 at 1791430662
</span>
<script type="application/ld+json">{"@context":"http://schema.org","@type":"EmailMessage","action":{"@type":"ViewAction","name":"View Work item","url":"https://gitlab.rtems.org/rtems/rtos/rtems/-/work_items/5804"}}</script>
</p>
</div>
</body>
</html>