Re: [boost] Re: Boost Mathematicians

From: Jeremy Graham Siek (jsiek_at_[hidden])
Date: 2004-07-05 15:55:56

Hi Michael,

On Jul 5, 2004, at 11:09 AM, Michael Stevens wrote:

> On Saturday 03 July 2004 16:54,David Abrahams 
> <dave_at_[hidden]>
>
>> Jeremy and I have just completed a re-evaluation of uBlas based on
>> what's in uBlas' own CVS repository, having not discovered that until
>> recently (you should have that info on uBlas' Boost page!)  We have
>> some major complaints with uBlas' design.  The list is long, and the
>> issues run deep enough that we don't believe that uBlas is a suitable
>> foundation for the work we want to do.
>
> This is very interesting. Thanks for writing this up and posting. I 
> can't
> address all the issues. However those which I can I will endeavor to 
> give you
> and the Boost community my feedback on.
>
> First of all I am currently making sure Boost is updated with the 
> latest uBLAS
> development version. This already has updated documentation which 
> points to
> all the correct locations for discussions, CVS and Wiki. This should 
> make it
> much easier for users to find the correct locations if the stable 
> version in
> Boost does not meet their needs.
>
> To facilitate the development of solutions I will place many of the 
> points
> into the uBLAS bug tracker on SF.
>
>> Interface Design
>> ----------------
>>
>> * Not grounded in Generic Programming.  The concept taxonomies, to the
>>   extent they exist, are weak, and poorly/incorrectly documented.
>>   Aspects of the design that should be generic are not (e.g. only
>>   certain storage containers are supported, rather than supplying
>>   storage concept requirements).  No linear algebra concepts (vector
>>   space, field, etc.)  The library is so out-of-conformance with our
>>   expectations for Generic Programming that this one item by itself
>>   is probably enough to make it unsuitable for us.
>
> This is a big issue. I believe we need to split the documentation 
> issues from
> the design issues. Documentation is high on the priority list of many 
> uBLAS
> users and developers. Most new users start with a requirement for a C++
> matrix and BLAS library with nice syntax, efficiency and 
> documentation! The
> need for clearly defined and documented concepts comes for most people 
> a
> little latter when extensibility becomes an issue.
>
> The storage concept is not as bad as it appears. The concept although 
> not
> documented is sufficiently well defined that creating a new model is
> unproblematic. At present the concepts are documented by their models 
> :-)

That is not satisfactory.

>
>> No linear algebra concepts (vector space, field, etc.)
> I not sure if these concepts really need to be defined. They are 
> already well
> described in many mathematical text books and in Wikipedia.

Sure, but they do not spell out the C++ syntax that should be used. The 
syntax
is important, because it must be standardized in order for people to 
write
generic algorithms.

> Almost all the
> major reference works on BLAS and Matrices simply state elements are 
> either
> Real or Complex and are therefore implicitly a field.
> Of course a C++ linear algebra library should be generic enough to 
> work with
> any type which is a numeric approximation to a field.
>
>
>>
>> * Redundant specification of element type in matrix/vector storage.
> Not sure what is meant here, can you elaborate ?
>
>> * size1 and size2 should be named num_rows and num_columns or
>>   something memnonic
>>
>> * iterator1 and iterator2 should be named column_iterator and
>>   row_iterator or something memnonic.
> I think many uBLAS users have come to appreciate the brevity of 
> naming. I
> think the concensus in the Boost review was as long as they were used
> consistenty these names are acceptable.
>
>> * prod should be named operator*; this is a linear algebra library
>>   after all.
> Oh, there has been much ink spent on this! Joerg argues against 
> operator* for
> two reasons I think. a) operator* brings an expectation of 
> commutativity and
> this is not the case in linear algebra
> b) The are many products (inner,outer,element) and there should be a 
> clarity
> of naming.

However, matrix product is *the* central operation in linear algebra, 
and should
have the most convenient syntax. The other products can have other 
names.

