Efficient modeling through the Mosel Profiler

The efficiency of a model may be measured through its execution speed and also its memory consumption. The execution times can be analyzed in detail with the help of the Mosel Profiler. Several commands of the Mosel debugger that are also discussed in this section provide the user with further information, such as memory consumption.

Using the Mosel Profiler

Once a model you are developing is running correctly, you will certainly start testing it with larger data sets. Doing so, you may find that model execution times become increasingly larger. This may be due to the solution algorithms, but a more or less significant part of the time will be spent simply in defining the model itself. The Mosel Profiler lets you analyze the model behavior line-by-line. Solution algorithms, such as LP or MIP optimization with Xpress Optimizer, may be improved by tuning solver parameters (please refer to the corresponding software manuals). Here we shall be solely concerned with improvements that may be made directly to the Mosel model. Even for large scale models, model execution times can often be reduced to just a few seconds by carefully (re)formulating the model.

Just as for the debugger, Mosel models that are to be run in the profiler need to be compiled with the option G. The command profile of the Mosel command line performs all required steps:

mosel profile prime2.mos

or, if we wish to generate the BIM file explicitly:

mosel comp -G prime2.mos
mosel run -prof prime2.bim

The profiler generates a file filename.prof with the profiling statistics. For the test model prime2.mos this file has the following contents (leaving out the header lines and comments):

                           model Prime

                            parameters
       1     0.00     0.00   LIMIT=20000
                            end-parameters

                            declarations
       1     0.00     0.00   SNumbers: set of integer
       1     0.00     0.00   SPrime: set of integer
                            end-declarations

       1     0.01     0.00  SNumbers:={2..LIMIT}

       1     0.00     0.01  writeln("Prime numbers between 2 and ", LIMIT, ":")

       1     0.00     0.01  n:=2
       1     0.00     0.01  repeat
    2262     0.04     3.44    while (not(n in SNumbers)) n+=1
    2262     0.00     3.44    SPrime += {n}
    2262     0.00     3.44    i:=n
    2262     0.04     3.44    while (i<=LIMIT) do
   50126     3.31     3.44      SNumbers-= {i}
   50126     0.04     3.44      i+=n
                              end-do
    2262     0.00     3.44  until SNumbers={}

       1     0.00     3.44  writeln(SPrime)
       1     0.00     3.45  writeln(" (", getsize(SPrime), " prime numbers.)")

       1     0.00     3.45 end-model 

The first column lists the number of times a statement is executed, the second column the total time spent in a statement, and the third column the time of the last execution; then follows the corresponding model statement. In our example, we see that most of the model execution time is spent in a single line, namely the deletion of elements from the set SNumbers. This line is executed more than 50,000 times, but so is the following statement (i+=n) and it only takes a fraction of a second. Indeed, operations on large (> 1000 entries) sets may be relatively expensive in terms of running time. If our prime number algorithm were to be used in a large, time-critical application we should give preference to a more suitable data structure that is addressed more easily, that is, an array. For instance, by modifying the model as follows the total execution time for this model version becomes 0.19 seconds:

model "Prime (array)"

 parameters
  LIMIT=20000                   ! Search for prime numbers in 2..LIMIT
 end-parameters

 declarations
  INumbers = 2..LIMIT           ! Set of numbers to be checked
  SNumbers: array(INumbers) of boolean
  SPrime: set of integer        ! Set of prime numbers
 end-declarations

 writeln("Prime numbers between 2 and ", LIMIT, ":")

 n:=2
 repeat
   SPrime += {n}                ! n is a prime number
   i:=n
   while (i<=LIMIT) do          ! Remove n and all its multiples
     SNumbers(i):= true
     i+=n
   end-do
   while (n <= LIMIT and SNumbers(n)) n+=1
 until (n>LIMIT)

 writeln(SPrime)
 writeln(" (", getsize(SPrime), " prime numbers.)")

end-model

To start the Mosel profiler from Xpress Workbench, open the Run Dialog window from the menu Run or by clicking on the tools button and select the run mode Profile the Model.

Profiling concurrent models

The Mosel profiler can be used to profile models that are running concurrently. The profiler run is started by launching the profiler for the master model. For every model file, an output file filename.prof is generated. If several instances of the same model file are being run, Mosel creates unique filenames of the form filename.modelid.prof where modelid is formed from the model counter per model tree level.

The user is reminded that all (sub)models used in profiler runs need to be compiled with the 'G' flag.

Other commands for model analysis

The Mosel debugger provides a few other commands that may be helpful with quickly obtaining information about models that have been executed in Mosel.

Consider, for example, the following model flow.mos.

model "Dynamic arrays"
 declarations
  Suppliers = 1..150
  Customers = 1..10000
  COST: dynamic array(Suppliers,Customers) of real
  flow: dynamic array(Suppliers,Customers) of mpvar
 end-declarations

 initializations from "flow.dat"
  COST
 end-initializations

 forall(s in Suppliers, c in Customers | COST(s,c)>0 ) create(flow(s,c))

end-model 

Now execute the following sequence of Mosel commands from the command line (as before, Mosel output is printed in bold face). The commands we wish to use are part of the Mosel debugger.—Since we do not wish to launch a debugging session, we use the option -g to compile in debug mode, but without tracing information. This results in a standard model run without entering an interactive debugging session.

The command lsmods displays information about all models loaded in Mosel, and in particular their size (= memory usage in bytes). With the command info followed by a symbol name we obtain detailed information about the definition of this symbol (without giving a symbol this command will display release and license information for Mosel). Alternatively, it is also possible to print the complete list of symbols (with type information and sizes) defined by the current model by using the command lssymb.

If we now remove the keyword dynamic from the declaration of the two arrays, COST and flow, and re-run the same command sequence as before, we obtain the following output:

We can run a similar experiment with the model version flowh.mos that defines the two sparse arrays as hashmap. As shown in the output below, the memory usage is somewhat higher albeit in the same order of magnitude as the model version with dynamic arrays:

It is easily seen that in this model the use of the keyword dynamic or hashmap makes a huge difference in terms of memory usage. A model defining several arrays of comparable sizes is likely to run out of memory (or at the least, it may not leave enough memory for an optimization algorithm to be executed).

Note: If COST is defined as a sparse (dynamic or hashmap) array, the condition on the forall loop should really be exists(COST(s,c)) for speedier execution of this loop.

Some recommendations for efficient modeling

The following list summarizes some crucial points to be taken into account, especially when writing large-scale models. For more details and examples please see Appendix Good modeling practice with Mosel.

• Use sparse arrays to
  • size data tables automatically when the data is read in,
  • initialize the index values automatically when the data is read in,
  • conserve memory when storing sparse data,
  • eliminate index combinations without using conditions each time.
• Don't use sparse arrays
  • when you can use ordinary (dense) arrays instead,
  • when storing dense data (if at least 50% of its entries are defined an array should clearly be considered as dense), and you can size the data table and initialize the indices in some other way, such as by reading in the size first.
• General procedure for declaring and initializing data:
  1. declare all index sets and the minimal collection of data arrays required to initialize the sets,
  2. initialize the data arrays (which also initializes all index sets),
  3. finalize the index sets,
  4. declare and initialize all other arrays.
• Efficient use of sparse arrays:
  • use the keyword exists for enumeration (in sums or loops),
  • access the elements in ascending order of the indices (particularly with dynamic arrays),
  • use hashmap when array elements are predominantly accessed in random order,
  • use ranges, rather than sets, for the index sets.
• Efficient use of exists:
  • use named index sets in the declarations,
  • use the same index sets in the loops,
  • use the index sets in the same order,
  • use the dynamic/hashmap qualifier if some index sets are constant or finalized,
  • make sure exists is the first condition,
  • always use exists, even if no condition or an alternative condition is logically correct,
  • conditions with or cannot be handled as efficiently as conditions with and.
• Loops (sum, forall, etc.):
  • where possible, use conditional loops—loop index set followed by a vertical bar and the condition(s)—instead of a logical test with if within the loop,
  • make sure exists is the first condition,
  • always use exists, even if no condition or an alternative condition is logically correct,
  • enumerate the index sets in the same order as they occur in the arrays within the loop,
  • broken up, conditional loops are handled less efficiently.
• Do not use any debugging flag for compiling the final deployment version of your models.