Re: [eigen] Malloc-free dynamic matrices

[Eamon Nerbonne <eamon.nerbonne@xxxxxxxxx>]

If you make a matrix both reservable and resizable, how do these two features interact?  If you write to a matrix with a shape that doesn't fit into the reserved area, what happens to the reservation?  If you have a col+row reservation scheme, and only one of the bounds is exceeded, do you still maintain the other bound?

I think there's a lot of corner cases wrt resizing and reservations..  If they are solved, they'll be tricky to make intuitive; and they can probably cause weird perf. problems either way.

Also, eigen's claim to fame is also partially it's speed, so it'd be a shame to compromise that unnecessarily.

If the following were easy to express:

MatrixXf mat =...reserve...;
....some fixed-size view of a matrix... = mat.block(0,0,currentRows,currentCols);

Then perhaps this would be less of an issue.

--eamon@xxxxxxxxxxxx - Tel#:+31-6-15142163

On Wed, Mar 3, 2010 at 10:48, Gael Guennebaud <gael.guennebaud@xxxxxxxxx> wrote:

On Tue, Mar 2, 2010 at 6:16 PM, Benoit Jacob <jacob.benoit.1@xxxxxxxxx> wrote:

2010/3/2 leon zadorin <leonleon77@xxxxxxxxx>:

> On 3/3/10, leon zadorin <leonleon77@xxxxxxxxx> wrote:
>> On 3/3/10, Benoit Jacob <jacob.benoit.1@xxxxxxxxx> wrote:
>>> 2010/3/2 Márton Danóczy <marton78@xxxxxxxxx>:
>> [...]
>>>> The only API changes are a new option NeverRealloc (the name is maybe
>>>> not the best) and a method reserve(int size) that allocates the
>>>> memory. Then, a Matrix<Scalar, Dynamic, Dynamic, NeverRealloc> keeps
>>>> track of its allocated size via the member variable m_size and each
>>>> mat.resize(rows, cols) only changes two ints instead of actually
>>>> allocating memory. If rows*cols < m_size, an assertion error is
>>>> raised.
>>
>> [...]
>>
>>> approach... my main concern right now is that it's touching and
>>> complexifying a few very central places in Eigen, whereas the use case
>>> is very special. For that reason I wonder if this should rather be
>>> implemented as a new separate variant of the Matrix class itself...
>>
>> And if it is a special/rare case usage, would it not be possible to
>> already achieve this behavior with a custom pre-allocated block of
>> memory and then instead of using matrix type simply using the
>> object(s) of Map<> type?
>>
>> The "mapped" matricies would not need explicit resizing in the first
>> place... and reserving of the max size is simply done at allocation of
>> the very original memory slab -- as per current API and it's
> capabilities?
>
> To clarify -- I'm getting at saying that one may not need patching
> anything in eigen in the first place, and by simply using the
> already-existing API of Map<> objects one could achieve what the
> original poster wanted :-)

Yes, that sounds like a very good idea. It may require minor API
additions to class Map to make it convenient for Marton, but that's
still much lighter than the proposed patch.

In practice, being able to reserve memory is a really important feature. Even though it is currently possible to achieve the same using either a big matrix + blocks, or a std::vector + a map, such approaches are not very convenient for the user. So having such a feature directly inside Eigen is really important to me. I'd even go further by adding functions such as pushRows(MatrixBase<>)/pushColumns(MatrixBase<>) to easily append a set of rows or columns to an existing matrix. We can also think about pushInner/pushOuter versions, or other names such as pushBottom/pushRight, etc.

Then we can discuss about the kind of "reserve" we want. Indeed, Marton's goal is to completely avoid heap allocation once the memory has been reserved, that is why heap reallocation are even forbidden in Marton's patch via an assert. However, I think that in most cases, we only want to be able to reserve memory to reduce the risk of dynamic memory reallocation. So the assert in resize should definitely not be the default behavior.

Also, if I understood it correctly, Marton proposed a unique reserve(int size) function preallocating size coefficients such that all coefficients are always sequentially stored in memory. In other word it guaranties linear access and outer_stride == inner_size.

Another approach would be to allow two dimensional reserve: mat.reserve(int preAllocatedRows, int preAllocatedCols). This approach is really like a big matrix + a block glued together. The main advantage is that allows to add rows to a column major matrix without any overhead. With Marton's approach you need complex memory copies to insert space inbetween the columns. On the other hand my proposal means linear access cannot be guaranteed at compile time, and you need to store 2 additional integers instead of a single one. So pros and cons, I'm puzzled.

Finally, there is the discussion on how this should be exposed to the user:

- in Matrix without option, i.e., all dynamic sized matrices would have reserve() working.
 * pro: simple for the user, no new types
 * cons: sizeof(MatrixXf) slightly increase (very minor), MatrixXf lost the linear access bit if we go for the 2D reserve approach (minor too since the linear access path is mainly useful for small matrices, for large one there is almost no benefit)

- in Matrix via an option:
 * pro: we keep MatrixXf as it is
 * cons: introduce new types, reserve() won't work by default => add complexity for the user

- introduce a cousin of Matrix
 * pro: a bit easier for the user than the Matrix option
 * cons: more difficult to maintain for us, add new types

So, overall, for simplicity (both for us and the users) I'm slightly in favor of implementing it directly in Matrix (actually, in DenseStorageBase). For 1D reserve versus 2D reserve, well as I said I'm puzzled and I'm looking forward to hear your opinions.

cheers,

gael