Re: Priority Queues?

[Geoff Leyland <geoff_leyland@...>]

Thanks everyone for the replies.  I hope you don't mind me collating  
them into one mail to reply to you all.

On 25/07/2007, at 5:59 PM, Wesley Smith wrote:
> Did you see that the LOOP library already has Priority Queues?
> http://loop.luaforge.net/docs_classlib.html#collection

No, I didn't.  I googled "lua priority queue" a fair bit, and missed  
this, so thanks!  Both the priority queue and all of loop look  
interesting.

On 26/07/2007, at 12:06 AM, Stefan Sandberg wrote:
> I don't really get the reason for having all that stuff on the c  
> side.. Why not just do the prio-queue in lua?

Because at the moment all that stuff is on the C side.  The  
simulation uses a std::priority_queue of C++ "functors".  I don't  
think that a long-term change to a Lua priority queue would  
necessarily be wrong, and I do think that getting a little discrete  
event simulation running in Lua would be a good learning exercise,  
but the incremental step for the existing code would be storing Lua  
callable objects in the C++ functors.  There may be a largish number  
of them, and I can think of reasons for storing many more.

> Also, as a general rule (especially since you seem to favour rapid  
> development/testing/etc as opposed to raw speed), don't  
> preemptively try to optimize like this until you're certain of what  
> is actually slow.. I would do the whole thing in lua, then pinpoint  
> any reason that would impact performance, and move that over to the  
> C side

I absolutely agree!  The code's been through one round of being  
written in a "fast to develop" language and then moving to something  
that's "fast to run".  Sorry for being a bit unclear on that.  At the  
moment, speed is increasingly important, but the event queue is not a  
bottleneck - but I don't want it to become one either!

On 26/07/2007, at 3:49 AM, Luis Carvalho wrote:
> Are you planning on making your work available?

Thanks Luis for the code!  As I've said a couple of times, I think I  
will do a "pure-lua" simulation as a learning exercise.

As for making the code available, the short answer is no - I don't  
even need to ask to know the client would never agree to that.
A slightly longer answer is that they have agreed to the use of some  
open source software, so why should they object to, say, an open- 
source discrete-event framework I might have had a hand in developing?
Having said that though, the simulation is largely adequate for them  
now, so I might find myself working on something completely different  
soon.

> This is a bit off-topic, but what kind of transport simulation  
> you're doing?
> Is it traffic network simulation? I used to be a transport engineer  
> and these
> things still entice my curiosity. :) Please keep us informed of  
> your progress.

I'm very happy to hear there's interest!  What are/were you involved in?

I don't think I'd call it a traffic simulation, maybe more of a fleet  
simulation.  A number of vehicles need to go to a considerably larger  
number of places.  How do you plan for that, and what happens in  
(simulated) reality when you execute those plans?  To my mind the  
interesting bits are the discrete event simulation engine and the  
shortest path engine, but to be honest, neither are state of the art  
at the moment - they're sufficient.

As I mentioned to Jerome, the idea of a DE framework using coroutines  
that can yield from any level in the stack is very cool - I have a  
friend using ?SimPy?, and he keeps running into Python's yield  
restriction, and of course in C++, every event is a separate function.
I imagine that coroutines are one of the reasons Lua is popular with  
game programmers?

Cheers and thanks to you all,
Geoff