# Non-contiguous update routine

This topic is 3732 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'm sorry if the title doesn't really fit my problem, but I just couldn't find a better way to describe it in a few words. So here's my actual problem: I have a Marketing Simulation where basically I have a few hundreds and thousands of what I like to call Entities, each defined through one or more Entity Types. If I say Entity I basically mean every thing which exists inside the simulation - be that a Location, an AI, a Market Commodity or whatever. Most of those Entities affect other Entities - this means that I need to call an update method for those Entities, however - with a few hundreds of thousand Entities, it is impossible to do that every simulation frame. Which is why I thought of implementing a non-contiguous update routine idiom (I came up with that term). Basically I want to only update an Entity whenever an update is actually necessary. As it is now however I struggle with a clean way to accomplish this - because it is very difficult to compute values for a time t2=500 when you don't really know which Entity could have changed your to-be-updated Entity between t1=200 and t2... Well, its all very confusing - and my brain is kinda starting to melt away by now, so I just figured I'd ask whether anyone knows of a programming pattern/idiom which describes all the problems I need to look out for when trying to implement something like this.

##### Share on other sites
I think maybe you are overcomplicating the situation.

Perhaps you could do a "continuous update" but just keep it cyclical.

T=100 Resources update
T=200 Suppliers update
T=300 Stores update
T=400 Consumers update
T=500 Repeat

Space your intervals out where processors keep up, then just set it up where your bottom rung on the overall ladder updates first, followed by the next etc. I know your spiderweb may be interconnected, but I do believe that you have an overall ladder in your marketing sim.

My 2cents.

##### Share on other sites
Sounds like you're over-engineering your program. I think you're splitting responsibilities up too much. For example, a location is a property of an entity, and I believe it's too low-level, too fundamental, to make it an actual entity of itself. Entity systems are usefull, but up to a certain point. You need to keep things practical. At some point, you need to stop forming abstractions and make something concrete - because that's what you're trying to accomplish in the end, something concrete. Abstraction is only a tool to reach that goal.

Anyway, it sounds like you'll want many of these entities to be event-driven. A particle emitter shouldn't do anything untill a trigger entity tells it to start spawning particles, for example. I've done something similar in the past by using a modified version of the observer design pattern for my entities, so entities could pass messages to other entities and I then only needed to update entities that required it. I haven't investigated the case much further though, but I'm sure there are others here who have more experience with this particular subject.

##### Share on other sites
Quote:
 Original post by MHOOOI have a Marketing Simulation where basically I have a few hundreds and thousands of what I like to call Entities, each defined through one or more Entity Types. [...]Basically I want to only update an Entity whenever an update is actually necessary. As it is now however I struggle with a clean way to accomplish this - because it is very difficult to compute values for a time t2=500 when you don't really know which Entity could have changed your to-be-updated Entity between t1=200 and t2...

At some point, your system must know. If you need to change an object, update it. If you don't change an object, don't update it. There are no invisible changes, after all.

Put objects into an update queue, ordered by next update time from soonest to latest. Each time, you start at the front of the queue and update any objects that are due for updates now. If they have knock-on effects on other objects, do them now as well. Once an object has been updated, remove it from the queue and add it back in with a new update time.

Beware - managing a dynamic list of hundreds of thousands of objects may actually be more resource intensive than just updating everything anyway, depending on how you do each of these things.

##### Share on other sites
Quote:
 Original post by robert4818[...]Space your intervals out where processors keep up, then just set it up where your bottom rung on the overall ladder updates first, followed by the next etc. I know your spiderweb may be interconnected, but I do believe that you have an overall ladder in your marketing sim.[...]

Yeah well, I thought about doing that as well, however this would restrict me to Updates based on the interval - and there are some Entities which are able to spawn other Entities at a given time t1. If that time t1 lies between two updates - and furthermore if the newly spawned Entity has its attributes changed just after spawning and still before the next update, I won't be able to figure out *when* exactly the attribute has changed.
This is actually one of the main problems I was facing.

Quote:
 Original post by Captain P[...]Sounds like you're over-engineering your program. I think you're splitting responsibilities up too much. For example, a location is a property of an entity, and I believe it's too low-level, too fundamental, to make it an actual entity of itself. Entity systems are usefull, but up to a certain point. You need to keep things practical. At some point, you need to stop forming abstractions and make something concrete - because that's what you're trying to accomplish in the end, something concrete. Abstraction is only a tool to reach that goal.[...]

Well, the Location was basically just an example.
The system in fact works somewhat different. Basically an Entity can have an arbitrary number of types - one of them a Location Type. It is somewhat like a parent class which defines the Entities properties and methods. This way I can easily reuse code for future Entities which are supposed to have the same behavior. Unless I actually assign values to, say, the x and y coordinates of the Location Type within an Entity, the default values of those properties from the Location Type are being used. So it's not like its a new Location Entity, but rather an Entity with the properties of a Location.
Puh... too much Entity...

Quote:
 Original post by Captain P[...]Anyway, it sounds like you'll want many of these entities to be event-driven. A particle emitter shouldn't do anything untill a trigger entity tells it to start spawning particles, for example. I've done something similar in the past by using a modified version of the observer design pattern for my entities, so entities could pass messages to other entities and I then only needed to update entities that required it. I haven't investigated the case much further though, but I'm sure there are others here who have more experience with this particular subject.

