chocoteam / choco-solver

An open-source Java library for Constraint Programming
http://choco-solver.org/
BSD 4-Clause "Original" or "Old" License
687 stars 137 forks source link

Reduce memory footprint for CompactTable #1017

Open cprudhom opened 1 year ago

cprudhom commented 1 year ago

I think there is room to reduce CT+ structure initialization when tuples' ranges are smaller than domains' range.

For instance:

IntVar[] xs = model.intVarArray("X", 4, 0, 99_999);
Tuples comb = new Tuples(true);
comb.setUniversalValue(-1);
comb.add(1, 0, -1, 0);
comb.add(1, 3, -1, 3500);
comb.add(2, 3, -1, 3500);
comb.add(4, 3, -1, 3500);
model.table(xs, comb, "CT+").post();

CT will allocate supports array (of longs) of size 99_999, whereas smaller size would do the job.

I'm not saying it is easy to do, but it could be useful.

Note that I agree that the domain could be reduced at the first place, but sometimes (when parsing instances for instance) this is quite complicated.

PS: same goes for "STR2+"

martins-avots commented 1 year ago

One could maybe add an array shrinking function inside the model#table method. Alternatively, one could pass a Function<Integer, IntVar[]> to the model#table method, in order to avoid any duplicate allocations.