Lazy object copy as a platform for population-based probabilistic programming
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....
Main Author: | |
---|---|
Format: | Text |
Language: | unknown |
Published: |
2020
|
Subjects: | |
Online Access: | http://arxiv.org/abs/2001.05293 |
id |
ftarxivpreprints:oai:arXiv.org:2001.05293 |
---|---|
record_format |
openpolar |
spelling |
ftarxivpreprints:oai:arXiv.org:2001.05293 2023-09-05T13:23:43+02:00 Lazy object copy as a platform for population-based probabilistic programming Murray, Lawrence M. 2020-01-08 http://arxiv.org/abs/2001.05293 unknown http://arxiv.org/abs/2001.05293 Computer Science - Distributed Parallel and Cluster Computing text 2020 ftarxivpreprints 2023-08-16T15:41:44Z 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)$ memory, while sparse representation requires only $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. Text The Pointers ArXiv.org (Cornell University Library) |
institution |
Open Polar |
collection |
ArXiv.org (Cornell University Library) |
op_collection_id |
ftarxivpreprints |
language |
unknown |
topic |
Computer Science - Distributed Parallel and Cluster Computing |
spellingShingle |
Computer Science - Distributed Parallel and Cluster Computing Murray, Lawrence M. Lazy object copy as a platform for population-based probabilistic programming |
topic_facet |
Computer Science - Distributed Parallel and Cluster Computing |
description |
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)$ memory, while sparse representation requires only $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. |
format |
Text |
author |
Murray, Lawrence M. |
author_facet |
Murray, Lawrence M. |
author_sort |
Murray, Lawrence M. |
title |
Lazy object copy as a platform for population-based probabilistic programming |
title_short |
Lazy object copy as a platform for population-based probabilistic programming |
title_full |
Lazy object copy as a platform for population-based probabilistic programming |
title_fullStr |
Lazy object copy as a platform for population-based probabilistic programming |
title_full_unstemmed |
Lazy object copy as a platform for population-based probabilistic programming |
title_sort |
lazy object copy as a platform for population-based probabilistic programming |
publishDate |
2020 |
url |
http://arxiv.org/abs/2001.05293 |
genre |
The Pointers |
genre_facet |
The Pointers |
op_relation |
http://arxiv.org/abs/2001.05293 |
_version_ |
1776204310587113472 |