Re: [boost] Re: Boost Mathematicians

From: Ralf W. Grosse-Kunstleve (rwgk_at_[hidden])
Date: 2004-07-03 04:07:54

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

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")

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

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>

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:

       template <
         typename ValueType,
         typename MemoryModelType,
         typename IndexingModelType,
         typename AlgebraType> array;

   In an ideal world I could then do this:

       template <typename ValueType, std::size_t MaxSize>
       typedef array<
         ValueType,
         stack_variable<MaxSize>,
         matrix_indexing,
         matrix_algebra> small_matrix;

       small_matrix<double, 20> a(3,3), b(4,5);

       template <typename ValueType>
       typedef array<
         ValueType,
         heap_shared,
         matrix_indexing,
         matrix_algebra> shared_matrix;

       shared_matrix<double> a(300, 400);

       template <typename ValueType, std::size_t NDim>
       typedef array<
         ValueType,
         heap_shared,
         c_convention<NDim>, // or fortran_convention<NDim>
         element_wise_algebra> n_dim_c_array;

       n_dim_c_array<double, 3> a(10,20,30);

   [I know we don't have template typedefs :-( :-( ]

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. Having or not having to throw in a few extra loops by
   hand doesn't make a difference.

Ralf

                
__________________________________
Do you Yahoo!?
Yahoo! Mail - You care about security. So do we.
http://promotions.yahoo.com/new_mail