≡ Menu

Killing Memory Errors with the STL

section-1whackamole.JPG
Share the knowledge

Pull up a chair and let me tell you a story from my early days as a professional programmer. It’s about how I screwed up, and what I’ve done since then to make sure that mistake is never repeated.

I’m going to ramble for a bit but I promise that I’ll get to the point eventually.

One of my first big tasks as a programmer was to update, in preparation for an upgrade, some iMan and Unigraphics code I inherited. For you younger kids out there, iMan was the predecessor of Teamcenter Engineering and Unigraphics later bought IDEAS and became NX.

The code was a mess. Of course, every programmer always thinks that code done by someone else is a mess. But this really was. There were single functions that would have taken two dozen sheets of paper to print out — double sided. My favorite was a family of functions that instead of returning values or modifying a parameter via a pointer updated fields in a global array. One function would update element 0, another would update element 1, etc. And then other functions would know which element to read. But that’s besides the point.

This code was prone to unrepeatable memory crashes. Memory errors are like that. One function would allocate memory, typically for a string or arrays, and then pass the pointers back to their callers. The callers would be responsible for freeing the memory — unless they passed the allocated pointers to their callers who would then have the responsibility, and so on.

If you’re familiar with this type of code you know that it is error prone. Freed memory is read, allocated memory is allocated again, etc. These types of bugs can be hard to track down. Sometimes there’s a problem in an execution path that’s rarely taken. Or sometimes the pointer will still point to valid data so long as the OS hasn’t seen fit to reuse that space already. Nine times out of ten the code will seem to work fine, and then on the tenth try the OS will actually use that address for something else and the program crashes.

I didn’t care much for this type of code, but it would have taken a massive overhaul to make any substantial change. Being new on the job and new to this code base I was reluctant to make too many changes to it. So we tested the code until we found a problem and then I’d hunt it down and try to fix it, and then we’d repeat the process.

Over and over and over and over. Think, whack-a-mole.

Eventually we couldn’t produce any more errors so we decided it was finally ready to release.

So we went ahead with the upgrade. And then… (cue dramatic music) …nothing much happened. The upgrade went about as well as upgrades ever do. There were some snafus here and there, but no show stoppers.

So a week later I left for my first PLM World users group conference.

And then all hell broke loose.

Hitting Bottom

On the first day of the conference we start getting calls from the home office. The drafting department is at a standstill. No drawings can be released. Programs are screaming about delays and imminent deadlines. Oh, and how’s the conference?
Not my best week to be sure.

The Recovery Process

When I got back to the office I knew I had to do something dramatic. I had tried the whack-a-mole approach for too long. I might have be able to fix the cause of the current complaints but I had no confidence that another bug wouldn’t be uncovered in another week. I couldn’t continue like that.

I resolved that I would eliminate all of the memory errors from the code once and for all. Doing so required the massive overhaul I had been afraid to undertake earlier. Now I was more afraid of releasing another buggy version of the code.

I set two goals for my code:

  1. The code had to work correctly.
  2. See goal number one.

Admitting I Have a Problem

Fixing this mess was a bit like starting a Twelve Step Progrom.
The first step was to admit I had a problem:

I am not smart enough to manage memory myself.

The first step was to be modest about my programming abilities. Given my recent failure, this wasn’t difficult.

Many times we programmers want to show how incredible our skills are. So we do wild and crazy things in our code that might eke out some extra bit of performance or optimize memory just a bit more or… or… something. More power to you if you can pull that off, but I’m not that good of a programmer.

From admitting I wasn’t very good at dealing with memory management came the obvious solution to my problem: I should not manage any memory.

Okay, fine, but short of hiring an assistant to write my code for me, how do I do that?

Turning to the Standard Template Library

After admitting you have a problem, the second big step in twelve-step programs is to turn to a higher power for assistance. For a C programmer who needs to manage memory correctly, that higher power is C++ and the Standard Template Library (STL).

Now the STL is vast, but there were really only two things I needed to use from it, the std::string class and the std::vector class template.

char*std::string

The first major area of my code where I was trying to allocate memory was string manipulation.

void work_with_c_string(const char* input_c_string)
{
	char *c_str = NULL;
	size_t len = strlen(input_c_string);
	c_str = (char *)malloc(len + 1);
	strcpy(c_str, input_c_string);
 
	// do whatever…
 
	free(c_str);
	return;
}

Now, simple examples look simple, but real code gets messy in a hurry, especially when the malloc() and free() are in different functions. The std::string class deals with all of that internally though. It will allocate enough memory to store its contents, and free that memory when the string finally goes out of scope.

void work_with_cpp_string(const &input_cpp_string)
{
	// memory allocated and copy made automatically
	string cpp_string(input_cpp_string); 
 
	// adding a suffix -- memory resized automatically
	cpp_string += ".foobar";
 
	// whatever…
 
	return; // memory for cpp_string automatically released
}

For the record, notice that I did more in three lines of C++ code than I had done in five lines of C code. That adds up.

Passing std::string to C Functions

But wait, the ITK libraries expect plain old char* strings as input, right? Fortunately for us, std::string has a member function, c_str() that returns a char* representation of the string.

	const string value("my new value");
	AOM_set_value_string(object_tag, "my_property", value.c_str() );

Accepting allocated char* from the API

We can’t entirely escape managing memory for C strings. The ITK API has many functions which return a char* which you are then expected to free. My approach to avoiding problems with those strings was bluntly simple.

  1. Initialize a new std::string from the char* string.
  2. Immediately free the char* string.
  3. Do all work with the copy.

Is this overkill sometimes? Probably, but I’ve found that by not trying to be clever and figure out when it was necessary to do and when it wasn’t I saved myself a lot of trouble later on.

	char* temp = NULL;
	AOM_ask_value_string(object_tag, "my_property", &temp);
 
	// copy char* to std::string
	const value( temp );
 
	// free char* string
	MEM_free( temp );
 
	// work with std::string…

dynamic arrays → std::vector<>

The second big area that accounted for most of my memory management needs was building and using dynamic arrays to store lists of items. Again, the STL has an alternative that will deal with the memory management for you, the std::vector<> class template.

Like string, vector will automatically allocate enough memory to store its contents, reallocate as new contents are added, and free its memory when it goes out of scope.

	vector<string> str_vec; // a vector of strings
	str_vec.push_back("first");
	str_vec.push_back("second");
	str_vec.push_back("third");

Passing vectors to C-functions taking arrays

Also, like string, vectors can be passed to C functions that expect regular arrays. The format may look a little odd at first. There isn’t a member function, like c_str(), to call. Instead you use the fact that the contents of a vector are guaranteed to be in contiguous memory, just as if they were in an array. The value of a standard array variable is the address of the memory block holding the array’s first element. So to pass a vector as an array you need to pass the memory address of the vector’s first element: &my_vector[0], where my_vector[0] gives you the first element, and then & gives you its address.

Typically functions that take arrays also need to know how long the array is and take that as separate parameter. You can pass that value by using the length() member function.

See the example below.

Accepting arrays from the API

As with strings, when the API returns an array that I am expected to free I immediately copy it into a vector, free the memory, and then work with the vector.

Example using vector

	int *int_array = NULL;
	int array_size = 0;
 
	AOM_ask_value_ints(my_object_tag, "my_property", 
                           &array_size, &int_array);
 
	// initialize vector with contents of array 
        // using the iterator constructor
	vector<int> int_vector(int_array, 
                               int_array // pointer arithmetic!
                               + sizeof(int_array) / sizeof(int) 
                              );
 
	// Free array
	MEM_free(int_array);
 
	// add a value to the vector
	int_vector.push_back(999);
 
	// pass to c-function API
	AOM_set_value_ints(another_object_tag, "my_property", 
                           int_vector.length(), &int_vector[0]
                          );

A Note on Performance

Earlier I said that I decided that above all other things my code had to work correctly.

The corollary to that was that I did not have the following goals:

  1. To write the fastest possible code.
  2. To write the most memory-efficient code.

The reasons I bring this up is because some people might complain that the STL isn’t as efficient as pure C. My response is, yeah. So what?

The typical sorts of things my ITK code does are to check some preconditions when creating an item or perform some task during a workflow task. During a typical day they might be executed a dozen times or less by most users. If the prefect implementation takes half a second to run and my implementation takes three, I may be 600% slower, but honestly, will the user notice much? No, they really won’t. But if my code blows up and kills their session, hoo-boy, I will definitely hear about it.

Back to My Story

