Re: CF: object structure layout.

[Steve Fink <sfink@digital-integrity.com>]

> > Except that this makes insertions O(n), so you'd want to keep a separate
> > list of pointers to the wait nodes (in fact, you can take the wait nodes
> > out of the main queue and keep them in the separate list, then do
> > pointer comparisons to check for the wait nodes... but I digress.) Then
> > insertions are O(k), where k is the number of contiguous "chunks" of
> > events (equivalent to the number of queues in your scheme). (O(k) is
> > deceptive, because it would actually take <5 pointer traversals for
> > those first 5 chunks.) If that's a problem, you can reduce it to
> > O(log(k)) by using an array in place of a linked list, putting
> > timestamps (tickstamps?) in the array instead of wait counts, and
> > calling bsearch() to find the insertion point. (Well, creating a new
> > queue is still O(k), because you have to insert an element into the
> > array, but that's a quick memcpy() on a small, cache-efficient list).
> 
>  But if you are going to have these different insertion marks with pointers to
> where they are, why not just have these pointers be the queues themselves.  For
> example, something like:
> 
>  void *queues[50]
>  int queue_one=0;
> 
>  So the queueu you insert into is queue_one+tick_delay % 50.  Each tick, you
> increase queue_one by one, and wrap at 50.

I guess this is where my unfamiliarity with the code comes in. I was
assuming that the leftover queue (>50 ticks away, or whatever) would be
fairly long, so it would be expensive to scan through. Although with 50
queues, that's once every 50 ticks, so it can't be that bad. I'll take
your word for it that it's typically small. The array of pointers to
queues in my scheme can also use up less memory if it's dynamically
allocated, because it only uses a slot for every nonempty queue. But
sizeof(void*) * #queues * #activemaps sounds small anyway, so I have to
agree, it's not worth the complexity.
-
[you can put yourself on the announcement list only or unsubscribe altogether
by sending an email stating your wishes to crossfire-request@ifi.uio.no]