>> * begin() and end() should never violate O(1) complexity expectations.
>>
>> * insert(i,x) and erase(i) names used inconsistently with standard 
>> library.
> Agreed.
>
>> * Matrix/Vector concept/class interfaces are way too "fat" and need to
>>   be minimized (e.g. rbegin/rend *member* functions should be
>>   eliminated).
> Interesting. Certainly the fatness is a worry. I think rbegin/rend 
> need to
> stay as members as this is part of the Reversible Container concept.
>
>> * The slice interface is wrong; stride should come last and be
>>   optional; 2nd argument should be end and not size; then a separate
>>   range interface could be eliminated.
> For std::slice (valarray) compatibility stride should be last. Not 
> sure why
> this was not picked up on a long time ago!!
> valarray (and uBLAS) use size (not end) for good reason however.
> I also think it would be a mistake to drop range. slices can be 
> degenerate
> (zero stride) and this has a runtime cost which range does not need to 
> share.
>
>> * No support for unorderd sparse formats -- it can't be made to fit
>>   into the uBlas framework.
> Interesting. I guess this requires some thinking time for a sensible
> discussion.
>
>
>> Implementation
>> --------------
>>
>> * Expressions that require temporaries are not supported by uBLAS
>>   under release mode. They are supported under debug mode.  For
>>   example, the following program compiles under debug mode, but not
>>   under release mode.
>>
>>       std::cout << prod (prod(v, m), m) << std::endl;
>>   }
>>
>>   The workaround to make it compile under release mode is to
>>   explicitly insert the creation of a temporary:
>>
>>       std::cout << prod (vector<double>(prod(v, m)), m) << std::endl;
>>
>>   There should be no such surprises when moving from debug to
>>   release.  Debug mode should use expression templates, too, as the
>>   differences can cause other surprises.
>
> This was changed by Joerg after the last stable release to Boost. I 
> will check
> there has been no regression.
> The fix propagates an expression complexity that is statically 
> checked. This
> check explictly prevents the creation of nested products!! Therefore 
> the
> correct code is now that with the explicit temporary or with one of the
> parameterized prod's.
> The change is aimed at the user. They must clearly express the 
> evaluation and
> storage complexity of the expressions.

That is not what I would call a "fix". The right approach is to
have smarter expression templates that know when to create temporaries.
I know this approach is possible since the MTL 3 prototype does it.

>
> The change of semantics between debug/release builds is unfortunate. 
> The
> partial disabling of the expression templates in debug mode is 
> currently the
> default and a config macro. With current compiler technology this 
> prevents
> debuggers crashing and users scrolling through type names that are 
> pages
> long. In a perfect environment the default would be the opposite.
>
>> * Should use iterator_adaptor. There is a ton of boilerplate iterator
>>   code in the uBLAS that needs to be deleted.
> Agreed 100%. A well used iterator_adaptor would shorten uBLAS 
> definitions to
> about 30% of their current size !!
>
>> * Should use enable_if instead of CRTP to implement operators. uBLAS
>>   avoids the ambiguity problem by only using operator* for
>>   vector-scalar, matrix-scalar ops, but that's only a partial
>>   solution.  Its expressions can't interact with objects from other
>>   libraries (e.g. multi-array) because they require the intrusive CRTP
>>   base class.
> Interesting solution. Agreed, the current implementation is closed to 
> other
> objects because of the intrusive base class. Sadly uBLAS was designed 
> before
> enable_if. Any pointers to compile/runtime effects of the enable_if 
> solution?
>
> We would however lose the static type checking that argument matching 
> with the
> CRTP base class gives us. At this point I think we land in a deep
> philosophical argument as to the strengths and weaknesses of generic
> progreamming %-)

No, we would still have static type checking.

>> * Certain operations, especially on sparse matrices and vectors, and
>>   when dealing with matrix_row and matrix_column proxies have the
>>   wrong complexity.  Functions such as begin() and end() are suppose
>>   to be constant time. I see calls to find1 and find2, which look like
>>   expensive functions (they each contain a loop).
> Agreed. The implementation with findN is simple but expensive. I am 
> not sure
> why Joerg choose this route.
>
>> Testing
>> -------
>> * There should be a readme describing the organization of the tests.
>>
>> * Tests should not print stuff that must be manually inspected for
>>   correctness.
>>
>> * Test programs should instead either complete successfully
>>   (with exit code 0) or not (and print why it failed).
> Agreed. If anyone submits a patch it would be included very quickly!
>
>> * Abstraction penalty tests need to compare the library with tuned
>>   fortran BLAS and ATLAS, not naive 'C' implementation.
> There was some very good work on this about a year ago. Sadly the 
> results are
> no longer accessable on the web. Since the loss to Intel of the KAI 
> compiler
> it is hard to see any library archiving really exceptional results in 
> this
> regard.
>
>> Documentation
>> -------------
>>
>> * In really bad shape.  Redundant boilerplate tables make the head
>>   spin rather than providing useful information.
>>
>> * Needs to be user-centered, not implementation centered.
>>
>> * Need a good set of tutorials.
> Agreed.
>
>> Compilers
>> ---------
>>
>> * Simple example doesn't compile with gcc 3.3. Got it to compile by
>>   #if'ing out operator value_type() in vector_expression.hpp.
> Strange gcc-3.3.3 is my primary compiler. Can you specify the problem 
> more
> exactly. Which gcc-3.3 subversion is causing the problem?
>
> Thanks,
> 	Michael
> ___________________________________
> Michael Stevens Systems Engineering
>
> Navigation Systems, Estimation  and
>                  Bayesian Filtering
>     http://bayesclasses.sf.net
> ___________________________________
>
> _______________________________________________
> Unsubscribe & other changes: 
> http://lists.boost.org/mailman/listinfo.cgi/boost
>
_______________________________________________
Jeremy Siek <jsiek_at_[hidden]>
http://www.osl.iu.edu/~jsiek
Ph.D. Candidate, Indiana University Bloomington
C++ Booster (http://www.boost.org)
_______________________________________________