Memory allocations

[josechenf]

Hello!

I'm wondering what is required to use ProxyQP without performing any memory allocations during runtime. For my specific problems, I know the matrix sizes before-hand, but the sparsity pattern of these matrices may change in-between calls and the non-zero elements may change to different values (e.g. some constraint rows may become zero).

I'm aware that a related issue was fixed in the past, but I'm wondering under which assumptions this holds. Under which cases would ProxyQP need to allocate memory? For example, would ProxyQP need to allocate memory if the sparsity pattern of the constraint matrix changes between two calls to the solver?

Thanks!

[jcarpent]

Thanks @josechenf for raising this set of questions.
It really depends on the backend used.

For the dense back end, we perform a lot of memory pre-allocation. If your sparsity pattern does change, this is not an issue per se.

For the sparse back end, we pre-analyze the sparsity and tend to perform some adequate permutations to enforce the numerical robustness.

In both cases, we rely on Eigen for matrix-product operations.
In this case, Eigen may internally choose to do some memory allocations for caching and efficiency issues.
We may change this strategy, and add more features to limit Eigen internal allocations.

@josechenf Could you provide typical examples where you think allocation matters, on which we can start to work with your help?

Best,
Justin

[josechenf]

Thank you Justin!

For our specific applications, we use a QP solver to solve constrained linear least-squares problems for robot control.

Even though we tend to have faster computation times with a sparse solver (OSQP), the problem is small enough that we don't mind taking a performance hit by using a dense solver as long as there are no memory allocations during run-time. This is the library we use for solving linear least-squares problems with OSQP, and this is an application that solves the 6D Cartesian to joint velocity mapping problem with collision avoidance. We did have some issues in the past with some dense solvers when some of the constraint matrix rows became zero, as during runtime sometimes we disable certain constraints that are unnecessary (e.g., if the object is too far and is unlikely to collide with the robot).

Even though OSQP allocates memory whenever the sparsity pattern changes, it works fine for our use-case in a single-threaded setting. The issue we are having is that when we try to run this in a massive multi-threaded setting (100+ threads running as fast as possible), the memory allocations are the biggest bottleneck, as they are blocking and only one thread can allocate memory at a given point. We use TCMalloc to alleviate some of these issues, but it is still a problem.

Ideally, there would be an option (for let's say, the dense backend) to completely disable memory allocations or provide a pre-allocated arena to prevent allocating memory during run-time.

Thank you for your time!

[jcarpent]

To move forward, could you please provide a typical example written with ProxQP that you aim to solve?
We would look afterward at the way to remove all memory allocations.

[josechenf]

Thank you!
Will do, it may take me a bit of time as we need to refactor quite a bit of code to use different QP solvers, but I will update here once I have a working example with ProxQP :)

[jcarpent]

@josechenf Thanks for the feedback.