To be frank I think you should stop thinking so much about it, go with something relatively straightforward for now, and profile it later. Don't spend lots of time writing code that might not be useful later. "Profile, don't think" :smile:

The nice thing about encapsulated interfaces is that you can replace the implementation later.

I'm still not sure what it is you're trying to do. It sounds a lot like you're just making a coroutine system that includes a number of blocking events, ranging from timers to external stimuli?

Is the STL pqueue a binary heap?

By the STL pqueue I assume you mean std::priority_queue. It's an adaptor over another container using the STL heap algorithm functions. They are not explicitly defined to be a binary heap, and I am unsure how they are done in common implementations. Google might be able to tell you with a little hunting.

Well basically I am trying to construct time delayed function calls which execute sequentially but at the same time points nondeterministically. It isnt really a coroutine system and unlike something like that the function call runs to completion or tosses out an exception (indicating the evaluation took too long- i guess some ppl call this semi-decidable). This is currently designed to be close to compatible with fluffos so that it can support a similar call out system (which is what this kind of system is called in LPC).

Not sure what you mean about non-determinism here. Do you mean that it will occasionally pull out random entries?


FWIW semi-decidability is something else; there's a difference between "too long for our purposes" and "might run forever".

Ah wasn't too sure what that term meant. I have seen it use to describe Cayenne's dependent type system which is like a block of LPC code can run indefinitely and thus my understanding has some kind of give up behavior. What is the precise definition of semi-decidable?

In terms of nondeterminism what I mean is the order per pulse is in principle irrelevant- though most implementations enforce an ordering on the same time step i.e. FIFO order but I suspect that this shouldnt really be relied upon. I.e. if you insert A before B insisting they both execute at time step 1000 A can be followed by B or B followed by A. Obviously this generalizes to n elements where any permutation is possible in theory (though in practice it is only nondeterministic in the sense that it's unspecified). I am not sure if in principle if implementing some NP algorithm in deterministic environments if you want all permutations to be equiprobable though this isn't really nondeterministic either.

A decidable algorithm is one that is guaranteed to terminate eventually. An undecidable algorithm is one that is not guaranteed to terminate. A semi-decidable algorithm is one that is guaranteed to terminate for positive answers, but not for negative answers. (Or, terminate for negative, but not for positive.)


I have to admit I'm not entirely sure what your problem is. Do you want FIFO behavior or not? You can guarantee it if you want, or choose not to. I suspect that choosing to not guarantee FIFO makes life somewhat easier, but it might not. Do you want all possible orderings to be equiprobable? Heh, have fun with that :tongue:

You programming-is-math people make me giggle. ;)

Basically all you're doing is assigning some kind of callback/event to a timer. There are many ways of dealing with that efficiently without some advanced data structure. For example, all you really need is a list of upcoming event times, each of which has a list of actual events. If you need quick removal, just make sure the event structures you're storing point back to their "bucket" for quick removal. The event times can be a circular buffer (with code to grow the buffer) and the event lists within can be simple vectors with a pool allocator. Implement it as a LIFO and it'll be pretty darn efficient, very easy to implement, and should cover all your needs.

Ah alright I guess perhaps Martin-Lof's dependent type theory is semi-decidable or some such in a different sense and Cayenne maybe just has some sort of escape hatch. I was aware of the definitions for decidability and undecidability but it was the first time I encountered the term semi-decidability.

Well this is the behavior I need to emulate given two time stamps for calls-

if ts(A) < ts(B). A executes before B.

if ts(A) = ts(B). even if A is queued before B there are no guarantees that A runs before B.

EDIT: per Cayenne I suspect maybe it might also mean it just runs indefinitely for negative answers per your description.

Semi-decidability is basically undecidability, it just happens that you can answer one class of questions for sure. If it hasn't terminated yet, you don't know if it's because you're in the decidable section and just haven't finished, or if you're in the undecidable section and might never terminate. Note that two semi-decidable algorithms each answering opposite questions give you a decidable algorithm (just run both in parallel, one is guaranteed to terminate eventually).

Anyhow, your case means that you can do FIFO, LIFO, "BLAFO", whatever. Unless you have to actually worry about some kind of fairness, do whatever is most expedient…

Basically the implementations I have looked at use something akin to a circular buffer and it's also what I am using (which holds the current -> current + m). The problem is how to deal with situations when the ts is outside this range. If the ts - current is very large would just growing the buffer work?

EDIT: On nm I think I see what you are saying though in principle it might be a bit slower on insertion than what I am doing at present.

If I did anything at all on my own here, and didn't reuse e.g. the STL's pqueue, I would just implement a chunk list and do the normal thing with chunk lists. If the chunk the element should go into is full, make a new chunk. You seem to think that the problem is fairly complex so it's possible I'm not understanding the subtlety, but it seems kind of straightforward to me.

Well actually I am using a chunk list as well but separately chaining for each time stamp. This part I have already implemented. Quick removal isn't really necessary and yes you could in theory have a pointer back to the call in question but this somewhat breaks the interface w.r.t. how calls are specified in removal operations in LPC which is either by a id number which acts as a handle or by the object it's called on and the function name.

As I said I am kind of new to this sort of thing so yeah might be a bit harder for me to grasp certain ideas at present- so I apologize for that.

What does it mean to "separately chain for each time stamp"?

(Why is quick removal not necessary? Wasn't that part of the point of this whole conversation?)

Well the data structure I am using is currently a circular buffer similar to what Elanthis describes but the difference being at present the size is fixed and a modulus is applied to the current time to lookup the relevant event time. Each entry of the circular array is of type ChunkList. So it is in that sense separately chained i.e. a linked list exists for each time stamp mod m. But I think I will change the implementation a bit so that this area is dynamic and get rid of the mod lookup.

Ideally you would like removal to be perhaps be rather fast since I cannot predict how ppl with use this stuff- but from grepping some mud libraries I noticed that the number of remove_call_out calls is pretty infrequent (but I am not sure if this is because it's slow so ppl dont use it or if there is generally limited use for such an operation).

Anyhow thanks guys. This discussion has been helpful and I have made some adjustments to my data structures per various suggestions you guys made.

So what you're really doing is more like a hash table, where the hash function is the time stamp.

Sounds like a classic timing wheel. Here's a pointer to a comparison of different implementations…

http://www.cse.wustl.edu/~cdgill/courses...

qua SocketMud