Preparing for reference behavior while using header-only awkward

[tomeichlersmith]

Howdy everyone! 🤠 I have greatly appreciated using awkward in my HEP research since it so neatly follows the structure of our data. I am now working on a project to try to load data stored in LCIO into ak.Array in-memory using the header-only version of awkward to access the LCIO C++ API and construct the array.

The basic demo for using awkward with pybind11 has been very helpful and I have gotten pretty far, but now I am stuck at (what I believe to be) the largest hurdle: representing "references" in the data (what LCIO calls "relations"). In general, these "references" come in two types:

1. An object has a reference to one (or more) objects that are "parts" of it (e.g. the EVENT::Track object contains references to the EVENT::TrackerHits which make up the track).
2. An stand-alone collection which maps objects from one collection to another collection (collections of EVENT::LCRelation). These are often helpful for associating extra information that is not always necessary (e.g. data about the kinks in any constructed tracks can be related to the tracks via this object).

I'm curious if awkward experts have a good idea on how to design this reference behavior. I know I'll need to implement some awkward behavior so that "de-referencing" can happen in an automatic way (coffea already has "de-referencing" for the PhysLite schema so I'm not too worried about writing that side of things), but what about the actual data construction side? Should I just have a "reference" be a Numpy array of ints that I can apply as indices? Is IndexOptionArray what I'm looking for?

As a side note, it appears to me that the LCIO file format (well, technically the slcio file format since its LCIO written with SIO - confusing I know) is completely row-wise - i.e. there is no chunking of columns near to each other in the file (like how ROOT does with TBasket), so I will need to construct the array one event at a time. This will be relatively slow but I think I'll implement some caching-to-parquet protocol if it is really painful. In addition, this means I am focusing on doing a single-pass reading all requested data into memory (a.k.a. I'm not going to attempt to do lazy-loading at this time).

Hopefully this project will be promoted to a "Show and Tell" project in a few weeks 😉 but we will see if I am able to get it into a good enough form to display.

[jpivarski]

In the array structure itself, a NumpyArray of integers is the best you can do. An Awkward Array is a tree structure, not a general graph¹, so any links that would make it not a tree have to at least be of a different kind, like weak references or symlinks. A NumpyArray of integers is like weak references because the existence of the reference doesn't guarantee the existence of the referent; it's a lookup address that you can follow and hope to find the referent.

The lookup function (and action to be taken if the referent is not there) can be encapsulated in a behavior, as it is for Coffea.

Doing a row-wise read in C++ is not as bad as doing it in Python. At least there's that. :)

I was going to say that I was surprised that something as new as the ILC would be based on a custom row-wise format, but I see that the paper goes back to 2003. That's a long development time. Will the same technology be used when the ILC is actually built? CMS switched frameworks twice in its early development. (From something before my time, to ORCA, which I saw the very end of, to CMSSW.)

Footnotes

1. Historically, we went back and forth on that one, and there are Awkward v0 demonstrations of how you can make a graph, both with cycles (a node's child can be its ancestor) and as a DAG (a node's child can be its cousin). When this is possible, all recursive functions need to keep track of what nodes they've seen to avoid recursing in an infinite loop. Also, even when they're possible, these structures are hard to set up, and can't be done without modifying pre-built structures (Python doesn't have lazy val), so the original structure needed a placeholder that was later thrown away. These complications, on top of the fact that demonstrations of non-tree Awkward Arrays were ignored, led to them eventually being dropped. ↩

[agoose77]

To add to @jpivarski's reply, we just added support for stashing metadata in ak.Array.attrs. Coffea doesn't yet use this, as it's such a new addition, so instead stores references in ak.Array.behavior.

The node for re-indexing another node is ak.contents.IndexedArray (which is identical to ak.contents.IndexedOptionArray but without the option-type).

A note on references (without thinking too much about your data structures): it's worth also thinking about whether the constraints that lead to the need for references disappear when working with Awkward Arrays.

[jpivarski]

The indexed node types can't break the tree structure, which is what I think @tomeichlersmith needs, at least for part 2. Perhaps you're right that an IndexedArray could be used in part 1, in which a set of tracks reference each others' hits.

• list of events
  • list of tracks
    • list of
      • IndexedArray
        • hits

Multiple tracks would be able to point to the same hits, and some hits might not be pointed to by any tracks. As long as the hits node is exclusively under the tracks node, this is fine. But if tracks and hits were both directly under events:

• list of events
  • list of tracks
  • list of hits

then the tracks couldn't point into the hits, because the hits would then be both a sibling and a child—the graph would become a DAG, rather than a tree.

---

This is a fundamental issue—Awkward Array types are strictly tree-like. (The values can be DAGs, as illustrated in my first example with two tracks including the same hit through an IndexedArray. From a user perspective, though, the distinction between the multiple views and a copy is hidden—as far as users are aware, the hit might be copied in both tracks.) The strict tree of types also means that a value can't be arbitrarily deep: we can make Awkward Arrays whose values are depth $n$ trees by nesting $n$ type nodes.

Even though I say that this is a fundamental limitation, one could go behind the public interface and try to force it:

infinite_depth = ak.Array([None, 1, 2, 3, 4, 5, 6, 7, 8, 9])
infinite_depth.layout._content = infinite_depth.layout
infinite_depth.layout.index.data[:] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]

