[QIR] Alias management on arrays can have major perf impact

[swernli]

Whenever an array in QIR is set to a new variable, the alias counts on each item have to be incremented for the new alias and later decremented if the previous variable goes out of scope. This can also happen when returning an array from a callable, such that the return results in a loop over each element decrementing alias count and then the caller will have a loop over every element incrementing the alias count when capturing the returned value in a variable. In some testing, we have algorithms where list sizes can get very large (up to 500k), and the repeated looping over the elements for alias count management noticeably impacts perf as the array is passed around. We should investigate a way to optimize alias and reference counting for contained items to avoid having to scale by array size.

[swernli]

One idea I had for addressing this is that we could have a mechanism whereby an object registers a container, and then has a function that will calculate the alias/reference count on the object by summing the direct count with the count reported from the container. That way incrementing/decrementing the count on the container itself will automatically increment/decrement the count on all contained objects without having to loop through them. I haven't thought this idea out all the way, but it would result in a change to the QIR spec, so it's possible this discussion and issue should be moved to the language repo first before turning into a code change here.

[bettinaheim]

A low risk improvement that won't require a spec update is to omit alias count increases when assigning to variables as long as there are no copy-and-update expressions in the callable. An improvement over that is to detect which variables the copy-and-update expressions involve. I think there are a lot of good improvements here we can do, and I think your idea above is good to explore further, but I would like to defer any riskier changes until we have better test coverage.

[bettinaheim]

Thinking a bit more carefully: it is slightly more than just copy-and-update to watch out for; basically we'd need to look for anything where the runtime decides to copy or not copy an array (or other data structure) depending on the alias count, and if a variable is used in that context we need to update the count.