add bisimilar abstraction

[blegat]

How fast are we with the deterministic abstraction ? If we're not fast enough (but that would be another PR), we could investigate having a specialized datastructure for deterministic abstraction but that would be more work so we should first check whether it's needed and whether this is the bottleneck

[adrienbanse]

@blegat Thanks I'll implement your suggestions

@blegat @JulienCalbert On my computer, the overall procedure takes ~2.004sec with Dionysos, and ~2.282sec with Cosyma

[JulienCalbert]

[like] Julien Calbert reacted to your message:

---

From: Adrien Banse @.> Sent: Monday, April 15, 2024 11:46:40 AM To: dionysos-dev/Dionysos.jl @.> Cc: Julien Calbert @.>; Mention @.> Subject: Re: [dionysos-dev/Dionysos.jl] add bisimilar abstraction (PR #346)

@blegathttps://github.com/blegat Thanks I'll implement your suggestions

@blegathttps://github.com/blegat @JulienCalberthttps://github.com/JulienCalbert On my computer, the overall procedure takes ~2.004sec with Dionysos, and ~2.282sec with Cosyma

— Reply to this email directly, view it on GitHubhttps://github.com/dionysos-dev/Dionysos.jl/pull/346#issuecomment-2056634331, or unsubscribehttps://github.com/notifications/unsubscribe-auth/AJF6SNKUP6LQN6LGW6KD3W3Y5O42BAVCNFSM6AAAAABGG6JHNSVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDANJWGYZTIMZTGE. You are receiving this because you were mentioned.Message ID: @.***>

[blegat]

What's the time taken in generating the abstraction vs computing the controller ?

[adrienbanse]

What's the time taken in generating the abstraction vs computing the controller ?

@blegat More or less 50-50 (0.92sec to generate the abstraction, 2sec for the overall procedure)

[JulienCalbert]

Je pense qu'on ne peut pas optimiser bcp plus la calcule de l'abstraction. En revanche, on peut faire certainement mieux pour le calcule du solveur en changeant la structure de l'abstraction (en un digraphe). Mais on est déjà pas mal comme ca.

[blegat]

The last commit fix some allocation issue. The line https://github.com/dionysos-dev/Dionysos.jl/blob/436f554aadcb7070d451791263505527c5cb0ef0/src/optim/abstraction/uniform_grid_abstraction.jl#L49 was allocating a lot:

0.102675 seconds (3.19 M allocations: 136.377 MiB, 27.06% gc time)

After 9caa369, it's now down to

0.010267 seconds (5 allocations: 224 bytes)

So build_abstraction went from 20.39 M allocations: 877.508 MiB to 17.18 M allocations: 740.429 MiB. Now that's still way to many allocations :) When we push to a Vector, the number of allocations scales with log2 of the length of the vector so these are all type instabilities. We should analyse the result of @profview_allocs to see where these are coming from.

[blegat]

With 59dca38, build_abstraction is down to:

0.337130 seconds (115 allocations: 93.833 MiB)

where 20 of the 115 allocations are actually due to the @time macro. I think we're good for that part. Actually the hack of 9caa369 is not necessary anymore. Everything was due to the non-constant modules!

[blegat]

To stress the importance of constant module shortcuts

Before the fix

Part	time	allocation	allocated
build_abstraction	0.990188 seconds	19.44 M allocations	834.695 MiB
build_abstract_problem	0.121359 seconds	1.28 M allocations	111.045 MiB
solve_abstract_problem	0.555608 seconds	5.38 M allocations	226.961 MiB

After the fix

Part	time	allocation	allocated
build_abstraction	0.349844 seconds	115 allocations	93.833 MiB
build_abstract_problem	0.107292 seconds	89 allocations	72.079 MiB
solve_abstract_problem	0.166343 seconds	71 allocations	65.177 MiB

[adrienbanse]

To stress the importance of constant module shortcuts

Really impressive... I wasn't aware of such a difference in performance 🤯

[blegat]

We noticed the same issue with Julien when working on the CDC's "Alternating simulation on hierarchical abstractions". That's why performance regression tests are useful ^^ Tests with @allocated can spot these things as well.

[blegat]

Not sure why the tests are now failing though, any idea ?

[adrienbanse]

No idea why, but the function shouldn't allocate anything, so the test should be @test f(...) == 0.

See comment above # Preallocates to make sure _compute_controller_reach does not need to allocate

[blegat]

Ah yes, it was an allocation check so it's actually good that it was failing ^^