makes an IndexedOptionArray that has itself as its child, such that index 0 is index 1 is index 2 is ... is index 9 is index 0...

infinite_depth[0]

raises a RecursionError. Okay, that's an infinite depth value, but what about using a recursive type to make a finite but arbitrary depth tree value?

arbitrary_depth = ak.Array([[1], [2, 3], [4, 5], [6, 7], [], [], [], []])
arbitrary_depth.layout._content = ak.contents.IndexedArray(
    ak.index.Index(arbitrary_depth.layout.content.data),
    arbitrary_depth.layout
)
arbitrary_depth.layout.offsets._data = np.array([0, 1])

should make a structure like this

[[[[]], [[]]], [[[]], [[]]]]

but still, trying to look at it causes a RecursionError because somewhere in the pretty-printer, we try to make a Form, which recurses infinitely. If we instead use ak.to_list, we get a different RecursionError because ak.to_list calls ak.to_packed.

So in some cases, self-reference should be broken, in other cases, it's accidentally broken by the fact that we do recursion on Types and Forms, and in all cases, one has to break the public interface to even attempt it.

We're firmly in the camp of tree-like data only. But that only means that if we want to express something that's like a non-tree, we have to introduce a distinction between strong references and weak references, or hard links and symbolic links in a filesystem. The weak/symbolic links are virtual, but a behavior can execute the code that would make them active.

---

Oh, I've only been showing pathologies in graphs with cycles. You'd still have to break the public interface, but you could make DAGs.

events = ak.Array([
    {"tracks": [[0, 1], [1], [1, 1, 1]], "hits": [1.1, 2.2]}, 
    {"tracks": [[2, 2, 3, 3], [3]], "hits": [3.3, 4.4, 5.5]}.
])
events.layout.content(0).content._content = ak.contents.IndexedArray(
    ak.index.Index(events.layout.content(0).content.content.data),
    events.layout.content(1).content
)

Now the hits is a sibling to tracks and it looks like another copy of it is nested within tracks:

>>> events.type.show()
2 * {
    tracks: var * var * float64,
    hits: var * float64
}
>>> events.tolist()
[
    {'tracks': [[1.1, 2.2], [2.2], [2.2, 2.2, 2.2]], 'hits': [1.1, 2.2]},
    {'tracks': [[3.3, 3.3, 4.4, 4.4], [4.4]], 'hits': [3.3, 4.4, 5.5]},
]

and even

>>> events.layout
<RecordArray is_tuple='false' len='2'>
    <content index='0' field='tracks'>
        <ListOffsetArray len='2'>
            <offsets><Index dtype='int64' len='3'>
                [0 3 5]
            </Index></offsets>
            <content><ListOffsetArray len='5'>
                <offsets><Index dtype='int64' len='6'>
                    [ 0  2  3  6 10 11]
                </Index></offsets>
                <content><IndexedArray len='11'>
                    <index><Index dtype='int64' len='11'>
                        [0 1 1 1 1 1 2 2 3 3 3]
                    </Index></index>
                    <content><NumpyArray dtype='float64' len='5'>[1.1 2.2 3.3 4.4 5.5]</NumpyArray></content>
                </IndexedArray></content>
            </ListOffsetArray></content>
        </ListOffsetArray>
    </content>
    <content index='1' field='hits'>
        <ListOffsetArray len='2'>
            <offsets><Index dtype='int64' len='3'>
                [0 2 5]
            </Index></offsets>
            <content><NumpyArray dtype='float64' len='5'>[1.1 2.2 3.3 4.4 5.5]</NumpyArray></content>
        </ListOffsetArray>
    </content>
</RecordArray>

but there's only one copy of the hits in memory. That situation might not last if some ak.* operation needs to make a copy of the tracks's nested contents, but deep copies are avoided whenever possible.

[agoose77]

Yes, this last example is what I'm pointing to -- as long as you aren't trying to make cycles, we can share layouts at different depths within our layout system!

[tomeichlersmith]

Thank you for this long and detailed discussion @jpivarski and @agoose77 - I've learned some more and I got some ideas to try in my loading framework.

break the public interface

How bad would it be if I did this? Would that just mean my package would be more "delicate" to future developments of awkward?

Will the same technology be used when the ILC is actually built?

I am actually not involved with the ILC at all, so I unfortunately cannot answer this question. I'm working with an experiment at SLAC which chose LCIO as the data format for their reconstruction software (written in java) and I am interested in getting the data files into awkward in an easier/faster way than my current solution (which is just to copy the data into a ROOT file and then use uproot).

[jpivarski]

The internals (anything starting with an underscore) can in principle be changed at any time, and we wouldn't know who is using it to contact everybody before making a change. So it would be a risk that you'd be taking on, a risk that some new version of Awkward Array could break your code without any warning (which we post as deprecation warnings when changing the public interface).

The breakage might be unlikely...

I am actually not involved with the ILC at all, so I unfortunately cannot answer this question. I'm working with an experiment at SLAC which chose LCIO as the data format for their reconstruction software (written in java) and I am interested in getting the data files into awkward in an easier/faster way than my current solution (which is just to copy the data into a ROOT file and then use uproot).

It sounds like a good project!