Well, I thought about using an approach like this as well, however using this method, I still need to check when exactly an event happened - and in order to check for that, I'd need to implement a contiguous update routine :x
At least with the system as it is now, all possible events come from values which are changing *all the time*, so basically at any possible time t there *could* be a new value v(t).
But after thinking a lot while writing this here, I see there is really no other method of implementing this... I guess it all comes down to machine power in the end :/

##### Share on other sites
You need to think if you need to update all the entities every time. If you do, you are bound to some form of queue. If not mabe it's worth to use some kind of event system. Think of event brokers and event subscribers. That way you can update only those entities which are affected by certain entity, and after proper implementation it's easy to manage whole tree of events triggered by one change.

##### Share on other sites
Quote:
 You need to think if you need to update all the entities every time. If you do, you are bound to some form of queue. If not mabe it's worth to use some kind of event system.

A queue IS an event system; the event system par excellence, one could say. As Kylotan said, the benefit of updating all entities according to a fixed time step lies in NOT having to maintain a queue.

Maintaining a priority queue for n events takes O(nlogn) operations, and it has to be processed serially. The benefit of an event queue is that you can use timesteps of arbitrarily small granularity.

Updating every entity once per timestep (or efficient variants thereof, like maintaining an unsorted list of 'dirty' entities per timestep and only updating those) takes O(n) time and can be distributed across several processors very simply. Disadvantage is you have to fix a timestep size that is not too small, because you have to actually traverse tsteps.

Quote:
 Yeah well, I thought about doing that as well, however this would restrict me to Updates based on the interval - and there are some Entities which are able to spawn other Entities at a given time t1. If that time t1 lies between two updates - and furthermore if the newly spawned Entity has its attributes changed just after spawning and still before the next update, I won't be able to figure out *when* exactly the attribute has changed.This is actually one of the main problems I was facing.

You need to stop thinking about 'entities', or rather 'Entities' and start thinking about events. The way you figure out when things happen is by keeping track of the pending events in an ordered fashion. So even if an event triggers others, you'll always be guaranteed to process the correct event next.

Of course, if two events occur at exactly the same time, you run into ambiguities...

The event model assumes you have things that can recieve an event and act upon it (by sending other events, for example).

So, each thing needs, apart from any logic specific to itself:

1) a list of things it knows about and can send messages to;

To synchronize events we need

2) a priority queue.

The time to process a message will be the time the receiver takes to process it + a time proportional to logn, where n is the number of messages currently in flight.

Voila. In fact, writing an event system is so simple I'll give you an example in python. Imagine we want to model a network of chatty people who all know each other. They react to being told gossip in two ways:

1) If they didn't know the gossip already, they call two of their friends (it takes a random amount of time to complete a call) and tell them the gossip.

2) If they did know the gossip, they tell the person who told them that they're boring.

Next post brings the code.

Edit: Man, it's my day for stupid mistakes. Good night.

[Edited by - Anonymous P on October 31, 2007 10:54:09 AM]

##### Share on other sites
Here's a simple example; notice that most of the code (the people class) is incidental to the actual event queue mechanism, which is very straightforward if you have a heap algorithm. Both Python and C++'s STL have them, and writing your own is trivial.

from heapq import heappush, heappopfrom random import sample, randintevent_q = []# A message is a tuple of the form (time, sender, receiver, mtype, message)def send(time, sender, receiver, mtype, message):    heappush(event_q, (time, sender, receiver, mtype, message))def next_event():    m = heappop(event_q)    m[2].receive_message(m)    class Thing:    def __init__(self, name, known_things = []):        self.known_things = known_things        self.name = name    def receive_message(self, m):        time, sender, receiver, mtype, message = m        print self.name, ' received ', message.ljust(40), ' from ', sender.name, ' at ', timeclass Person(Thing):    def __init__(self, name):        Thing.__init__(self, name)        self.known_gossip = set()    def set_known(self, known):        self.known_things = known    def receive_message(self, m):        Thing.receive_message(self, m)        time, sender, receiver, mtype, message = m        if mtype == 'gossip':            if message in self.known_gossip:                time += 0.1                send(time, self, sender, 'snarky', "I knew that %s" % message)            else:                self.known_gossip.add(message)                for friend in sample(filter(lambda x: self != x, self.known_things), 2):                    time += randint(10, 15)                    send(time, self, friend, 'gossip', message)        elif mtype == 'snarky':            time += 0.1            send(time, self, sender, 'abuse', "Yeah well I knew about yo mamma")        elif mtype == 'abuse':            pass #Gossipers get scared of strong language        # Create peoplepeople = [Person(name) for name in ['Joe  ', 'Jim  ', 'Jane ', 'Sally', 'Larry', 'Sue  ']]for person in people:    person.set_known(people)heappush(event_q, (0, people[0], people[1], 'gossip', 'Events are the new black'))heappush(event_q, (0, people[0], people[1], 'gossip', 'Bears shit in the woods'))while len(event_q) > 0:    next_event()

We see very edifying conversations emerging:

Jim    received  Bears shit in the woods                   from  Joe    at  0Jim    received  Events are the new black                  from  Joe    at  0Jane   received  Events are the new black                  from  Jim    at  14Sally  received  Bears shit in the woods                   from  Jim    at  14Joe    received  Events are the new black                  from  Jim    at  25Jane   received  Bears shit in the woods                   from  Sally  at  27Jane   received  Bears shit in the woods                   from  Jim    at  28Sally  received  Events are the new black                  from  Jane   at  28Jim    received  I knew that Bears shit in the woods       from  Jane   at  28.1Jane   received  Yeah well I knew about yo mamma           from  Jim    at  28.2Sally  received  Events are the new black                  from  Joe    at  37Joe    received  I knew that Events are the new black      from  Sally  at  37.1Sally  received  Yeah well I knew about yo mamma           from  Joe    at  37.2Jim    received  Events are the new black                  from  Sally  at  39Sally  received  I knew that Events are the new black      from  Jim    at  39.1Jim    received  Yeah well I knew about yo mamma           from  Sally  at  39.2Joe    received  Events are the new black                  from  Jane   at  40Jane   received  I knew that Events are the new black      from  Joe    at  40.1Joe    received  Yeah well I knew about yo mamma           from  Jane   at  40.2Joe    received  Bears shit in the woods                   from  Jane   at  41Larry  received  Bears shit in the woods                   from  Sally  at  41Sue    received  Events are the new black                  from  Joe    at  48Larry  received  Bears shit in the woods                   from  Jane   at  51Jane   received  I knew that Bears shit in the woods       from  Larry  at  51.1Larry  received  Yeah well I knew about yo mamma           from  Jane   at  51.2Sally  received  Bears shit in the woods                   from  Larry  at  53Larry  received  I knew that Bears shit in the woods       from  Sally  at  53.1Sally  received  Yeah well I knew about yo mamma           from  Larry  at  53.2Joe    received  Events are the new black                  from  Sally  at  54Sally  received  I knew that Events are the new black      from  Joe    at  54.1Joe    received  Yeah well I knew about yo mamma           from  Sally  at  54.2Sally  received  Bears shit in the woods                   from  Joe    at  55Joe    received  I knew that Bears shit in the woods       from  Sally  at  55.1Sally  received  Yeah well I knew about yo mamma           from  Joe    at  55.2Jim    received  Events are the new black                  from  Sue    at  62Sue    received  I knew that Events are the new black      from  Jim    at  62.1Jim    received  Yeah well I knew about yo mamma           from  Sue    at  62.2Joe    received  Bears shit in the woods                   from  Larry  at  64Larry  received  I knew that Bears shit in the woods       from  Joe    at  64.1Joe    received  Yeah well I knew about yo mamma           from  Larry  at  64.2Jim    received  Bears shit in the woods                   from  Joe    at  68Joe    received  I knew that Bears shit in the woods       from  Jim    at  68.1Jim    received  Yeah well I knew about yo mamma           from  Joe    at  68.2Joe    received  Events are the new black                  from  Sue    at  72Sue    received  I knew that Events are the new black      from  Joe    at  72.1Joe    received  Yeah well I knew about yo mamma           from  Sue    at  72.2

Minor bugfix edit.

[Edited by - Anonymous P on October 31, 2007 10:00:58 AM]

##### Share on other sites
So, after thinking a lot and reading your post over and over again, and trying to make it fit with what I had in mind, I kinda get this one huge problem pop up in my head.
Lets make this into an example.

"We have one power plant which produces 20 energy units per hour. Furthermore we have one car factory which manufactures cars. Needless to say, the latter requires Energy, say 15 energy units per hour. All is fine and well, the power plant produces more than the car factory can use up. But what if we now, add a new car factory which is connected to the same power plant?
We'd have energy consumption of 30 units per hour and energy production of 20 units per hour. So lets say the energy storage was at 30 units the moment the second factory has been connected to the power plant. Basically every hour, we'd lose 10 units of energy - after 3 hours chaos breaks loose as there is not enough energy. Needless to say, the car factories are going to work less efficient, as there is simply not enough energy. If we split it evenly, both get 10 energy units per hour - instead of 15, so they work with an efficiency of ~66.66%."

I kinda struggle with an implementation of this. But then again, this is really an implementation specific detail which I am only going to solve if I adapt it to the code I already have o.O

I'll have to try and think some more if I want to implement this.

So errm,
thanks all :)

##### Share on other sites
Quote:
 So, after thinking a lot and reading your post over and over again, and trying to make it fit with what I had in mind, I kinda get this one huge problem pop up in my head. (example snipped)
Yes; it's the problem of managing dependencies in a concurrent system. You don't seem to realize that this is basically what 'simulation' boils down to. :)

Because electricity is limited, we can't just let an arbitrary amount of factories request (and get) 15 watts at the same time; they would be using electricity that doesn't exist, and thus leave our system in an inconsistent state (more electricity is being used than is being produced).

Basically, if a factory consumes electricy, that electricity will be unavailable to other factories. That's fine, we might say: every time a factory uses electricity, just decrement the amount of electricity available. If a factory requests electricity, check that there is enough before satisfying the request.

But multiple factories may request electricity at the same time, and all the individual checks will succeed, and all factories will be given electricity!

One way to solve this issue is to introduce explicit locks around operations which have to know about each other (as in typical multithreaded programming). We know that the 'request electricity and decrement the amount available for others' operation needs to be atomic. If requests are serviced one after another instead of in parallel, we will never give out electricity we don't have. So we say, 'perform the check and give out electricity to one user at a time'.

The problem with this approach is that we must explicitly keep track of the interactions that may conflict, and lock them. That can quickly become unmanageable if we have lots of interactions with different requirements (as in modeling).

