Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Tutorial on particle filters should emphasize that model that calls Unfold needs to be static #449

Open
ztangent opened this issue Feb 25, 2022 · 5 comments

Comments

@ztangent
Copy link
Member

After going through the tutorial on particle filters, @kach ran into issues trying to get incremental computation working, and it turned out this was because of not annotating the model that calls the Unfold combinator with static. Ideally, this would be emphasized in the tutorial (and the docs) so that others don't run into the same issue!

@bgroenks96
Copy link

Why is this necessary, actually?

@ztangent
Copy link
Member Author

ztangent commented May 5, 2024

In the current implementation, if the static annotation isn't added, then the model which calls Unfold ends up passing a conservative change hint / "argdiff" in the Gen.update call to the Unfold combinator, causing Unfold to conservatively assume that the model needs to be rerun from the very beginning, instead of just simulating the next time step. This results in a $O(T^2)$ run time instead of an $O(T)$ runtime, where $T$ is the number of steps.

I think there are slight changes we could make to the current implementation of Unfold so that (static) isn't necessary, but it will require more runtime checking of whether the arguments have changed.

@bgroenks96
Copy link

Ok, so at least it's a performance concern rather than a correctness concern.

@bgroenks96
Copy link

I actually can't reproduce this in a standalone example...?

@gen (static) function kernel(i::Int, zₜ, σ)
    zₜ₊₁ ~ normal(zₜ, σ)
    return zₜ₊₁
end

@gen (static) function static_unfold(z₀, n::Int)
    σ ~ exponential(0.1)
    return @trace(Unfold(kernel)(n, z₀, σ), :unfold)
end

@gen function dynamic_unfold(z₀, n::Int)
    σ ~ exponential(0.1)
    return @trace(Unfold(kernel)(n, z₀, σ), :unfold)
end

@benchmark simulate(static_unfold, (0.0,1000))
@benchmark simulate(dynamic_unfold, (0.0,1000))
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  305.523 μs …   8.214 ms  ┊ GC (min … max):  0.00% … 85.66%
 Time  (median):     371.969 μs               ┊ GC (median):     0.00%
 Time  (mean ± σ):   489.648 μs ± 732.991 μs  ┊ GC (mean ± σ):  15.00% ±  9.41%

  █                                                              
  █▃▅▂▂▂▂▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▂▂▂▂▂ ▂
  306 μs           Histogram: frequency by time         6.77 ms <

 Memory estimate: 1.68 MiB, allocs estimate: 4139.

BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  299.787 μs …   7.530 ms  ┊ GC (min … max):  0.00% … 85.84%
 Time  (median):     348.430 μs               ┊ GC (median):     0.00%
 Time  (mean ± σ):   453.382 μs ± 694.182 μs  ┊ GC (mean ± σ):  15.33% ±  9.40%

  █▃▅▁                                                          ▁
  ████▇▅▃▃▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▃▁▄▅▆ █
  300 μs        Histogram: log(frequency) by time       6.43 ms <

 Memory estimate: 1.68 MiB, allocs estimate: 4169.

Does it depend on the type of arguments?

@ztangent
Copy link
Member Author

Gen.simulate isn't affected, but if you repeatedly call Gen.update with an increasing value of n (as happens under the hood with particle filters), you should see a slowdown with dynamic_unfold.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants