Friday, November 24, 2006
Improving performances in C++ code
What makes the situation peculiar is that there is no Pareto law at work: the overhead seems largely distributed among hundred (if not thousands) of places. There seems to be no way to get a high return through a small investment. Although most of what we've done so far is rather context-dependent, a few general concepts can always be applied. Here is a distilled list of problems we've tackled, and solutions we've applied:
- inefficient algorithms. This is often considered problem #1 but, in this specific case, it accounted for just a fraction. For instance, std::element was used to find the max element in a std::map, where std::map::rbegin would give you an iterator to the last (and therefore max) element in the map. Even worse, sometimes an element had to be removed from the map, by searching for the value and not for the key. That means linear-time lookup. We changed the algorithm so that the removal wasn't needed anymore.
- temporary objects. A lot of temporary objects where created. Some of those objects did dynamic allocations, and then parts of them were cloned into long-lived objects. There are several techniques to avoid or minimize the creation of temporary objects, and I borrowed some ideas from the "dual classes" approach (Robert M. Adams, Temporary Object Management through Dual Classes, C/C++ Users Journal, April 2003) to eliminate all those clones (which in turn removed several new/delete pairs).
- temporary containers. Sounds similar to the above, but is more complex. The new code relied (as usual) upon existing code. The existing code provided some functions to obtain certain sets of data, hiding a complex internal navigation among different data structures. So far, so good.
The existing code returned those set of data inside containers, which seems pretty logical. However, looking at the profiling data, in our case 3,600,000 temporary containers were created. For each one, we did some processing of the contained data, then discarded the container.
It's interesting to observe that some people in the company hold the opinion that OOP is not efficient: in this case, they would say, the abstraction layer provided by those functions, returning simple containers and hiding the intricacies of the internal structures, has to be paid with inefficiency. A simple solution would be to dismiss abstraction and encapsulation, access the intricate structures directly, and enjoy better performances.
Of course, that's very simplistic. We can have encapsulation and efficiency, we just have to think differently.
A simple approach is to change the function returning the data set into a function returning nothing, but taking one more parameter: a functor to be called for each element. The functor should also be able to inform the function itself that no further iteration is needed. In this way, no temporary container is created. A different approach (more complex) would be to turn the function into a custom iterator. This is what Koenig suggested in a little-known article I've often suggested, as it contains an interesting design insight ("Turning an interface inside out", Journal of Object Oriented Programming, May 1997). In both cases, the gain is huge, encapsulation is even improved (we're not even bound to a concrete container class anymore) and efficiency increases. It's also possible to build the previous interface (returning a container) over the new one, just by passing a back-inserter as the functor, so you don't even lose backward compatibility.
- decoupling overhead. This is by far the most difficult aspect to deal with. Decoupling is a good design principle. However, design is always contextual. Blindly following non-contextual design principles is a recipe for failure.
The company suffered a lot because of strongly coupled code in the past, and a wave of "decoupling at any cost" thinking emerged from that pain. However, in this case there is a big layer of dynamically allocated, interface-based, virtual-inheritance laden, smart-pointers managed code where stack-allocated concrete classes would have been just enough (ok, maybe a regular C++ interface here and there could have been useful as well, but just in the right places). There is also a lot of call forwarding going on inside that layer.
This won't be easy to change, and probably we won't change most of it (which is rather unfortunate). Simple lesson: design is a careful balance of several factors. Pushing too much on one side won't give you balance. Following rigid guidelines, outside the problem context, makes a lot of critical thinking disappear, which may be good for your cognitive load :-) but not for the ultimate result (this is also true when you're constrained by overly restrictive frameworks and languages, but that was not the case).
- caching result: that's pretty easy. Because of the way the algorithms work, the same function was called in many cases with the same exact parameters. I didn't need to build a sophisticated cache: just keep the previous parameters and result, do a simple check, and return the cached value when possible. I had some doubts about the simplicity of this caching mechanism, which can be easily invalidated, but trying that on real cases we saw a 99.8% cache hits, which is just excellent :-) and doesn't need any further improvements (actually, trying to improve on that with more sophisticated caching would probably make the overall performance worse).
- overall, profiling was invaluable. However, looking at times wasn't really that useful, as the overhead was really distributed among thousands of functions. What I've found really useful is the visit count for each function. Looking at those numbers, we can understand (or guess :-) if we have non-linear computational complexity, and where. We can also see how many temporary objects we have, for each class, by just looking at counts for constructors and destructors. In practice, the profiling tool we used was good enough to be used on a large project, but not so handy when exploring result. However, the tool saved the results in XML (although they didn't say so :-), therefore I wrote a small program to do some useful processing of that XML, export the results to Access, and built some handy queries, so that I could see at a glance (for instance) the cumulative cost of all the member functions of a given class, divided by parent function in a pivot table, and so on. That made some decision-making a whole lot easier.
Wednesday, November 22, 2006
JOOP & C++ Report Articles
Speaking of C++, I've been helping one of my clients optimizing some code recently, and although most of what we have done is really context-dependent, I probably have a few interesting ideas to share. Especially because this is not one of the lucky cases (80% of the time spent in 20% of the code). It's more like a "distributed overhead", which is harder to tackle. More on this stuff later on, I hope.
Saturday, November 18, 2006
Quote of the day [again...]
Somewhat inspired by an answer I gave to comments on my previous post, here it comes: People willing to trade their freedom for temporary security deserve neither and will lose both. (Benjamin Franklin)
Tuesday, November 14, 2006
Slip Charts
Software development is a learning process, yet we are often asked for early estimates. In several cases, those estimates turn out to be wrong, because we didn't have enough information. In pathological companies, estimates are considered promises. In more enlightened (should I say realistic :-) companies, estimates are periodically reframed.
It's very common for early estimates to be overoptimistic, so when we review an estimate it's usually to add more effort. Unless we can shrink requirements, or unless we can find a smarter way to satisfy requirements (which is usually what I try to do), we have to postpone delivery.
When the project has high complexity and high uncertainty, it's not uncommon to slip several times, as more and more knowledge is gained. Of course, at some point we have to understand if we are going somewhere, or if we simply don't know how much it's gonna take. A useful, cheap, and simple way to get a better understanding of slippage is to draw a slip chart. You simply add one point every time you review your estimate. On the x axis, you have the current date; on the y, you have the expected delivery date.
Here is a real slip chart (from a real project)
as you can see, after less than one month, the estimate was increased by about one month. Then it remained fixed up, to delivery. After a few reviews, the confidence in making the deadline increases.
Here is another real slip chart (same product as above, but different project):
now, that's a troubled project. The team is learning a lot along the road, but not enough to give better estimates. As you can guess, it wasn't really finished when it was declared finished.
Although learning to read a slip chart (and its counterpart, the slip/lead chart) is easy, if you want to squeeze every ounce of information from the chart, I suggest that you read an excellent book from Gerald Weinberg, "Quality Software Management Vol. 2". Well, if you're any serious about software project management, you probably want to read all the 4 volumes anyway :-).
Note: looking at the slip chart can give you precious information, but information without action is useless. Now, action is always context-dependent. For the real project above, my suggested action would have been (I've seen the slip charts too late) at least to exclude the project from the next delivered version of the product, and possibly to schedule a design review to understand what was really going on. Of course, removing a single project from the next version of a requires some configuration management discipline (which was in place), and in this case it certainly mandates that the development had to be done outside the baseline (so, sorry, no continuous integration).
But then, when you have high technical uncertainty, continuous integration is not necessarily a good practice (quite the opposite, I would say). Continuous integration is good when you have high uncertainty on functional requirements, because you can (ideally) get early feedback from users. It's also good for low-uncertainty projects, because in this way you don't add additional uncertainty (from late integration). But it's not a silver bullet, and should not be applied blindly "by the book".
It's very common for early estimates to be overoptimistic, so when we review an estimate it's usually to add more effort. Unless we can shrink requirements, or unless we can find a smarter way to satisfy requirements (which is usually what I try to do), we have to postpone delivery.
When the project has high complexity and high uncertainty, it's not uncommon to slip several times, as more and more knowledge is gained. Of course, at some point we have to understand if we are going somewhere, or if we simply don't know how much it's gonna take. A useful, cheap, and simple way to get a better understanding of slippage is to draw a slip chart. You simply add one point every time you review your estimate. On the x axis, you have the current date; on the y, you have the expected delivery date.
Here is a real slip chart (from a real project)
as you can see, after less than one month, the estimate was increased by about one month. Then it remained fixed up, to delivery. After a few reviews, the confidence in making the deadline increases.
Here is another real slip chart (same product as above, but different project):
now, that's a troubled project. The team is learning a lot along the road, but not enough to give better estimates. As you can guess, it wasn't really finished when it was declared finished.
Although learning to read a slip chart (and its counterpart, the slip/lead chart) is easy, if you want to squeeze every ounce of information from the chart, I suggest that you read an excellent book from Gerald Weinberg, "Quality Software Management Vol. 2". Well, if you're any serious about software project management, you probably want to read all the 4 volumes anyway :-).
Note: looking at the slip chart can give you precious information, but information without action is useless. Now, action is always context-dependent. For the real project above, my suggested action would have been (I've seen the slip charts too late) at least to exclude the project from the next delivered version of the product, and possibly to schedule a design review to understand what was really going on. Of course, removing a single project from the next version of a requires some configuration management discipline (which was in place), and in this case it certainly mandates that the development had to be done outside the baseline (so, sorry, no continuous integration).
But then, when you have high technical uncertainty, continuous integration is not necessarily a good practice (quite the opposite, I would say). Continuous integration is good when you have high uncertainty on functional requirements, because you can (ideally) get early feedback from users. It's also good for low-uncertainty projects, because in this way you don't add additional uncertainty (from late integration). But it's not a silver bullet, and should not be applied blindly "by the book".
Sunday, November 05, 2006
Quote of the day [after]
I'm gonna need Albert on my side tomorrow :-)). So much that I'm gonna drop another quote from the great man here:
"Imagination is more important than knowledge. For knowledge is limited , wheras imagination embraces the entire world, stimulating progress, giving birth to evolution".
Saturday, November 04, 2006
Quote of the Day
Wednesday, November 01, 2006
Inclusive and Exclusive Communities
It is not rare for people inside a community to act as a tribe. Also, it is not rare for people inside a community to selectively choose what to read, whom to listen to, and so on, applying a reinforcing filtering to the information they're exposed to. In the end, that tends to generate a lot of self-fulfilling expectations. As I've recently discovered, people who are deeply inside self-fulfilling expectations won't obviously accept the fact that they're experiencing self-fulfilling expectations :-). They just believe to be right.
Some of those communities never felt really attractive to me. It was hard to explain, I just felt I didn't like them much. Overall, I tended to say that I'm always staying away from fanatics, but that was an oversimplification. We have fanatics everywhere. Inside every community we can find a small group of radicals (and in most cases, they're not the best minds in the community :-).
More recently, I started to look at this issue from a different point of view. Some communities are exclusive, some are inclusive (for a little background on exclusive and inclusive communities, from a socio-economical perspective, you can take a look at a short presentation from the Department of Human Ecology at the University of Alberta: Community Development and Sustainability - Inclusive and Exclusive Communities).
Exclusive communities spend a great deal of effort bashing other communities. They build barriers, so that people can only be totally in or totally out. They don't want you to freely move from one camp to another. They brainwash their members.
This is a deep cultural issue; it's much more pervasive than the mere existence of a few radicals.
I tend to stay away from exclusive communities. What they usually have to offer is a very narrow view of a complex field. I won't exclude their findings and results - actually I'm always happy to borrow good ideas from every source. But I'll never get trapped into their myopic view of software development (or life :-).
Enough rambling for today :-). On a more personal note, we had a nice sunny morning here, so I took off for a short run (about 10Km). It was so great :-).
