Suppose that Alice is researching different image classification pipelines. She has a large labeled set of images and progressively tries different combinations of preprocessing steps and neural network architectures. For example, she may replace an entire step with one that is more sophisticated but slower, or vice-versa. As she makes changes, she keeps a copy of the previous versions in separate Jupyter notebooks. We call these her different program versions; they are similar to different experiments in scientific computing. Once done, Alice would like to share her different program versions with Bob so that he can independently repeat and regenerate the results and verify Alice's work. We say Bob faces the multiversion replay problem: executing all the versions given to him by Alice as efficiently as possible where (i) many versions repeat some of the same preprocessing steps, but (ii) without reusing any of Alice's own computation. In this paper, we address this problem.
Collaborative scenarios such as the one above arise routinely in scientific computing and data science, where sharing, repeating, and verifying results is common. Several tools have been recently proposed for sharing and reproducing such scenarios [1,8,22,[41][42][43][44]57]. These tools audit the execution of a program, and create a container-like package consisting of all files referenced by the program during its execution. This package can then be used to repeat results in different environments. These tools have much to offer; they do not, however, exploit the efficiency possible by solving the multiversion replay problem. As the reproduction of results becomes increasingly time consuming [53], addressing such problems is critical.
One of the above tools is the Sciunit system [1,55], developed by some of the co-authors. It allows multiple versions of a program to be included in the same package and shared for repetition. We noted that having two or more versions in the same package sets up a natural opportunity for reusing computations that are often common across versions-i.e., a number of versions may perform the same computations for quite some time before they branch out as the researcher tries out different options. But, in order to accurately identify computations that can be reused across versions, we need to be able to determine the point to which the execution of two versions can be treated as equivalent and from which point the execution branches. We develop a methodology to identify common computations in program code fragments or cells of the versions. This methodology depends on lineage audited during program execution [38,42,43]. For repetition, at Bob's end, we share computational state across versions in the form of checkpoints. Let us now see with an example how sharing computational state across versions via checkpoints creates an opportunity to optimize computational time when repeating multiple versions.
Suppose that Alice has shared with Bob a package with three versions. Assume Alice has developed her code using a notebook, and her first version is divided into two cells that take time 1 minute and 10 minutes, respectively (Figure 1 left). Her second version has the same first two cells but she adds a third cell. Her last version, which processes the dataset, has the same first cell, but diverges after that, and cells 2 and 3 now takes 11 and 2 minutes, respectively. Now, during repetition, if Bob checkpoints cell 𝑏 while computing 𝑣1 and then restores that checkpoint for 𝑣2, he can complete 𝑣2 in just 1 unit of time (saving 11 units in 𝑣2). This checkpoint is, however, not useful for 𝑣3 since cell 𝑏 has been changed to 𝑑 in this version. Observe, that although 𝑎 is common across all three versions, checkpointing 𝑎, instead of 𝑏, is not optimal. In the example on the right, on the other hand, checkpointing 𝑎 is the better option since the bulk of the computation takes place in 𝑎. The example above leads to the question: Why doesn't Bob just checkpoint both 𝑎 and 𝑏? Storage is cheap after all! Indiscriminate caching, however, is not a practical solution: In machine learning examples, e.g., checkpointing all cells across versions (as our experiments indicate) can lead to a memory requirement in the range of 50-550GB, for even moderately-sized multiversion programs. Thus, we consider a limited in-memory space as this avoids additional I/O costs from checkpointing. Limited space leads to an optimization problem: As we will show, given limited space and multiple versions with different cost and size estimates of cells, deciding checkpoint locations for efficient replay of all versions is an NP-hard problem. We present efficient heuristics to solve this problem.
The CHEX system. We present CHEX, a system for efficient multiversion replay that uses recorded lineage shared in container-like auditing systems to (i) determine when the program state is identical across versions, and (ii) decides which common computations to save in an in-memory, limited-size cache, and where to continue recomputing. Effectively, CHEX computes an efficient plan for Bob to use his cache to repeat Alice's multiversion program with minimum computation cost. Subsequently CHEX repeats the computation according to this plan.
To execute the multiversion program, we first need a plan for sharing and reusing computational state across versions. A possible approach would be to reuse program elements such as the output of functions, expressions, or jobs. Such reuse approaches were examined in [16][17][18]. However, these methods make assumptions about the programs-they are limited to programs with no side-effects and apply to specific (functional or interpreted) programming languages. Such assumptions are too restrictive in a sharing scenario.
Our approach is program-agnostic and we, instead, use checkpoints. A checkpoint saves the computational state at a specific program location so that the same program can be restored from the location at a later time. To share computations, we extend checkpoint-restore to checkpoint-restore-switch, in which a system checkpoints a common computational state and and restores it later to resume a different version of the program.
The challenge of checkpoint-restore-switch, however, is determining locations at which to checkpoint, since ideally programs may be checkpointed after each instruction. Even if we decide at a fixed number of program locations, before reusing a checkpoint we must verify that two versions share the same computational state at a given program location. In this paper we solve this dual challenge by showing that when a program is divided into cells, computational state can be shared across versions by using fine-grained execution lineage. Dividing a program into cells is used in read-evaluate-print (REPL) programming environments, which are increasingly popular [26]. However, CHEX does not necessitate that a user employ REPL style; it transparently divides a program into REPL-style cells. This paper contributes the following: Maintains lightweight package sharing. CHEX does not require users like Alice to share checkpoints as part of the shared package. Instead, CHEX audits the execution of each version to record execution details. We note that in reproducibility settings, it is not desirable to allow Alice to share her checkpoints since that defeats the purpose of reproducibility. Merging versions based on lineage. CHEX compares fine-grained lineage to check if the program state is common across cell versions. It combines versions into an execution tree. Deciding checkpoint location. Given that the multiversion replay problem under space constraints is computationally intractable, we rely on depth-first-search (DFS) traversals of the execution tree to help us identify a subset of possible checkpointing decisions for the execution units of the program. We call the members of this subset DFS-based replay sequences. We propose two heuristic algorithms for deciding which cell state to checkpoint such that the multiple versions can be replayed in a minimum amount of time. Experiments on real and synthetic datasets. We experimented with real machine learning and scientific computing notebooks as well as synthetic datasets, showing that CHEX improves the total time of multiversion replay by 50%, or correspondingly replays twice the number of versions in a given amount of time. We show that the overheads of creating execution trees is significantly lower than the gain from replay efficiency. Working prototype system: We have developed a prototype CHEX system, which given an execution tree performs multiversion replay. CHEX currently uses standard auditing methods, developed by us [1,55], to build execution trees and determine cell reuse. For multiversion replay, we extended these methods to work with interactive Jupyter notebooks, as well as, transform regular programs to REPL-style computation via code-style paragraphs.
We briefly describe the REPL environment under which CHEX operates. CHEX is not limited to the REPL environment but this is easy to illustrate visually so we adopt this for ease of exposition. We discuss generalization to other environments in Section 9. In a typical REPL execution, cells are executed in sequence from the first to last. While the Jupyter notebook allows out-of-order cell execution, we do not consider such execution. (We elaborate on this constraint further in Section 9.) The state of the program at the end or beginning of each cell is termed the program state. The program state at any point of execution consists of the values of all variables and objects used by the program at that point -intuitively, it is all the contents of the memory associated with the program. So, e.g., for the program 𝐿 = [𝑥 1 , 𝑥 2 , . . . , 𝑥 5 ], the corresponding program states are [𝑝𝑠 0 , 𝑝𝑠 1 , . . . , 𝑝𝑠 5 ], in which 𝑝𝑠 𝑖-1 denotes the program state just before cell 𝑥 𝑖 is executed. The state 𝑝𝑠 0 , which is just before the first cell is executed, includes the value of the environment and any initial input.
CHEX works in combination with an auditing system which monitors executions and provides the following details about each program state, 𝑝𝑠 𝑖 :
• computation time, 𝛿 𝑖 , the time to reach the program state 𝑝𝑠 𝑖 from its predecessor 𝑝𝑠 𝑖-1 , • size, 𝑠𝑧 𝑖 , size of the program state 𝑝𝑠 𝑖 , • code hash, ℎ 𝑖 , computed by hashing code in cell 𝑖, and • lineage, 𝑔 𝑖 , which is determined by combining the predecessor cell's lineage with the sequence of system events that are triggered by program instructions in the cell 𝑖 and the hashes of the associated external data dependencies. Thus,
where 𝐸 𝑖 is the ordered set of system events in cell along with the hash of the content accessed by the event. Initially, 𝑔 0 = {}.
To see why 𝑔 𝑖 is defined so, we note that the execution of the program code in cell 𝑖 (and the code in previous cells) resulted in 𝑝𝑠 𝑖 . Therefore, 𝑝𝑠 𝑖 at the end of a cell's execution depends on its (i) initial environment, (ii) code that is run, and (iii) external input data. The environment is determined by the execution state at the start of the cell. Thus, (i) and (ii) are captured via 𝑔 𝑖-1 and ℎ 𝑖 . Further, every external input data file 𝑓 is accessed via a system call event.
For each such event, we record a hash of its contents of 𝑓 in 𝐸 𝑖 .
Figure 3 shows the audited information for the two programs, 𝐿 1 and 𝐿 2 . The ordered set of system events for the third cells of the two programs are shown in the shaded box below. We determine how to check if 𝐸 3 across versions is equal in Section 6.
As we see in Figure 2, the two programs behave the same till the end of the third cell (𝑥 3 in 𝐿 1 , 𝑦 3 in 𝐿 2 ) and then diverge. If the audited lineage, as shown in Figure 3, is established to be the same, then the program state at the end of 𝑥 3 can be used before 𝑦 4 . i.e, we can skip executing cells 𝑦 1 to 𝑦 3 . CHEX uses recorded lineage to determine when the program state is identical across versions, and decides which common computations to save. We now present a high-level block diagram of CHEX in Figure 4.
CHEX has two modes: audit and replay. It is used in audit mode to audit details of executions on Alice's side. Details of multiple executions, i.e. the 𝛿, 𝑠𝑧, ℎ and 𝑔 of each cell across versions are represented in the form of a data structure called the Execution Tree. We discuss the execution tree and how it is created in detail in Section 6. CHEX creates a package of all Alice's versions and their data, binary, and code dependencies, along with the execution tree. This package can now be shared with Bob. CHEX is used in replay mode on Bob's side. It first determines an efficient replay sequence or replay order, i.e., a plan for execution that includes checkpoint caching decisions. To do so CHEX inputs a cache size bound, 𝐵, and then executes a heuristic algorithm on the execution tree received from Alice to determine the most cost efficient replay sequence for that cache size. Computing a costoptimal replay sequence for multiple versions of a program with a cache bound is an NP-hard problem as we show in Section 4 and so we describe some efficient heuristics for this purpose (Section 5). Finally, once the replay sequence is computed, CHEX uses this replay sequence to compute, checkpoint, restore-switch REPL program cells or evict stored checkpoints from cache.
Our assumptions. Our basic assumption is that Bob wishes to independently verify the results from Alice's versions but is time constrained to repeat all her versions. We do not make any assumptions on the types of edits that differentiates one version from the next. Thus, Alice can change values of parameters, specifications of datasets, models, or learning algorithms. She can also add or delete entire cells. We illustrate possible changes via red boxes (Figure 2) across program versions. We only assume that edits result in valid executions, which do not terminate in an error, and, each version is executed in the natural order, top to bottom.
We now describe the multiversion replay problem. Figure 6 summarizes the symbols used in Section 2. In the replay mode, CHEX inputs an execution tree, 𝑇 , and a fixed cache size, 𝐵, to solve the multiversion replay problem. We define the execution tree as: Definition 1. (Execution Tree) An execution tree 𝑇 = (𝑉 , 𝐸) is a tree in which each program state is mapped to a node and equal program states across the different versions are mapped to the same node. Each root to leaf path in 𝑇 corresponds to a distinct version 𝐿 𝑖 .
Example. Figure 5 shows the execution tree created from five versions. In this tree, each root to leaf path corresponds to version 𝐿 𝑖 . In 𝐿 1 there is an edit to settings of the program at cell 𝑏, resulting in 𝐿 2 and a branch at 𝑎, the last common node across 𝐿 1 and 𝐿 2 . Similarly, in 𝐿 3 there is a dataset change to 𝐿 2 at cell 𝑒, resulting in 𝐿 3 and a branch at 𝑐, the last common node across 𝐿 2 and 𝐿 3 . The common nodes till a branch in the tree correspond to the subsequence of cells that are equal across versions. The tree branches at a cell node, subsequent to which cells are not reusable. CHEX computes cell equality using execution lineages. We will discuss how this is done via system calls in detail in Section 6. Intuitively, establishing cell equality makes program states reusable across versions. The multiversion replay problem is an optimization problem that arises when multiple versions of a program, each previously executed, are replayed as a collection. Once the multiversion program is represented as an execution tree it is clear that there is some advantage in not replaying the common prefixes of this tree.
Example. If we replay the five versions of Figure 5 sequentially we incur total cost of 129. On the other hand, assuming a cache size of 25, if we store the checkpoint at common prefixes, restore-switch the checkpoint later to avoid computing the common prefix for the next version, and evict the previous checkpoint to store a new one, the replay cost is reduced to 114 as shown in the first replay sequence of Figure 7. In the second figure we see that a different set of checkpointing decisions can improve the cost even when the cache size remains the same. Finally we see that increasing the space to 50 further improves replay costs to 95.
Under these operations, and given an execution tree and a fixed amount of space for storing checkpoints, the multiversion replay problem aims to determine a replay sequence that has the minimum replay costs. We define a general replay sequence as follows:
Definition 2 (Replay seqence). Given execution tree 𝑇 = (𝑉 , 𝐸) and a cache of size 𝐵, a replay sequence 𝑅 consists of 𝑚 steps such that step 𝑡 specifies the operation 𝑂 𝑡 performed and the resulting state of the checkpoint cache 𝑆 𝑡 , i.e.,
We will use the term replay order interchangeably with the term replay sequence.
At the initial step 𝑆 0 is empty and the root of the tree is computed. At any given step 𝑡, 𝑂 𝑡 is of one of the following four types. Here, 𝑢 𝑗 and 𝑢 𝑘 are nodes in 𝑉 , the vertices of 𝑇 .
• The cache size can never exceed 𝐵, i.e. |𝑆 𝑡 | ≤ 𝐵 for 0 ≤ 𝑡 ≤ 𝑚. Further, an operation 𝑂 𝑡 at step 𝑡 can only be performed on 𝑢 𝑗 , 𝑢 𝑘 under the following constraints:
• Checkpoint from working memory: A node in the execution tree is checkpointed only if it was computed in some previous step, after which there are only some evictions (to make space), if at all, i.e., if
• Restore from cache and switch to child: A node is restored only if it was in cache in a previous step, and without altering cache state, switches to one of its children in the execution tree, which is computed next i.e., if
• Evict from cache: A node is evicted from cache and alters its state, i.e., if
• Continue computation: Continue computing a node if its parent was being computed or if its parent was restored, i.e., if 𝑂 𝑡 = 𝐶𝑇 (𝑢 𝑗 ) =⇒ 𝑂 𝑡 -1 = 𝐶𝑇 (𝑝𝑎𝑟𝑒𝑛𝑡 (𝑢 𝑗 )) or 𝑂 𝑡 -1 = 𝑅𝑆 (𝑝𝑎𝑟𝑒𝑛𝑡 (𝑢 𝑗 ), 𝑢 𝑗 ) and 𝑆 𝑡 = 𝑆 𝑡 -1 or t= 1 and 𝑢 𝑗 =root of the tree 𝑇 . We assume the operations generate complete and minimal sequences. A replay sequence is complete if all leaf nodes of the tree 𝑇 appear in 𝑅, and is minimal if no 𝑢 𝑗 that is in cache is recomputed.
Given tree 𝑇 (𝑉 , 𝐸), the multiversion replay problem is to find a complete replay sequence 𝑅 that minimizes
in which 𝛿 𝑂 𝑡 = 𝛿 𝑗 , when 𝑂 𝑡 = 𝐶𝑇 (𝑢 𝑗 ), and 𝛿 𝑂 𝑡 = 0 otherwise.
In MVR-P, we assume the cost of checkpoint, restore-switch, and evict operations to be negligible. Thus, the only cost considered is the cost of computing the cells. Determining the minimum cost replay order leads to a natural trade-off between computational cost of cells and fixed-size cache storage occupied by the checkpointed state of the cells. Thus, to optimally utilize a given amount of storage we must determine for each cell whether its next cell be recomputed, or some other cell be recomputed by checkpointing the state of the current cell. We state that determining the replay order is computationally hard. Theorem 1. MVR-P is NP-hard.
We show that the decision version of MVR-Pis NP-hard. Given an execution tree 𝑇 , a cache size parameter 𝐵 > 0 and a total cost parameter Δ > 0, define 𝑅𝑃 (𝑇 , 𝐵, Δ) to be the decision problem with answer YES if there is a replay sequence of 𝑇 with cost at most Δ and size of cache at most 𝐵, and with answer NO otherwise.
The proof is by reduction from the decision version of bin packing. In outline, the proof works by constructing an execution tree whose depth 1 nodes have checkpoint sizes corresponding to the size of the items to be packed into bins in the bin packing problem. The 𝐵 of 𝑅𝑃 (𝑇 , 𝐵, Δ) is set to the size of the bins. In order to force caching, we keep Δ small and add nodes below the depth 1 nodes so that each of the level one nodes has to be cached when first computed. We are able to show that by carefully adding subtrees below the depth 1 nodes we are able to prove a tight relationship between the two problems, i.e., the bin packing decision problem gives a Yes answer iff 𝑅𝑃 (𝑇 , 𝐵, Δ) gives a yes answer.
We omit the proof due to space restrictions, referring the reader to the full version of this paper available at [34].
From Theorem 1 we know that it is unlikely we will find polynomial time solution to MVR-P. Accordingly, we present two efficient heuristics for this problem. Both heuristics restrict our exploration of the search space to solutions in which the execution order of the nodes of the execution tree corresponds to a DFS traversal of the tree-a natural, simple order in which to approach the replay of the tree. In order to formalize this notion we present some definitions. In the following, for sake of brevity, we specify only the compute 𝐶𝑇 (𝑢 𝑗 ) type operations in replay sequences. The other operations (checkpoint, restore, evict) are separately specified. In this briefer format, each step of a replay sequence is of the form (𝑢 𝑡 , 𝑆 𝑡 ) specifying that at step 𝑡, 𝑢 𝑡 is computed, and the resulting cache is 𝑆 𝑡 . Definition 3 (Ex-Ancestor replay seqence). Suppose 𝑇 = (𝑉 , 𝐸) is an execution tree. Given any replay sequence 𝑅 = {(𝑢 𝑡 , 𝑆 𝑡 ) : 1 ≤ 𝑡 ≤ 𝑇 } we define its first appearance order to be
is the first appearance of a node 𝑣 𝑗 of T in 𝑅. We call the indices 𝑖 1 , . . . , 𝑖 |𝑉 | as first appearances and all other indices as repeat appearances. For a replay sequence 𝑅, for each 𝑗 ∈ {2, . . . , |𝑉 |} the sequence of cells 𝑢 𝑖 𝑗 -1 +1 . . . 𝑢 𝑖 𝑗 -1 is called the helper sequence for 𝑣 𝑗 . If the helper sequence for 𝑣 𝑗 forms a path from an ancestor of 𝑣 𝑗 to 𝑣 𝑗 for each 𝑗 then 𝑅 is called an ex-ancestor replay sequence.
We observe that in an ex-ancestor replay sequence if the helper sequence of 𝑣 𝑗 is non-empty then it either begins with the root of 𝑇 or with a node whose parent is in 𝑆 𝑖 𝑗 -1 .
We illustrate this definition with an example. Consider the tree in Figure 5. Assume for now that cache size 𝐵 = 0 and consider the following replay sequence: 𝑎, 𝑏, 𝑑, 𝑔, 𝑘, 𝑜, a, 𝑐, 𝑒, ℎ, 𝑙, a, c, 𝑓 , 𝑖, 𝑚, a, c, f, i, 𝑛, 𝑝, a, c, f, 𝑗 where bold font indicates repeat appearance nodes. Here the indices 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 14, 15, 16, 21, 22, and 26 are first appearances and all others are repeat appearances. Let's take the example of node 𝑛. It's first appearance index is 21. Its helper sequence extends from indices 17 to 20 and contains a, c, f, i. This is a simple path in the tree beginning from the node containing 𝑎 which is an ancestor of 𝑛. In fact it is easy to verify that this sequence is an ex-ancestor replay sequence.
The question arises: Are there meaningful replay sequences that are not ex-ancestor replay sequences? For example, would it make sense to modify 𝑛's helper sequence and make it a, c, 𝑒, f, i. It appears that the extra computation of 𝑒 is superfluous and so a priori it is not obvious that such replay sequences are meaningful from the point of view of efficient replay. Therefore we focus on ex-ancestor replay sequences. We conjecture that an optimal solution to MVR-P will be such a sequence. Definition 4 (DFS-based replay seqence). Suppose𝑇 = (𝑉 , 𝐸) is an execution tree for a collection of traces C. We say a complete and minimal replay sequence 𝑅 is a DFS-based replay sequence if 𝑅 is an ex-ancestor sequence and the first appearance order of 𝑅 is a DFS-traversal order of 𝑇 .
Note that first appearance sequence of the example discussed below Definition 3 gives us a DFS-traversal of 𝑇 . Hence this is a DFS-based replay sequence for the tree of Figure 5. Now assume a cache size 𝐵 = 25 and the caching decisions made according to the first replay sequence in Figure 7. 1 The corresponding replay sequence is similarly: 𝑎, 𝑏, 𝑑, 𝑔, 𝑘, 𝑜, 𝑐, 𝑒, ℎ, 𝑙, 𝑓 , 𝑖, 𝑚, i, 𝑛, 𝑝, 𝑗. Since 𝑎, 𝑐, and 𝑓 are cached at appropriate junctures, the only node with a non-empty helper sequence is 𝑛 and the length of this sequence is just one, i.e., there is only one cell that has to be recomputed apart from its first appearance computation. For the second and third sequence in Figure 7 the number of recomputations are similarly three (a, c, f) and zero respectively.
We are able to explicitly bound the number of DFS-based replay sequences. Then, the number of DFS-based replay sequences of𝑇 is 𝑂 (2 𝑛 (ℎ+log ℎ+ b) ).
1 All three replay sequences in Figure 7 are DFS-based.
Proof. Let us fix a DFS traversal order. The helper sequence preceding (and including) each node can be at most ℎ in length and hence the length of a replay sequence can be no longer than ℎ𝑛. Since each helper sequence is an ex ancestor path to a node of the tree, we can have at most ℎ choices of a helper sequence at each node. Therefore there are at most ℎ 𝑛 different sequences that can qualify to be DFS-based replay sequences. Note that at each point of one of these sequences of cells we can decide to either cache the cell that we have just computed (this may require the eviction of something previously cached) or to not cache it. Hence there are at most 2 𝑛ℎ replay sequences associated with each of the ℎ 𝑛 different sequences that we got for a single DFS traversal order. This gives us an upper bound.
To compute the number of DFS traversal we simply permute the children visited by DFS at each step to get 𝑢 ∈𝑉 𝑏 𝑢 ! which can be rewritten as 2 𝑛 b by using Stirling's approximation. Multiplying we get the result. □
Since ℎ is Ω(log 𝑛) from Proposition 1 it appears that the space of possible solution is superexponential. In order to control the complexity of our solutions we restrict the solution space in two different ways and define two heuristics.
Within the space of DFS-based replay sequences, for our first heuristic, we propose the following caching policy: A cell can be cached only when it is first computed. Once cached the cell remains in the cache till every leaf of the subtree rooted at the node containing cell is computed. We call this the DFS Persistent Root policy.
Given a DFS traversal order this policy reduces the size of the solution space to 𝑂 (2 𝑛 ) which is still exponential in the size of the tree. We present a greedy algorithm called Persistent Root Policy Greedy (PRP) that helps find a good solution in polynomial time. We present the listing of PRP as Alg. 1. The algorithm begins with the baseline cost (stored in min) of a DFS-based replay sequence in which no node is cached and seeks out the node of the tree whose addition to the list 𝑆 achieves the maximum improvement over the baseline. This process continues incrementally while it is possible to include another node in the list. The process will stop when the subroutine DFSCost tells us that there is no node remaining in 𝑉 \ 𝑆 that can be included in 𝑆. Typically this will happen because for every node 𝑢 remaining in 𝑉 \ 𝑆, the cache will be full when it is encountered in the DFS order. In such a situation DFSCost will return ∞. This algorithm takes 𝜃 (𝑛 2 ) time to find each candidate to include in the list of nodes to be cached, and there are potentially 𝑂 (𝑛) such nodes. Therefore the time complexity of this algorithm is 𝑂 (𝑛 3 ). However there is no guarantee of optimality.
PRP is a greedy algorithm that seeks, at each iteration, to pick for caching the vertex of the execution tree that minimizes the cost. However, it can be easily modified to choose a vertex that minimizes the cost incurred per unit of cache memory consumed. Normalizing by size is a common measure for object caches [7,32]. We experimentally study both these variants in Section 7. We will refer to the cost-minimizing version as PRP-v1 and the ratio minimizing version as PRP-v2.
Algorithm 1 A greedy algorithm that takes as input execution tree 𝑇 , and a cache size parameter 𝐵. It outputs list 𝑆 of nodes to be cached under the DFS Persistent Root policy. return 𝑆 1: function DFSCost(𝑢, 𝑆, 𝐵, 𝑏) ⊲ 𝑢 is a node of 𝑇 ; 𝑏 is the cache budget used by the path from the root of 𝑇 to 𝑢. Called with 𝑢 = root(𝑇 ) and 𝑏 = 0 this returns the cost of computing the entire tree.
if 𝑢 ∈ 𝑆 and 𝑏 + 𝑠𝑧 𝑢 > 𝐵 then for each 𝑣 that is a child of 𝑢 do sum ← DFSCost(𝑣, 𝑆, 𝐵, 𝑏) + 𝑐 𝑢 ⊲ 𝑢 is not cached so must be recomputed for each child 13: if 𝑢 ∈ 𝑆 then 14:
sum ← sum + 𝑐 𝑢 ⊲ 𝑢 must be computed once 15: return sum
We now present a second heuristic that, while still not being optimal, searches a superset of the portion of the solution space searched by PRP. For each 𝑢 ∈ 𝑉 it seeks to partition the children of 𝑢 into two sets: 𝑃 𝑢 of nodes for which it is better to cache 𝑢 for the computation of the corresponding child subtrees, and 𝑃 𝑢 for which it is not. As in Persistent Greedy, caching choices once made persist here as well.
The listing of the essential recursive Parent Choice is presented as Alg. 2. When called with (𝑢, 𝑆) we explore the situation in which we are given the set 𝑆 of ancestors of 𝑢 that will be in cache while the subtree rooted at 𝑢 is computed. In case 𝑢 happens to be a leaf, no further decisions are needed, and we simply return the cost of computing 𝑢 given cache 𝑆 (Lines 2-4). Else, we need to determine what is best for each child 𝑢 𝑖 of 𝑢: Should the subtree rooted at 𝑢 𝑖 be computed with 𝑆 as is, or is it better to augment the cache with 𝑢 (denoted 𝑆 +𝑢 ). In the former the subtree may be forced to Algorithm 2 A recursive algorithm the computes for a tree rooted at 𝑢 the lowest DFS-based replay cost for a given cache 𝑆. The child subtrees of 𝑢 are allowed to choose between executing with 𝑆 or in addition caching 𝑢. if 𝑢 is a leaf then ⊲ If 𝑎 doesn't exist, return cost of computing 𝑢 from scratch.
𝑆 +𝑢 ← 𝑆 ∪ {𝑢} ⊲ 𝑆+𝑢 is cache that also includes 𝑢.
if size of cache 𝑆 +𝑢 > 𝐵 then 8:
⊲ Caching 𝑢 is not a option; process its children with 𝑆.
𝑃 𝑢 ← ∅; 𝑃 𝑢 ← 𝐶ℎ𝑖𝑙𝑑𝑟𝑒𝑛(𝑢). ⊲ 𝑃𝑢 will collect the nodes for which caching parent 𝑢 is cheaper.
for each 𝑢 𝑖 ∈ 𝐶ℎ𝑖𝑙𝑑𝑟𝑒𝑛(𝑢) do
recompute 𝑢 multiple times, in the latter cache space which may be more useful down the subtree is used up. The two costs are computed recursively (Lines 14-15), and the child is assigned to the set 𝑃 𝑢 or 𝑃 𝑢 corresponding to the lower cost (Lines 16-19)). Note that when adding 𝑢 to the cache is infeasible, i.e. |𝑆 +𝑢 | > 𝐵, we make the first choice for each node, i.e. assign them all to 𝑃 𝑢 . (Lines 7-10). Finally, we return the cost value up the recursion stack (Line 20). 2The essential recursive algorithm PC needs to be implemented using standard dynamic programming memoization and backpointers (see, e.g., [11]). Once a call with input (𝑢, 𝑆) is complete, the corresponding return cost value and the two sets 𝑃 𝑢 and 𝑃 𝑢 are recorded. The initial call is with (root(𝑇 ), ∅). This returns the cost of the optimal replay sequence for the entire 𝑇 . To construct the replay sequence itself, "follow the backpointers": Start with 𝑢 = root(𝑇 ) and 𝑆 = ∅. If for the corresponding call, 𝑃 𝑢 is not empty, compute 𝑢 (possibly by restoring the closest ancestor in the current cache) and checkpoint it. Update 𝑆 to include 𝑢. Then recursively compute the subtrees rooted at the nodes in 𝑃 𝑢 . Next update 𝑆 to remove 𝑢. Following this, recursively compute the subtrees rooted at the nodes in 𝑃 𝑢 , if any.
The above implementation takes time and space proportional to the total number of child nodes encountered over all recursive calls. For each 𝑢 ∈ 𝑉 , at most one recursive call is made for each possible set of ancestors in the cache. The number of different ancestor sets is at most 2 ℎ . Thus the total time taken is 𝑂 (2 ℎ 𝑢 ∈𝑉 𝑏 𝑢 ).
We In other words we say that two states are equal if they are reusable i.e., they are (i) equal at code syntactic level, (ii) after cell execution, result in the same state lineage (note state lineage of 𝑖 𝑡ℎ cell depends on state lineage of previous cell), and (iii) have roughly similar execution costs. Program state does not remain equal when cell code is edited, which changes the hash value of that cell and any subsequent cell. Similar states across versions also do not remain equal if costs change drastically, i.e., computed on different hardwares (viz. GPU vs CPU). Equating state lineage depends on the granularity at which the system events are audited. Since in CHEX, lineage is audited at the level of system calls, there are some pre-processing steps that are necessary to establish equality, such as accounting for partial orders, abstracting real process identifiers, and accounting for hardware interrupts. We describe these issues below.
Lineage equality implies that at end of cell 𝑖 of version 𝐿 1 , 𝑔 𝑖 is the same as that at end of cell 𝑖 of version 𝐿 2 . This is true if and only if the sequence of system call events (and their parameters)-till 𝑖 in 𝐿 1 and 𝑖 in 𝐿 2 -exactly match. But if a cell, e.g., forks a child process, which itself issues system calls, then each version's sequence will contain the parent calls and the child process calls interleaved in possibly different orders.
In Figure 3 the parent process forks a child and then issues a 'mem' memory call, and the child process itself issues 'exec', 'open', and 'read' calls. As the figure shows, it is possible that in the sequence for version 𝐿 1 the 'mem' access is before the 'read', while for 𝐿 2 it is after. If we want to correctly determine that the state in 𝐿 1 is identical to that in 𝐿 2 at this point, we need to recognize that the sequence of system calls is an arbitrary total order imposed on an underlying partial order. The partial order for 𝐿 1 and 𝐿 2 is identical, while the total order can differ.
In our implementation, we reconstruct the underlying partial order when we detect asynchronous computation, and match it to identify equality of program states in different versions. This is achieved by separating the events into PID-specific sequences and then comparing corresponding sequences. The above comparison is established by abstracting process identifiers to their logical values. Memory accesses cannot be abstracted and we just count the number of accesses in a cell. Comparison must also account for external inputs in addition to system events. As Figure 3 shows the hash of external dataset file 'new_fashion' is changed from 'b2e1772' to '6789b34. Thus, the two cells cannot be equated even though the order of system call sequence in 𝐸 is the same.
A related nuance is due to hardware interrupts. If 𝑃 1 experiences a hardware interrupt and 𝑃 2 does not, we make the safe choice: assume the program states are not equal. (It is easy to make the opposite choice, by simply ignoring hardware interrupts.)
We now describe CHEX's implementation and present an extensive evaluation of CHEX for multiversion replay.
Implementation. CHEX is implemented in C and Python. CHEX relies on Sciunit [1] for monitoring the application on Alice's side and it relies on Checkpoint/Restore in Userspace (CRIU) [10] to checkpoint/restore program states. CHEX maintains a ramfs cache to maintain checkpoints. These checkpoints are of the process corresponding to the REPL program and not of the container that Sciunit creates.
We use CRIU as a checkpointing mechanism. This is precisely to enable checkpoint of a process independent of its programming language 3 . CRIU does not freeze the state of the container but just the application process. Currently, CHEX is integrated with the IPython kernel. In future, we plan to integrate CHEX with Xeus [9], which will help us extend CHEX to C programs as well. For the purposes of reproducibility we have made available the code for the audit and replay mode of CHEX at [40].
We used a combination of real-world applications and synthetic datasets for evaluation. We ran all our experiments on a 2.2GHz Intel Xeon CPU E5-2430 server with 64GB of memory, running 64-bit Red Hat Enterprise Linux 6.5. The heuristics were developed in Python 3.4.
Real-world Applications. We searched GitHub and identified compute-and data-intensive notebooks, i.e., the programmer had already divided the code into cells. Most of these notebooks were published as artifacts in specific domain conferences (pre-established to be reproducible), and they were described as compute-and dataintensive.
We used four neural network machine learning applications (ML) and two scientific computing (SC) applications. Table 1 describes the characteristics of these notebooks. For the majority of the applications, the number of versions was determined in consultation with the notebook authors, by identifying meaningful changes to parameter values. Other notebooks were changed similarly. Total replay cost is the time to run all the versions with no cache. Total checkpoint size is the space required if each corresponding cell of the execution tree is checkpointed. Cell compute range and Cell checkpoint size represents the range of cell compute time and checkpoint size ranges, respectively. The changed parameter row mentions application parameters that were changed to create versions. The only way we created versions was by changing parameters. We did not modify any other part of the programs.
The case of the parameter epochs in ML notebooks is special. In our case, the ML notebooks embed deep neural networks, in which typically the compute-intensive part is the back propagation during the training phase. Back propagation is usually implemented as an iterative for-loop, whose upper bound is defined by the epochs parameter. Changing epochs will change the training length and the number of iterations in the for-loop. Such a change to create a new version, however, will also re-run the entire training phase again, Figure 8: Performance of DFS algorithms on 6 real-world applications. 𝑋 denotes the size of the largest checkpoint cell as specified in the last row of Table 1. The 𝑦-axis is truncated to show finer performance variations between algorithms. Synthetic. To test the sensitivity of our heuristics we randomly generated synthetic execution trees with different costs and sizes. We controlled the tree structure using the following parameters: max. branch out factor: The maximum number of branches possible at a node. Each branch is constructed with a 50% probability. This leads to trees in which many nodes have a single child. This is what we have observed in real notebooks. max. version length: The number of cells in each version. In general, the length for each version is different because of the randomization described above. max. number of versions: The number of leaves in the execution tree generated by using max. branch out factor and max. version length.
Using the above parameters, we generate three synthetic datasets:
• Compute intensive (CI): In the CI tree, the compute cost (𝛿) of cells is high and the checkpoint cost (𝑠𝑧) is modest. • Data intensive (DI): In the DI tree, the checkpoint cost (𝑠𝑧) of cells is high and compute cost (𝛿) is modest. • Analytic (AN): In the AN tree, compute and checkpoint costs i.e., 𝛿 and 𝑠𝑧 increase with version length.
Table 2 presents the total compute time and total storage size as well as the compute and storage ranges per cell.
Baselines. IncPy [17,18] avoids recomputing a function with the same inputs when it is called repeatedly or across program versions. Despite our best attempts we could not get IncPy to run with our real datasets. IncPy is not longer actively maintained and is Python 2.7 based which creates conflicts with more recent notebooks. We simulated the Vizier system, by taking one notebook version at a time [6], and using the simple caching policy that is used for Vizier: Least Frequently used (LFU), which is a standard caching algorithm. We adapt LFU to our case by checkpointing every cell of the first version of a notebook till the cache space fills up. As subsequent versions arrive, the cache eviction policy is decided by the measure 𝑓 𝑟𝑒𝑞𝑢𝑒𝑛𝑐𝑦 × # 𝑜 𝑓 𝑛𝑜𝑑𝑒𝑠 𝑖𝑛 𝑠𝑢𝑏𝑡𝑟𝑒𝑒/𝑐𝑒𝑙𝑙 𝑠𝑖𝑧𝑒, i.e., retaining cells which are used frequently and are responsible for larger subtree, normalized by their size. Least recently used, another standard caching algorithm, is not relevant in our case due to the depth-first replay order.
We first evaluate the benefit different algorithms provide in terms of reduction in replay time. We then evaluate the overhead of operating CHEX.
7.1.1 Comparing decrease in replay cost via different algorithms. Persistent Root Policy (PRP) and Parent Choice (PC) make different choices with respect to cells that must be retained in cache for recomputation. In this experiment, we evaluate how those decisions compare with the (LFU) baseline. Recall that PRP has two versions: PRP-v1, in which we cache checkpoints greedily based on contribution to reduction in cost, and PRP-v2, in which we normalize the cost reduction by the checkpoint size.
To compare algorithmic performance, we choose a cache size that is equal to the largest checkpoint size in a notebook and compute total replay time. The 𝑦-axis is initialized with a non-zero value to show finer comparisons between algorithms. For both PC and PRP algorithms on real-world applications, as is expected, Figures 8(a)-(f), show decreasing compute times (𝑦-axis) as the cache size is increased (𝑥-axis). We also see PRP and PC always perform substantially better than LFU, and PC reduces total compute cost more than either of the PRP versions.
Both these result trends are not exhibited in Figure 8(e) (SC1) and, to an extent, in Figure 8(d) ML4. In (e), as we observe, none of the algorithms, including the baseline LFU, show any benefit of caching. This is because in this notebook only the last cell of each version is compute-intensive, and none of the intermediate cells are cache-worthy. In (d), similarly, most computation is towards the later cells; PRP and PC still find some ways to optimize which LFU cannot find. The effect of reuse of intermediate results is welldemonstrated when comparing ML4 and SC2 which exhibit similar total replay costs. However, there is a much greater reduction in total replay cost in SC2 (from 100% to 18%) as there are several compute-intensive pre-processing steps in the earlier cells of the notebook, where as in ML4 most computation occurs towards the later cells.
Analyzing deeper we also observe these trends: (i) Sometimes, initially, PRP performs better, and this happens due to small cache size effect, since PC becomes a clear win with some additional cache space; (ii) PRP-v1 performs better than PRP-v2 indicating that eviction on a cost/size measure leads to more greedy eviction policy where checkpoints are evicted which need to recomputed later; and finally (iii) ML1, ML3 and SC2 are compute-intensive notebooks. Using the PC algorithm, these notebooks show a reduction of 60-65% in their compute time at a size of the cache which is at most double the size of the largest checkpoint cell in the notebook. This indicates that smart algorithms can provide significant benefits even with small cache sizes. We obtain similar results for synthetic datasets, and, for lack of space, only include the figures for synthetic results in the extended version of the paper [34].
7.1.2 Determining number of versions replayed with fixed cache size. We also examine the direct benefit of a system like CHEX for users. For most users CHEX will be configured with a given amount of cache space. Users, however, have time constraints. Thus we determine, for given cache sizes, number of versions that can be replayed with CHEX in a given amount of time, on the AN dataset. Figure 9(a) presents the result (number of versions (𝑦-axis) for the amount of time it takes to replay them (𝑥-axis)) for a given cache size, the value being either: no cache, 0.25GB, 0.5GB, and 1GB. The Figure shows that a user can run 50% more number of versions by doubling the space for the same fixed amount of time. To be able to run larger number of runs for the same amount of time has implications for scaleable collaborative sharing and artifact evaluation use cases. Cost of Auditing. CHEX performs auditing of state for each version of an application in terms of computation time 𝛿, state size 𝑠𝑧, state code hash ℎ, and state lineage 𝑔. We report both normal execution and audited execution as a percentage of the total time of using CHEX on a real application.
Amongst these audited quantities, the primary overhead is the additional time required to audit the application for state lineage, i.e., 𝑔. We further divide time to audit for 𝑔 into time required to (i) monitor and log system events in the application, and (ii) the time required to compute the hash of any external content that is referenced. As Figure 9(b) shows, a 15-25% of total auditing overhead is added across all applications. We are reporting 5 out of six applications as ML2 has relatively insignificant running time to begin with. Also the time to perform cell equality and construct the execution tree is negligible. Alice shares a package with the execution tree, the size of which is less than 1KB.
Cost of computing cache eviction decisions. We have shown the multiversion replay problem to be NP-hard; PRP and PC are heuristic algorithms, and thus have some time and space cost of making the cache eviction decisions. In this experiment, we measure the cost of using PRP and PC algorithms in comparison to LFU in terms of running time, space used, and number of times checkpoint/restore call was made. We experimented with the AN synthetic dataset.
The variability in running time of the algorithms with cache size is negligible (∼[0.05%]). Therefore, we fix the cache size to 1GB and show the variation with respect to two other parameters, the number of nodes in the tree, i.e., tree size and the different algorithms. Figure 10 (a) shows that PC is better than PRP in terms on run-time overhead, but in terms of space, it does incur a cost.
PRP has negligible state maintenance as it uses the execution tree to determine the order. However, PC takes storage, because it has to store all possible combinations of execution orders for different cache eviction sizes to get the most optimal one. Figure 10 (b) shows the increase in storage for different tree sizes as cache size is increased. Despite these differences, we highlight that the runtime and memory overheads of both algorithms is much lower (0.5-2%) than the overall compute time and storage of multiversion execution of any given real dataset.
The above experiment measures decision-making time and space. In practice to implement the decisions we must account for inmemory checkpoints and restore (C/R) time. In general, time to C/R are proportional to the size of the checkpointed state and are negligible. So we measured the number of times C/R were performed to check if small C/R costs adds to the overall latency of multiversion execution (Figure 10 (c)). As we see C/R costs are negligible, and decision making accounts for the primary cost.
Apart from the experiments reported above, we attempted a comparison between PC and an optimal algorithm,using the AN dataset for comparison. For optimal, we wrote our problem, the MVR-P, as an Integer Linear Program (ILP) and attempted to solve it with the Couenne optimizer [30]. The Couenne timeout was set as ten minutes. For tree size of 2-6 nodes, Couenne finished finding a solution in less than 10 seconds, but after that the time starts increasing exponentially. At 12 versions and an execution tree of 20 nodes, the optimal solution could not be found within the set time out. On increasing the number of versions, it took more time to find the optimal solution than naive replay (without cache). On the other hand, as we show in Figure 10(a) we took milliseconds to find a solution for more than a tree-size of 30.
Since we only found optimal solution for small trees, in terms of the quality of the solution, we found the replay cost of PC similar to optimal. For larger tree sizes, it may give better cost estimates, but given the large running time of optimal for larger and complex instances, we assess, it is not worth it. Finally, the overhead of implementing the decisions in CHEX is too small to be measured and often smaller than the variance between multiple runs.
Tools and hubs for sharing and reuse. Sharing and replaying is essential for verifying, and reproducing complex applications. Several user-space virtualization based tools have recently been proposed to enable sharing and repeating computations [8,19,22,41,43,55]. These tools do not address multiversion replay. In a virtualization package, code and data remain separate as files or databases [43]. Computational notebooks, which combine code and data, have received wide attention recently for sharing and use [26]. Notebook sharing, like package sharing, is easy but (re-)execution across versions remains sequential. Nodebooks [58] and Vizier [6] are specialized notebook clients that support and store notebook versions at a cell level. Neither, however, compute deltas between versions or trade computation for storage. Our work complements specialized notebook systems used for interactive development [24], and given lineage from these systems [31], replay can be enabled. Execution lineage. There are several provenance models for capturing execution lineage [52]. In this paper, we adopt the systemevent trace analysis process that is also used in other whole system provenance tracking methods [3,15,51]. Data caching. Data management systems have a rich history of employing object caches that tradeoff space for time to improve performance of applications. Semantic caching allows caching of query results [12,48], web-object caching allows caching of web objects [7,23], and query-based object caching allows database object caching based on queries [32]. In all of these works, the workload sequence is not known. In the multi-query scenarios [48] the workload is presented as set of queries and hence there is the possibility of caching the results of common sub-expressions and reusing them across queries. However, efficient reuse in the multi-query setting primarily involves searching through the space of query answering plans to identify plans that could potentially lead to optimal reuse. In certain cases not finding the optimal plan and blindly reusing common subexpressions may blow up the computation time because a large join may be required. Our scenario appears similar but we do not have the wiggle room provided by the semantics of a query, nor the potential pitfalls associated with blind reuse. State management for recomputation. [54] provides an excellent survey of state management for computation. State can be recomputed from lineage or state can be stored 'as-is'. In SciInc [56] state is recomputed from lineage that is versioned. Versioned lineage or causality-based versioning [36,56] leads to correct computation of state for incremental replay. In this work, on the contrary, we are concerned with state that is stored 'as-is'. Several works store 'as-is' state-this state is state of a variable, query, program, or configuration [54]. Similar to [20,21,25,39], in this work, our operator is program state. However, in these works the purpose is fault-tolerance, and so the system periodically checkpoints but does not consider space limitations. We determine a limited number of checkpoints of program state to save in-memory space, and using lineage, choose to simply recompute when efficient. To reduce space an alternative would be to incrementally checkpoint as explored in differential flows [35,37] and query re-optimization [29]. These approaches are not extendable to checkpoints of program state, which is an in-memory map. Very recently checkpointing was used to improve efficiency, but the checkpoint frequency is periodic [14]. Checkpoint location. Deciding when to checkpoint has received attention in HPC scheduling [5,47]. A primary objective is to minimize the amount of computation that needs to be redone in case the system fails. In HPC workflows, the checkpoint also has an overhead. We consider machine learning and scientific computing programs in which the checkpoint overhead is nearly zero.
Closer in spirit to our work is the DataHubs [4] system that seeks to maintain multiple versions of large data sets without fully replicating them. In this system some versions are stored fully materialized and others are stored only as deltas linked to other versions. The problem is to trade off total storage required versus time taken to recreate a version. At a glance, it is possible to think that the program states of the cells of our multiversion program can be aligned with the data sets considered in DataHubs. However, the fundamental difference is that DataHubs assumes each version of a data set has already been created the first time. Thus, they assume that at least one version of the data set is stored in its entirety. In CHEX, the equivalent thing would be for Alice to share some of the program states generated in her execution with Bob. This defeats the entire purpose of independent repetition by Bob.
We now discuss any assumptions that CHEX makes and our results. We assumed that CHEX works with REPL cells, but, in general, we do not constrain users like Alice to program with REPL interfaces. If the code is not developed via a REPL interface, CHEX preprocesses it into cells, akin to a program developed via a REPL interface, before monitoring. This preprocessing takes care to not split functions or control flows into separate cells. Thus every input program is automatically transformed into an equivalent REPL program and then entered into the CHEX.
We have assumed multiple versions for a given program. We make no assumptions on the types of edits that constitutes a version on Alice's side. Thus, Alice can change values of parameters, specifications of datasets, models, or learning algorithms. She can also add or delete entire cells. In practice we have found such versions to not correspond to development versions but as separate branches in version-control repositories. In workflow systems they also correspond to independent, but related, experiments.
We have only demonstrated a scenario in which Alice shares notebooks with Bob for multiversion replay. A more evolved backand-forth sharing of packages, one that accounts for any previous multiversion replay decisions to be persisted, will require further changes both to the system and the algorithm. In such a scenario, if the caches persist, some intermediate results are available for free and the algorithm needs to accommodate for that accordingly. This scenario is part of our future work.
Finally, our experiments show that CHEX significantly decreases the replay time for notebooks and allows a user to execute a far higher number of versions in a given amount of time. The benefit arises particularly for notebooks where pre-processing or training steps are compute and data-intensive. In particular, if all computation is conducted in the last cell, then opportunities for optimization on intermediate results reduce drastically. In this case, one option is to encourage the developer to further divide the last cell, which creates further opportunities of optimization. If the cell cannot be divided, then one may employ a hybrid approach of using functionbased caching within this cell. This may, however, require some analysis of the program in the last cell.
In this work we have highlighted the need for improving the efficiency of multiversion replay. Our work shows that execution lineage can be used to establish cell equality and reuse shared program state to optimize replaying of multiversions. We show that optimizing is not trivial and, given a fixed cache size, MVR-P is NP-hard and present two efficient heuristics for reducing the total computation time. We develop novel checkpoint-based caching support for replaying versions and show that CHEX is able to reduce the compute time of several machine learning and scientific computing notebooks using a cache size that is smaller than the checkpoint size of a notebook.
In the future, we wish to extend CHEX for queries and the standard database provenance model. This problem seems akin to how we previously extended provenance-based application virtualization [42] to database virtualization [43]. We also wish to explore how CHEX can incorporate program restructuring, which happens during interactive notebook development leveraging recent provenance models developed in this area [6,24,31] and developing corresponding online algorithms.
We do not explicitly show the cost of computing 𝑢 in order to cache it for 𝑃 𝑢 . This cost is offset by the same cost incurred by the first child subtree in 𝑃 𝑢 , as shown, but not actually paid since 𝑢 is already in cache when it is executed. The case of 𝑃 𝑢 = ∅ has a further optimization that is possible; see the full version of this paper[34].
Native serializations, viz. Pickle, provide only a slight performance benefit (1-2%).