search

google / or-tools

Google's Operations Research tools:
https://developers.google.com/optimization/
Apache License 2.0
10.79k stars 2.09k forks source link

Performance regression from v9.7 -> v9.8/v9.9/v9.10 #4166

Open hanno-becker opened 3 months ago

hanno-becker commented 3 months ago

What version of OR-Tools and what language are you using? Version: v9.7, v9.8, v9.9 Language: Python

Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi)

CP-SAT

What operating system (Linux, Windows, ...) and version?

Apple M1 Pro, MacOS Sonoma Version 14.3.1

What did you do?

Updated OR-Tools from v9.7 to v9.8 and v9.9 when used as the backend for the SLOTHY assembly superoptimizer.

What did you expect to see

CP-SAT performance that is similar or better in terms of runtime and consistency.

What did you see instead?

Significant inconsistency in the runtime of CP-SAT.

Steps to reproduce:

  1. Save the attached model.txt (5.4MB) and the following as run_model.py:
# Following https://groups.google.com/g/or-tools-discuss/c/jg-LYSWAgZA/m/QMsyJQI-AgAJ

import ortools
from ortools.sat.python import cp_model
from google.protobuf import text_format

TIMEOUT=15 # In the good case, the model solves in ~8s on an Apple M1
ITERATIONS=30

def load_and_solve(i):
    model = cp_model.CpModel()
    with open("model.txt", "r") as file:
        text_format.Parse(file.read(), model.Proto())
    print (f"[{i}]: Solve using OR-Tools v{ortools.__version__} ... ", end='', flush=True)
    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = TIMEOUT
    status = solver.Solve(model)
    status_str = solver.StatusName(status)
    print(f"{status_str}, wall time: {solver.WallTime():.4f} s")

for i in range(ITERATIONS):
    load_and_solve(i)
  1. In an environment with OR-Tools v9.7/v9.8/v9.9 setup, do 
    python3 run_model.py
  2. Observe
    • High consistency in performance for v9.7
    • Low consistency in performance for v9.8 and v9.9

Here are the outputs on my local machine (see above):

[0]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.7095 s
[1]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6358 s
[2]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6029 s
[3]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6173 s
[4]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6677 s
[5]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6342 s
[6]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6091 s
[7]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6222 s
[8]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6853 s
[9]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6149 s
[10]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6368 s
[11]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6400 s
[12]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6311 s
[13]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6256 s
[14]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6580 s
[15]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6790 s
[16]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.5866 s
[17]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6641 s
[18]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6367 s
[19]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.5504 s
[20]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6438 s
[21]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6866 s
[22]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6646 s
[23]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6997 s
[24]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.7523 s
[25]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6659 s
[26]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6842 s
[27]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6527 s
[28]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6678 s
[29]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6791 s

[0]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0477 s
[1]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0498 s
[2]: Solve using OR-Tools v9.8.3296 ... OPTIMAL, wall time: 8.0398 s
[3]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0509 s
[4]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0495 s
[5]: Solve using OR-Tools v9.8.3296 ... OPTIMAL, wall time: 7.7925 s
[6]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0494 s
[7]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0490 s
[8]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0499 s
[9]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0521 s
[10]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0441 s
[11]: Solve using OR-Tools v9.8.3296 ... OPTIMAL, wall time: 7.5001 s
[12]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0480 s
[13]: Solve using OR-Tools v9.8.3296 ... OPTIMAL, wall time: 7.7570 s
[14]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0510 s
[15]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0435 s
[16]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0512 s
[17]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0548 s
[18]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0482 s
[19]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0505 s
[20]: Solve using OR-Tools v9.8.3296 ... OPTIMAL, wall time: 7.7389 s
[21]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0518 s
[22]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0549 s
[23]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0517 s
[24]: Solve using OR-Tools v9.8.3296 ... OPTIMAL, wall time: 8.5971 s
[25]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0511 s
[26]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0454 s
[27]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0479 s
[28]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0486 s
[29]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0584 s

[0]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 7.5733 s
[1]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1111 s
[2]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1614 s
[3]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 8.0639 s
[4]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 8.1368 s
[5]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 7.9110 s
[6]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1061 s
[7]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1078 s
[8]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1067 s
[9]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 7.9369 s
[10]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 8.0701 s
[11]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 7.9486 s
[12]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 7.9123 s
[13]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1139 s
[14]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1011 s
[15]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 7.5487 s
[16]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 7.9708 s
[17]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1062 s
[18]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1557 s
[19]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1104 s
[20]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1042 s
[21]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1049 s
[22]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 7.9224 s
[23]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 8.0476 s
[24]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1151 s
[25]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 7.9463 s
[26]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1065 s
[27]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 7.9260 s
[28]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 7.9473 s
[29]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 7.9736 s

Anything else we should know about your project / environment

If you need any more information, please let me know.

lperron commented 3 months ago

how many workers are you using ?

lperron commented 3 months ago

the hint is incomplete. Can you improve it ?

lperron commented 3 months ago

I have consistent results with these parameters:

fix_variables_to_their_hinted_value:true,num_workers:10,use_feasibility_jump:false,use_rins_lns:false,use_feasibility_pump:false,cp_model_probing_level:0

