September 20, 2014
Hot Topics:
RSS RSS feed Download our iPhone app

Utility Libraries for BREW - A Vector Class

  • March 25, 2003
  • By Radu Braniste
  • Send Email »
  • More Articles »

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
and writeVector(bi, 9); will be: 66 82 69 87

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)





Page 1 of 2



Comment and Contribute

 


(Maximum characters: 1200). You have characters left.

 

 


Sitemap | Contact Us

Rocket Fuel