[boost] Re: Boost Mathematicians

From: David Abrahams (dave_at_[hidden])
Date: 2004-07-03 09:43:23

"Ralf W. Grosse-Kunstleve" <rwgk_at_[hidden]> writes:

> --- David Abrahams <dave_at_[hidden]> wrote:
>> "Ralf W. Grosse-Kunstleve" <rwgk_at_[hidden]> writes:
>> 
>> > --- David Abrahams <dave_at_[hidden]> wrote:
>> >> with expression templates, and of course, zero abstraction penalty ;-)
>> >
>> > Is a reference-counted array type also part of the plan?
>> 
>> Not specifically.  We'll probably be relying on Boost.Move (in the
>> sandbox) to avoid unneccessary copies.  We may use reference-counting
>> to implement an "fine-grained immutable" array type, but if so, that
>> will provide a complete illusion of value semantics and *not*
>> reference semantics.  It's crucial that
>> 
>>      array a = b;
>>      a *= 2;
>> 
>> never alters b.  A concept taxonomy in which b is sometimes altered
>> and sometimes not would be impossible to write generic code for.
>
> You are hitting the nail on the head. Experience with my own
> reference-counted array type tells me that the issue of
> immutability/constness needs extreme care. My own solution has the
> glaring shortcoming of not providing a const-reference-counted array
> type (excuses available on request :-). But having said that, I found
> it a lot worse not to be able to write a function that returns a new
> array without incurring a deep copy. 

It seems quite a few compilers implement one or another form of RVO.l

> Move semantics in one form or another is absolutely crucial to
> enable writing of readable code.
>
> Some related thoughts from an amateur array library designer that may
> or may not be useful:
>
> 0. The two fundamental properties of array types are:
>
>      - Memory management model
>      - Indexing model

I guess you haven't read the MTL concept breakdown:

  - Shape
  - Storage (I think this is what you're calling memory management)
  - Orientation (row-major, column-major, diagonal-major...)

> 1. I found the following memory management models for arrays to
>    be essential in practical applications (i.e. I implemented
>    them all, and make heavy use of all):
>
>        stack, fixed size
>        stack, variable size, fixed capacity
>        heap, variable capacity, one owner (e.g. std::vector)
>        heap, variable capacity, shared ownership
>        reference to any of these (i.e. "no management")

That's storage.

> 2. Common "indexing models" are 1-dim indexing (e.g. std::vector),
>    2-dim (matrix types), n-dim regular grids (e.g. Fortran's DIMENSION
>    statement, Python's Numeric arrays, Blitz). However, these are just
>    typical examples. Applications often require custom indexing models
>    (e.g. we have periodic grids and grids with other types of
>    symmetry; spare matrices may be viewed as another example).

For linear algebra, you only need 1-dimensional vectors and
2-dimensional matrices.  However, you can have matrices of matrices
which could be thought of as 4D (although that's probably a flawed
way to look at them).

I should point out that an "array library" like Blitz++ is probably a
different beast from a Matrix/Linear Algebra library like MTL, so
what I'm going to be working on may not be aimed at the things you're
interested in.

> 3. A general purpose array library should provide a mechanism for
>    reusing memory management models and indexing models in
>    various combinations. This could lead to:
>
>        memory_model<typename ValueType, typename IndexingModelType>
>    or
>        indexing_model<typename ValueType, typename MemoryModelType>

I don't understand why you think one of them should take the other as
a parameter.

> 4. Array algebras (unary and binary operators, functions) are a third
>    property that is ideally separated from memory models and, if
>    applicable, indexing models. This could lead to:
>
> 5. Expression templates are an optimization on top of all this and
>    in my practical experience the least important of all the points
>    mentioned here. In all likelihood the 5-10% of code that matter for
>    runtime performance have to be hand-optimized anyway, usually
>    leading to distortions of the original, intuitive code beyond
>    recognition. 

The aim is to make the library smart enough to do those optimizations
correctly so you don't have to do it by hand.

-- 
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com