MatrixVariable.sum is slower than quicksum #1070
Description
Is your feature request related to a problem? Please describe.
Weirdly, Matrix is slower than list or dict.
The time costing: list/dict < numpy.ndarray < MatrixVariable.
In [2]: import numpy as np
...:
...: from pyscipopt import Model, quicksum
In [3]: def test_pyscipopt(n):
...: model = Model()
...:
...: model.addMatrixVar((n, n), vtype="I").sum()
...:
In [4]: def test_numpy(n):
...: model = Model()
...: matrix = np.empty((n, n), dtype=object)
...: for idx in np.ndindex(matrix.shape):
...: matrix[idx] = model.addVar(vtype="I")
...:
...: matrix.sum()
...:
In [5]: def test_dict(n):
...: model = Model()
...:
...: x = {}
...: for i in range(n):
...: for j in range(n):
...: x[i, j] = model.addVar(vtype="I")
...:
...: quicksum(x[i, j] for i in range(i) for j in range(n))
...:
In [6]: timeit test_pyscipopt(180)
14 s ± 4.61 s per loop (mean ± std. dev. of 7 runs, 1 loop each)
In [7]: timeit test_numpy(180)
10.6 s ± 305 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
In [8]: timeit test_dict(180)
265 ms ± 56.4 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
Describe the solution you'd like
A clear and concise description of what you want to happen.
Speed up MatrixVariable.
Additional context
Add any other context or screenshots about the feature request here.
Numpy could handle numeric and static data types.
But it is hard to handle non-numeric and dynamic data types.
The profiler information
In [9]: prun test_pyscipopt(180)
65009 function calls (65008 primitive calls) in 9.413 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
1 9.151 9.151 9.151 9.151 {method 'reduce' of 'numpy.ufunc' objects}
1 0.134 0.134 9.375 9.375 <ipython-input-3-00105e30a609>:1(test_pyscipopt)
32401 0.087 0.000 0.094 0.000 _index_tricks_impl.py:715(__next__)
1 0.018 0.018 0.022 0.022 history.py:833(_writeout_input_cache)
1 0.013 0.013 9.387 9.387 <string>:1(<module>)
32407 0.007 0.000 0.007 0.000 {built-in method builtins.next}
1 0.003 0.003 0.025 0.025 decorator.py:232(fun)
7 0.000 0.000 0.001 0.000 numeric.py:324(full)
7 0.000 0.000 0.000 0.000 {built-in method numpy.empty}
2/1 0.000 0.000 9.413 9.413 {built-in method builtins.exec}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1 0.000 0.000 0.000 0.000 _stride_tricks_impl.py:37(as_strided)
1 0.000 0.000 0.000 0.000 _index_tricks_impl.py:688(__init__)
2 0.000 0.000 0.000 0.000 traitlets.py:3631(set)
2 0.000 0.000 0.000 0.000 {method '__exit__' of 'sqlite3.Connection' objects}
1 0.000 0.000 0.000 0.000 {method 'execute' of 'sqlite3.Connection' objects}
1 0.000 0.000 0.022 0.022 history.py:845(writeout_cache)
1 0.000 0.000 0.000 0.000 inspect.py:3133(_bind)
2 0.000 0.000 0.000 0.000 traitlets.py:718(_validate)
1 0.000 0.000 0.000 0.000 traitlets.py:1527(_notify_observers)
2 0.000 0.000 0.000 0.000 traitlets.py:3474(validate)
1 0.000 0.000 0.000 0.000 numeric.py:98(zeros_like)
7 0.000 0.000 0.000 0.000 _weakrefset.py:39(_remove)
2 0.000 0.000 0.000 0.000 traitlets.py:689(set)
1 0.000 0.000 0.022 0.022 history.py:55(only_when_enabled)
5 0.000 0.000 0.000 0.000 {built-in method builtins.hasattr}
6 0.000 0.000 0.000 0.000 traitlets.py:676(__get__)
1 0.000 0.000 9.151 9.151 _methods.py:49(_sum)
1 0.000 0.000 0.000 0.000 {built-in method numpy.asarray}
2 0.000 0.000 0.000 0.000 traitlets.py:727(_cross_validate)
6 0.000 0.000 0.000 0.000 traitlets.py:629(get)
1 0.000 0.000 0.000 0.000 traitlets.py:1512(_notify_trait)
1 0.000 0.000 0.000 0.000 decorator.py:200(fix)
1 0.000 0.000 0.000 0.000 {built-in method _thread.allocate_lock}
1 0.000 0.000 0.000 0.000 threading.py:311(_acquire_restore)
2 0.000 0.000 0.000 0.000 traitlets.py:3624(validate_elements)
1 0.000 0.000 0.000 0.000 inspect.py:2949(apply_defaults)
2 0.000 0.000 0.000 0.000 traitlets.py:708(__set__)
1 0.000 0.000 0.000 0.000 inspect.py:3275(bind)
8 0.000 0.000 0.000 0.000 {built-in method builtins.isinstance}
1 0.000 0.000 0.000 0.000 traitlets.py:1523(notify_change)
2 0.000 0.000 0.000 0.000 traitlets.py:2304(validate)
1 0.000 0.000 0.000 0.000 history.py:839(_writeout_output_cache)
1 0.000 0.000 0.000 0.000 inspect.py:2896(args)
2 0.000 0.000 0.000 0.000 threading.py:302(__exit__)
2 0.000 0.000 0.000 0.000 threading.py:299(__enter__)
1 0.000 0.000 0.000 0.000 threading.py:308(_release_save)
3 0.000 0.000 0.000 0.000 {method 'acquire' of '_thread.lock' objects}
22 0.000 0.000 0.000 0.000 typing.py:2187(cast)
7 0.000 0.000 0.000 0.000 {method 'discard' of 'set' objects}
2 0.000 0.000 0.000 0.000 {built-in method numpy.zeros}
4 0.000 0.000 0.000 0.000 {method '__exit__' of '_thread.lock' objects}
1 0.000 0.000 0.000 0.000 threading.py:627(clear)
1 0.000 0.000 0.000 0.000 {built-in method numpy.array}
2 0.000 0.000 0.000 0.000 traitlets.py:3486(validate_elements)
4 0.000 0.000 0.000 0.000 {method 'get' of 'dict' objects}
1 0.000 0.000 0.000 0.000 inspect.py:2919(kwargs)
8 0.000 0.000 0.000 0.000 multiarray.py:1106(copyto)
3 0.000 0.000 0.000 0.000 {built-in method builtins.len}
3 0.000 0.000 0.000 0.000 base_events.py:728(__del__)
2 0.000 0.000 0.000 0.000 {method '__enter__' of '_thread.lock' objects}
1 0.000 0.000 0.000 0.000 {method 'values' of 'mappingproxy' objects}
4 0.000 0.000 0.000 0.000 {method 'append' of 'list' objects}
2 0.000 0.000 0.000 0.000 {method 'extend' of 'list' objects}
2 0.000 0.000 0.000 0.000 {built-in method builtins.iter}
1 0.000 0.000 0.000 0.000 _stride_tricks_impl.py:24(_maybe_view_as_subclass)
10 0.000 0.000 0.000 0.000 inspect.py:2808(kind)
3 0.000 0.000 0.000 0.000 {method 'items' of 'mappingproxy' objects}
1 0.000 0.000 0.000 0.000 {method 'append' of 'collections.deque' objects}
1 0.000 0.000 0.000 0.000 threading.py:314(_is_owned)
3 0.000 0.000 0.000 0.000 base_events.py:724(is_closed)
4 0.000 0.000 0.000 0.000 inspect.py:3089(parameters)
1 0.000 0.000 0.000 0.000 _stride_tricks_impl.py:19(__init__)
1 0.000 0.000 0.000 0.000 {method 'release' of '_thread.lock' objects}
4 0.000 0.000 0.000 0.000 inspect.py:2796(name)
1 0.000 0.000 0.000 0.000 inspect.py:2888(__init__)
1 0.000 0.000 0.000 0.000 multiarray.py:115(empty_like)
1 0.000 0.000 0.000 0.000 numeric.py:92(_zeros_like_dispatcher)
1 0.000 0.000 0.000 0.000 _index_tricks_impl.py:696(__iter__)
In [10]: prun test_numpy(180)
64971 function calls in 9.433 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
1 9.187 9.187 9.187 9.187 {method 'reduce' of 'numpy.ufunc' objects}
1 0.194 0.194 9.392 9.392 <ipython-input-4-d9bf266ea23e>:1(test_numpy)
2 0.014 0.007 0.016 0.008 {method '__exit__' of 'sqlite3.Connection' objects}
1 0.012 0.012 0.014 0.014 {method 'execute' of 'sqlite3.Connection' objects}
1 0.011 0.011 9.403 9.403 <string>:1(<module>)
32401 0.008 0.000 0.014 0.000 _index_tricks_impl.py:715(__next__)
32407 0.006 0.000 0.006 0.000 {built-in method builtins.next}
1 0.000 0.000 0.000 0.000 {built-in method numpy.empty}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1 0.000 0.000 9.403 9.403 {built-in method builtins.exec}
2 0.000 0.000 0.000 0.000 traitlets.py:718(_validate)
5 0.000 0.000 0.000 0.000 {built-in method builtins.hasattr}
1 0.000 0.000 0.030 0.030 history.py:845(writeout_cache)
1 0.000 0.000 0.000 0.000 traitlets.py:1527(_notify_observers)
1 0.000 0.000 0.030 0.030 history.py:833(_writeout_input_cache)
2 0.000 0.000 0.000 0.000 traitlets.py:3631(set)
1 0.000 0.000 0.000 0.000 _stride_tricks_impl.py:37(as_strided)
1 0.000 0.000 0.000 0.000 _index_tricks_impl.py:688(__init__)
2 0.000 0.000 0.000 0.000 traitlets.py:689(set)
2 0.000 0.000 0.000 0.000 traitlets.py:727(_cross_validate)
2 0.000 0.000 0.000 0.000 traitlets.py:3474(validate)
1 0.000 0.000 0.000 0.000 inspect.py:3133(_bind)
2 0.000 0.000 0.000 0.000 traitlets.py:3624(validate_elements)
1 0.000 0.000 0.000 0.000 numeric.py:98(zeros_like)
1 0.000 0.000 0.000 0.000 traitlets.py:1512(_notify_trait)
6 0.000 0.000 0.000 0.000 traitlets.py:676(__get__)
1 0.000 0.000 9.187 9.187 {method 'sum' of 'numpy.ndarray' objects}
2 0.000 0.000 0.000 0.000 traitlets.py:708(__set__)
2 0.000 0.000 0.000 0.000 traitlets.py:2304(validate)
1 0.000 0.000 0.000 0.000 traitlets.py:1523(notify_change)
8 0.000 0.000 0.000 0.000 {built-in method builtins.isinstance}
6 0.000 0.000 0.000 0.000 traitlets.py:629(get)
1 0.000 0.000 0.000 0.000 {built-in method _thread.allocate_lock}
1 0.000 0.000 0.000 0.000 decorator.py:200(fix)
1 0.000 0.000 0.030 0.030 decorator.py:232(fun)
1 0.000 0.000 0.000 0.000 _weakrefset.py:39(_remove)
1 0.000 0.000 0.000 0.000 history.py:839(_writeout_output_cache)
1 0.000 0.000 9.187 9.187 _methods.py:49(_sum)
1 0.000 0.000 0.030 0.030 history.py:55(only_when_enabled)
1 0.000 0.000 0.000 0.000 inspect.py:2949(apply_defaults)
1 0.000 0.000 0.000 0.000 inspect.py:3275(bind)
4 0.000 0.000 0.000 0.000 {method 'get' of 'dict' objects}
22 0.000 0.000 0.000 0.000 typing.py:2187(cast)
2 0.000 0.000 0.000 0.000 threading.py:299(__enter__)
1 0.000 0.000 0.000 0.000 {built-in method numpy.asarray}
2 0.000 0.000 0.000 0.000 traitlets.py:3486(validate_elements)
1 0.000 0.000 0.000 0.000 threading.py:311(_acquire_restore)
4 0.000 0.000 0.000 0.000 {method '__exit__' of '_thread.lock' objects}
1 0.000 0.000 0.000 0.000 threading.py:308(_release_save)
2 0.000 0.000 0.000 0.000 {built-in method numpy.zeros}
3 0.000 0.000 0.000 0.000 {method 'acquire' of '_thread.lock' objects}
2 0.000 0.000 0.000 0.000 {method '__enter__' of '_thread.lock' objects}
1 0.000 0.000 0.000 0.000 inspect.py:2896(args)
2 0.000 0.000 0.000 0.000 threading.py:302(__exit__)
3 0.000 0.000 0.000 0.000 {built-in method builtins.len}
2 0.000 0.000 0.000 0.000 {method 'extend' of 'list' objects}
1 0.000 0.000 0.000 0.000 threading.py:627(clear)
1 0.000 0.000 0.000 0.000 inspect.py:2919(kwargs)
1 0.000 0.000 0.000 0.000 {method 'values' of 'mappingproxy' objects}
1 0.000 0.000 0.000 0.000 {method 'discard' of 'set' objects}
1 0.000 0.000 0.000 0.000 {built-in method numpy.array}
10 0.000 0.000 0.000 0.000 inspect.py:2808(kind)
1 0.000 0.000 0.000 0.000 threading.py:314(_is_owned)
3 0.000 0.000 0.000 0.000 {method 'items' of 'mappingproxy' objects}
4 0.000 0.000 0.000 0.000 {method 'append' of 'list' objects}
1 0.000 0.000 0.000 0.000 {method 'append' of 'collections.deque' objects}
2 0.000 0.000 0.000 0.000 {built-in method builtins.iter}
1 0.000 0.000 0.000 0.000 {method 'release' of '_thread.lock' objects}
1 0.000 0.000 0.000 0.000 _stride_tricks_impl.py:24(_maybe_view_as_subclass)
4 0.000 0.000 0.000 0.000 inspect.py:3089(parameters)
4 0.000 0.000 0.000 0.000 inspect.py:2796(name)
1 0.000 0.000 0.000 0.000 inspect.py:2888(__init__)
1 0.000 0.000 0.000 0.000 multiarray.py:1106(copyto)
1 0.000 0.000 0.000 0.000 _stride_tricks_impl.py:19(__init__)
1 0.000 0.000 0.000 0.000 numeric.py:92(_zeros_like_dispatcher)
1 0.000 0.000 0.000 0.000 multiarray.py:115(empty_like)
1 0.000 0.000 0.000 0.000 _index_tricks_impl.py:696(__iter__)
In [11]: prun test_dict(180)
32371 function calls in 0.252 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.140 0.140 0.145 0.145 <ipython-input-5-60ba8a587fa8>:1(test_dict)
1 0.049 0.049 0.049 0.049 history.py:833(_writeout_input_cache)
1 0.047 0.047 0.047 0.047 {method 'execute' of 'sqlite3.Connection' objects}
1 0.011 0.011 0.156 0.156 <string>:1(<module>)
32221 0.005 0.000 0.005 0.000 <ipython-input-5-60ba8a587fa8>:9(<genexpr>)
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1 0.000 0.000 0.096 0.096 history.py:845(writeout_cache)
1 0.000 0.000 0.000 0.000 inspect.py:3133(_bind)
2 0.000 0.000 0.000 0.000 {method '__exit__' of 'sqlite3.Connection' objects}
1 0.000 0.000 0.000 0.000 decorator.py:200(fix)
1 0.000 0.000 0.252 0.252 {built-in method builtins.exec}
2 0.000 0.000 0.000 0.000 traitlets.py:3631(set)
1 0.000 0.000 0.000 0.000 inspect.py:2919(kwargs)
1 0.000 0.000 0.000 0.000 _weakrefset.py:39(_remove)
1 0.000 0.000 0.096 0.096 history.py:55(only_when_enabled)
6 0.000 0.000 0.000 0.000 traitlets.py:676(__get__)
1 0.000 0.000 0.000 0.000 traitlets.py:1527(_notify_observers)
1 0.000 0.000 0.000 0.000 inspect.py:2949(apply_defaults)
6 0.000 0.000 0.000 0.000 traitlets.py:629(get)
2 0.000 0.000 0.000 0.000 traitlets.py:3624(validate_elements)
2 0.000 0.000 0.000 0.000 traitlets.py:718(_validate)
2 0.000 0.000 0.000 0.000 traitlets.py:689(set)
1 0.000 0.000 0.000 0.000 threading.py:311(_acquire_restore)
1 0.000 0.000 0.000 0.000 inspect.py:3275(bind)
1 0.000 0.000 0.096 0.096 decorator.py:232(fun)
1 0.000 0.000 0.000 0.000 {built-in method _thread.allocate_lock}
2 0.000 0.000 0.000 0.000 traitlets.py:3474(validate)
5 0.000 0.000 0.000 0.000 {built-in method builtins.hasattr}
2 0.000 0.000 0.000 0.000 traitlets.py:727(_cross_validate)
1 0.000 0.000 0.000 0.000 inspect.py:2896(args)
1 0.000 0.000 0.000 0.000 traitlets.py:1512(_notify_trait)
2 0.000 0.000 0.000 0.000 threading.py:299(__enter__)
6 0.000 0.000 0.000 0.000 {built-in method builtins.next}
2 0.000 0.000 0.000 0.000 traitlets.py:708(__set__)
3 0.000 0.000 0.000 0.000 {method 'acquire' of '_thread.lock' objects}
2 0.000 0.000 0.000 0.000 threading.py:302(__exit__)
1 0.000 0.000 0.000 0.000 traitlets.py:1523(notify_change)
7 0.000 0.000 0.000 0.000 {built-in method builtins.isinstance}
2 0.000 0.000 0.000 0.000 traitlets.py:2304(validate)
1 0.000 0.000 0.000 0.000 threading.py:627(clear)
22 0.000 0.000 0.000 0.000 typing.py:2187(cast)
1 0.000 0.000 0.000 0.000 history.py:839(_writeout_output_cache)
1 0.000 0.000 0.000 0.000 {method 'values' of 'mappingproxy' objects}
3 0.000 0.000 0.000 0.000 {method 'items' of 'mappingproxy' objects}
4 0.000 0.000 0.000 0.000 {method 'append' of 'list' objects}
4 0.000 0.000 0.000 0.000 {method '__exit__' of '_thread.lock' objects}
10 0.000 0.000 0.000 0.000 inspect.py:2808(kind)
4 0.000 0.000 0.000 0.000 inspect.py:3089(parameters)
1 0.000 0.000 0.000 0.000 threading.py:308(_release_save)
2 0.000 0.000 0.000 0.000 {built-in method builtins.iter}
4 0.000 0.000 0.000 0.000 {method 'get' of 'dict' objects}
2 0.000 0.000 0.000 0.000 traitlets.py:3486(validate_elements)
2 0.000 0.000 0.000 0.000 {method '__enter__' of '_thread.lock' objects}
1 0.000 0.000 0.000 0.000 threading.py:314(_is_owned)
2 0.000 0.000 0.000 0.000 {method 'extend' of 'list' objects}
1 0.000 0.000 0.000 0.000 {method 'discard' of 'set' objects}
2 0.000 0.000 0.000 0.000 {built-in method builtins.len}
4 0.000 0.000 0.000 0.000 inspect.py:2796(name)
1 0.000 0.000 0.000 0.000 inspect.py:2888(__init__)
1 0.000 0.000 0.000 0.000 {method 'append' of 'collections.deque' objects}
1 0.000 0.000 0.000 0.000 {method 'release' of '_thread.lock' objects}
In [12]: