httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Yann Ylavic <ylavic....@gmail.com>
Subject Re: Event and RINGs
Date Thu, 05 Mar 2015 09:20:15 GMT
On Wed, Mar 4, 2015 at 7:59 PM, Jim Jagielski <jim@jagunet.com> wrote:
> I am wondering if we are continuing to use RINGs in places
> where we should really migrate to using skiplists. afaict, we
> used RINGs initially because it was the only valid and available
> data structure we could use, but it was not idea.

Using a single skiplist for all timers in event would indeed make the
code cleaner and ease insertion and maintenance (to cleanup *all*
expired timers in a single loop), but would probably complexify
removal of individual timers (here some keepalive timer beacuse the
connection becomes active, there a write completion timer because the
filter chain is flushed, ...).
Currently with RINGs all these operations are O(1), skiplist would
make insertions and removals O(log n) (and still maintenance O(1)).

Btw, short term (which is not what you are talking about I guess),
skiplists in APR-1.5 are missing apr_skiplist_add(), so timers may
collide and apr_skiplist_insert() won't add them (which does not help
moving to them in several cases).
(That reminds me that things need to be backported to APR-1.6 before
it gets released ...)

> Even
> now, we aren't really using it as a FIFO queue and whenever
> we access it, we appear to be trying to do so in a sorted
> way (as related to time stamps)...

This is indeed not ideal, and it won't work as soon as we need to
handle dynamic timeouts (unknown at init time, so that we can't create
a RING per timeout)...

> I may end up doing
> some tests to see what the performance diffs would be if
> we instead just used skiplists.

+1

> Besides, I think all that RING macro junk is ugly :) :)

I personnaly love RINGs (despite pointer-type puning and terrific
code!), that's an excellent intrusive container :)
Not applicable everywhere though...

Regards,
Yann.

Mime
View raw message