ANOTHER way (the event-actor way I described above) says: 'the only atomic operations are those performed by an object internally. Messages are asynchronous.' This means that an object can't assume anything about the state of another at any point in time; it can only react to messages from it. This makes simulations easier; it just requires you to think carefully about what states objects can have, because local change of state is the only guaranteed atomic operation.

Still another way is to permit events that are not local to an object; this looks like mutiple dispatch (eg Lisp provides it) and solves the problem elegantly.

So, how would we write the factories-powerplant model in the Thing formalism? We would bear in mind the atomicity of local ops.

##### Share on other sites
from heapq import heappush, heappopfrom random import sample, randintevent_q = []# A message is a tuple of the form (time, sender, receiver, mtype, message)def send(time, sender, receiver, mtype, message):    heappush(event_q, (time, sender, receiver, mtype, message))def next_event():    m = heappop(event_q)    m[2].receive_message(m)    class Thing:    def __init__(self, name, known_things = []):        self.known_things = known_things        self.name = name    def receive_message(self, m):        time, sender, receiver, mtype, message = m        print self.name, ' received ', mtype, message, ' from ', sender.name, ' at ', timeclass Powerplant(Thing):    def __init__(self, name, electricity_per_hour):        Thing.__init__(self, name)        self.eph = electricity_per_hour        self.remaining_e = electricity_per_hour    def receive_message(self, m):        #Thing.receive_message(self, m)        time, sender, receiver, mtype, message = m        if mtype == 'new hour':            self.remaining_e = self.eph            send(time + 1, self, self, 'new hour', None)                    elif mtype == 'request':            if self.remaining_e >= message:                send(time, self, sender, 'electricity', message)                self.remaining_e -= message            else:                send(time, self, sender, 'electricity', 0)class Factory(Thing):    def __init__(self, name, cars_per_hour, powerplant):        Thing.__init__(self, name)        self.cph = cars_per_hour        self.powerplant = powerplant        self.cars_made = 0        self.state = 'idle'    def receive_message(self, m):        #Thing.receive_message(self, m)        time, sender, receiver, mtype, message = m        if mtype == 'start':            send(time, self, self.powerplant, 'request', 1)        elif mtype == 'electricity':            if message == 1:                send(time + (1. / self.cph), self, self, 'finish', None)                            elif message == 0:                print self.name, ' waiting for juice', time                print                send(time + 1, self, self.powerplant, 'request', 1)        elif mtype == 'finish':            print self.name, ' finished car.', time            print            self.cars_made += 1            send(time, self, self, 'start', None)                        powerplant = Powerplant('E0', 10)factory_0 = Factory('F0', 5, powerplant)factory_1 = Factory('F1', 20, powerplant)boss = Thing('The Boss')heappush(event_q, (0, boss, factory_0, 'start', 'I need more money for my extravagant lifestyle'))heappush(event_q, (1, boss, powerplant, 'new hour', 'start the engines'))heappush(event_q, (2, boss, factory_1, 'start', 'My secretary needs a fur coat'))while len(event_q) > 0:    next_event()

Let's watch the output:

F0  finished car. 0.2F0  finished car. 0.4F0  finished car. 0.6F0  finished car. 0.8F0  finished car. 1.0F0  finished car. 1.2F0  finished car. 1.4F0  finished car. 1.6F0  finished car. 1.8F0  finished car. 2.0F1  finished car. 2.05F1  finished car. 2.1F1  finished car. 2.15F1  finished car. 2.2F0  finished car. 2.2F1  finished car. 2.25F1  finished car. 2.3F1  finished car. 2.35F1  finished car. 2.4F0  finished car. 2.4F0  waiting for juice 2.4F1  finished car. 2.45F1  waiting for juice 2.45F1  finished car. 3.5F1  finished car. 3.55

[Edited by - Anonymous P on November 3, 2007 2:23:44 PM]

##### Share on other sites
That is a wonderful example! Demonstrating perfectly one of my initial fears.
It's the continuous-check. Basically the factory needs to request energy all the time. But what if we have so many factories, that the simulation engine will no longer be able to keep up? Basically all events would get processed later. This would make the simulation proceed at a slower speed. If I want to keep the speed 'real time', I'd need to, say, produce 2 cars in one event. But you can't do that, cause you won't know whether the supplier (the powerplant) will actually have enough energy for 2 cars - and you can't just request more energy, as this would warp the requesting party into an undefined time-frame in the future.