It seems to solve consistently in 6-7s.

hanno-becker commented 3 months ago

how many workers are you using ?

The minimal example above does not set them explicitly, so I assume it's determined by the number of cores on the system? In my case, that's 8.

the hint is incomplete. Can you improve it ?

Can you elaborate? Should one either give no hints at all or hints to all variables?

I have consistent results with these parameters: fix_variables_to_their_hinted_value:true,num_workers:10,use_feasibility_jump:false,use_rins_lns:false,use_feasibility_pump:false,cp_model_probing_level:0

The configurationfix_variables_to_their_hinted_value:true does not seem like an option in my case, because the hints really are only hints -- I set them based on an expectation that for the majority of variables of a certain kind the hinted property will be true, but there will be exceptions (in more detail: SLOTHY can interleave neighbouring loop iterations, and there are booleans indicating if an instruction is pulled forward into the previous iteration (e.g. an early load), or deferred to the next iteration (e.g. late store) -- most instructions will stay in their original iteration and hence the tool is hinting at that, but without early/late instructions altogether, the tool would be much less powerful).

Can you comment further on the configuration options you have set to force consistency? It does look like search either succeeds quickly, or some search strategy leads the solver astray entirely (because where the usual ~8s solution is missed, solution are often not even found with a significantly larger budget.

lperron commented 3 months ago

The closer to completeness the hint is, the less effort is needed in search. We do process complete feasible hints differently. Laurent Perron | Operations Research | @.*** | (33) 1 42 68 53 00

Le lun. 1 avr. 2024 à 17:51, Hanno Becker @.***> a écrit :

how many workers are you using ?

The minimal example above does not set them explicitly, so I assume it's determined by the number of cores on the system? In my case, that's 8.

the hint is incomplete. Can you improve it ?

Can you elaborate? Should one either give no hints at all or hints to all variables?

I have consistent results with these parameters:

fix_variables_to_their_hinted_value:true,num_workers:10,use_feasibility_jump:false,use_rins_lns:false,use_feasibility_pump:false,cp_model_probing_level:0

The configurationfix_variables_to_their_hinted_value:true does not seem like an option in my case, because the hints really are only hints -- I set them based on an expectation that for the majority of variables of a certain kind the hinted property will be true, but there will be exceptions (in more detail: SLOTHY can interleave neighbouring loop iterations, and there are booleans indicating if an instruction is pulled forward into the previous iteration (e.g. an early load), or deferred to the next iteration (e.g. late store) -- most instructions will stay in their original iteration and hence the tool is hinting at that, but without early/late instructions altogether, the tool would be much less powerful).

Can you comment further on the configuration options you have set to force consistency? It does look like search either succeeds quickly, or some search strategy leads the solver astray entirely (because where the usual ~8s solution is missed, solution are often not even found with a significantly larger budget.

— Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/4166#issuecomment-2030036562, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3M5G7FGLMAHO44BJJLY3F667AVCNFSM6AAAAABFQV5KC6VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDAMZQGAZTMNJWGI . You are receiving this because you commented.Message ID: @.***>

hanno-becker commented 3 months ago

The closer to completeness the hint is, the less effort is needed in search.

There are usually simple solutions which follow the (incomplete) hints, but they won't minimize the given objective (stall minimization, in SLOTHY's case) -- are those still useful hints in your experience, or should they be removed?

lperron commented 3 months ago

can you try num_workers:24 ?

lperron commented 3 months ago

or just num_workers:1,search_branching:FIXED_SEARCH

hanno-becker commented 3 months ago

What is the takeaway here? When should I consider setting search_branching=FIXED_SEARCH and/or num_workers=1?

I will start a SLOTHY CI run using search_branching=FIXED_SEARCH and see how other workloads fare.

hanno-becker commented 3 months ago

@lperron Unfortunately, unconditionally setting search_branching=FIXED_SEARCH (with or without num_workers=1) does lead to performance problems in other SLOTHY CI workloads.

How would you suggest to proceed here? Do you have a sense of what v9.7->v9.8 change might have triggered this performance change? Has some new search strategy been added in v9.8 that might lead the solver astray in the models produced by SLOTHY?

lperron commented 3 months ago

OK. I have no quick solution. Stay and 9.7 for the time being.

If you could send me a collection of models, I can integrate those into out benchmark suite.

hanno-becker commented 3 months ago

@lperron I will prepare a set of models representative of SLOTHY workloads and share them in the coming days.

hanno-becker commented 3 months ago

@lperron @Mizux I have exported some of the models exercised in the SLOTHY CI here: https://github.com/slothy-optimizer/slothy/tree/ci_models/paper/scripts/models Performance numbers as observed on my local Apple M1 are in https://github.com/slothy-optimizer/slothy/blob/ci_models/paper/scripts/models/results.txt. Some of them are solved/refuted very quickly, so one should probably hand-select a few that can be solved in seconds-minutes.

Please let me know if this is useful to you, or what kind of models/format you would prefer otherwise.

lperron commented 2 months ago

can you try with these parameters ?

um_workers:10,linearization_level:0,use_rins_lns:false,use_feasibility_pump:false,cp_model_probing_level:0
lperron commented 2 months ago

I ran all the models with 15 runs per model with different settings

16 workers, 20s:

    problems      optimal     feasible   infeasible      unknown
        1440          945           15          465           15

12 workers, 20s, linearization_level:0,use_rins_lns:false,use_feasibility_pump:false,cp_model_probing_level:0

    problems      optimal     feasible   infeasible      unknown
        1440          950           15          465           10
hanno-becker commented 2 months ago

@lperron Thank you for investigating! What do your measurements tell you?

lperron commented 2 months ago

The second set of parameters is stable, and solve all the set of problems reliably.

hanno-becker commented 2 months ago

@lperron Thank you very much for investigating. Are you going to make changes in CP-SAT to make the behaviour the default, or what are next steps?

lperron commented 2 months ago

No.

Try setting these parameters in your code, and t ll me how it performs.

Le mar. 23 avr. 2024, 05:15, Hanno Becker @.***> a écrit :

@lperron https://github.com/lperron Thank you very much for investigating. Are you going to make changes in CP-SAT to make the behaviour the default, or what are next steps?

— Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/4166#issuecomment-2071330568, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3I2OYNWR5VWZRBGWT3Y6XG4NAVCNFSM6AAAAABFQV5KC6VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDANZRGMZTANJWHA . You are receiving this because you were mentioned.Message ID: @.***>

hanno-becker commented 2 months ago

@lperron I'll run the CI on the proposed parameters and get back to you.

hanno-becker commented 1 month ago

Unfortunately, the parameters didn't help -- the tests were still timing out.

@lperron @Mizux How can we move forward here? I tried v9.10 in the meantime, but am still seeing CI failing because of timeouts.

hanno-becker commented 1 week ago

@lperron @Mizux Gentle ping.

lperron commented 1 week ago

No progress on our side. This is on my radar. Laurent Perron | Operations Research | @.*** | (33) 1 42 68 53 00

Le mar. 2 juil. 2024 à 07:43, Hanno Becker @.***> a écrit :

@lperron https://github.com/lperron @Mizux https://github.com/Mizux Gentle ping.

— Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/4166#issuecomment-2201984909, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3JTZRWSMBJ2XMOEPQLZKI4YTAVCNFSM6AAAAABFQV5KC6VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDEMBRHE4DIOJQHE . You are receiving this because you were mentioned.Message ID: @.***>

lperron commented 1 week ago

I re-ran everything this morning

parameters: num_workers:16,max_time_in_seconds:15,cp_model_probing_level:0,linearization_level:0

I run each example 5 times. Everything is solved optimally (optimal or infeasible), except slothy_ci_fft_1712650422585 which is feasible all 5 runs, and ntt_dilithium_123_45678_a55_1712651065788 which is unknown 2 times out of 5.

hanno-becker commented 2 days ago

@lperron With those parameters (excluding timeout, which SLOTHY sets itself), the CI passes for the first time in https://github.com/slothy-optimizer/slothy/pull/57, though still at a large performance penalty compared to v9.7: For example, the examples_ntt_kyber_dilithium_neon_core job runs in 30min instead of 20min. I'll re-run to see if this is consistent.

Is there a way to restore the v9.7 behaviour through specific parameters, or was the switch from v9.7 to v9.8 deeper?

lperron commented 2 days ago

Good news.

We are in a optimizing spree. Hopefully, it will show in your benchmarks. Laurent Perron | Operations Research | @.*** | (33) 1 42 68 53 00

Le lun. 8 juil. 2024 à 16:47, Hanno Becker @.***> a écrit :

@lperron https://github.com/lperron With those parameters (excluding timeout, which SLOTHY sets itself), the CI passes for the first time in slothy-optimizer/slothy#57 https://github.com/slothy-optimizer/slothy/pull/57, though still at a large performance penalty compared to v9.7: For example, the examples_ntt_kyber_dilithium_neon_core job runs in 30min instead of 20min. I'll re-run to see if this is consistent.

— Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/4166#issuecomment-2214298999, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3PMOC4OR6AC6TVT25LZLKQ7RAVCNFSM6AAAAABFQV5KC6VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDEMJUGI4TQOJZHE . You are receiving this because you were mentioned.Message ID: @.***>

hanno-becker commented 2 days ago

@lperron Thanks! Should I read this as "Wait for 9.11, it may solve your issues"?

lperron commented 2 days ago

it could solve your issues, ..., or not :-) Laurent Perron | Operations Research | @.*** | (33) 1 42 68 53 00

Le lun. 8 juil. 2024 à 17:46, Hanno Becker @.***> a écrit :

@lperron https://github.com/lperron Thanks! Should I read this as "Wait for 9.11, it may solve your issues"?

— Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/4166#issuecomment-2214484734, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3MYUX3I4QVP3AGRWTLZLKX4LAVCNFSM6AAAAABFQV5KC6VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDEMJUGQ4DINZTGQ . You are receiving this because you were mentioned.Message ID: @.***>

hanno-becker commented 2 days ago

@lperron Ok, let's wait and see :-)