nkremerh / sugarscape

Development repository for the Digital Terraria Lab implementation of the Sugarscape agent-based societal simulation.
https://github.com/digital-terraria-lab/sugarscape
MIT License
7 stars 12 forks source link

Improves benthamHalfLookaheadValueOfCell() efficiency by ~40% #29

Closed colinhanrahan closed 8 months ago

colinhanrahan commented 8 months ago

In my test using benthamHalfLookaheadTop, 75% of findBenthamHalfLookaheadValueOfCell() runtime is taken up by one call to agent.findNeighborhood(cell) which is then passed to len(agent.findNeighborhood(cell)). 80% of the call to agent.findNeighborhood(cell) is self.findCellsInRange(newCell), and 60% of that is shuffling. For this specific use case, there is no need to shuffle — you just want the size of the neighborhood at the next cell.

findNeighborhood() is called 4 times in the repository:

findCellsInRange() is only used for findNeighborhood(). I've moved the shuffle() from findCellsInRange() to the "if newCell == None" block in findNeighborhood(). This will also improve all other *HalfLookaheadValueOfCell() functions by a similar percentage, but I didn't test them all individually. In my testing, the change seems to speed up benthamHalfLookaheadTop total simulation runtimes by 30%.

colinhanrahan commented 8 months ago

Removed shuffle and comment in new commit.

nkremerh commented 8 months ago

Such a small change netted ~5% to ~45% improvements in simulation runtime using the Bentham decision model and did not cause any catastrophic changes in overall agent population (numbers are relatively stable on average across a handful of seeds). Fantastic catch!