So I figured what I really need, is a system which will make updates less dependant on how often they're being done and more dependant on... well, complexity I guess? At least that's what my head is telling me...
Basically the following code puts all Consumers and Producers into a 'context' (yeah, it's probably a very bad way of describing it, but oh well...). This way we can check whether we have too much consumption or not. If we do have too much consumption, the consumers will be notified of that fact when it happens - no sooner, no later. It is possible the consumption may change before that again, so I'd need to re-calculate everything and move/delete the events. Using this technique I can basically reduce the amount of events needed, however it does add a lot of complexity to it, so I'm sure I am missing a lot of drawbacks...
Oh well, I'll find out if I keep going with it.

Here's my approach at things anyway, it's probably very bugged still, but it works fine as an example (for which it is already huge enough :/) :

from collections import defaultdictfrom heapq import heappush, heappopimport weakrefevent_q = []# A message is a tuple of the form (time, sender, receiver, mtype, message)def send(time, sender, receiver, mtype, message):    heappush(event_q, (time, sender, receiver, mtype, message))    # make sure to sort the list    event_q.sort()def next_event():    m = heappop(event_q)    m[2].receive_message(m)class DefaultValueDict(dict):	def __init__(self, default=None):		self._Default = default		def __missing__(self, offset):		import copy		try:			self[offset] = copy.deepcopy(self._Default)		except Exception, e:			self[offset] = self._Default		return self[offset]	class Thing(object):	def __init__(self, name):		self._name = name		self._efficiency = 1.0		self._state = 'uninitialized'			def receive_message(self, m):		globalTime, sender, receiver, mtype, message = m				if mtype=='init':			self._state = 'active'			print "t=%04.2f: %s (a %s) is starting up"%			(globalTime, self._name, self.__class__.__name__)class Consumer(Thing):	def __init__(self, name, storage, consumdict={}):		Thing.__init__(self, name)		self._storage = storage				hash(self)		self._storage.Insert(self)				# a dict:		# [commodity] = consumption_amount_per_second		self._consumedict = consumdict			def _compute_highest_possible_eff(self):		# now we'll check the highest possible eff we can get		highest_possible_eff = 1.0		for commodity, eff in self._effOnCommodity.iteritems():			if highest_possible_eff > eff:				highest_possible_eff=eff		return highest_possible_eff				def receive_message(self, m):		Thing.receive_message(self, m)		globalTime, sender, receiver, mtype, message = m				if mtype=='init':			self.__lastUpdate = globalTime			self._effOnCommodity = DefaultValueDict(1.0)		elif mtype=='update' and self._state!='uninitialized':			time_passed = globalTime - self.__lastUpdate			for commodity, amount_per_sec in self._consumedict.iteritems():				self._storage._commodities[commodity] -= (amount_per_sec*time_passed)*self._efficiency				print "t=%04.2f: %s consumed %s units of %s over %s seconds (%s%% eff)"%				(globalTime, self._name,(amount_per_sec*time_passed)*self._efficiency, 				commodity, time_passed, self._efficiency*100)			self.__lastUpdate = globalTime						elif mtype=='shortage' and self._state!='uninitialized':			# oh noes, shortage sucks. But we'll have to deal with it			commodity, new_amount = message			# now that we lack a certain commodity, we won't be able			# to operate at full efficiency. We need to calculate			# our new efficiency.			we_need = self._consumedict[commodity] # this is the amount which we need for 100% eff			we_get = new_amount # this is the amount which we get			# if we take what we get, and calc how many times one percent of what we need fits in, we get our eff			new_efficiency = (we_get/(we_need/100.0)/100.0) # 1.0 for 100%, 0.5 for 50%, ...			# save the commodity-efficiency			self._effOnCommodity[commodity] = new_efficiency						# now we'll get the highest possible eff we can get			oldeff = self._efficiency			self._efficiency = self._compute_highest_possible_eff()			print "t=%04.2f: %s changed efficiency from %s to %s, as there is shortage on %s"% 			(globalTime, self._name, oldeff, self._efficiency, commodity)					elif mtype=='shortage_end' and self._state!='uninitialized':			commodity = m			self._effOnCommodity[commodity] = 1						oldeff = self._efficiency			self._efficiency = self._compute_highest_possible_eff()			print "t=%04.2f: %s changed efficiency from %s to %s, as there is no more shortage on %s"% 				(globalTime, self._name, oldeff, self._efficiency, commodity)				class Producer(Thing):	def __init__(self, name, storage, producedict={}):		Thing.__init__(self, name)		self._storage = storage				self._storage.Insert(self)		self.__lastUpdate = 0				# a dict:		# [commodity] = production_amount_per_second		self._producedict = producedict	def receive_message(self, m):		Thing.receive_message(self, m)		globalTime, sender, receiver, mtype, message = m				if mtype=='init':			self.__lastUpdate = globalTime		elif mtype=='update' and self._state!='uninitialized':			time_passed = globalTime - self.__lastUpdate			for commodity, amount_per_sec in self._producedict.iteritems():				self._storage._commodities[commodity] += 					(amount_per_sec*time_passed)*self._efficiency				print "t=%04.2f: %s produced %s units of %s over %s seconds (%s%% eff)"%					(globalTime, self._name,(amount_per_sec*time_passed)*self._efficiency, 					commodity, time_passed, self._efficiency*100)			self.__lastUpdate = globalTime			class Storage(Thing):	def __init__(self, name):		Thing.__init__(self, name)		self._things = []		self._commodities = defaultdict(float)		# we need first, a context to access consumer and producer		# these will be a		# [commodity] => list of things		self._consumer = defaultdict(str)		self._producer = defaultdict(str)		# then, we need a context in order to easily see whether there		# is shortage on something		# [commodity] => total_plus_or_minus		self._producecontext = defaultdict(float)		self._consumecontext = defaultdict(float)		self._context = defaultdict(float)			def Insert(self, thing):		if self._things.count(thing)==0:			self._things.append(thing)		# make sure pure consumer are always at the end of the list		# and producer at the top		pure_producer = []		pure_consumer = []		whatever = []		for thing in self._things:			if isinstance(thing, Producer) and not isinstance(thing, Consumer):				pure_producer.append(thing)			elif isinstance(thing, Consumer) and not isinstance(thing, Producer):				pure_consumer.append(thing)			else:				whatever.append(thing)		self._things = pure_producer+whatever+pure_consumer	def Remove(self, thing):		self._things.remove(thing)			def receive_message(self, m):		Thing.receive_message(self, m)		globalTime, sender, receiver, mtype, message = m				if mtype=='update' and self._state!='uninitialized':			# make sure to also (manually) update all things			for thing in self._things:				m = (globalTime, self, thing, 'update', None)				thing.receive_message(m)							producecontext = defaultdict(float)			consumecontext = defaultdict(float)			context = defaultdict(float)			consumer = defaultdict(list)			producer = defaultdict(list)						for thing in self._things:				if isinstance(thing, Producer):					for commodity, amount_per_sec in thing._producedict.iteritems():						producer[commodity].append(thing)						producecontext[commodity] += amount_per_sec						context[commodity] += amount_per_sec 					if isinstance(thing, Consumer):					for commodity, amount_per_sec in thing._consumedict.iteritems():						consumer[commodity].append(thing)						consumecontext[commodity] += amount_per_sec						context[commodity] -= amount_per_sec									# with the new context, we can see where something has changed			#  and can thus determine which things we need to notify of			#  changes.						# context can now, in comparision with old self._context, have:			#  o new things, which are producer/consumer						# now that we have the context, we can determine where we could			# run into problems. Basically all contexts which are negative			# values, are commodities which we don't have enough of.			for commodity, amount in context.iteritems():				if self._context[commodity]==amount: continue # if its nothing new, ignore it				if amount&lt;0: # oh noes, shortage					# now we need to compute when that shortage is going to happen...					storage = self._commodities[commodity]					shortage_happens_in = abs(storage/amount) # in seconds					# how much energy will every thing get from then on?					# first, the amount of things which want some energy:					amountConsumerThings = len(consumer[commodity])					# then the average energy everyone gets (lets split it evenly)					average_shortage_energy = producecontext[commodity]/amountConsumerThings					# now we'll queue a new message for every thing					print "t=%04.2f: Shortage in %ss detected for %s. Curr. Prod./s: %s; Curr. Cons./s: %s; Storage: %s."% 						(globalTime, shortage_happens_in, commodity, producecontext[commodity], consumecontext[commodity], 						self._commodities[commodity])					for thing in consumer[commodity]:						send(globalTime + shortage_happens_in, self, thing, 'shortage', (commodity, average_shortage_energy))				else: # no shortage					# check whether we had shortage before					if self._context[commodity]<amount:						# if we did have, make sure to tell everyone we got						# everything running again!						if self._consumer.has_key(commodity):							for thing in self._consumer[commodity]:								send(globalTime, self, thing, 'shortage_end', commodity)			self._producer = producer			self._consumer = consumer			self._context = context			self._producecontext = producecontext			self._consumecontext = consumecontextclass PowerPlant(Producer):	def __init__(self, name, storage, ene_per_hour):		producedict = {					'Energy':(ene_per_hour/60.0)/60.0 # we want per_second values					}		Producer.__init__(self, name, storage, producedict)class Factory(Consumer, Producer):	def __init__(self, name, storage, cars_per_hour, ene_per_hour):		producedict = {					'Car': (cars_per_hour/60.0)/60.0 # we want per_second values					}		consumedict = {					'Energy':(ene_per_hour/60.0)/60.0 # we want per_second values					}		Producer.__init__(self, name, storage, producedict)		Consumer.__init__(self, name, storage, consumedict)			def receive_message(self, m):		Consumer.receive_message(self, m)		Producer.receive_message(self, m)Boss = Thing('Boss')Storage1 = Storage('Main Storage')PowerPlant1 = PowerPlant('Power Plant', Storage1, 20000)Factory1 = Factory('Main Factory', Storage1, 3, 15000)Factory2 = Factory('Sub Factory', Storage1, 2, 10000)heappush(event_q, (0, Boss, Storage1, 'init', None))heappush(event_q, (0, Boss, PowerPlant1, 'init', None))heappush(event_q, (0, Boss, Factory1, 'init', None))# after half an hour we initialize another factory,# at this point the...# Power Plant should have produced 10 Energy# Main Factory should have produced 1.5 Cars and consumed 7.5 Energyheappush(event_q, (1800, Boss, Storage1, 'update', None))heappush(event_q, (1800, Boss, Factory2, 'init', None))heappush(event_q, (3600, Boss, Storage1, 'update', None))while len(event_q) > 0:    next_event()

This gives the following output:
t=0.00: Main Factory (a Factory) is starting upt=0.00: Main Factory (a Factory) is starting upt=0.00: Power Plant (a PowerPlant) is starting upt=0.00: Main Storage (a Storage) is starting upt=1800.00: Sub Factory (a Factory) is starting upt=1800.00: Sub Factory (a Factory) is starting upt=1800.00: Power Plant produced 10000.0 units of Energy over 1800 seconds (100.0% eff)t=1800.00: Main Factory consumed 7500.0 units of Energy over 1800 seconds (100.0% eff)t=1800.00: Main Factory produced 1.5 units of Car over 1800 seconds (100.0% eff)t=1800.00: Sub Factory consumed 0.0 units of Energy over 0 seconds (100.0% eff)t=1800.00: Sub Factory produced 0.0 units of Car over 0 seconds (100.0% eff)t=1800.00: Shortage in 1800.0s detected for Energy. Curr. Prod./s: 5.55555555556; Curr. Cons./s: 6.94444444444; Storage: 2500.0.t=3600.00: Main Factory changed efficiency from 1.0 to 0.666666666667, as there is shortage on Energyt=3600.00: Sub Factory changed efficiency from 1.0 to 1.0, as there is shortage on Energyt=3600.00: Power Plant produced 10000.0 units of Energy over 1800 seconds (100.0% eff)t=3600.00: Main Factory consumed 5000.0 units of Energy over 1800 seconds (66.6666666667% eff)t=3600.00: Main Factory produced 1.0 units of Car over 1800 seconds (66.6666666667% eff)t=3600.00: Sub Factory consumed 5000.0 units of Energy over 1800 seconds (100.0% eff)t=3600.00: Sub Factory produced 1.0 units of Car over 1800 seconds (100.0% eff)

Adjustments to make the code not break the page layout[/Edit]

##### Share on other sites
Quote:
 So I figured what I really need, is a system which will make updates less dependant on how often they're being done and more dependant on... well, complexity I guess?
That's a good intuition.

Updates are dependent on their effects; you can decouple a subset of the simulation from the rest as long as the subset doesn't interact with the other subset.

Efficiently finding out when you can decouple a subset from a constantly changing graph is nontrivial; garbage collection algorithms are basically solving the same problem: finding connected components in a graph. Depending on the communication patterns of your actors, it might not even result in any gain; see the gossip example.

Quote:
 Basically the following code puts all Consumers and Producers into a 'context' (yeah, it's probably a very bad way of describing it, but oh well...). This way we can check whether we have too much consumption or not. If we do have too much consumption, the consumers will be notified of that fact when it happens - no sooner, no later. It is possible the consumption may change before that again, so I'd need to re-calculate everything and move/delete the events. Using this technique I can basically reduce the amount of events needed, however it does add a lot of complexity to it, so I'm sure I am missing a lot of drawbacks...

Congratulations. You have just reinvented speculative execution. :)

Don't go down that path. Whether it works or not depends on the locality of the interactions between your actors (maybe their nature is NOT amenable to speculative execution in the first place) and on your capacity to write a fast AND effective speculative execution subsystem, which is no small task; it'd detect connected subgraphs that are relatively isolated and speculate on those.

Manually hardcoding which components to speculate on and performing consistency checks and synchronization yourself will mire you in a sea of bugs, and might make your simulation actually slower. Don't. It's hard enough to correctly specify the individual actors' behaviour.

Remember: the reason you are running a simulation is precisely because simpler and more efficient models CAN'T model your problem set: the factories-powerplant model for example is a system of differential equations that can be solved very very efficiently for any point in time; but if you need it to interact with nonlinear and discrete actors...

My advice: stop worrying about performance and write a straightforward system that works correctly. Nothing is slower than a system that is not actually running yet ;)