I decided on change the code to use strings and vectors instead of char* and arrays. I’d change one function at a time, attempt to recompile, and see what other functions couldn’t compile. Then I’d track those functions down and change them, and so on. This went on for a week of late nights, with managers stopping by daily to check on my progress. Can’t we make a quick fix? Frankly, I largely blew them off. I was convinced that the only true solution was what the radical overhaul solution. If they had had anyone else they thought could have fixed the code I’d probably have been out of a job, or at least reassigned elsewhere. Thankfully, they didn’t.

After a week of this I finally had a new version of the code to test.

It was put into production.

The memory errors were gone.

It has been years now. I’ve found plenty of other things to get wrong in the code, but not memory errors. The memory errors are gone.

Coda

A tool designer I once worked with shared a quote with me once that has always stuck with me. I’ll paraphrase his paraphrasing:

It is one thing to create something that can’t obviously fail.
It is another to create something that obviously can’t fail.

– Anonymous

(If anyone can tell me the original quote and author I’d be very grateful. I have consulted the oracle at Google with no luck.)

Code that passes allocated memory around between functions and hands off responsibility for freeing the memory will, at best, be code that can’t obviously fail. It will never be code that obviously can’t fail.

Using the STL puts me closer to writing code that obviously can’t fail.

Resources

There are two books that I have found invaluable for learning to write better C++ code.

