[prev in list] [next in list] [prev in thread] [next in thread]
List: asterisk-dev
Subject: Re: [asterisk-dev] [Code Review]: RFC for proposed astobj2 API container enhancements
From: "rmudgett" <reviewboard () asterisk ! org>
Date: 2012-03-30 15:44:22
Message-ID: 20120330154422.5119.19195 () hotblack ! digium ! com
[Download RAW message or body]
[Attachment #2 (multipart/alternative)]
> On March 29, 2012, 9:50 a.m., Mark Michelson wrote:
> > /trunk/include/asterisk/astobj2.h, line 1064
> > <https://reviewboard.asterisk.org/r/1835/diff/1/?file=26924#file26924line1064>
> >
> > A couple of things:
> >
> > 1) Does providing a sort_fn imply that the container is sorted? In other words, \
> > will every object linked into the container undergo sorting so that it is \
> > inserted in the proper spot? Based on the fact there appears to be no ao2_sort() \
> > function or anything similar, I'm assuming so. Would there be value to providing \
> > a sort_fn but not having the container be automatically sorted? I'm thinking of a \
> > case where the order of elements in a container typically does not matter but for \
> > the output of a CLI or AMI command, we want to list objects in a particular \
> > order.
> > 2) What does it mean to sort a hash table? Does the sort_fn only apply to items \
> > with duplicate keys (i.e. in the same bucket)? The phrase "buckets not sorted" is \
> > ambiguous in your parenthetical note.
>
> rmudgett wrote:
> The presence of the sort_fn implies that the container is sorted in some manner. \
> For hash containers this means that the hash buckets are sorted. Traversing over a \
> hash container still does not give a sorted output of all contents in the \
> container. Hashing works against sorting.
> Your normal use case of a container as unsorted but the CLI or AMI output being \
> sorted is the reason for the ao2_container_dup() function. You duplicate a hash \
> container into a sorted container. Problems will arise if the contained objects \
> change their search key values when in more than one container.
> A "sorted" hash container is only useful if you want to use the duplicate object \
> handling options. However, the degenerate hash container (only one bucket) is a \
> list which has more uses for the sorted property.
> The same could be said for traversal order over a hash container. The degenerate \
> hash container has more use for traversal order since it is a list.
> How is "NULL if buckets not sorted" ambiguous in that context? I changed the \
> wording to "NULL to not sort the buckets".
> Mark Michelson wrote:
> The ambiguity of "buckets not sorted" is that I don't know if you mean that the \
> contents within a single bucket is not sorted or if the buckets themselves \
> (somehow) are not sorted. You've answered this with your clarifying comments here \
> indicating that you mean the contents of the individual buckets.
> schmidts wrote:
> i dont know if this will still brake something but i had once the idea of adding \
> the "move to front" algorithm for objects in a bucket but this had broke some thing \
> in the code. When you are doing a sort order in a bucket it should also be possible \
> to add this move to front method also, right?
> Cause this could improve the access speed of objects in a bucket.
I had seriously considered adding a move-to-front option because you had attempted to \
add that feature. I rejected it for several reasons:
1) It is incompatible with rwlocks. Every read would modify the container and thus \
require the write lock to be obtained. 2) It would still break iterators. I came up \
with a way around the problem but the overhead needed did not seem worth it and \
iterators could not get the benefit. 3) It is a specialized list optimization.
When I get a chance to implement the red-black tree container, we might get an \
overall speed improvement from the channels container because a partial channel name \
search would not have to search the whole container.
One thing you might want to look at is the hashing algorithm used for the channels \
container and the number of buckets. It might be suffering from too many hash \
collisions, a non-prime number of buckets, or just too few buckets. Hash containers \
are supposed to have O(1) access. However, if you have too many collisions, you then \
have to consider the access time of the buckets. In this case a linked list which is \
O(n)/2.
- rmudgett
-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviewboard.asterisk.org/r/1835/#review5906
-----------------------------------------------------------
On March 29, 2012, 5:06 p.m., rmudgett wrote:
>
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> https://reviewboard.asterisk.org/r/1835/
> -----------------------------------------------------------
>
> (Updated March 29, 2012, 5:06 p.m.)
>
>
> Review request for Asterisk Developers, Mark Michelson and Matt Jordan.
>
>
> Summary
> -------
>
> RFC to add proposed API enhancements for containers.
>
> API allows for sorted containers, insertion options, duplicate handling options, \
> and traversal order options.
> Also has several documentation corrections.
>
>
> Diffs
> -----
>
> /trunk/include/asterisk/astobj2.h 360828
>
> Diff: https://reviewboard.asterisk.org/r/1835/diff
>
>
> Testing
> -------
>
> It compiles but doesn't link. This is a RFC. :)
>
>
> Thanks,
>
> rmudgett
>
>
[Attachment #5 (text/html)]
<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/1835/">https://reviewboard.asterisk.org/r/1835/</a>
</td>
</tr>
</table>
<br />
<blockquote style="margin-left: 1em; border-left: 2px solid #d0d0d0; padding-left: \
10px;"> <p style="margin-top: 0;">On March 29th, 2012, 9:50 a.m., <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/1835/diff/1/?file=26924#file26924line1064" \
style="color: black; font-weight: bold; text-decoration: \
underline;">/trunk/include/asterisk/astobj2.h</a> <span style="font-weight: \
normal;">
(Diff revision 1)
</span>
</th>
</tr>
</thead>
<tbody style="background-color: #e4d9cb; padding: 4px 8px; text-align: center;">
<tr>
<td colspan="4"><pre style="font-size: 8pt; line-height: 140%; margin: 0; ">struct \
ao2_container;</pre></td>
</tr>
</tbody>
<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">1036</font></th> <td bgcolor="#c5ffc4" \
width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "><span \
class="cm"> * \param sort_fn Pointer to a sort function. (NULL if buckets not \
sorted.)</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;">A couple of things:
1) Does providing a sort_fn imply that the container is sorted? In other words, will \
every object linked into the container undergo sorting so that it is inserted in the \
proper spot? Based on the fact there appears to be no ao2_sort() function or anything \
similar, I'm assuming so. Would there be value to providing a sort_fn but not \
having the container be automatically sorted? I'm thinking of a case where the \
order of elements in a container typically does not matter but for the output of a \
CLI or AMI command, we want to list objects in a particular order.
2) What does it mean to sort a hash table? Does the sort_fn only apply to items with \
duplicate keys (i.e. in the same bucket)? The phrase "buckets not sorted" \
is ambiguous in your parenthetical note.</pre> </blockquote>
<p>On March 29th, 2012, 12:19 p.m., <b>rmudgett</b> wrote:</p>
<blockquote style="margin-left: 1em; border-left: 2px solid #d0d0d0; padding-left: \
10px;"> <pre style="white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: \
-pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">The presence of the \
sort_fn implies that the container is sorted in some manner. For hash containers \
this means that the hash buckets are sorted. Traversing over a hash container still \
does not give a sorted output of all contents in the container. Hashing works \
against sorting.
Your normal use case of a container as unsorted but the CLI or AMI output being \
sorted is the reason for the ao2_container_dup() function. You duplicate a hash \
container into a sorted container. Problems will arise if the contained objects \
change their search key values when in more than one container.
A "sorted" hash container is only useful if you want to use the duplicate \
object handling options. However, the degenerate hash container (only one bucket) is \
a list which has more uses for the sorted property.
The same could be said for traversal order over a hash container. The degenerate \
hash container has more use for traversal order since it is a list.
How is "NULL if buckets not sorted" ambiguous in that context? I changed \
the wording to "NULL to not sort the buckets".</pre> </blockquote>
<p>On March 29th, 2012, 2:05 p.m., <b>Mark Michelson</b> wrote:</p>
<blockquote style="margin-left: 1em; border-left: 2px solid #d0d0d0; padding-left: \
10px;"> <pre style="white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: \
-pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">The ambiguity of \
"buckets not sorted" is that I don't know if you mean that the contents \
within a single bucket is not sorted or if the buckets themselves (somehow) are not \
sorted. You've answered this with your clarifying comments here indicating that \
you mean the contents of the individual buckets.</pre> </blockquote>
<p>On March 30th, 2012, 5:53 a.m., <b>schmidts</b> wrote:</p>
<blockquote style="margin-left: 1em; border-left: 2px solid #d0d0d0; padding-left: \
10px;"> <pre style="white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: \
-pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">i dont know if this will \
still brake something but i had once the idea of adding the "move to front" \
algorithm for objects in a bucket but this had broke some thing in the code. When you \
are doing a sort order in a bucket it should also be possible to add this move to \
front method also, right?
Cause this could improve the access speed of objects in a bucket.</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;">I had \
seriously considered adding a move-to-front option because you had attempted to add \
that feature. I rejected it for several reasons:
1) It is incompatible with rwlocks. Every read would modify the container and thus \
require the write lock to be obtained. 2) It would still break iterators. I came up \
with a way around the problem but the overhead needed did not seem worth it and \
iterators could not get the benefit. 3) It is a specialized list optimization.
When I get a chance to implement the red-black tree container, we might get an \
overall speed improvement from the channels container because a partial channel name \
search would not have to search the whole container.
One thing you might want to look at is the hashing algorithm used for the channels \
container and the number of buckets. It might be suffering from too many hash \
collisions, a non-prime number of buckets, or just too few buckets. Hash containers \
are supposed to have O(1) access. However, if you have too many collisions, you then \
have to consider the access time of the buckets. In this case a linked list which is \
O(n)/2.</pre> <br />
<p>- rmudgett</p>
<br />
<p>On March 29th, 2012, 5:06 p.m., rmudgett wrote:</p>
<table bgcolor="#fefadf" width="100%" cellspacing="0" cellpadding="8" \
style="background-image: \
url('https://reviewboard.asterisk.org/media/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, Mark Michelson and Matt Jordan.</div>
<div>By rmudgett.</div>
<p style="color: grey;"><i>Updated March 29, 2012, 5:06 p.m.</i></p>
<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;">RFC to add proposed API enhancements for containers.
API allows for sorted containers, insertion options, duplicate handling options, and \
traversal order options.
Also has several documentation corrections.</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;">It compiles but doesn't link. This is a RFC. :)</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>/trunk/include/asterisk/astobj2.h <span style="color: grey">(360828)</span></li>
</ul>
<p><a href="https://reviewboard.asterisk.org/r/1835/diff/" style="margin-left: \
3em;">View Diff</a></p>
</td>
</tr>
</table>
</div>
</body>
</html>
--
_____________________________________________________________________
-- Bandwidth and Colocation Provided by http://www.api-digital.com --
asterisk-dev mailing list
To UNSUBSCRIBE or update options visit:
http://lists.digium.com/mailman/listinfo/asterisk-dev
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic