MemoryUtils code explosion

[JCampbellBradley]

At present, the code generators (both WriteC and ScheduledC) attempt to create a mapping from the iteration space of each variable to a one-dimensional array, so that only the memory corresponding to in-bounds points needs to be allocated.

The first problem with this is that it involves a call to Barvinok's 'card' function with potentially very complex unions of polyhedra as the inputs. When calling WriteC on a modified version of bpmax (see attached files), the code generator spent approximately 10 minutes within the card function alone.

The second, and more major problem, is that the generated memory mappings explode in complexity very quickly. The .c file resulting from my modified bpmax ended up being ~16 MB in size, despite only being ~500 lines long total.

So, our current method seems to be intractable. The most naive way to solve this problem, in my opinion, would be to generate memory for the entire bounding box of each variable. This is extremely wasteful in terms of space, but would not require complex mapping functions, nor take up any extra time when accessing memory. Alternatively, we could try to find some conservative superset of the variable iteration space (a convex hull of some kind), in order to balance the costs of memory waste, with larger file size and memory access time.

Some approaches I've thought of, in descending order of hull complexity:

1. Polyhedral hull: It might be the case that most of this complexity explosion comes from trying to iterate through unions of polyhedra, in which case taking the polyhedral hull should largely solve the problem. We should test this and see what sort of code it generates.
2. Right-simplicial-prism hull: First, find the bounding box of the variable space. Then, for each dimension, cut the space in half diagonally, if possible. This has the same worst-case memory wastage as the bounding box approach, but given how common it is to define variable domains as right-simplicial prisms, or something close to that, I suspect this will have a good realistic-case performance. That, and the memory access functions should be very simple and efficient.
3. Minimal simplicial hull: Finding the minimal simplicial hull of a polyhedron is a very hard problem, but there are efficient methods to find a local minimum. Those would take a lot work to implement (too much work, in my opinion), but the generated simplex ought to be easy to iterate through.
4. Bounding box: Reserving memory for the entire box surrounding a variable is extremely wasteful of memory; post-exponentially so with regards to dimension in the worst case (i.e. when a variable is a simplex). It would negate the need for a memory access function entirely, however.

It might be worth it to implement multiple of these, and allow the user to select whichever suits their needs the most. This could be done after or along with issue #129.

bpmax_split.alpha