`sum` function is still very slow

[rrandall1471]

After the conversation with Robert and Simon, I tested out the 9.9.9 gurobipy library

and tested it on a fairly large DF (93,600 rows of gurobi.Var data) and tested a sum on them. I ran it using quicksum of the pd.Series, quicksum on a list, the series.sum(), and sum on a list. As can be seen below the quicksum versions are significantly faster still.

I still see similar behavior on the groupby functions as well:

[Dr-Irv]

Issue seems to be that if you have a list of variables, quicksum is much faster. sum is faster if you use the tupledict representation:

import gurobipy as grb
print("version ", grb.gurobi.version())
m = grb.Model()
v = m.addVars(100000)
vals = v.values()

print("timing sum of the list")
%timeit sum(vals)

print("timing quicksum of the list")
%timeit grb.quicksum(vals)

print("timing sum of the tupledict")
%timeit sum(v)

print("timing quicksum of the tupledict")
%timeit grb.quicksum(v)

Then use ipython < speedtest.py and you get:

Python 3.9.13 (main, Aug 25 2022, 23:51:50) [MSC v.1916 64 bit (AMD64)] :: Anaconda, Inc. on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> import gurobipy as grb
>>> grb.gurobi.version
<bound method gurobi.version of <class 'gurobipy.gurobi'>>
>>> grb.gurobi.version()
(9, 9, 9)
>>> quit()

(gurobi999) c:\Code\Misc\gurobitst\gurobipandas>ipython < speedtest.py
Python 3.9.13 (main, Aug 25 2022, 23:51:50) [MSC v.1916 64 bit (AMD64)]
Type 'copyright', 'credits' or 'license' for more information
IPython 8.4.0 -- An enhanced Interactive Python. Type '?' for help.

In [1]:
In [2]: version  (9, 9, 9)

In [3]: Set parameter TokenServer to value "gurobi.princeton.com"
Gurobi 9.9.9 (pre-release) - expires 2022-10-31

In [4]:
In [5]:
In [6]:
In [6]: timing sum of the list

In [7]: 154 ms ± 4.16 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [8]:
In [8]: timing quicksum of the list

In [9]: 2.87 ms ± 174 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [10]:
In [10]: timing sum of the tupledict

In [11]: 2.16 ms ± 33.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [12]:
In [12]: timing quicksum of the tupledict

In [13]: 8.07 ms ± 156 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

[rluce]

You are right that the native sum is still slower by a constant factor, but the important change is that the sum(...) performance now scales linearly in the number of Var objects. Moreover, it's important to not benchmark sum/quicksum in isolation, but in conjunction with adding the result to the model (some parts of the sum operation may be evaluated lazily, and eventually you will need to add the expression to the model, right ;) ).

For example...

x = m.addVars(int(1e6)).values()
%timeit m.addConstr(sum(x) == 0)
%timeit m.addConstr(gp.quicksum(x) == 0)

With v9.5.2 I get

31 s ± 58.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
278 ms ± 1.31 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

but with the beta version I get

1.73 s ± 3.52 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
263 ms ± 2.48 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

So if the factor of ~8 in performance gain over using quicksum does play a big role in your code, you should continue to use it. We will add a note about the .agg(gp.quicksum) combo in the documentation.

[simonbowly]

Closing this, as we have #32 for integrating quicksum