I'd say, write it in C++; python isn't designed to run this kind of code quickly, and standard C++ has heap algorithms and objects too so it shouldn't be too annoying.

Once you've gotten the prototype working, you can assess whether your goals are reasonable; if you envision a system that displays, say, two million entities interacting in real time with an average of 10 messages per second per entity, you're probably out of luck unless you want to write a thesis. Never mind processing the messages; ram latency will kill you on the nasty nonlocal access patterns to simply pull each entities' data into cpu cache 10 times per second.

If this is the scale of your project, you'll have to abandon the event queue approach, fix a time step, and simply update all actors in parallel at every step. That'll scale because it turns a serially dependent problem into an embarrassingly parallel one with cache-friendly memory access patterns (you can throw multicore at it or even run it on a graphics card if you're careful with the design), but has its own problems and annoyances, like layout of actors in memory...

##### Share on other sites
Quote:
 Original post by Anonymous P[...]Congratulations. You have just reinvented speculative execution. :)Don't go down that path. Whether it works or not depends on the locality of the interactions between your actors (maybe their nature is NOT amenable to speculative execution in the first place) and on your capacity to write a fast AND effective speculative execution subsystem, which is no small task; it'd detect connected subgraphs that are relatively isolated and speculate on those.[...]

lol :/
That's like telling me to stop working on my system just because it's too complicated. Then again, after reading through some articles on speculative execution it really is a non-trivial task for, say, a factory which generates something based on a random value... though in such cases, I could still use the conventional approach of continuous updates. But I see your point in this... which is bad, cause now I really don't know what to do - this will result in me trying to think of a solution all night long... god, I won't be able to sleep, mh.

