chocoteam / chocoteam/choco-solver
Reduce memory footprint for CompactTable
- Dominant language
- Java
- Stars
- 779
- Forks
- 159
- Avg merge
- 6d 9h
- Merged PRs (30d)
- 10
Description
I think there is room to reduce CT+ structure initialization when tuples' ranges are smaller than domains' range.
For instance:
```java
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+"
Contributor guide
Research direction
Start by locating the CompactTable implementation behind the CT+ option and the corresponding STR2+ implementation, then inspect how supports are sized from tuple and domain ranges. Measure the example's allocation and define completion as preserving solver behavior while avoiding arrays sized to the full domain when smaller tuple ranges suffice, with regression coverage for both propagators.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- backend
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100