Re: [eigen] Malloc-free dynamic matrices

[Gael Guennebaud <gael.guennebaud@xxxxxxxxx>]

On Fri, Mar 5, 2010 at 6:25 AM, Benoit Jacob <jacob.benoit.1@xxxxxxxxx> wrote:

ok i can finally reply.....

first of all let me say that my idea of
d-pointers-without-a-shared-library fails because of the case when a
program would first create a Eigen 3.0 matrix and then load (at
runtime) a library that uses Eigen 3.1. In other words, it only works
as long as any library loading predates any matrix creation...

2010/3/4 Gael Guennebaud <gael.guennebaud@xxxxxxxxx>:
>

> Ok, let me try to summarize. As far as I understood, the led us to two
> options:
>
> Option1: we add a tiny shared library implementing the
> creation/initialization of the D_structure and a method to get the
> D_structure.

Yes; nitpick: rather, offers methods to get the individual data
members in the D_structure. Getting the d pointer itself is useless,
precisely as you don't want to have to use hardcoded offsets.

> Then where and how it is store is a detail. This approach
> offers full flexibility in the future but requires a shared lib.

Yes.

>
> Option2: if we don't want a shared lib, then there is no way we can change
> the size of the D_structure and/or the way it is initialized.

I'm afraid this is true, although I didn't realize this earlier.

Initially I though that we could at least add more data members, that
the problem was only that we couldn't remove/change existing members.
But I realize I was wrong. One can't even add data members. That would
already require putting them in a d-pointer.

> So we can
> still keep some flexibility (~10% ?) by deciding for 3.0 to reserve some
> extra bytes for future uses.

I realize, now, why you were hardcoding a fixed amount of reserved
space. It's indeed the only thing we can do in that direction.

I'm just wondering what we're going to do with that, and if we're not
going to be forced to write a separate class or Options template
parameter anyway whenever we need to do anything serious...

> Those bytes will be initialized to 0, and in
> the future their default values must still be zero.

hm i see. in case the old version creates a matrix that is then used
by the new version.

> In this case, there is
> indeed no need to store them on the heap, and we can store them on the stack
> as members of Matrix.

yes.

My conclusion:
 - adding a shared library would be giving up a very large advantage
that we have. Being purely headers makes it far easier for people to
use Eigen.

Adding -leigen is not far more complicated. It's only more complicated for people following the devel branch because they have to do a "hg pull -u && cd build && make && make install && cd -". But ok, as long as we can safely workaround without relying on complex mechanisms, then it's definitely better not to add a shared lib.

Second degree: if we add a shared lib no more how do I compile Eigen ? I run make but nothing happened ? ;)

 - once allocatedSize member is added, i don't see any more potential
reason on the horizon for changing the Matrix ABI, hence no potential
use case for a d-pointer.
 - if such a use case happens it's always possible to do that with a
new template parameter / class.
 - any fixed amount of reserved space can still fail to be enough the
day we need it, while having a constant cost. Hence, I'm not
convinced.

So my opinion: Option2 without any reserved space, just set in stone
the matrix ABI after you've implemented this change.

I'd still add one integer flag. We can always add new flags while ensuring that 0 is the default, and I already have a few ideas for such runtime flags:
- block heap reallocation
- mark the object as temporary. E.g., when a user return a MatrixXf by value => Matrix::operator= can use a cheap swap instead of a full copy:

MatrixXf foo() { MatrixXf ret; /*...*/ ret.markTemporary(); return ret;}

MatrixXf y;
/* ... */
y = foo();

- etc.

gael.
 

Benoit

