This patch adds support for intersection a set with a relation.
Not blocking, but I would be interested to see a more efficient implementation. Currently, it will first copy the constraints from poly to rel, then resize rel to accommodate range variables that likely leads to copies, then resize it *again* to accommodate local ids, and then copy the constraints from rel to this. Sounds like a whole lot of copying for a relatively simple operation. Perhaps we could get this done with only one resize (of the constraints of this relation, which increases both the number of rows and the number of ranges) and a direct copy of coefficients from poly to this. It may be less concise and use non-trivial indexing, but likely more efficient.
That's why I mentioned the increase of both the rows and columns in one sweep. I had drilled down a bit in the code and had seen that mereLocalIds does additional column manipulations itself (with even more copies!), which led me to conclude that decreasing the number of copies required non-trivial work and it was not reasonable to block this patch until that work is done. I am quite positive that what I have in mind will ultimately work, it's just harder to implement; if one transitively inlined mergeLocalIds into this call, it would become more obvious.
On a general design point, I think more care should be taken, eventually, about the memory effects of copies hidden under the layers of API. Copies are not free (although small copies may be cheap) and may have larger effects on memory behavior of the objects copied take, e.g., a little bit more than half of L1. It is not clear to me how much this affects performance of some compilation flow, largely because I don't have access to an end-to-end flow that extensively uses affine, especially compared to algorithmically-expensive things like the simplex, but I take small gains whenever possible. (One could imagine some sort of transactional protocol for updating the contraint matrices that has an indirection table for column accesses and doesn't actually remove/reshuffle the columns until the transaction is committed. Depending on the amount of data copied vs. the cost of extra indirection in address computation, this may end up beneficial.)
There is another small trade-off here: increase the API surface by having overloads that take rvalue-references but let the user spare the copy if they know they don't need the object anymore after the operation.
Right, I see what you mean.
We have some more work in the pipeline to improve the interface and de-virtualize the hierarchy. After that, we can benchmark, try out the transaction idea, try to remove copies as much as possible and see how it impacts performance.
The rvalue-reference idea also seems interesting and I think we can try to prototype that.
use inverse here?
Not for this patch, but I would like an intersect function to mergeLocalIds and append.
In the operations that were added previously, we've been following a system where most operations return their results, with operations that mutate in-place having a suffix InPlace, like unionInPlace. Not for this patch, but we should have uniformity in naming here.