Utility Libraries for BREW - A Vector Class

Abstract

This article is the second one in a series that presents possible implementations of utility libraries in BREW. This time we will analyze the intricacies of a vector class (BrewVector), examining in greater detail the code bloat usually associated with general purpose containers and how BrewString tries to avoid it. BrewString specifics will be further presented and analyzed (efficiency, safety, special features).

The basics...

Avoiding dynamically allocated arrays translates into avoiding memory leaks, double deletes, and more. (see ^[1] for a discussion). The vector container comes to the rescue, wrapping an array and hiding all its error prone details in a convenient way.

As vector and string are strongly related we expect similar inner details — a raw pointer, size, capacity, possible allocation policy. There is, however, a major difference — a string expects no more than two types to be used (char and AEChar for BREW) where as a vector can be used with virtually any possible type. This might lead to code bloat, or at least something that's perceived as such. Let's take a closer look at the inner mechanics of the phenomenon.

Dealing in our code with an array of floats and an array of ints translates into:

• C approach: we have to instantiate and manage two arrays
• C++ idiom like 'initialization is resource acquisition': we have to instantiate two array objects
• Templetized vector: compiler will generate a vector<int> and a vector<float>

As long as we are in control of the process (meaning that we know exactly the cost of instantiating a vector<T>) there is no code bloat. There might even be small reductions in the final size of the code (we use only one vector declaration). To cite from an article devoted to EC++ efficiency ^[2] —" Much of the code bloat found in C++ code comes not from using a feature such as a template but from referencing templates that are found in large C++ libraries."

Even in the above described situation there is a technique that might be used to alleviate the bloat tendency, technique that (paradoxically one might say) looks much more natural when using templates. Basically the idea is to use a common type if any safe cast exists to/from that type. For example:

typedef BrewVector<int> Bint;

Obviously, one can now use Bint for both ints and chars, as in:

template <class S, class T  >
void writeVector(Writer writer,  S& bi)
{
   for (int i = 0, sz = bi.size(); i < sz; ++i)
      writer.WriteLine( static_cast<T>(bi[i]));
}
	//this specialization is not conformant in VC 6.0 
template <class S  >
void writeVector(Writer writer,  S& bi)
{
   for (int i = 0, sz = bi.size(); i < sz; ++i)
      writer.WriteLine( static_cast<S::REAL_TYPE>(bi[i]));
}

Bint bi;
bi.append('B');
bi.append('R');
bi.append('E');
bi.append('W');
writeVector <Bint, char>(bi, 9);

will result in

B
R
E
W

There is another interesting case in this discussion — containers of pointers. Usually they are used to preserve the polymorphic information of the elements (avoiding slicing problems). Their usage might be even more extensive in BREW due to the fact that heap allocation is so common. Automatically applying the above mentioned technique results in using the obvious "common type" of void*. But when comparing vector<void*> with vector<int*> for example we can easily see what we are losing when using void*: the type safety net, as void* is notorious for the bugs it might introduce. There is a compromise — a partial specialization like:

template<class T> 
class vector<T*> : private vector {
   // specialized implementation for T*
   // relying of the common vector code
};

where private signifies an "is-implemented-as" relationship (can be considered as composition). This means that we can hide all the casting details and enjoy the benefits of a type safe implementation, paying a small price, as the specialization is usually small and presented inline.

For example:

template <class S  >
void pwriteVector(Writer writer,  S& bi)
{
   for (int i = 0, sz = bi.size(); i < sz; ++i)
      writer.WriteLine( *bi[i]);
}
template <class T, class ReallocPolicy  >
void deleteBrewPVectorElems(BrewPVector<T, ReallocPolicy> & pi)
{
   for (int i = 0, sz = pi.size(); i < sz; ++i)
   {
      delete(pi[i]) ;
   }
}
//for a discussion of why BrewPvector and not BrewVector
// see next paragraph
typedef BrewPVector<int, ReallocPolicy_2> Bpv;
Bpv bi;
bi.ensureCapacity(3);
bi.append( new int(100));
bi.append( new int(2));
bi.append( new int(3));
delete bi[2];
bi.setAt(new int(88), 2);
pwriteVector(writer,bi);
deleteBrewPVectorElems(bi) ;

Results in:

100
2
88

There are other important sources of code bloat (inline, RTTI, etc.) but they are beyond the scope of this article (please consult ^[3] for ARM compiler specifics)

...and the details

BrewVector goals are the same as for the string implementation we presented last time[4]:

