Containers & Allocators

[Ares Lagae]

Hello,

I am trying to create a container the stl way, and I have a couple of
questions. The code of the container in question can be found at

http://www.cs.kuleuven.ac.be/~ares/tmp/array_2_hpp.html

It is a 2d array that dynamically allocates its storage. It cannot be
resized. It offers element access methods for both sequential access and 2d
element access.

It allocates one big chunk of memory.
To avoid computing 1D indices from 2D indices like:

T* elements
elements = new T[rows * cols]
....
return elements[i + (j * cols)]

it then allocates an array of row pointers, that point in this big chunk of
memory:

T** elements
elements = new T*[...] // row pointers
elements[0] = new T[rows * cols] // actual storage
// set row pointers
....
return elements[j]

On the systems I tested, this made a lot of difference.

I have the following questions / thoughts on which I would appreciate
comments.

1) I need two kinds allocators (one for T's and one for T*'s). The exception
safe constructors seem overly complicated. For array_3 I would need an
additional allocator for T**'s, and almost 10 try/catch constructs.

2) Can allocator::deallocate() throw ? I had expected a no throw
declaration.

3) Whats the deal with the allocators ? Do they have instace variables or
not ? Do I need to store them or not ?

4) The std::uninitialized* functions seem to be unusable in this context ?

5) Have a look on how the begin() and end() are implemented. If the size of
the array is 0, then they both return the 0 pointer. Is this OK ?

6) In swap, do the allocators also need to be swapped?

7) std::swap is very important, but it cannot be partially specialized, and
you cannot define an overload in the std namespace ? How do I handle that ?

best regards,
Ares Lagae

 

[SirMike]

Sorry for not responding for your questions but why do you force in the
"opened door" ?

 

[Ares Lagae]

Sorry for not responding for your questions but why do you force in the
"opened door" ?

I hope you are not suggesting to use a std::vector< std::vector<T> >, which
is quite a different beast than a 2D array according to me.

The question is not how to get a 2d array in C++, rather how to create an
array_2 class "the stl way", but you do have a point.

Ares

 

[Howard Hinnant]

I have the following questions / thoughts on which I would appreciate
comments.

Apologies in advance for not studying your code (though I did glance at
it). But I felt I might be able to give a helpful response anyway.

1) I need two kinds allocators (one for T's and one for T*'s). The exception
safe constructors seem overly complicated. For array_3 I would need an
additional allocator for T**'s, and almost 10 try/catch constructs.

I find the easiest way to write code like this is to separate the class
into a private base class that implements everything but resource
acquiring constructors, and a derived class that implements the resource
acquiring constructors. Bjarne's Appendix E may help illustrate:

http://www.research.att.com/~bs/3rd_safe0.html

If a (derived) resource acquiring constructor throws an exception, the
base class will (should) clean up all resources already acquired.

It is possible that this idiom will be obsoleted in C++0X if we get
"Delegating Constructors":
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1618.pdf .

2) Can allocator::deallocate() throw ? I had expected a no throw
declaration.

No, throwing in deallocate is forbidden by 20.1.5p2 (in the C++
standard).

3) Whats the deal with the allocators ? Do they have instace variables or
not ? Do I need to store them or not ?

They usually don't have instance variables, but they can. Imho, the
highest quality solution is to store them using boost::compressed_pair:

http://www.boost.org/libs/utility/compressed_pair.htm

This is a pair-like utility that will optimize away the space for a
member that is "empty". By pairing an allocator with some member that
you know not to be empty (like size or whatever), you can effectively
compute at compile time whether you need to allocate space for your
allocator(s).

4) The std::uninitialized* functions seem to be unusable in this context ?

Imho yes. Although it is fuzzy whether it is required to use the
allocator's construct function (is allocator::construct a customization
point, or merely a convenience function for placement new?).

5) Have a look on how the begin() and end() are implemented. If the size of
the array is 0, then they both return the 0 pointer. Is this OK ?

Without studying your specific implementation, in general yes, it is ok.

6) In swap, do the allocators also need to be swapped?

The standard does not specify what should happen with unequal allocators
(those that can not deallocate each other's pointers). Therefore there
is no need to swap allocators if they are all equal. However, what to
do with unequal allocators is currently a controversial point. There is
a defect report on it here:

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#431

And my (strongly held) opinion is here:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1599.html

7) std::swap is very important, but it cannot be partially specialized, and
you cannot define an overload in the std namespace ? How do I handle that ?

Put swap in the same namespace as array_2. See lwg defect reports 225,
226 and 229, and the proposed resolution here:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1523.htm

-Howard

 

[Dave Moore]

Hello,

I am trying to create a container the stl way, and I have a couple of
questions. The code of the container in question can be found at

http://www.cs.kuleuven.ac.be/~ares/tmp/array_2_hpp.html

It is a 2d array that dynamically allocates its storage. It cannot be
resized. It offers element access methods for both sequential access and 2d
element access.

