<!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: rgba(255,255,255,.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: rgba(255,255,255,.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 style="color: #777777;">
<a href="https://gitlab.rtems.org/Chandanuvm">Chandan U</a>
commented on a
discussion on <a href="https://gitlab.rtems.org/rtems/rtos/rtems/-/merge_requests/1164#note_148597">cpukit/include/rtems/score/coremsg.h</a>:
</p>
<table class="code gl-mb-5" style="border-spacing: 0; margin-bottom: 1rem; border-collapse: collapse; width: auto; font-family: monospace; font-size: 90%;" bgcolor="#ffffff" width="100%" cellpadding="0" cellspacing="0">
<tr class="line_holder" style="line-height: 1.6;">
<td class="old_line diff-line-num" data-linenumber="163" style="width: 35px; color: rgba(5,5,6,.24); border-right-width: 1px; border-right-color: #ececef; border-right-style: solid; padding: inherit;" align="right" bgcolor="#fbfafd">
163
</td>
<td class="new_line diff-line-num" data-linenumber="169" style="width: 35px; color: rgba(5,5,6,.24); border-right-width: 1px; border-right-color: #ececef; border-right-style: solid; padding: inherit;" align="right" bgcolor="#fbfafd">
169
</td>
<td class="line_content" style="padding: inherit;"><pre style="display: block; font-size: 14px; color: #3a383f; position: relative; 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: break-all; word-wrap: break-word; background-color: inherit; border-radius: 2px; margin: 0; padding: 0; border: inherit solid #dcdcde;"> <span class="line" data-lang="c"> <span class="n" style="color: #333333;">Chain_Control</span> <span class="n" style="color: #333333;">Inactive_messages</span><span class="p">;</span></span>
</pre></td>
</tr>
<tr class="line_holder" style="line-height: 1.6;">
<td class="old_line diff-line-num" data-linenumber="164" style="width: 35px; color: rgba(5,5,6,.24); border-right-width: 1px; border-right-color: #ececef; border-right-style: solid; padding: inherit;" align="right" bgcolor="#fbfafd">
164
</td>
<td class="new_line diff-line-num" data-linenumber="170" style="width: 35px; color: rgba(5,5,6,.24); border-right-width: 1px; border-right-color: #ececef; border-right-style: solid; padding: inherit;" align="right" bgcolor="#fbfafd">
170
</td>
<td class="line_content" style="padding: inherit;"><pre style="display: block; font-size: 14px; color: #3a383f; position: relative; 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: break-all; word-wrap: break-word; background-color: inherit; border-radius: 2px; margin: 0; padding: 0; border: inherit solid #dcdcde;"> <span class="line" data-lang="c"><span class="p">};</span></span>
</pre></td>
</tr>
<tr class="line_holder" style="line-height: 1.6;">
<td class="old_line diff-line-num" data-linenumber="165" style="width: 35px; color: rgba(5,5,6,.24); border-right-width: 1px; border-right-color: #ececef; border-right-style: solid; padding: inherit;" align="right" bgcolor="#fbfafd">
165
</td>
<td class="new_line diff-line-num" data-linenumber="171" style="width: 35px; color: rgba(5,5,6,.24); border-right-width: 1px; border-right-color: #ececef; border-right-style: solid; padding: inherit;" align="right" bgcolor="#fbfafd">
171
</td>
<td class="line_content" style="padding: inherit;"><pre style="display: block; font-size: 14px; color: #3a383f; position: relative; 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: break-all; word-wrap: break-word; background-color: inherit; border-radius: 2px; margin: 0; padding: 0; border: inherit solid #dcdcde;"> <span class="line" data-lang="c"></span>
</pre></td>
</tr>
<tr class="line_holder new" style="line-height: 1.6;">
<td class="old_line diff-line-num new" data-linenumber="166" style="width: 35px; color: rgba(5,5,6,.24); border-right-width: 1px; border-right-color: #c7f0d2; border-right-style: solid; padding: inherit;" align="right" bgcolor="#ddfbe6">
</td>
<td class="new_line diff-line-num new" data-linenumber="172" style="width: 35px; color: rgba(5,5,6,.24); border-right-width: 1px; border-right-color: #c7f0d2; border-right-style: solid; padding: inherit;" align="right" bgcolor="#ddfbe6">
172
</td>
<td class="line_content new" style="padding: inherit;" bgcolor="#ecfdf0"><pre style="display: block; font-size: 14px; color: #3a383f; position: relative; 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: break-all; word-wrap: break-word; background-color: inherit; border-radius: 2px; margin: 0; padding: 0; border: inherit solid #dcdcde;">+<span class="line" data-lang="c"><span class="cp" style="color: #999999; font-weight: 600;">#if defined( RTEMS_POSIX_API ) && ( MQ_PRIO_MAX <= 255 )</span></span>
</pre></td>
</tr>
<tr class="line_holder new" style="line-height: 1.6;">
<td class="old_line diff-line-num new" data-linenumber="166" style="width: 35px; color: rgba(5,5,6,.24); border-right-width: 1px; border-right-color: #c7f0d2; border-right-style: solid; padding: inherit;" align="right" bgcolor="#ddfbe6">
</td>
<td class="new_line diff-line-num new" data-linenumber="173" style="width: 35px; color: rgba(5,5,6,.24); border-right-width: 1px; border-right-color: #c7f0d2; border-right-style: solid; padding: inherit;" align="right" bgcolor="#ddfbe6">
173
</td>
<td class="line_content new" style="padding: inherit;" bgcolor="#ecfdf0"><pre style="display: block; font-size: 14px; color: #3a383f; position: relative; 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: break-all; word-wrap: break-word; background-color: inherit; border-radius: 2px; margin: 0; padding: 0; border: inherit solid #dcdcde;">+<span class="line" data-lang="c"><span class="k" style="font-weight: 600;">typedef</span> <span class="k" style="font-weight: 600;">struct</span> <span class="p">{</span></span>
</pre></td>
</tr>
<tr class="line_holder new" style="line-height: 1.6;">
<td class="old_line diff-line-num new" data-linenumber="166" style="width: 35px; color: rgba(5,5,6,.24); border-right-width: 1px; border-right-color: #c7f0d2; border-right-style: solid; padding: inherit;" align="right" bgcolor="#ddfbe6">
</td>
<td class="new_line diff-line-num new" data-linenumber="174" style="width: 35px; color: rgba(5,5,6,.24); border-right-width: 1px; border-right-color: #c7f0d2; border-right-style: solid; padding: inherit;" align="right" bgcolor="#ddfbe6">
174
</td>
<td class="line_content new" style="padding: inherit;" bgcolor="#ecfdf0"><pre style="display: block; font-size: 14px; color: #3a383f; position: relative; 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: break-all; word-wrap: break-word; background-color: inherit; border-radius: 2px; margin: 0; padding: 0; border: inherit solid #dcdcde;">+<span class="line" data-lang="c"> <span class="n" style="color: #333333;">CORE_message_queue_Control</span> <span class="n" style="color: #333333;">Base</span><span class="p">;</span></span>
</pre></td>
</tr>
<tr class="line_holder new" style="line-height: 1.6;">
<td class="old_line diff-line-num new" data-linenumber="166" style="width: 35px; color: rgba(5,5,6,.24); border-right-width: 1px; border-right-color: #c7f0d2; border-right-style: solid; padding: inherit;" align="right" bgcolor="#ddfbe6">
</td>
<td class="new_line diff-line-num new" data-linenumber="175" style="width: 35px; color: rgba(5,5,6,.24); border-right-width: 1px; border-right-color: #c7f0d2; border-right-style: solid; padding: inherit;" align="right" bgcolor="#ddfbe6">
175
</td>
<td class="line_content new" style="padding: inherit;" bgcolor="#ecfdf0"><pre style="display: block; font-size: 14px; color: #3a383f; position: relative; 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: break-all; word-wrap: break-word; background-color: inherit; border-radius: 2px; margin: 0; padding: 0; border: inherit solid #dcdcde;">+<span class="line" data-lang="c"> <span class="n" style="color: #333333;">Priority_bit_map_Control</span> <span class="n" style="color: #333333;">Queue</span><span class="p">;</span></span>
</pre></td>
</tr>
</table>
<div class="md" style="position: relative; z-index: 1; color: #3a383f; word-wrap: break-word;">
<p dir="auto" style="color: #3a383f; margin: 0 0 1rem;" align="initial">This is really insightful, <a href="https://gitlab.rtems.org/joel" title="Joel Sherrill" class="gfm gfm-project_member js-user-link" data-user="7" data-original="@joel" data-container="body" data-placement="top" data-reference-type="user" style="color: #284779; background-color: #cbe2f9; border-radius: .25rem; margin-top: 0; padding: 0 2px;">@joel</a> Thank you so much for the detailed explanation.</p>
<p dir="auto" style="color: #3a383f; margin: 0 0 1rem;" align="initial">I clearly understand now that the fixed array of Chain_Control which eats the memory of 384/ 768 bytes all the time in the bucket + bitmap implementation is really concerning for the real time systems, on the other hand RB tree using the advantage of the fixed priority limit (32) which reduces the worst case time complexity to log2(32)=5 (constant) and also has no static memory overhead unlike bucket + bitmap is the most optimal.</p>
<p dir="auto" style="color: #3a383f; margin: 0 0 1rem;" align="initial">I'll pivot to complete implementation of RB tree logic with maintaining backward compatibility.</p>
<p dir="auto" style="color: #3a383f; margin: 0 0 1rem;" align="initial">I'll rework on the patch and update the draft shortly.</p>
<p dir="auto" style="color: #3a383f; margin: 0;" align="initial">Thank you and <a href="https://gitlab.rtems.org/sebhub" title="Sebastian Huber" class="gfm gfm-project_member js-user-link" data-user="28" data-original="@sebhub" data-container="body" data-placement="top" data-reference-type="user" style="color: #284779; background-color: #cbe2f9; border-radius: .25rem; margin-top: 0; padding: 0 2px;">@sebhub</a> for the clear guidance on this architectural decision!</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/-/merge_requests/1164#note_148597">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/-/sent_notifications/3-8xwv072mjp1a0zf42camdfun4/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/-/merge_requests/1164#note_148597 at 1776305653
</span>
<script type="application/ld+json">{"@context":"http://schema.org","@type":"EmailMessage","action":{"@type":"ViewAction","name":"View Merge request","url":"https://gitlab.rtems.org/rtems/rtos/rtems/-/merge_requests/1164#note_148597"}}</script>
</p>
</div>
</body>
</html>