Boost logo

Boost :

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

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk