[asterisk-dev] [Code Review]: RFC for proposed astobj2 API container enhancements

[rmudgett]

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.digium.com/pipermail/asterisk-dev/attachments/20120330/286cab3b/attachment.htm>