Propagation profiler

[cprudhom]

Some times ago, a request for a minimal profiler was done (Profiler).
I'm considering the issue now, and have some propopsitions.
The idea is to record various statistics related to propagation:

• From a propagator point of view: number of coarse propagations (global propagation), number of fine propagations (on a specific variable modification), number of times it filters values, number of times it throws failures.
• From a variable point of view: number of times a specific event occurs (f-ex, instantiation).

I propose to export the result to a file.
I consider either to show raw values or to normalise them.

Raw values

Propagators
 
* id      : row id
* coarse  : for a given propagator, number of coarse propagations, i.e., calls to `propagate(int)`
* fine    : for a given propagator, number of fine propagations, i.e., calls to `propagate(int,int)`
* filter  : for a given propagator, number of times a call to propagation removes a value from a variable's domain
* fails   : for a given propagator, number of times it throws a failure
* name    : name of the given propagator 
 
 id        coarse      fine    filter     fails  name
 0              1         0         0         0  "true"
 1              1         0         3         0  "binLoad[0] + binLoad[1] + binLoad[2] = 24576"
 2              3         2         4         0  "PropBinPacking(VGU0, VGU1, VGU2, ..., binLoad[2])"
Total           5         2         7         0

Integer variables
 
* id      : row id
* inst    : for a given integer variable, number of instantiation events
* lower   : for a given integer variable, number of lower bound increasing events
* upper   : for a given integer variable, number of upper bound decreasing events
* bounds  : for a given integer variable, number of bounds modification events
* remove  : for a given integer variable, number of value removal events
* name    : name of the given variable 
 
 id          inst     lower     upper    bounds    remove  name
 0              1         0         0         0         0  "VGU0"
 1              1         0         0         0         0  "VGU1"
 2              2         0         0         0         0  "VGU2"
 3              2         0         0         0         0  "VGU3"
 4              0         0         0         0         0  "VGU4"
 5              0         0         0         0         0  "VGU5"
 6              1         0         0         0         0  "binLoad[0]"
 7              1         0         0         0         0  "binLoad[1]"
 8              1         0         0         0         0  "binLoad[2]"
 9              0         0         0         0         0  "cste -- 24576"
 10             0         0         0         0         0  "cste -- 1"

Normalised

Propagators
 
* id      : row id
* coarse  : for a given propagator, number of coarse propagations, i.e., calls to `propagate(int)`
* fine    : for a given propagator, number of fine propagations, i.e., calls to `propagate(int,int)`
* filter  : for a given propagator, number of times a call to propagation removes a value from a variable's domain
* fails   : for a given propagator, number of times it throws a failure
* name    : name of the given propagator 
 
 id        coarse      fine    filter     fails  name
 0         20,00%     0,00%     0,00%      NaN%  "true"
 1         20,00%     0,00%    42,86%      NaN%  "binLoad[0] + binLoad[1] + binLoad[2] = 24576"
 2         60,00%   100,00%    57,14%      NaN%  "PropBinPacking(VGU0, VGU1, VGU2, ..., binLoad[2])"
Total           5         2         7         0

Integer variables
 
* id      : row id
* inst    : for a given integer variable, number of instantiation events
* lower   : for a given integer variable, number of lower bound increasing events
* upper   : for a given integer variable, number of upper bound decreasing events
* bounds  : for a given integer variable, number of bounds modification events
* remove  : for a given integer variable, number of value removal events
* name    : name of the given variable 
 
 id          inst     lower     upper    bounds    remove  name
 0              1         0         0         0         0  "VGU0"
 1              1         0         0         0         0  "VGU1"
 2              2         0         0         0         0  "VGU2"
 3              2         0         0         0         0  "VGU3"
 4              0         0         0         0         0  "VGU4"
 5              0         0         0         0         0  "VGU5"
 6              1         0         0         0         0  "binLoad[0]"
 7              1         0         0         0         0  "binLoad[1]"
 8              1         0         0         0         0  "binLoad[2]"
 9              0         0         0         0         0  "cste -- 24576"
 10             0         0         0         0         0  "cste -- 1"

Any comment is welcome.

CP

[fhermeni]

Thanks for this initiative.
At my level, it matters to catch constraints that never filters. So we need to have a way to profile what is done inside the initial propagation as well.
In terms of result exploitation, a human readable format makes sense but eventually, I need to be able to export data that can be manipulated somehow.

So, once the profile is done, the export should be manageable.
You can provide a default collector (the human readable format) but having the possible to use our own collector would be nice (CSV, JSON, YAML, ...)

[cprudhom]

As a first attempt, I wrote CSV file.
But, it is not human-readable and requires a third-party software to be read.
In addition, I asked myself what is the usage of a profiler.
I think the main idea is simply to have an idea of the impact of each propagator on the variables.
So what would be the benefit of using JSON object, f-ex ?

Note : I can record the total time spent in each propagator, but I doubt that it will be very representative for low-complexity ones.

[cprudhom]

Maybe, an alternative would be to provide propagation engine observer.
Such an observer could then be turned into anything, by default pretty file export.

[dimitri-justeau]

Hello ! I also think that this is a great idea !

To share my experience, when I need to profile Choco execution, I use the Intellij'idea profiling tool. It is useful because it can help to identify bottleneck methods, but it has some limitations. When optimizing the implementation of set and graph views, I needed to know the number of times related propagators were called, how many times domain modifications methods were called, and so on. I did it manually by temporarily adding counter variables, so a profiler would have helped me a lot in this process. Notably, what helped me optimize the code was the identification of useless method calls, e.g. when a propagator tries to remove a value from a variable that is not in its domain (see commit d0383f9).

I am looking forward to see this profiler at work :-)

[cprudhom]

The beta version (available in the master branch) does not provide any insight about useless calls.
The current version extends PropagationEngine and collects data when propagators are to be executed and variables are modified.
There is no possibility to go inside a propagator algorithm.

[gadavidd]

Hello @cprudhom! I also think that this is a great ideia!

But I don't understand the parameters: fine of Propagation and lower, upper and bounds for Integer Variables. Can you provide more informations about this?

[cprudhom]

A propagator can either filter :

• globally : the domain of one or more variables has been changed. This is known as a coarse event, or
• locally: the lower bound of the variable x has been increased or the value r has been removed from the domain of y. These are known as fine events.

For IntVar, there are 4 types of fine events:

• inst : domain reduction to a unique value,
• lower : increase the lower bound,
• upper : decrease of the upper bound,
• remove : a value is remove from the domain.

For example:

X = [0,5], Y = [0,5]
C1 : (X < Y)

When propagating C1, the value 5 will be removed from X which corresponds to a upper event. And the lower bound of Y will be refined to 1, which corresponds to a lower event.