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

Boost list run by bdawes at, gregod at, cpdaniel at, john at