Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Performance regression after 9.9.4133 (3194fd5) #4189

Open
magneticflux- opened this issue Apr 18, 2024 · 4 comments
Open

Performance regression after 9.9.4133 (3194fd5) #4189

magneticflux- opened this issue Apr 18, 2024 · 4 comments
Assignees
Labels
Lang: Java Java wrapper issue Solver: CP-SAT Solver Relates to the CP-SAT solver
Milestone

Comments

@magneticflux-
Copy link

What version of OR-Tools and what language are you using?
Version: main, 9ed0074, 3194fd5
Language: Java

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

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

What did you do?
Steps to reproduce the behavior:

  1. Solve the attached model using 9.9.4132 (9ed0074) (it takes ~20 seconds on an i9-10900K)
  2. Solve the attached model using 9.9.4133 (3194fd5) (it takes ~40 seconds on the same hardware)

What did you expect to see

log_9ed0074090aacba704afd420234a6083e2644b5b.txt

What did you see instead?

log_3194fd5bb2017957dd3460719ba08affaa803511.txt

The model I used for comparison:
model.zip

Some differences I noticed in the logs:

  • # vars in presolve went down (different propagation changing probing order?)
  • # propagations under "Search stats" went up, but the summary stayed the same
  • approx gap integral went up
  • all SAT stats increased significantly
@magneticflux- magneticflux- changed the title Performance regression after 3194fd5bb2017957dd3460719ba08affaa803511 Performance regression after 9.9.4133 Apr 18, 2024
@magneticflux- magneticflux- changed the title Performance regression after 9.9.4133 Performance regression after 9.9.4133 (3194fd5) Apr 18, 2024
@Mizux Mizux added Lang: Java Java wrapper issue Solver: CP-SAT Solver Relates to the CP-SAT solver labels Apr 18, 2024
@Mizux Mizux added this to the v10.0 milestone Apr 18, 2024
@fdid-git
Copy link
Collaborator

I think there is a high variance on your model (like it is often the case, especially in multithread). If you try to solve it many times with different random seed, you can get various solve time. I attached an histogram of 1k runs with the latest version.

Histogram of walltime

Also, solving it with one thread, like with --params subsolvers:"max_lp" seems to work better now.
So I don't think there is much we can do here.

@magneticflux-
Copy link
Author

magneticflux- commented Apr 18, 2024

You're right, there's a lot of variance in my model. I've been using ministat to do t-tests comparing changes and updates and it seems like I got bizarrely unlucky with the first 6 samples. Then, I ran 3 more samples on another machine and it took ~2x the usual time again so I checked the commits and grabbed (what I thought were) representative logs.

I went and did some other stuff and just started a new run with 9.9.4133 now. The new linear propagation code seems to be slightly slower on average, and the standard deviation is much higher which I failed to account for in my initial assessment:

+---------------------------------------------------------------------------------------------------------+
|       +                                                                                                 |
|      ++                                                                                                 |
|      ++                                                                                                 |
|      ++                                                                                                 |
|     +++ +                                                                                               |
|     +++ +                                                                                               |
|     +++ +                                                                                               |
|     +++ +                                                                                               |
|     +++ + x                                                                                             |
|     +++ +xx                                                                                             |
|     +++ +xxx                                                                                            |
|     +++ +xxx                                                                                            |
|     +++ +xxx                                                                                            |
|    ++++ +xxx                                                                                            |
|    ++++ +xxx                                                                                            |
|    +++++**xx                                                                                            |
|    +++++**xx                                                                                            |
|    +++++**xx                                                                                            |
|    +++++***x                                                                                            |
|    +++++***x                                                                                            |
|    +++++***x                                                                                            |
|    +++++***x                                                                                            |
|    +++++***xx                                                                                           |
|    +++++***xx                                                                                           |
|    +++++***xx x                                                                                         |
|    +++++***xx x                                                                                         |
|    +++++***xx x                                                                                         |
|    +++++***xx x                                                                                         |
|    +++++***xx x                                                                                         |
|    +++++***xxxx                                                                                         |
|    +++++***xxxx                                                                                         |
|   ++++++***xxxx     +                                                                                   |
|   ++++++***xxx*     +                                                                                   |
|   ++++++***xxx*+    +   +                                                                               |
|   ++++++***x****+   + x +                                                                               |
|   ++++++********+   + x +         +                                                                     |
|   ++++++********+   + x +         +                                                                     |
|   ++++++*********   + xx+    ++   +                                                                     |
|   ++++++********** ++ xx+ +  ++  ++ +  +                                                                |
|   ++++++********** ++ xx+ +  ++  ++ +  + +                                                              |
|   ++++++********** ++ *x+ ++ ++ +++ +  + +                                                              |
|   ++++++********** +++**+++++++ ++++++ + ++                                                             |
|   ++++++********** +++**++++++++++++++ + ++                                                             |
|   ++++++********** +++**++++++++++++++ ++++        +                                                    |
|  +++++++**********x+++**++++++++++++++ +++++   +   +                                                    |
|  ++++++************+++**++++++++++++++ +++++  ++ + +                                                    |
|  ++++++************+++**+++++++++++++++++++++ ++++ +  +                                                 |
|  ++++++*************+***+++++++++++++++++++++ ++++++ ++                                                 |
|  ++++++*************+****++++++++++++++++++++ +++++++++   ++                                            |
| +++++++******************++++++++++++++++++++ +++++++++  +++    +                                       |
| +++++++******************++++++++++++++++++++++++++++++ ++++   ++    + +                                |
| +++++********************++++++++++++++++++++++++++++++ ++++++ +++ +++ +   +    +                       |
|++++++********************++++*++*++*+*+++++**+++++++++++++++++++++ +++++++ +++  +         +        +   +|
|         |___MA_____|                                                                                    |
|     |___________M_____A_________________|                                                               |
+---------------------------------------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x 387       18.9284       31.4842        21.078     21.568593     1.7512407
+ 1000       16.9395       50.3212       22.5186     24.288804     5.7543101
Difference at 99.5% confidence
	2.72021 +/- 0.920084
	12.6119% +/- 4.26585%
	(Student's t, pooled s = 4.97378)

I'll leave it running to get a better estimate, and I might try testing a patch to change which vars are pushed first to see if that makes a difference.
Thank you for taking the time to run an independent test, and sorry about the noise if this turns out to be benign!

@fdid-git
Copy link
Collaborator

Yes, I think the new code adds more "randomness" which explain the higher variance, especially if you test with different random seed. On another hand, the code should be more robust to future change in other places.

@Mizux Mizux modified the milestones: v10.0, Backlog Apr 26, 2024
@lperron
Copy link
Collaborator

lperron commented Sep 27, 2024

Can you retry ?

I have good results with main. So try with 9.11.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Lang: Java Java wrapper issue Solver: CP-SAT Solver Relates to the CP-SAT solver
Projects
None yet
Development

No branches or pull requests

4 participants