Re: [eigen] Malloc-free dynamic matrices

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

2010/3/5 Gael Guennebaud <gael.guennebaud@xxxxxxxxx>:
>
>
> On Fri, Mar 5, 2010 at 3:19 PM, Benoit Jacob <jacob.benoit.1@xxxxxxxxx>
> wrote:
>>
>> 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.
>
> wow very impressive list!
>
>>
>> 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.
>
> yep sorry for not having been very explicit at the beginning. Anyway sounds
> like we are converging.

Yes i think we're done with this debate :)

Benoit

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