Skip to content

BUG: Fix highspy __getitem__ speed#1438

Closed
HaoZeke wants to merge 4 commits intoERGO-Code:masterfrom
HaoZeke:fixGetItemSpeed
Closed

BUG: Fix highspy __getitem__ speed#1438
HaoZeke wants to merge 4 commits intoERGO-Code:masterfrom
HaoZeke:fixGetItemSpeed

Conversation

@HaoZeke
Copy link
Copy Markdown
Contributor

@HaoZeke HaoZeke commented Sep 30, 2023

Closes #1277. For this test case (adapted from here):

import highspy
import timeit

h = highspy.Highs()

h.readModel("80bau3b.mps")
h.setOptionValue("time_limit", 10)

# Solve
start_time = timeit.default_timer()
h.run()
elapsed = timeit.default_timer() - start_time

print(f"Time taken to solve: {elapsed:.4f}")

solution = h.getSolution()
num_vars = h.getNumCol()

# Extract values using __getitem__ N times
start_time = timeit.default_timer()
values = [solution.col_value[icol] for icol in range(num_vars)]
elapsed = timeit.default_timer() - start_time
print(f"__getitem__ method for {num_vars} vars: {elapsed:.4f}")


# Extract values by copying first to list
start_time = timeit.default_timer()
col_values = list(solution.col_value)
values = [col_values[icol] for icol in range(num_vars)]
elapsed = timeit.default_timer() - start_time
print(f"Copy-first method for {num_vars} vars: {elapsed:.4f}")

Where the 80bau3b.mps is part of this repo, we have:

# Original
Time taken to solve: 0.1016
__getitem__ method for 9799 vars: 0.7423
Copy-first method for 9799 vars: 0.0003

As a first approximation, we can use the buff protocol and numpy:

# Numpy readonly (33b6634823b41252f28fdd9daa5b553c6b9b43cd)
Time taken to solve: 0.0974
__getitem__ method for 9799 vars: 0.0956
Copy-first method for 9799 vars: 0.0010

However, this isn't equivalent to readwrite and isn't very nice conceptually, so we can try to use an opaque type:

# Opaque type (standard) for std::vector<double> (2aa08d9c8471a86aafa544d7976de1e520c7357f)
Time taken to solve: 0.1007
__getitem__ method for 9799 vars: 0.0064
Copy-first method for 9799 vars: 0.0015

This can be optimized a bit more:

# Custom opaque type and class
Time taken to solve: 0.0919
__getitem__ method for 9799 vars: 0.0046
Copy-first method for 9799 vars: 0.0015

Note that this method has the caveats listed in the documentation. I think the standard opaque type is probably about as far as can be optimized safely, though there seem to be some micro-optimizations discussed on Gitter (which I admit are beyond me).

__getitem__ method for 9799 vars: 0.0956
Copy-first method for 9799 vars: 0.0010
__getitem__ method for 9799 vars: 0.0064
Copy-first method for 9799 vars: 0.0015

ERGO-Code#1277
HaoZeke added a commit to HaoZeke/HiGHS that referenced this pull request Sep 30, 2023
HaoZeke added a commit to HaoZeke/HiGHS that referenced this pull request Sep 30, 2023
@HaoZeke
Copy link
Copy Markdown
Contributor Author

HaoZeke commented Oct 1, 2023

One of the biggest issues with this is that now users need to be careful to cast:

# Before:
lp.col_cost_ = c

# After:
vector_double_c = highspy._highs.VectorDouble(c.tolist())
lp.col_cost_ = vector_double_c

This can be sidestepped with the NumPy approach (or just documented). Alternatively, since for the modeling API we have the Python wrapper over the C++ internals anyway, we can just extract it into a list before operating on it (as is done in the test case).

@HaoZeke
Copy link
Copy Markdown
Contributor Author

HaoZeke commented Oct 1, 2023

I don't like any of these here actually. They're a mess for downstream library integration (e.g. SciPy). The solution should be to rework the highs python module instead to extract the list and store it.

@HaoZeke HaoZeke closed this Oct 1, 2023
HaoZeke added a commit to HaoZeke/HiGHS that referenced this pull request Feb 3, 2024
HaoZeke added a commit to HaoZeke/HiGHS that referenced this pull request Feb 3, 2024
HaoZeke added a commit to HaoZeke/HiGHS that referenced this pull request Feb 3, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Overhead using highspy

1 participant