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 Latest
GPU Programming in the Cloud
How to develop on remote cloud instances, and a roundup of cloud service providers.

Lawrence Murray

22 Nov 22

GPU Programming in the Cloud
blog Related
Responsive Images with Jekyll and ImageMagick
Step by step through the HTML, ImageMagick and Ruby. Works with Jekyll 4.

Lawrence Murray

30 Oct 22

photography Next
Canadian Rockies
research Previous
Parameter elimination in particle Gibbs sampling

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

Parameter elimination in particle Gibbs sampling