The first is Scott Meyers Effective C++, and the second was C++ Coding Standards by Sutter and Alexandrescu (disclosure: affiliate links). I highly recommend both books if you’re going to be doing any C++ programming. One small disclaimer, I actually have an older edition of the Meyer’s book.

  • Clarke

    Check out the Boost Graph library. It’s STL on steroids.

  • Teamcenter Heretic

    It is nice that the C++ stuff is finally available.

    So many times in the past I would have loved to use ANY C++ library but it always was “unsupported” by Siemens. I used the Rogue Wave stuff when STL was not yet robust.

    The books by Myers and Stroustrup still sit in my library.

    Also your comment about “…by not trying to be clever…” is sage advice to programmers out there. I cannot tell you how many times I’ve run across functions that used pointer arithmetic to walk thru some dynamically allocated array 😉

    • http://plmdojo.com/ Scott Pigman

      I found Stroustrup impenetrable back in the day. I should look at it again to see if it’s clearer now, although personally I find the O’Reilly C++ in a nutshell book an excellent general reference.

      Good catch calling me out on the pointer arithmetic 😀

      To confess, in my own actual code I have a fill_vec template function that iterates over the array and uses push_back() to populate the vector. If I had to implement it again I’d probably use the form I used above, but then I’d only have that one block of code to debug to make sure I got the offsets defined correctly. I lifted that example from the example code for the vector constructor.

  • http://www.facebook.com/yogesh.fegade.56 Yogesh Fegade

    I too, don’t agree with anybody who says that C++ STL library functions are slower than straight C functions. STL libraries are extremely optimized. Yes, because of some additional C++ overhead, it will be a bit slower. But the difference is hardly noticeable.

    One thing you MUST be careful about is – If you use C++ code which is fired from C function (user exit, user service, workflow handlers, pre/post conditions, methods, etc), you MUST NOT pass exception from your C++ code back to C function. C code is not at all forgiving if it receives an exception. In your C++ code, you MUST convert C++ exception into appropriate C error handling prior to returning. I am working on a post on my site about this. Should be available in few days.

    • http://plmdojo.com/ Scott Pigman

      Yes, you are 100% correct about passing exceptions to C-functions (not that you needed my validation or anything 😉 ). The two books I recommend both cover that topic. I look forward to reading your post.

  • http://plmdojo.com/ Scott Pigman

    So it causes high blood pressure, liver damage, acne, and testicular atrophy?

    • Teamcenter Heretic

      No, but is does help you to win 😉

  • Yogesh Fegade

    People often complain that C++ STL library performs poorly. From what I see, most common cause of poor performance, especially with C++ code is poor programming, poor design and poor understanding of C++. It is one thing to write C++ code as better C code but it is entirely different thing to write a well thought out C++ code.

    For example: I have seen this countless times, that a function would create a std::vector and pass it to another function as an argument by value or as a return by value from a function. Unless one really think it through, the performance impact in such case is not quite obvious. When a vector is passed by value as an argument or as a return value, a copy constructor is called. This involves – creating new vector, allocating memory for that new vector, copying old vector elements into new vector (which by the way may involve copy constructor of the element type), and potentially calling destructor on vector and its elements.

    • http://plmdojo.com/ Scott Pigman

      At risk of losing your professional respect, I have to tell you that I return objects from functions on occasion. Usually strings, but I couldn’t swear that I’ve never returned a vector. But I do it knowing that there is a (likely) a cost of of destruction and construction, but I’m usually trading that off against being able to use the function to initialize a const variable. I like to use const whenever I can because it helps ensure correct behavior. Whatever the cost is in terms of speed & memory, it’s not been so severe that it’s ever been an issue in the code the users interact with. Like I said in the post, it’s on the order of a few seconds a few times a day. Now code for batch type utilities that might have to interact with thousands of items is another matter and efficiency is more important — but these days I generally write that code in python, so that’s a whole ‘nother ball of wax.

      One thing that’s interesting — and why I used that “(likely)” up above. I looked up the topic of returning objects from functions in the Scott Meyers’ Effective C++, 2nd edition’s item 23: “Don’t return a reference when you must return an object”. After explaining why there’s no good way to return a reference instead of an object, he makes this comment,

      the bill that so terrifies you may never arrive. Like all programming languages, C++ allows the compiler implementers to apply certain optimizations to improve the performance of the generated code, and it turns out that in some cases… [the] return value can be safely eliminated. When compilers take advantage of that fact (and current compilers often do), our program continues to behave the way it’s supposed to, it just does it faster what you expected

      • http://www.facebook.com/yogesh.fegade.56 Yogesh Fegade

        You are absolutely right. There are legitimate reasons for returning an object by value or pass an object by value. Now a days compilers generate extremely optimized code. So some of the apparent obvious inefficiencies may never exist.

        The compiler optimization that you refereed is known as Return Value Optimization. However, that only applies to return values not to objects passed by value as function parameters.

        I must confess. I too was guilty of poor C++ programming in my early days:-)

        • http://plmdojo.com/ Scott Pigman

          ha, you’re funny :-)

          The bottom line is that you really need to do some profiling of your application to identify bottlenecks if you’re worried about performance.

          IIRC, in one of those two books there’s advice about avoiding “premature optimization” — beyond following general guidelines like pass-by-reference whenever appropriate, worry about correctness over what you think is the optimal solution. Most of the time we programmers are poor judges of where the real bottlenecks are in the code.

          • Teamcenter Heretic

            Remember, this is Teamcenter we are talking about.
            There are very FEW places where your code will affect run-time performance. C, C++ or Java really make little difference other than Java has memory issues.

            The API is what it is and IMHO most of the overhead is in the system, not the code.

            However, I’d live to hear some of the pain points and where optimization makes sense…

          • http://plmdojo.com/ Scott Pigman

            The types of things where I’ve seen big hits to performance are in traverse-the-whole-database types of operations where I’ve done something silly like execute an expensive operation for every item traversed where I could have just executed it once and saved the result or implemented a simple caching mechanism to store the most common results.

            Often it’s just the difference between putting the call outside of the for loop instead of inside. D’oh!

          • Teamcenter Heretic

            Yes. Simply thinking about what you are doing can make a real difference.

            Just remember that a PSE call is the MOST expensive thing you can do in Teamcenter IMNSHO.

  • Teamcenter Heretic

    Well, I finally took the plunge!

    It has been a big year for me, joined LinkedIn,… AND moved onto C++.

    Now, the latter is a big step for me as I have a SIGNIFICANT library of ITK code built up in C and was reluctant, after all if it ain’t broke… However, knowing that folks like Scott have had some positive experiences I decided to move forward. I also took into consideration how many memory issues I had run across at client sites so I decided to make my code more maintainable for programmers not quite so familiar with the ITK API.

    One of the main driving factors was a need for a really good pseudo-number generator and I found one in the Mersenne Twister available in Boost and this is a C++ lib, so off I went!

    You can read about this here: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html

    And the boost libs can be found at: http://www.boost.org

    Here is a sample of how easy it is with CPP:

    boost::mt11213b::result_type seed = (boost::mt11213b::result_type)time(0)+(boost::mt11213b::result_type)clock(); // get a seed
    boost::mt11213b prng(seed); // initialize the generator
    boost::random::uniform_int_distribution dist(10000,99999); // set a range of numbers
    unsigned int skip = 1000; // purge off the first 1000 or so
    while( skip–)
    {
    dist( prng );
    }
    std::cout << dist( prng ) << std::endl; // call the generator for the next number

Optimization WordPress Plugins & Solutions by W3 EDGE