Utility Libraries for BREW - A String Class
This article is the first one in a series that will present possible implementations of utility libraries in BREW. We will start today with a string library and continue with vector and hashtable in the next installment.
A legitimate question might be: "We have STL — why something else?" STL is flexible and powerful (I am one of its greatest supporters, believe me!) but sometimes STL is simply "too heavy", especially on platforms like BREW. Examples of possible performance penalties: heavy use of copying (), differences in string implementation(), temporaries(, ), etc.
Pulling the std::string...
A basic container, widely used, is std::string. The advantages of using strings instead of dynamically allocated arrays are well known (). But there are different ways to implement strings, and from the BREW perspective this is extremely important. Replacing char* with string means we might increase the size of the object we place on the stack from 1 to 7, depending on the implementation. BREW uses AECHAR too, and as AECHAR manipulators don't have standard (wchar_t like) interfaces additional changes are needed. Some temporaries may be avoided for particular uses of string. We will investigate all these aspects one by one.
A very sensitive issue, especially for BREW, is the size of the string. There are 4 different ways to implement a string and each one has a different size. The basic approach is to use directly a size, a capacity, the raw pointer, allocator and reference count (if available). Size is at least 3 times the raw pointer. Performance is very good.
A very conservative way is to embed all the above mentioned class data in a structure and reference the structure via a pointer. Size is equal to the raw pointer but there is a big performance penalty — an extra allocation.
Other implementations exhibit the "small string optimization" idiom — an internal buffer holds strings smaller than 15 characters. If size exceeds this value the buffer holds the pointer to the dynamically allocated memory holding the string. This has seven times the size of the raw pointer but has the best performance.
A fourth approach is uses a variant of 2, like:
This way the size of the string equals the size of the raw pointer and the string is fully populated in one single allocation. Performance is good.
Reference counting (copy-on-write) is less and less used in STL libraries and even in the single-threaded world is a mixed blessing (, ).
Taking into account the whole picture and the restrictions of the BREW platform BrewString implements the fourth variant and is not referenced counted.
Page 1 of 3