Quote:
 Original post by Anonymous P[...]My advice: stop worrying about performance and write a straightforward system that works correctly. Nothing is slower than a system that is not actually running yet ;) [...]

Well, in fact, I started with an approach like that. But I soon came to the conclusion that it would not work out. With the simulation running longer and longer, more Entities would get created, thus resulting in more updates per frame. I got rather fast to 400'000 updates per frame, with implementing merely the 'factory'-like behavior above. So I started experimenting from there on, looking for other ways to implement it.
Actually I don't really like the update-per-frame approach, because this is in fact something which I believe is bad coding style (read that here a lot of times :x ). You want your simulation to be based on time, and not on frames. Be it 4 or 400 frames passing, the result should be the same if the passed time is the same.

Quote:
 Original post by Anonymous P[...]I'd say, write it in C++; python isn't designed to run this kind of code quickly, and standard C++ has heap algorithms and objects too so it shouldn't be too annoying. [...]

Unfortunately, the whole entity system is written in python, because I want it to be dynamically changeable. I thought of implementing everything in C++ before, but I'd just loose too much flexibility - unless I use python for scripts which are called by the C++ application, and those are the scripts which would be updated every frame. So I might just as well skip out on the C++ part altogether.

Quote:
 Original post by Anonymous P[...]Once you've gotten the prototype working, you can assess whether your goals are reasonable; if you envision a system that displays, say, two million entities interacting in real time with an average of 10 messages per second per entity, you're probably out of luck unless you want to write a thesis. Never mind processing the messages; ram latency will kill you on the nasty nonlocal access patterns to simply pull each entities' data into cpu cache 10 times per second.If this is the scale of your project, you'll have to abandon the event queue approach, fix a time step, and simply update all actors in parallel at every step. That'll scale because it turns a serially dependent problem into an embarrassingly parallel one with cache-friendly memory access patterns (you can throw multicore at it or even run it on a graphics card if you're careful with the design), but has its own problems and annoyances, like layout of actors in memory...

