search

JuliaPOMDP / DiscreteValueIteration.jl

Value iteration solver for MDPs
Other
20 stars 12 forks source link

Sparse VI optimization #55

Closed WhiffleFish closed 1 year ago

WhiffleFish commented 1 year ago

Sparse VI implementation on master has some crazy intermediary allocations

Benchmarks

mdp = SparseTabularMDP(SimpleGridWorld(size=(100,100)))
sol = SparseValueIterationSolver(max_iterations=1_000, belres=0.0)
@benchmark solve(sol, mdp)

Master

BenchmarkTools.Trial: 16 samples with 1 evaluation.
 Range (min … max):  310.832 ms … 344.604 ms  ┊ GC (min … max): 5.08% … 11.91%
 Time  (median):     328.850 ms               ┊ GC (median):    8.23%
 Time  (mean ± σ):   326.575 ms ±   9.168 ms  ┊ GC (mean ± σ):  8.31% ±  1.79%

  █          ▁ ▁   ▁   ▁         █ ▁▁▁▁▁    ▁  ▁              ▁  
  █▁▁▁▁▁▁▁▁▁▁█▁█▁▁▁█▁▁▁█▁▁▁▁▁▁▁▁▁█▁█████▁▁▁▁█▁▁█▁▁▁▁▁▁▁▁▁▁▁▁▁▁█ ▁
  311 ms           Histogram: frequency by time          345 ms <

 Memory estimate: 1.05 GiB, allocs estimate: 41056.

This PR

BenchmarkTools.Trial: 28 samples with 1 evaluation.
 Range (min … max):  181.719 ms … 186.178 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     183.634 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   183.658 ms ± 822.542 μs  ┊ GC (mean ± σ):  0.00% ± 0.00%

                   ▄    █    ▁      ▁█                           
  ▆▁▁▁▁▁▆▁▁▁▁▁▁▁▆▁▁█▁▁▆▁█▆▆▆▆█▁▆▁▆▆▁██▁▆▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▆ ▁
  182 ms           Histogram: frequency by time          186 ms <

 Memory estimate: 938.73 KiB, allocs estimate: 22.