Re: [eigen] Malloc-free dynamic matrices

[Benoit Jacob <jacob.benoit.1@xxxxxxxxx>]

2010/3/5 Gael Guennebaud <gael.guennebaud@xxxxxxxxx>:
> 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 ? ;)

This is a problem that we currently have to deal with... three times a year..

By contrast here are some problems we'd have to address if we had a
binary library:
1) choose a license for it. Can't be LGPL (would prevent static
linking). Should be MIT/BSD.
2) rewrite (complexify) our licensing FAQ: we're LGPL except that,
we're a pure-headers-only lib except for that, but that doesn't matter
since that part is not LGPL.
3) complexify the tutorial to explain how to build Eigen and how to link to it
4) everytime users have strange crashes, we'd have to wonder if it's
caused by an outdated binary lib, so we'd ask them to rebuild,
reinstall, retry...
5) for users who can't do dynamic linking (some embedded users),
explain how to build a static library instead...
6) we could no longer say: you're not forced to use cmake, you can use
the headers right away
7) our (many, many) users who include in their own tree a copy of
Eigen headers, would no longer be able to do so, they could only
approach that if their own project is using CMake, otherwise they'd
probably give that up.
8) we'd no longer be just a -noarch package in linux distros. That
means that we'd no longer be available on all architectures as soon as
we're available on x86.
9) like any binary library, our users would expect us to provide at
least Windows and Mac build on the website.
10) small shared libraries are not innocuous with respect to startup
time. It's widely considered that one of the worst reasons why some
apps can take long to startup, is when they have to load lots of small
shared libraries (lots of small random disk accesses). So even if we'd
be only one of them we'd be contributing to that.

just a check-list to check that the two sides of the coin are being
considered...

>
>>  - 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.

ah ok a _flag_. I didn't think of that. As long as you were proposing
to add a blank field only for future use without knowing at all what
it'll be used for, I was not convinced. Now a _flag_, that's a precise
and reasonable use case. And yes, just adding a single 'int' is not
going to cost anything measurable.

>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.

yes ok, makes sense. We already have compite-time flags, why not runtime flags.

Benoit

>
> 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==set) value = v;
>> >> >   if(action==get) 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
>> >>
>> >>
>> >
>> >
>>
>>
>
>