>
> gael.
>
>
> On Thu, Mar 4, 2010 at 10:43 PM, Benoit Jacob <jacob.benoit.1@xxxxxxxxx>
> wrote:
>>
>> 2010/3/4 Gael Guennebaud <gael.guennebaud@xxxxxxxxx>:
>> >> >> > alloc:
>> >> >> > m_data = ei_aligned_new(size+<16 bytes>) + <16 bytes>;
>> >> >> > allocatedSize() = size;
>> >> >> >
>> >> >> > dealloc:
>> >> >> > ei_aligned_delete(m_data-<16bytes>);
>> >> >> >
>> >> >> > int& allocatedSize() {return (m_data-<16bytes>);}
>> >> >> >
>> >> >> > Disclaimer: yes the above is not C++, it is just to picture the
>> >> >> > idea!
>> >> >>
>> >> >> This looks like going only halfway toward heap-stored data. Instead,
>> >> >> why not take the bolder move of adding a d-pointer? We would put
>> >> >> there
>> >> >> any additional data that is OK to access with non-inline functions.
>> >> >> So
>> >> >> we would keep directly as data members the array pointer m_data and
>> >> >> the dimensions m_rows and m_cols so we can still call
>> >> >> rows()/cols()/data() at zero cost (useful as they are used all the
>> >> >> time) but other less frequently used data could be deferred onto the
>> >> >> d-pointer and accessed through no-inline accessors.
>> >> >
>> >> > To be honest I don't see how adding a d-pointer can offer more
>> >> > flexibility.
>> >>
>> >> With your approach, any additional member data that we may want to add
>> >> in the future, has to fit in the fixed number of bytes that were
>> >> reserved, like 8 bytes or 16 bytes. We have to decide once and for all
>> >> how much space we reserve for additional members. Moreover, once we've
>> >> added a member, we have to keep its offset fixed forever. All of that
>> >> can theoretically be overcome by using a d-pointer.
>> >
>> > hm... maybe I've been  clear but as "my proposal" I was referring to the
>> > solution of storing the D_structure in the dynamically allocated memory,
>> > i.e., with the data.
>>
>> Well let's look at your pseudo code:
>>
>>  m_data = ei_aligned_new(size+<16 bytes>) + <16 bytes>;
>>  allocatedSize() = size;
>>
>>  dealloc:
>>  ei_aligned_delete(m_data-<16bytes>);
>>
>> If I understand correctly, you're reserving a fixed amount of memory
>> (here 16 bytes) for the D_structure just before the location pointed
>> to by m_data. So yes it's on the heap, that's what I understood, but
>> you still hardcode the number of bytes that your D_structure may have.
>>
>> >> > My proposal affords the same with less memory and runtime overhead: a
>> >> > true
>> >> > d-pointer would requires in addition one pointer, one call to malloc,
>> >>
>> >> Yep, I thought about that just after sending the e-mail. The solution
>> >> might be to merge this idea with your idea: allocate at once the
>> >> matrix array and the D_structure. But in order to allow the
>> >> D_structure to grow in the future, place it after the array, not
>> >> before, and access it only with non-inline accessors .... now here's
>> >> the catch... that must be compiled into a shared library :( I didn't
>> >> think about that in my previous e-mail, but the d-pointer approach can
>> >> only work if we have a binary shared library :( Though at that point,
>> >> having such a tiny library would solve a bunch of problems at once
>> >> (cache size parameters, etc). I don't know what to think about that.
>> >
>> > You cannot easily put it at the end because ideally we would store the
>> > allocatedSize variable in the D_structure, and if you put it at the end
>> > of
>> > the data, you need the allocatedSize to access to the D_structure...
>>
>> Well yes, in my proposal of putting the D_structure at the end, we
>> have to add a new data member to Matrix, which can be either the
>> offset or why not directly the pointer to the D_structure. But I don't
>> think that it should be the allocatedSize that we should store, and
>> actually it still wouldn't be too convenient to address the
>> D_structure (need to take padding into account...)
>>
>> Then, from the moment we're storing 2 pointers, m_data and m_d, it
>> doesn't matter anymore which one is at the beginning and which one is
>> at the end of the buffer.
>>
>> Is that a big deal to add one more data member to MatrixXf...?
>>
>> Though in that vein, one might go further and ask why we're preferring
>> to put stuff on the heap at all, why not just add plain data members
>> to MatrixXf...? I'm not sure why sizeof(MatrixXf) matters more than
>> the size of the allocated buffer.
>>
>> > Since
>> > this whole approach  can only work via a shared library,
>>
>> ...if we want a real d-pointer. Without a shared lib, we can still
>> have a D_structure, it's just that the application using Eigen
>> hardcodes the D_structure data layout at compile time, so we don't get
>> the flexibility of a d-pointer.
>>
>> >> I'm completely hesitating, I can't make a decision on that. I guess
>> >> that if we treat this issue simultaneously with other issues that
>> >> would benefit from a binary lib, such as cache size runtime
>> >> parameters, then the case for a binary lib gets quite strong. On the
>> >> other hand it will require good communication and documentation, it
>> >> would be great to keep it optional (maybe make its code optionally
>> >> available as a header file...), and it should be WTFPL-licensed.
>> >
>> > Same here, though I become more and more in favor to a shared library as
>> > it
>> > might solve many issues.
>>
>> i don't know... above we're discussing a very good solution without a
>> binary lib, and below you have a great idea for the cache size problem
>> too:
>>
>> >
>> > Regarding runtime settings without a shared lib, I was thinking about
>> > using
>> > a static variable inside a function:
>> >
>> > // internal
>> > int manage_cache_size(enum action,int v=0)
>> > {
>> >  static int value = EIGEN_DEFAULT_CACHE_SIZE;
>> >   if(action="" value = v;
>> >   if(action="" return value;
>> >   return value;
>> >
>> > }
>> >
>> > // public:
>> > int cacheSize() { return manage_cache_size(get); }
>> > void setCacheSize(int v) { manage_cache_size(set,v); }
>> >
>> > but I'm really unsure about that...
>>
>> wow, that looks like a great idea!
>>
>> Such a static variable in a function, works exactly like a global
>> variable from a library as far as we're concerned... as far as I can
>> see.
>>
>> Benoit
>>
>>
>
>