Speedup by caching distributions in sparse matrix

[zsunberg]

Instead of repeatedly calling transition() on every iteration, shouldn't we just call it once for each state and action and store the resulting probabilities in a sparse matrix? Seems like this could be much faster.

[mykelk]

That would work for some problems. But for others (e.g., ACAS X), a sparse matrix would not fit in memory.

[zsunberg]

Ah, Ok, yeah, I think it would be beneficial to have both - it might be a big benefit for medium-sized problems with 10s or 100s of millions of states. Someone should implement it (either as an option for this solver or as another solver).

[rejuvyesh]

It definitely does. Seems to require fewer allocations too. Benchmark:

size = (10, 10)
[ Info: Sparse
9.729 ms (76558 allocations: 22.66 MiB)
[ Info: Vanilla
18.878 ms (475458 allocations: 20.78 MiB)
size = (100, 100)
[ Info: Sparse
812.970 ms (4544223 allocations: 2.21 GiB)
[ Info: Vanilla
2.994 s (67483266 allocations: 2.73 GiB)
size = (1000, 1000) 
[ Info: Sparse
  118.543 s (494746967 allocations: 221.35 GiB)  
[ Info: Vanilla                                                                         
  291.192 s (7344976963 allocations: 281.59 GiB)

And with julia -O3 it does even better:

size = (10, 10)
[ Info: Sparse
  8.938 ms (76558 allocations: 22.66 MiB)
[ Info: Vanilla 
  376.286 ms (8177250 allocations: 357.01 MiB)
size = (100, 100)
[ Info: Sparse
  678.314 ms (4544223 allocations: 2.21 GiB)
[ Info: Vanilla
  39.607 s (935603138 allocations: 37.78 GiB)
size = (1000, 1000)
[ Info: Sparse
  103.341 s (494746967 allocations: 221.35 GiB)  

[rejuvyesh]

See #23