[snip]

Looks like you may be re-inventing the wheel here ... if you are doing it to
better understand the inner workings, then go for it, and more power to you.
But if you just want a well-designed, performance-tuned Matrix class, then
have a look at the options at the Object Oriented Numerics site:

http://www.oonumerics.org/oon/

HTH,

Dave Moore

 

[Dave Moore]

Hello,

I am trying to create a container the stl way, and I have a couple of
questions. The code of the container in question can be found at

http://www.cs.kuleuven.ac.be/~ares/tmp/array_2_hpp.html

It is a 2d array that dynamically allocates its storage. It cannot be
resized. It offers element access methods for both sequential access and 2d
element access.

It allocates one big chunk of memory.
To avoid computing 1D indices from 2D indices like:

T* elements
elements = new T[rows * cols]
...
return elements[i + (j * cols)]

it then allocates an array of row pointers, that point in this big chunk of
memory:

T** elements
elements = new T*[...] // row pointers
elements[0] = new T[rows * cols] // actual storage
// set row pointers
return elements[j]

On the systems I tested, this made a lot of difference.

Are you sure? Integer arithmetic for array addressing has never
significantly affected the performance of any numerical code I have used.
After all, in C++, a[9] is equivalent to *(a+9), so the integer arithmetic
is implied anyway.

I have the following questions / thoughts on which I would appreciate
comments.

1) I need two kinds allocators (one for T's and one for T*'s). The exception
safe constructors seem overly complicated. For array_3 I would need an
additional allocator for T**'s, and almost 10 try/catch constructs.

Well, as I said, I think you are doing things in an unnecessarily
complicated fashion. I cannot see the need for 2-D data *allocation* as you
are currently doing ... that is only needed if the rows of the matrix can
have different lengths, which is not the case in your design. Why not
simply use 1-D allocation a-la vector<T> (or maybe valarray<T>) as the
underlying implementation? This gets rid of the need for the elaborate
allocation of pointers-to-pointers as you are currently doing. At the very
least you should use a T* (and not a T**) to point to the allocated data,
and you won't need all of that try .. catch stuff that currently makes your
constructor definitions virtually impenetrable.
How you do the addressing of such data is an implementation detail. You
could do address arithmetic, or store your "rows" using a vector<T*>, or
even a T** (but only with "first-level" allocation). Using 1D-data storage
also greatly reduces the difficulty associated with adding additional
dimensions to the array.

2) Can allocator::deallocate() throw ? I had expected a no throw
declaration.

Depends which allocator .. I think the ones in std cannot. Of course you
could write your own that can throw.

3) Whats the deal with the allocators ? Do they have instace variables or
not ? Do I need to store them or not ?

I don't really know ... I haven't found the need to "roll my own" container
types since before C++ was standardized. I use the STL containers, or one
of the libraries available at http://www.oonumerics.org/oon/.

[snip]

All the rest of your questions kind of disappear if you use a std::vector<T>
for your implementation, which is a(nother) strong argument in favor IMHO.
I would recommend trying such an implementation (it doesn't take much work)
and measuring its performance against your hand-rolled one in a *real* test.
IOW, one that does some real work with the elements, and doesn't just assign
them and pass them around. I have been misled by "lightweight" performance
analyses in the past, only to find out that the results were irrelevant in
"real code", because the work done elsewhere completely overwhelmed the
performance differences between storage class implementations.

Like I said in my earlier mail, if you are doing this for a challenge, or
for your own edification, then great. I will try to continue to help if I
can.

Dave Moore

 

[Ares Lagae]

Are you sure? Integer arithmetic for array addressing has never
significantly affected the performance of any numerical code I have used.
After all, in C++, a[9] is equivalent to *(a+9), so the integer arithmetic
is implied anyway.

I'm referring to the difference between

a[i + (j * rows)]

and

a[j]

or, for array_3

a[i + (j * rows) + (k * rows * cols)]

and

a[j][k]

Well, as I said, I think you are doing things in an unnecessarily
complicated fashion. I cannot see the need for 2-D data *allocation* as
you are currently doing ... that is only needed if the rows of the matrix
can
have different lengths, which is not the case in your design. Why not
simply use 1-D allocation a-la vector<T> (or maybe valarray<T>) as the
underlying implementation? This gets rid of the need for the elaborate
allocation of pointers-to-pointers as you are currently doing. At the
very least you should use a T* (and not a T**) to point to the allocated
data, and you won't need all of that try .. catch stuff that currently
makes your constructor definitions virtually impenetrable.

I am using an 1-D allocation a-la vector<T>. However, I also allocate an
additional array of pointers, pointing to row starts in that big chunk. I
do not allocate rows independent.

How you do the addressing of such data is an implementation detail.
You

No.
The adressing scheme I describe allows for a[j], and this requires a
slightly different allocation scheme as a[i + (j * rows)] adressing.

Ares Lagae