RTEMS | Speed up the red-black tree rebalance (#5804)

Thu Oct 8 03:37:43 UTC 2026

Issue created by Sebastian Huber: https://gitlab.rtems.org/rtems/rtos/rtems/-/work_items/5804

## Summary

The red-black tree of the score uses the macros of `bsd-tree.h`. The
rebalance does more loads and stores than it needs. The table lists the extra
work.

| Operation | Extra work |
| --------- | ---------- |
| insert | stores the color of the root after each call |
| insert | tests the parent again after its last rotation |
| insert, removal | loads the left child for the side, then the right child |
| removal | stores the root color after the last rotation |
| removal | copies the whole node to its successor |

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.

## Proposed change

The series has four commits:

1. 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.
2. Translate the `bsd-tree.h` macros of the red-black tree into static inline
   functions and remove the header. The test `sptree01` checked only that the
   macros of the header did not clash with `<sys/tree.h>`, so it goes with the
   header.
3. Flatten the node of the red-black tree. The fields get the prefix `rbn_`.
4. 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.

A Qemu plugin counted the work per call on the Cortex-M7, for random keys and
64 nodes:

| Function | Count | Before | After |
| -------- | ----- | -----: | ----: |
| `_RBTree_Insert_color()` | instructions | 30.1 | 21.9 |
| | loads | 10.0 | 5.8 |
| | stores | 7.4 | 3.9 |
| `_RBTree_Extract()` | instructions | 41.8 | 37.9 |
| | loads | 16.3 | 11.2 |
| | stores | 12.1 | 9.0 |

## A/B measurement on hardware

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 `-falign-functions=64`, so that a function moves to
no other cache line between A and B.

| SoC | BSP | Processor |
| --- | --- | --------- |
| Zynq UltraScale+ MPSoC | `aarch64/zynqmp_apu` | Cortex-A53, 4 cores |
| Zynq UltraScale+ MPSoC | `arm/zynqmp_rpu_lock_step` | Cortex-R5F |
| SAMRH71 | `arm/samrh71_flexram` | Cortex-M7 |
| Zynq-7000 | `arm/xilinx_zynq_zc702` | Cortex-A9, 2 cores |
| GR740 | `sparc/gr740` | LEON4, 4 cores |
| PolarFire SoC | `riscv/mpfs_u54` | U54, 4 cores |
| PolarFire SoC | `riscv/mpfs_e51` | E51 |
| LS1046A | a BSP outside the RTEMS tree | Cortex-A72, 4 cores |

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.

### Hot cache

![Runtime change with a hot cache over the tree size](rbtree-speed-up-hot-cache.png)

Each value is the geometric mean of the B/A ratio over the eight tree sizes.
Negative values are faster.

| Board | Extract minimum | Extract random node | Insert random key | Insert ascending key |
| ----- | --------------: | ------------------: | ----------------: | -------------------: |
| ZynqMP APU, Cortex-A53 | -32.7 % | -11.6 % | -4.4 % | -4.8 % |
| ZynqMP RPU, Cortex-R5F | -13.6 % | -5.5 % | -3.1 % | -2.9 % |
| SAMRH71, Cortex-M7 | -11.8 % | -6.8 % | -4.9 % | -4.3 % |
| Zynq-7000, Cortex-A9 | -18.0 % | +7.0 % | -3.2 % | +0.5 % |
| GR740, LEON4 | +0.2 % | -9.7 % | -5.4 % | -3.8 % |
| PolarFire SoC, U54 (mean) | -22.1 % | -9.9 % | -4.7 % | +4.4 % |
| PolarFire SoC, E51 (mean) | -12.3 % | -10.0 % | -7.5 % | -5.1 % |
| LS1046A, Cortex-A72 (mean) | -26.1 % | -11.3 % | -1.8 % | +2.4 % |

For these four operations, A2 differs from A by at most 1.0 %.

### Dirty cache and full load

![Geometric mean of the runtime change per board and environment](rbtree-speed-up-environments.png)

### Operations which the change does not touch

![Runtime change of the unchanged operations and the noise](rbtree-speed-up-unchanged.png)

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 %.

## Regression tests

The tests `sprbtree01` and `ts-unit-no-clock-0` pass on the boards of all eight
targets, for each of the commits 2 to 4.

## Known regressions

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.

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.

-- 
View it on GitLab: https://gitlab.rtems.org/rtems/rtos/rtems/-/work_items/5804
You're receiving this email because of your account on gitlab.rtems.org. Unsubscribe from this thread: https://gitlab.rtems.org/-/namespace/49/sent_notifications/6-5f78oniymc0702efsmit50a38-1d/unsubscribe | Manage all notifications: https://gitlab.rtems.org/-/profile/notifications | Help: https://gitlab.rtems.org/help

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/bugs/attachments/20261008/afed5a5f/attachment-0001.htm>