Performance degradation when using compact instances

[MoraruMaxim]

We tried to decrease the memory footprint of the FleCSI applications by using the Legion compact instances. This resulted in a huge slowdown (e.g. some of our applications have become 3 times slower).

If needed, I can potentially provide some profiling data.

[lightsighter]

I think it would be helpful to describe the number of rectangles in your compact sparse instances and the access patterns (e.g. random access, linear walk, etc.).

I would also describe what kind of accessors you're using. I'm presuming MultiAffineAccessor which at the moment does not support spatial search to discover which piece is needed to access for a random access entry. Therefore unless you hit in the cache, access time looks more like O(N) instead of O(log N).

[apryakhin]

I presume legion implements it's own spatial data structure somewhere? Realm I think builds a form of a kd-tree to optimize intersection testing. That should probably be packaged into some form of public data structure and used everywhere including accessors.

[apryakhin]

This issue looks relevant:

• Realm: Acceleration Data Exposure #629

[lightsighter]

I presume legion implements it's own spatial data structure somewhere? Realm I think builds a form of a kd-tree to optimize intersection testing. That should probably be packaged into some form of public data structure and used everywhere including accessors.

Yes, #629 is somewhat relevant, but I don't think we need to expose the acceleration data structure here though. We just need to leverage it in this case for the multi-affine accessor class inside Realm. It would be good to use Realm's existing spatial acceleration data structure rather than rolling a new one. Although, really we should only be doing this if the number of rectangular pieces in the instance is "large" and a linear search over the pieces would be inefficient. It's unclear where that threshold is but it shouldn't be too hard to measure as it should be a property of the number of rectangles and not their shapes.

For now I've encouraged @MoraruMaxim to use Realm's compute covering utility to try to coarsen up his compact sparse instances into fewer pieces that still doesn't waste much memory.