• minimum impact when used on the stack (sizeof(BrewVector) = sizeof(raw pointer)
• efficient
• easy to use
• integration with POD (plain old data)
• minimal implementation — no use of iterators or algorithms

Let's analyze these requests one by one.

BrewVector keeps the same internal representation as BrewString, so that sizeof(BrewVector) = sizeof(raw pointer). As usual an informal comparison between BrewVector and two std::vector implementations was conducted (see ^[4]). BrewVector is as fast as the fastest std::vector and between 2 and 3 times faster than the other.

As BREW development has its roots in C and POD is widely used BrewVector carefully considers integration with POD. Data manipulators accept usually both vectors and POD. For example:

int *iar = new int[3];
iar[0] = 4;
iar[1] = 44;
iar[2] = 444; 
Bint bi2(iar, 3); //constructs a vector from the first 3 elements of iar
Bint bi(10); 
Bint bi3(bi2);
Bint bi4(bi2, 2); //a vector from the first 2 elements of bi2

Similar constructs are accepted for assign (the assignment operator was replaced with this function from the very motive of this flexibility), insert and append. A very interesting constructor, inherited from BrewString and used to efficiently implement operator+() (allows return value optimization) is:

template <class U, class V>
BrewVector (const U& lhs, UINT lnl, const V& rhs, UINT lnr);

It can be used with any combination of POD/BrewVector as in:

Bint bi5 (iar, 2, bi2, bi2.size());

This generalization allows a great deal of flexibility that otherwise should have been implemented using iterators.

The BrewVector<T*> specialization

BrewVector can easily be used for pointers as it is. Unfortunately there are many dangers associated with this use, for example:

BrewVector<int*> bi(a3elementsvector);
bi.append(new int(2));
bi.setSize(2); // memory leak < silently deleting bi[3]

A specialization using void*, as discussed above, was provided under the name BrewPVector. There are 2 reasons:

• Some compilers don't have full support for partial template specialization
• There might be users preferring for different reasons the full implementation of BrewVector

BrewPVector is a reduced (and safer) version of BrewVector. For example there are no inserts or assignments. A separate setAt() method was provided to change elements — setAt does index range checking. No remove() and setSize too, only a simple and minimal interface avoiding (almost) all the potential traps.

There is an interesting policy of type ReallocPolicy used internally by BrewVector. Usually the capacity of std::vector is doubled any time the vector has to grow when using the default allocation. Keeping in mind the BREW memory limitations BrewVector allows a policy based on a threshold: allow one way to increase capacity up to some point and a different one after that. One naove example might be:

struct ReallocPolicy_200
{
   static UINT setSize(UINT size) 
   {
      if (size < 200)
         return 2*size;
      return size+10;
   }
};

typedef BrewVector<int, ReallocPolicy_200> Bint200;
Bint200 bi; //capacity will double up to 200 elements
            //capacity incremented by 10 after that 

BrewVector has even a for_each implementation — in this case is a member function defined like:

template < class F >
   F forEach(F func, UINT strt = 0, UINT end =0 );

where F is a functor.

It can be used like:

Writer writer(m_pIShell); 
typedef BrewPVector<int, ReallocPolicy_2> Bpv;
Bpv bi;
bi.ensureCapacity(3);
bi.append( new int(100));
bi.append( new int(2));
bi.append( new int(3));
typedef oOut<2> ppOut;
bi.forEach(ppOut(100, writer)).drawLine();
delete bi[2];
bi.setAt(new int(88), 2);
bi.forEach(ppOut(101, writer)).drawLine();
bi.forEach(del());

Other interesting applications of forEach are in the source code, notably an output technique based on Int2Type^[5]. Please note that the provided implementation is VC6.0 compatible — for VC7.x contact the author.

Possible future enhancements:

BrewVector can easily be extended to accept ranges.

References:

^[1] Scott Meyers — Effective STL ; Addison-Wesley, 2001

^[2] Christopher Smith — Program in Embedded C++ for Smaller and Faster Code http://www.spacetools.com/site/contact_v1_5/V1_5p42.pdf

^[3] Reducing C++ Code Bloat 7mdash; http://www.spacetools.com/site/contact_v1_5/V1_5p42.pdf

^[4] Utility Libraries for BREW — A String Class

^[5] Andrei Alexandrescu - Modern C++ Design, STL ; Addison-Wesley, 2001

Downloads: Source Code - 290 kb.

About the Author

Radu Braniste is Director of Technology at Epicad. He can be contacted at rbraniste@epicad.com

# # #