research

Lazy object copy as a platform for population-based probabilistic programming

L.M. Murray

arXiv

This work considers dynamic memory management for population-based probabilistic programs, such as those using particle methods for inference. Such programs exhibit a pattern of allocating, copying, potentially mutating, and deallocating collections of similar objects through successive generations. These objects may assemble data structures such as stacks, queues, lists, ragged arrays, and trees, which may be of random, and possibly unbounded, size. For the simple case of N particles, T generations, D objects, and resampling at each generation, dense representation requires O(DNT)O(DNT) memory, while sparse representation requires only O(DT+DNlogDN)O(DT+DN \log DN) memory, based on existing theoretical results. This work describes an object copy-on-write platform to automate this saving for the programmer. The core idea is formalized using labeled directed multigraphs, where vertices represent objects, edges the pointers between them, and labels the necessary bookkeeping. A specific labeling scheme is proposed for high performance under the motivating pattern. The platform is implemented for the Birch probabilistic programming language, using smart pointers, hash tables, and reference-counting garbage collection. It is tested empirically on a number of realistic probabilistic programs, and shown to significantly reduce memory use and execution time in a manner consistent with theoretical expectations. This enables copy-on-write for the imperative programmer, lazy deep copies for the object-oriented programmer, and in-place write optimizations for the functional programmer.

L.M. Murray (2020). Lazy object copy as a platform for population-based probabilistic programming.

L.M. Murray (2020). <a href="https://indii.org/research/lazy-object-copy/">Lazy object copy as a platform for population-based probabilistic programming</a>. 

@Article{,
  title = {Lazy object copy as a platform for population-based probabilistic programming},
  author = {Lawrence M. Murray},
  year = {2020},
  url = {https://arxiv.org/abs/2001.05293}
}
blog Related?
GPU Programming in the Cloud

A how-to and round-up of cloud service providers.

Lawrence Murray

22 Nov 22

blog Related?
Sums of Discrete Random Variables as Banded Matrix Products

Zero-stride catch and a custom CUDA kernel.

Sums of Discrete Random Variables as Banded Matrix Products

Lawrence Murray

16 Mar 23

photography Next
Canadian Rockies
3

15 Feb 20

research Previous
Parameter elimination in particle Gibbs sampling

A. Wigren, R.S. Risuleo, L.M. Murray and F. Lindsten