Intra-frame parallelism and reproducible ordering

[wdconinc]

In EIC, we tend to think of collections as sets rather than lists/vectors, with an ordering that's merely a result of the order in which they are filled but cannot be inherently guaranteed since it is not defined in the data model. In our event reconstruction code development we have some infrastructure to identify changes in the outputs between feature and target branch artifacts, and that is of course sensitive to changes in ordering. Due to concurrency in the framework, frames are written out of order, which is of course expected. However, we are also exploring intra-frame parallelism, which leads to vector members and collections being filled in an order that's not necessarily sequential or therefore reproducible (think: std::for_each(std::execution::unseq_par, hits.begin(), hits.end(), [&c](auto& h){ c.add ToHits(h); }) for hits in a cluster). Is there any way to fill podio vector members and collections out of sequence, yet still end up with a reproducible ordering on disk? I'm thinking orderable data types would need a hash or compare function to define the ordering, manifested in the data model. That could then be used to fill an ordered container, which would be serialized before saving to file.

[tmadlener]

std::for_each(std::execution::unseq_par, hits.begin(), hits.end(), [&c](auto& h){ c.add ToHits(h); })

I am not sure this is even possible at the moment. IIRC all the member functions that add relations / vector members are not thread-safe at the moment:

podio/python/templates/macros/implementations.jinja2

Lines 138 to 141 in db109c8

	void {{ class_type }}::{{ relation.setter_name(get_syntax, is_relation=True) }}(const {{ relation.full_type }}& component) {
	m_obj->m_{{ relation.name }}->push_back(component);
	m_obj->data.{{ relation.name }}_end++;
	}

Where m_obj->m_{{ relation.name }} is a std::vector and m_obj->data.{{ relation.name }}_end is an unsigned int, neither of which are protected in any form via a mutex or the use of an atomic.

In general the philosophy we had in mind for intra-event parallelism was that as long as collections are being filled, resp. they are still mutable they live on a single thread only. This is partially inspired by the requirements of Gaudi Functional with a similar philosophy and also because of trying to avoid some of the issues you have described, as now each collection is filled deterministically, even if the collections themselves are potentially not. The latter is (as you know) dealt with by hashing the collection names to get a collection id when putting them into the frame (Watch out for issues similar to key4hep/k4FWCore#311 here in case this is not done immediately).

An additional issue with imposing a deterministic order based on a hash (or any other order criteria than insertion order is) that insertion order might have a meaning in itself. For example for a track the intuitive assumption is that the hits have a natural order, e.g. from the IP outwards. Hence, this ordering would probably have to be configurable (maybe even at runtime).

Currently I don't really have an idea of how to best approach the issue if we have to / want to drop the assumption that the order in which collections are filled is not determined by the algorithm, but effectively random due to threading. Since the object id is also effectively defined by the insertion order, the only way I currently see is some form of "external hashing" of some data members and then filling the collections according to that (i.e. prepare all objects in a vector and then fill the collection at the end). From that point on the object id would become useful again for ordering purposes.

We could probably provide a static XYZCollection::from(const std::vector<XYZ>& coll) (probably better defined via std::span or a range, but in spirit something like this) to facilitate construction from externally collected ranges.

[m-fila]

Also the comparisons for datatype objects are based on object identity rather than equality, for instancestd::hash or operator< we already provide for datatype objects are based on address of some internal object. They can be used to identify or order objects only within a single execution - they don't have to be the same in two different executions of the same program, so each time the ordering defined by them would be different.

[wdconinc]

Thanks for engaging with my ramblings :-)

neither of which are protected in any form via a mutex or the use of an atomic

Yes, the snippet is too summarized, and would need to protect.

Hence, this ordering would probably have to be configurable

Agreed, and default to not changing the current behavior for backwards compatibility.

if we have to / want to drop the assumption that the order in which collections are filled is not determined by the algorithm

The assumption would continue to hold unless explicitly indicated to not be required.

std::hash or operator< we already provide for datatype objects are based on address of some internal object

Indeed, and the difference here would be to have the ordering be defined by content, not implementation-specific details.

[tmadlener]

A few more inputs to this discussion.

The ordering of the collections has to be finalized only before they are written, i.e. before the first collection calls prepareForWrite all the ObjectIDs in all collections have to be fixed. In-memory all relations are handled via pointers to objects so moving the objects around doesn't matter. Only when we persist them do we need a stable ObjectID. Since we don't make any assumptions about the order in which collections are written, we have to fix the order of all collections before they are written.

As already mentioned above one possibility would be to have a possibility to construct a collection from a range of objects (i.e. handles). This would make the construction of the order of that range entirely user-configurable. It would also "demote" the podio collections somewhat to pure I/O vehicles, at least on the writing side. This is partially against the original philosophy of having the collection at the center stage as easy to use access point to all objects.

A second possibility would be to add a sort method that takes a, potentially user defined, comparison function as argument and that can be used to sort the collection however the user sees fit. This would obviously only be callable on mutable collections. In contrast to the other option with constructing from ranges this would not change the role of collections in podio. We could probably also generate a default comparison for our handles based on the data members, such that there is a "natural" order.

[wdconinc]

As already mentioned above one possibility would be to have a possibility to construct a collection from a range of objects (i.e. handles).

So, a sorted view into the collection?

[tmadlener]

So, a sorted view into the collection?

I was rather thinking about something like

std::vector<edm4hep::MCParticle> particles{};

std::fill_n(particles.begin(), N, /* non-trivial constructor */);
std::ranges::sort(particles, /* arbitrary comparison */);

auto particleColl = edm4hep::MCParticleCollection::from(particles);
frame.put(std::move(particleColl), "sortedMCParticles");

The alternative approach would be

auto particleColl = edm4hep::MCParticleCollection{};
for (auto _ : std::ranges::view::iota(0, N)) {
  auto mc = particleColl.create();
}
particleColl.sort(/* arbitrary comparison */);
frame.put(std::move(particleColl), "sortedMCParticles");

A sorted view also sounds interesting, but without having looked into it in any detail to me it sounds non-trivial to implement, especially if we want it to be somewhat lightweight and not simply a vector<XYZ> that we construct on demand.

[wdconinc]

Coming back to this issue after finally having tracked down some irreproducible behavior in our reconstruction workflows to the default OrderKey address-based ordering. That causes collections which have been processed by different algorithms in different threads to be irreproducibly sorted (since they depend on the memory allocation in unrelated threads).

In our case, at the simplest level, we have one algorithm that processes N hits, another that processes P hits, and then a third algorithm that merged the N and P collections. Single threaded is reproducible against itself. Multi-threaded is reproducible against itself. But single-threaded and multi-threaded are not producing the same results due to ordering differences.

It really seems like a default ordering based on implementation (runtime even) details like memory addresses may not be ideal and can hide subtle some issues.