Guarantees for modifying while iterating

[gramalingam]

@justinchuby : some thoughts:

• The most common pattern is to handle iterating through nodes of a graph, while inserting or deleting nodes.
• A special-case that may be easier to support is that of iterating through the nodes of a graph, and optionally replacing the visited node by a list of (zero or more) new nodes.
• The above are fairly easy to support with standard imperative linked-lists. But not easily available in standard python lists or proto lists.
• Two patterns I have used with existing proto limitations are:
  • flatten ( replacement(x) for x in nodes ) (functional style, but incurs cost proportional to entire list)
  • using two loops: the first one constructs a list of updates of the form (i, new-nodes), and the second one does the transformation replacing nodes[i] by new-nodes (over all i). This does have a flavor of what you mention in terms of red-black trees.
  • But neither of the above pattern is ideal. But we can live with them for now.

[gramalingam]

A few more comments:

• O(1) cost direct-access to the i-th element in the list is not important in my opinion. The common pattern is iterating through all nodes in sequence.

While the data-structure can provide minimal guarantees in the presence of modifications while iterating. However, designers of optimizations still need to think about the interaction between different optimizations if we want to combine them.

Taking a step back, one key question is how to combine multiple optimizations. We can run them one after another, which is straight-forward. However, we encounter situations where two optimizations can enable each other. Eg., replacing and if-node by its then (or else) branch when its condition is a constant can enable us to discover further constants downstream. Conversely, discovering new constants can enable if-node optimization.

This makes it necessary to "compose" optimizations: that is, as we iterate through nodes, we apply a sequence of optimizations to the visited node (one after another).

Where this gets complicated is when some optimizations are dependent on information computed via analyses that are impacted by the transformations performed by some other optimization.

Bottomline, sometimes optimizations need to combined or split into different passes based on a careful analysis of their mutual dependences. For example, the constant-folder does not try to eliminate dead-code ... dead-code elimination is done as a separate pass in the end, since it helps simplify the optimization design and implementation.