Comments (11)
cargo run --release -- --prebake
in the game crate. This runs the weekday scenario for the montlake and lakeslice maps without the GUI, so all the work is just spent simulating. I've also used cpuprofiler
before; there's a few commands in docs/misc_dev_tricks, but right now, I think that pretty much just points to stuff in scheduler as the main hot spot.
The slight complication is that the simulation is still sensitive, so for example, if the a new priority queue slightly reorders commands with the same timestamp, then hypothetically gridlock could occur on these currently stable maps. If that happens, performance grinds to a halt, so it's obvious. :) On my machine, prebaking takes about 5 minutes total, so it's fairly obvious when a new problem is introduced.
from abstreet.
The priority is mainly determined by
Time
, but the tie-breaking for equal times needs to be deterministic.
It is deterministic, and independent of the hasher: garro95/priority-queue#29
from abstreet.
How did you profile the code? I would like to try some things and see the change
from abstreet.
@vks, based on your other repos (thanks for all your work on rand
by the way!), I'm wondering if you happen to be interested in / knowledgable about core data structures in Rust like this? Doing something more clever here would probably be the single greatest perf boost we could get by changing one thing.
from abstreet.
I'm not really an expert on data structures, but I would be interested having a look at performance! So thanks for marking me.
from abstreet.
This crate looks promising: priority-queue It is built with an ordered hash map (indexmap). We could try to swap it in and see whether it improves performance.
from abstreet.
This looks like it might work. I'm not sure if the Item struct should be the I
type, or if we could remove time
from that struct and just use the CommandType
. The priority is mainly determined by Time
, but the tie-breaking for equal times needs to be deterministic. peek doesn't say what happens when multiple items have the same greatest priority, but given the backing indexmap, it should probably work.
It would be nice if we could do away with having both a priority queue and a separate CommandType -> Command lookup. The queue's item must implement Hash
and Eq
. I tried just now and actually it's possible to make Command
derive Eq
. But not Hash
; at the end of the day, there's geom::Duration
and geom::Speed
buried somewhere inside, which just wrap anf64
. And maybe more importantly, the Command
struct can get quite big, so hashing it by looking at all of its fields recursively is probably bad for perf.
That's why the whole CommandType
indirection was started. The code using the scheduler promises to only ever have one Command
per CommandType
at a time in the priority queue. So we could probably ditch the queued_commands
mapping and use the entire Command
directly. Instead of deriving Hash
and Eq
, we would just make the hashing function take the CommandType
, created lazily in the hashing function, as the input.
from abstreet.
@vks, I might actually try tackling this soon. I just wanted to make sure I'm not repeating something you've started or were really keen to do
from abstreet.
Thanks for the heads up! I don't have plans to work on this soon, so please feel free to go ahead.
from abstreet.
Well that was anti-climactic. I tried two different approaches for using priority_queue
. https://github.com/a-b-street/abstreet/tree/pq_v2 just swaps out BinaryHeap
for PriorityQueue
, but otherwise keeps the CmdType -> Command
mapping. https://github.com/a-b-street/abstreet/tree/pq_v1 removes that mapping as well, and instead implements Hash
on Command
by lazily calculating the CommandType
and hashing that.
I measured total time to run the small montlake simulation. I repeated each run 3 times and tried to avoid other heavy activity while the test ran. There's a fair bit of noise repeating runs, but consistently, all of the variations using the new priority queue were slower than the current use of BinaryHeap.
So, failed experiment, sadly. :( But it could be eventually worth trying out other priority queue implementations.
from abstreet.
Do we know what priority queue operation is costing the most in this case?
Iām not too familiar with the design of this scheduled but I understood it required to update all the priorities regularly. Is that correct?
With a binary heap, I think updating one priority is log n
, so optimising Ć
priorities is a log n
.
Might have better luck with a data structure that has better priority update performance, like a Fibonacci heap? There may be other data structures I do not know.
from abstreet.
Related Issues (20)
- Improve LTN Turn Restriction editing UX design
- Design LTN tool: Improve isolated cell detection
- Improvements to Design LTN : Improved shortcut detection
- Design LTN tool - turn restriction editing: testing with `complicated_turn_restictions` required HOT 5
- Stuck at level 3 of 15-min Santa HOT 8
- Can't copy/paste error message (15-min Santa game)
- Impossible/impracticable to undo automated filter placement in Design LTN tool HOT 2
- Crash when clicking on a parking lot HOT 3
- Trying to load Camden data to test low traffic neighbourhoods HOT 6
- Boolean ops crash in WASM only HOT 4
- Mac builds broken HOT 9
- Switching maps doesn't clear proposal URL
- Missing crosswalks in LTN "crossing" feature HOT 1
- 15 min neighborhood routing issues HOT 2
- cant parse hebrew HOT 6
- Draw routes more clearly when unzoomed on large maps HOT 5
- Grid2Demand agent file fails to load.
- Crash when launching traffic sandbox HOT 1
- Crash when changing one-way direction
- Print / export map HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
š Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. ššš
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ā¤ļø Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from abstreet.