Re: CF: object structure layout.

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

> Steve Fink wrote:
> > Hmmm.... ok, so maybe I'm confused, but wouldn't 1..5 tick away queues
> > require a total of 15 queues? Or for 1..5000, 12.5 million? (The
> > every-tick queue, the every-other-tick queue that started at t0, the
> > every-other-tick queue that started at t0+1) And how to you keep track
> > of which 5 queues to look at each tick?
> 
>  What queue is the 1 queue would rotate along.  For example, lets have 6 queues
> - 1 to 5, and a 5+ queue.  We will letter them A-f for simplicity.
> 
>  On tick 1, queue A is the 1 tick away, B is 2 tick away, etc.
>  On tick 2, queue A is processed, queue B is the 1 tick away, C is 2 tick away,
> and A becomes 5 tick away.
>  On tick 3, process queue B, C is 1 tick away, etc.
> 
>  On tick 5, you process queue f - for stuff that will now run within the next 5
> ticks, you move it to queue A-E - for stuff still more than 5 ticks away, it
> stays on queue E.

Ah! Ok, I thought you were trying to optimize actions repeated every k
ticks by making queues in which nodes would never need to be dequeued or
enqueued if they always repeated with the same frequency. That's what
the scheme I outlined was for -- when you process a repeating action,
you don't even need to dequeue it.

I guess I don't know the code well enough to guess what really needs to
be optimized. But your scheme seems to do a lot of scanning of the f
queue, then dequeueing and requeueing the ones within 5 ticks. Why not
unify all those queues into a single queue with wait nodes separating
them? So if you label actions as letters and wait nodes as numbers, the
queue a-b-c-1-d-1-e-f-2-g would do actions a, b, and c on the next tick
(dequeueing them) and dequeue the wait(1) node, then action d on the
following tick, the e and f, then nothing (except decrementing the
wait(2) node to a wait(1) node), then g.

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

I would guess that the O(k) linear search would be fast enough. If not,
maybe you can merge this scheme with yours by keeping a certain number
of fixed queues (or pointers into the main queue) somehow. But you can't
get any faster for dequeuing.
-
[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]