<html>
<body>
<div style="font-family: Verdana, Arial, Helvetica, Sans-Serif;">
<table bgcolor="#f9f3c9" width="100%" cellpadding="8" style="border: 1px #c9c399 solid;">
<tr>
<td>
This is an automatically generated e-mail. To reply, visit:
<a href="https://reviewboard.asterisk.org/r/2883/">https://reviewboard.asterisk.org/r/2883/</a>
</td>
</tr>
</table>
<br />
<blockquote style="margin-left: 1em; border-left: 2px solid #d0d0d0; padding-left: 10px;">
<p style="margin-top: 0;">On September 26th, 2013, 12:26 p.m. CDT, <b>Mark Michelson</b> wrote:</p>
<blockquote style="margin-left: 1em; border-left: 2px solid #d0d0d0; padding-left: 10px;">
<table width="100%" border="0" bgcolor="white" style="border: 1px solid #C0C0C0; border-collapse: collapse; margin: 2px padding: 2px;">
<thead>
<tr>
<th colspan="4" bgcolor="#F0F0F0" style="border-bottom: 1px solid #C0C0C0; font-size: 9pt; padding: 4px 8px; text-align: left;">
<a href="https://reviewboard.asterisk.org/r/2883/diff/1/?file=46385#file46385line123" style="color: black; font-weight: bold; text-decoration: underline;">/team/dlee/taskprocessor-optimization/include/asterisk/vector.h</a>
<span style="font-weight: normal;">
(Diff revision 1)
</span>
</th>
</tr>
</thead>
<tbody>
<tr>
<th bgcolor="#b1ebb0" style="border-right: 1px solid #C0C0C0;" align="right"><font size="2"></font></th>
<td bgcolor="#c5ffc4" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "></pre></td>
<th bgcolor="#b1ebb0" style="border-left: 1px solid #C0C0C0; border-right: 1px solid #C0C0C0;" align="right"><font size="2">123</font></th>
<td bgcolor="#c5ffc4" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "><span class="cp">#define ast_vector_remove_unordered(vec, idx) do {<span class="tb"> </span><span class="tb"> </span>\</span></pre></td>
</tr>
<tr>
<th bgcolor="#b1ebb0" style="border-right: 1px solid #C0C0C0;" align="right"><font size="2"></font></th>
<td bgcolor="#c5ffc4" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "></pre></td>
<th bgcolor="#b1ebb0" style="border-left: 1px solid #C0C0C0; border-right: 1px solid #C0C0C0;" align="right"><font size="2">124</font></th>
<td bgcolor="#c5ffc4" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "><span class="cp"><span class="tb"> </span>size_t __idx = (idx);<span class="tb"> </span><span class="tb"> </span><span class="tb"> </span><span class="tb"> </span><span class="tb"> </span>\</span></pre></td>
</tr>
<tr>
<th bgcolor="#b1ebb0" style="border-right: 1px solid #C0C0C0;" align="right"><font size="2"></font></th>
<td bgcolor="#c5ffc4" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "></pre></td>
<th bgcolor="#b1ebb0" style="border-left: 1px solid #C0C0C0; border-right: 1px solid #C0C0C0;" align="right"><font size="2">125</font></th>
<td bgcolor="#c5ffc4" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "><span class="cp"><span class="tb"> </span>ast_assert(__idx < (vec).current);<span class="tb"> </span><span class="tb"> </span><span class="tb"> </span>\</span></pre></td>
</tr>
<tr>
<th bgcolor="#b1ebb0" style="border-right: 1px solid #C0C0C0;" align="right"><font size="2"></font></th>
<td bgcolor="#c5ffc4" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "></pre></td>
<th bgcolor="#b1ebb0" style="border-left: 1px solid #C0C0C0; border-right: 1px solid #C0C0C0;" align="right"><font size="2">126</font></th>
<td bgcolor="#c5ffc4" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "><span class="cp"><span class="tb"> </span>(vec).elems[__idx] = (vec).elems[--(vec).current];<span class="tb"> </span>\</span></pre></td>
</tr>
<tr>
<th bgcolor="#b1ebb0" style="border-right: 1px solid #C0C0C0;" align="right"><font size="2"></font></th>
<td bgcolor="#c5ffc4" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "></pre></td>
<th bgcolor="#b1ebb0" style="border-left: 1px solid #C0C0C0; border-right: 1px solid #C0C0C0;" align="right"><font size="2">127</font></th>
<td bgcolor="#c5ffc4" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "><span class="cp">} while (0)</span></pre></td>
</tr>
</tbody>
</table>
<pre style="white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">It's hard for me to imagine a situation where this would be useful or safe to use, since the index where a particular element is stored can potentially change.
In addition, couldn't this leak memory if the caller of ast_vector_remove_unordered() does not have a reference to the element being removed?
I like the idea of constant time removal from a vector, but in order to do it properly, I think you'd need to require that any item that can be placed in a vector be instrumented in some way to allow for the vector to track the element's index, like how AST_LIST_ENTRY() works for linked lists. That way, ast_vector_remove_elem_unordered() could work in constant time by using the stored index on the element (and also updating the stored index on the element that is moved).
Of course, this introduces the idea that vector operations can actually modify the elements in the vector, which may be something you were avoiding.</pre>
</blockquote>
</blockquote>
<pre style="margin-left: 1em; white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">Removal from the middle of a vector always requires the indexes of
elements to change. Otherwise, your vector will have a gap in the
middle.
Resource management is the responsibility of the caller, but I can see
where that can be difficult when removing by index. The macro can
return the removed element, so the caller can more easily unref/free
it.
As far as putting information in the element itself, the problem is
that an element may be in more than one vector, which makes storing
information in the element impossible.</pre>
<br />
<p>- David</p>
<br />
<p>On September 26th, 2013, 8:38 a.m. CDT, David Lee wrote:</p>
<table bgcolor="#fefadf" width="100%" cellspacing="0" cellpadding="8" style="background-image: url('https://reviewboard.asterisk.org/static/rb/images/review_request_box_top_bg.png'); background-position: left top; background-repeat: repeat-x; border: 1px black solid;">
<tr>
<td>
<div>Review request for Asterisk Developers.</div>
<div>By David Lee.</div>
<p style="color: grey;"><i>Updated Sept. 26, 2013, 8:38 a.m.</i></p>
<div style="margin-top: 1.5em;">
<b style="color: #575012; font-size: 10pt;">Repository: </b>
Asterisk
</div>
<h1 style="color: #575012; font-size: 10pt; margin-top: 1.5em;">Description </h1>
<table width="100%" bgcolor="#ffffff" cellspacing="0" cellpadding="10" style="border: 1px solid #b8b5a0">
<tr>
<td>
<pre style="margin: 0; padding: 0; white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">This patch optimizes how forwards are dispatched in Stasis.
Originally, forwards were dispatched as subscriptions that are invoked
on the publishing thread. This did not account for the vast number of
forwards we would end up having in the system, and the amount of work it
would take to walk though the forward subscriptions.
This patch modifies Stasis so that rather than walking the tree of
forwards on every dispatch, when forwards and subscriptions are changed,
the subscriber list for every topic in the tree is changed.
This has a couple of benefits. First, this reduces the workload of
dispatching messages. It also reduces contention when dispatching to
different topics that happen to forward to the same aggregation topic
(as happens with all of the channel, bridge and endpoint topics).
Since forwards are no longer subscriptions, the bulk of this patch is
simply changing stasis_subscription objects to stasis_forward objects
(which, admittedly, I should have done in the first place.)
Since this required me to yet again put in a growing array, I finally
abstracted that out into a set of ast_vector macros in
asterisk/vector.h.</pre>
</td>
</tr>
</table>
<h1 style="color: #575012; font-size: 10pt; margin-top: 1.5em;">Testing </h1>
<table width="100%" bgcolor="#ffffff" cellspacing="0" cellpadding="10" style="border: 1px solid #b8b5a0">
<tr>
<td>
<pre style="margin: 0; padding: 0; white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">Unit tests pass.
Performance testing to verify the speed up.</pre>
</td>
</tr>
</table>
<h1 style="color: #575012; font-size: 10pt; margin-top: 1.5em;">Diffs</b> </h1>
<ul style="margin-left: 3em; padding-left: 0;">
<li>/team/dlee/taskprocessor-optimization/apps/app_queue.c <span style="color: grey">(399869)</span></li>
<li>/team/dlee/taskprocessor-optimization/include/asterisk/stasis.h <span style="color: grey">(399869)</span></li>
<li>/team/dlee/taskprocessor-optimization/include/asterisk/vector.h <span style="color: grey">(PRE-CREATION)</span></li>
<li>/team/dlee/taskprocessor-optimization/main/cdr.c <span style="color: grey">(399869)</span></li>
<li>/team/dlee/taskprocessor-optimization/main/cel.c <span style="color: grey">(399869)</span></li>
<li>/team/dlee/taskprocessor-optimization/main/channel_internal_api.c <span style="color: grey">(399869)</span></li>
<li>/team/dlee/taskprocessor-optimization/main/manager.c <span style="color: grey">(399869)</span></li>
<li>/team/dlee/taskprocessor-optimization/main/manager_bridges.c <span style="color: grey">(399869)</span></li>
<li>/team/dlee/taskprocessor-optimization/main/manager_channels.c <span style="color: grey">(399869)</span></li>
<li>/team/dlee/taskprocessor-optimization/main/manager_mwi.c <span style="color: grey">(399869)</span></li>
<li>/team/dlee/taskprocessor-optimization/main/manager_system.c <span style="color: grey">(399869)</span></li>
<li>/team/dlee/taskprocessor-optimization/main/stasis.c <span style="color: grey">(399869)</span></li>
<li>/team/dlee/taskprocessor-optimization/main/stasis_cache_pattern.c <span style="color: grey">(399869)</span></li>
<li>/team/dlee/taskprocessor-optimization/res/stasis/app.c <span style="color: grey">(399869)</span></li>
<li>/team/dlee/taskprocessor-optimization/tests/test_stasis.c <span style="color: grey">(399869)</span></li>
<li>/team/dlee/taskprocessor-optimization/tests/test_stasis_endpoints.c <span style="color: grey">(399869)</span></li>
</ul>
<p><a href="https://reviewboard.asterisk.org/r/2883/diff/" style="margin-left: 3em;">View Diff</a></p>
</td>
</tr>
</table>
</div>
</body>
</html>