In the end, I guess I won't come around the use of a continuous update/check. I'll try to mix this together with an event/observer/SigSlot pattern, so at least those entities which only act on changes in their environment don't use up too much cpu power.
I'll have to think of getting new hardware though, lol.

Thanks for the great help,
you saved me from one huge headache.

##### Share on other sites
Quote:
 That's like telling me to stop working on my system just because it's too complicated.
Not at all. I just think it'd be wise to attack it from another angle.

Quote:
 Actually I don't really like the update-per-frame approach, because this is in fact something which I believe is bad coding style (read that here a lot of times :x ). You want your simulation to be based on time, and not on frames. Be it 4 or 400 frames passing, the result should be the same if the passed time is the same.
The question is completely unrelated to coding style.

It is a question of fixing the reference frame of 'time' in the model. A frame needn't correspond to a screen refresh.

Notice that in the event model, we are using floating point numbers, which have finite precision and consequently ALSO define a timestep (it is less obvious, but they certainly do).

What's worse, the implicit timestep precision changes as the floating point number gets bigger! We might confidently set a delta of 0.1 for one event, 0.2 for another. That'll work... for a while. Suddenly things go haywire because the float is too big.

Now, WHY do we need this precision? Will the simulation change significantly because its time resolution is, say, 1/10 of a second (a reasonable value for parallel update) instead of the (floating) precision of floating point?

That is a pretty deep question: is the simulation unstable at those time scales? Why? Does it make sense that this is so?

Quote:
 Unfortunately, the whole entity system is written in python, because I want it to be dynamically changeable.
There's no reason it couldn't be dynamically reconfigured in C++ or any other language. Of course, it will take a bit of work, but you're likely to see a factor of ten or more improvement performance-wise for this sort of code.

The bit of work entails realizing that the semantics of your actors needn't be directly built on top of the host languages' object system.

You could use a Common Lisp implementation which permits dynamic compilation of functions into running programs, like SBCL, but something tells me you'll find this option unappealing.

Quote:
 I'll try to mix this together with an event/observer/SigSlot pattern, so at least those entities which only act on changes in their environment don't use up too much cpu power.
You are under the misapprehension that cpu power is going to be the limiting factor in your simulation: it's not likely to be. Interactions between actors will likely require very little actual computation. That's how it usually goes; they are very simple entities and the power of the simulation comes from their interactions.

The limiting factor will likely be ram latency (if you use the event queue model and the unlocalized memory access patterns it entails). The sad thing is, buying a new system will not make it run much faster, because ram latencies don't get (significantly) better lately.

By doing parallel update and making your data structures cache, prefetch and tlb-friendly, you can make ram bandwidth be the limiting factor, which is a much nicer state of affairs.

In the worst case (high interaction) BOTH the event and the parallel update model will have to do the same amount of work; the event model will thrash cache and slow to a crawl. The fact that it does less work in the easy case will not seem very relevant if it is unable to handle the general case, will it? Its job is not to conserve cpu power in the easy case: it is to run your simulation quickly even if the going gets tough.

Not to mention that an event system can be trivially layered on top of the parallel update model and used when you feel it makes sense, while the converse is not true.

You seem to be very familiar with the fashionable 'OO Patterns' school of thought. I'll spare you my rants about "Patterns" (after all, simulation is one of the few places where the object oriented formalism is indisputably useful, in my opinion) but you might consider thinking about other (closely related) ways of modeling your actors.

They are finite state machines conceptually, not classes in some particular language. Wanting to reconfigure them at runtime needn't tie you to a language whose object system permits dynamic reconfiguration, because they needn't be expressed directly as classes. A more convenient representation may well exist for your particular problem.

In fact, inheritance might be a convenient way to model your entities. Then again, it very well might not be. Duck typing instead of inheritance might be a more convenient model (see all the nice stuff python can do by NOT following typical OO dogma too closely).

So you might model entities as subsets of a flat set of possible behaviours. You might let them send each other behaviours, just like messages, at runtime: bingo, you have a model of memetics.

You might go the functional programming inspired route, represent the state of an entity as an algebraic datatype, and conveniently define polymorphic behaviours by pattern matching against state (if you've ever toyed with Haskell or ML you'll know what I mean) going for less entities that are smarter.

If you define your own formalism you are unconstrained by the restrictions imposed by one which was not designed to solve your particular problem. :)