dynamobi/dynamobi — Issue #443: [FNL-59] ExecStreamGraph doesn't get built with correct flow output ordering
Author: dynamobi-build
Created: 2011-12-30 03:13:54+00:00
State: open
Labels: Exec, FNL

[reporter="jvs", created="Mon, 4 Dec 2006 17:46:36 -0500 (GMT-05:00)"]
Up until now, ExecStreamBuilder only preserves input flow ordering (even though Farrago and FEM transmit both input and output flow ordering to Fennel). Zelaine is putting in a stopgap to make it handle the case of preserving output flow ordering for streams which have only one input. For edges connecting streams where the producer has multiple outputs and the consumer has multiple inputs, the output ordering will be set correctly, and the input ordering may not be (whereas it would have been before).

A full solution requires changes to ExecStreamGraph's data structures. What we'd like to do is use the original ExecStreamBuilder logic (add edges according to input flow ordering) but annotate each edge with the correct output flow ordinal. Then, during ExecStreamGraphImpl::prepare, sort each vertex's list of output edges according to the annotated ordinal attribute.

From reading the Boost docs, I haven't been able to figure out whether it's actually safe/possible to use std::sort on the iterator pair returned by boost::out_edges (with a comparator to impose the order transmitted down from Java, which we would need to keep associated with the edge before the sort).

http://www.boost.org/libs/graph/doc/adjacency_list.html

The closest mention is here (section Structure Modification):

"The placement of the new edge in the out-edge list is in general unspecified, though ordering of the out-edge list can be accomplished through the choice of OutEdgeList."

I.e. our usage of std::vector for the edge lists will maintain insertion order, but that doesn't answer whether reordering existing edge lists will work (and reading the template code is not that easy).

I verified that it's at least possible to compile code which uses the returned iterators to swap edges, but I don't know if it will corrupt other data structures inside the graph.

If it doesn't work, then we would probably need to maintain redundant sorted edge vectors per-vertex and use those for output-order-sensitive graph accessors.

Either way, we also need to take into account how this interacts with post-prepare graph edits used by Disruptive Tech.