Saturday, September 13, 2008
Lost
I’ve been facing some small, tough design problems lately: relatively simple cases where finding a good solution is surprisingly hard. As usual, it’s trivial to come up with something that “works”; it’s also quite simple to come up with a reasonably good solution. It’s hard to come up with a great solution, where all forces are properly balanced and something beautiful takes shape.
I like to think visually, and since standard notations weren’t particularly helpful, I tried to represent the problem using a richer, non-standard notation, somehow resembling Christopher Alexander’s sketches. I wish I could say it made a huge difference, but it didn’t. Still, it was quite helpful in highlighting some forces in the problem domain, like an unbalanced multiplicity between three main concepts, and a precious-yet-fragile information hiding barrier. The same forces are not so visible in (e.g.) a standard UML class diagram.
Alexander, even in his early works, strongly emphasized the role of sketches while documenting a pattern. Sketches should convey the problem, the process to generate or build a solution, and the solution itself. Software patterns are usually represented using a class diagram and/or a sequence diagram, which can’t really convey all that information at once.
Of course, I’m not the first to spend some time pondering on the issue of [generative] diagrams. Most notably, in the late ‘90s Jim Coplien wrote four visionary articles dealing with sketches, the geometrical properties of code, alternative notations for object diagrams, and some (truly) imponderable questions. Those papers appeared on the long-dead C++ Report, but they are now available online:
Space-The final frontier (March 1998)
Worth a thousand words (May 1998)
To Iterate is Human, To Recurse, Divine (July/August 1998)
The Geometry of C++ Objects (October 1998)
Now, good ol’ Cope has always been one of my favorite authors. I’ve learnt a lot from him, and I’m still reading most of his works. Yet, ten years ago, when I read that stuff, I couldn’t help thinking that he lost it. He was on a very difficult quest, trying to define what software is really about, what beauty in software is really about, trying to adapt theories firmly grounded in physical space to something that is not even physical. Zen and the Art of Motorcycle Maintenance all around, some madness included :-).
I re-read those papers recently. That weird feeling is still here. Lights and shadows, nice concepts and half-baked ideas, lot of code-centric reasoning, overall confusion, not a single strong point. Yeah, I still think he lost it, somehow :-), and as far as I know, the quest ended there.
Still, his questions, some of his intuitions, and even some of his most outrageous :-) ideas were too good to go wasted.
The idea of center, that he got from The Nature of Order (Alexander’s latest work) is particularly interesting. Here is a quote from Alexander:
Centers are those particular identified sets, or systems, which appear within the larger whole as distinct and noticeable parts. They appear because they have noticeable distinctness, which makes them separate out from their surroundings and makes them cohere, and it is from the arrangements of these coherent parts that other coherent parts appear.
Can we translate this concept into the software domain? Or, as Jim said, What kind of x is there that makes it true to say that every successful program is an x of x's?. I’ll let you read what Jim had to say about it. And then (am I losing it too? :-) I’ll tell you what I think that x is.
Note: guys, I know some of you already think I lost it :-), and would rather read something about (e.g.) using variadic templates in C++ (which are quite cool, actually :-) to implement SCOOP-like concurrency in a snap. Bear with me. There is more to software design than programming languages and new technologies. Sometimes, we gotta stretch our mind a little.
Anyway, once I get past the x of x thing, I’d like to talk about one of those wicked design problems. A bit simplified, down to the essential. After all, as Alexander says in the preface of “Notes on the Synthesis of Form”: I think it’s absurd to separate the study of designing from the practice of design. Practice, practice, practice. Reminds me of another book I read recently, an unconventional translation of the Analects of Confucius. But I’ll save that for another time :-).
I like to think visually, and since standard notations weren’t particularly helpful, I tried to represent the problem using a richer, non-standard notation, somehow resembling Christopher Alexander’s sketches. I wish I could say it made a huge difference, but it didn’t. Still, it was quite helpful in highlighting some forces in the problem domain, like an unbalanced multiplicity between three main concepts, and a precious-yet-fragile information hiding barrier. The same forces are not so visible in (e.g.) a standard UML class diagram.
Alexander, even in his early works, strongly emphasized the role of sketches while documenting a pattern. Sketches should convey the problem, the process to generate or build a solution, and the solution itself. Software patterns are usually represented using a class diagram and/or a sequence diagram, which can’t really convey all that information at once.
Of course, I’m not the first to spend some time pondering on the issue of [generative] diagrams. Most notably, in the late ‘90s Jim Coplien wrote four visionary articles dealing with sketches, the geometrical properties of code, alternative notations for object diagrams, and some (truly) imponderable questions. Those papers appeared on the long-dead C++ Report, but they are now available online:
Space-The final frontier (March 1998)
Worth a thousand words (May 1998)
To Iterate is Human, To Recurse, Divine (July/August 1998)
The Geometry of C++ Objects (October 1998)
Now, good ol’ Cope has always been one of my favorite authors. I’ve learnt a lot from him, and I’m still reading most of his works. Yet, ten years ago, when I read that stuff, I couldn’t help thinking that he lost it. He was on a very difficult quest, trying to define what software is really about, what beauty in software is really about, trying to adapt theories firmly grounded in physical space to something that is not even physical. Zen and the Art of Motorcycle Maintenance all around, some madness included :-).
I re-read those papers recently. That weird feeling is still here. Lights and shadows, nice concepts and half-baked ideas, lot of code-centric reasoning, overall confusion, not a single strong point. Yeah, I still think he lost it, somehow :-), and as far as I know, the quest ended there.
Still, his questions, some of his intuitions, and even some of his most outrageous :-) ideas were too good to go wasted.
The idea of center, that he got from The Nature of Order (Alexander’s latest work) is particularly interesting. Here is a quote from Alexander:
Centers are those particular identified sets, or systems, which appear within the larger whole as distinct and noticeable parts. They appear because they have noticeable distinctness, which makes them separate out from their surroundings and makes them cohere, and it is from the arrangements of these coherent parts that other coherent parts appear.
Can we translate this concept into the software domain? Or, as Jim said, What kind of x is there that makes it true to say that every successful program is an x of x's?. I’ll let you read what Jim had to say about it. And then (am I losing it too? :-) I’ll tell you what I think that x is.
Note: guys, I know some of you already think I lost it :-), and would rather read something about (e.g.) using variadic templates in C++ (which are quite cool, actually :-) to implement SCOOP-like concurrency in a snap. Bear with me. There is more to software design than programming languages and new technologies. Sometimes, we gotta stretch our mind a little.
Anyway, once I get past the x of x thing, I’d like to talk about one of those wicked design problems. A bit simplified, down to the essential. After all, as Alexander says in the preface of “Notes on the Synthesis of Form”: I think it’s absurd to separate the study of designing from the practice of design. Practice, practice, practice. Reminds me of another book I read recently, an unconventional translation of the Analects of Confucius. But I’ll save that for another time :-).
Labels: book reference, design, form, pattern
Thursday, August 07, 2008
Do we need a Theory of Wrapping?
I think it was about 10 years ago. I was teaching OOD principles to a .COM company, and a senior developer said we should really develop a theory of wrapping. We talked a little about it, but then we moved to explore other concepts. I guess I totally forgot the idea till a few weeks ago, when 3 different customers came up with thorny issues, and they all had something in common: some kind of wrapper.
Wrappers are routinely created during software development, yet not all forms of wrapping are benign. Some may look convenient in the short term, but will come back to haunt us in the long term.
Would a theory of wrapping help? Indeed, we already have some organized knowledge on wrapping: several patterns are built upon the idea of wrapping an object or a subsystem. Looking at the GoF patterns alone, Adapter is a wrapper, Facade is a wrapper, Proxy is a wrapper. Decorator, although somehow similar to proxy in implementation, isnt't really a wrapper, as it adds new responsibilities.
Looking at wrapping through patterns, however, doesn't provide much guidance about the long-term consequences of wrappers. So, let's move to anedoctal knowledge for a while.
My first troubled customer is trying to solve an architectural problem by wrapping a few functions, and perform some magic inside those functions. The magic involves threads, fibers, apartments, and stuff like that. As any true form of magic, it must not be revealed to the general public :-)), so I won't.
Magic isn't well-known for reliability, but there is chance that magic might indeed work, which in a sense is even worse. We know the real problem is elsewhere: it has been known for more than 10 years, but the troubled area has never been fixed, just hidden under several layers. The real fix would entail changing 100 to 150 classes. Personally, I would work toward making that change as painless as possible, and then do it. They would rather go the wrapping way.
My second, less troubled customer has a much simpler problem: a legacy database, which in turn is mostly a mirror of the in-memory data structures of a legacy application (still maintained and developed). We need to provide a web front end, and the general agreement is to outsource that development. We basically have three choices:
1) ask the contractor to write the web app against the existing, ugly db. That requires some documentation effort on the company side, as the db can't be used without a detailed knowledge about fields (and bit-fields inside fields).
2) clean the database (in-house), clean the legacy app (in-house), let the contractor write the web app against the clean db. Sounds nice, but requires a lof of in-house work, and even worse, it would delay the contractor. Cleaning the legacy app seems daunting, and sooner or later we want to scrap that code anyway.
3) keep the ugly db, but provide a wrapper, in the form of a facade object model. Ask the contractor to write the web app against the facade. Delay cleaning the db for a while (possibly forever) and hope that a quickly developed facade will withstand the test (or ravages) of time. Because yeah, well, we ain't got much time, or we would go with (2). By the way, we could write the facade in-house, or write the same kind of documents as in (1) and ask the contractor to write the facade.
I would love to recommend (2), but being reality-based, I recommended (3), with the facade written by the contractor. So (dare I say it!!) I actually recommended that we spend our valuable in-house time writing documentation. How non-agile is that :-)). But the thing is, there is only one guy who knows the db, and that's bad risk management. Also, if at some point we want to redesign and clean the db, a documentation of what is currently hidden inside bit-fields stored as integers would be quite valuable. Oh, by the way: we did a little experiment to estimate how long is gonna take to write that doc: about 10 man/days, easily broken in short tasks, which can partially overlap the calendar time consumed by the contractor to build the facade object model. Not so bad after all, except we still keep a crappy db and application.
My third customer doesn't really feel troubled :-). Well, in fact, he's not really troubled: I am troubled :-). Years ago, a small team ventured into building an application-specific framework. Although I often preached about creating a set of small, loosely coupled mini-frameworks, people on that team weren't so interested in listening. So they went on and created a large, tightly coupled framework (which is much easier to build, and much harder to learn, change, etc).
When the company decided to build the first (web) application based on that framework, the application developers found out (guess what :-) that the ambitious design of the large framework was quite hard to understand, to the point that their main goal was surprisingly hard to reach. I proposed that the framework developers could create a simple facade, closer to our problem and therefore easier to use. They did, the application was completed, and is still in use today. So far so good :-).
A few years went by, and more applications have been written against that framework. The original framework developers moved to application development (or leaved the company), actually leading application development. Recently, I discovered that all the subsequent applications have been written against "my" facade, which was never designed to be general-purpose. However, it was so much simpler to use than the framework that people opted to use it anyway. They tweaked the facade when necessary, so we now have multiple versions of the facade around.
Again, the "right" thing to do would have been to make the framework easy to use on the first place. The facade was my backup plan because I never managed to make a dent in the framework developers' minds. Sure, it was instrumental in writing the applications, but somehow, it backfired: it became a superstructure of its own, living well beyond my expectations. Unfortunately, it was never designed to be a general-purpose component.
Of course, not every form of wrapping is evil. For instance, I often add a small facade between my code and any third party components and libraries. That shields me from many instabilities in interfaces, and in many cases allows me to change supplier if needed. That's harder with GUI components making heavy use of design-time properties, but there are techniques to deal with that as well (if warranted). Again, some wisdom is required: it makes little sense to wrap a pervasive library or framework; it makes little sense to invest in wrapping when you're developing a short-lived corporate application, and so on. Still, as someone said (exact quote needed :-), every programming problem can be solved by adding one level of indirection, and in some cases a wrapper provides a useful level of indirection.
Can we learn a general lesson from experience? From the pattern perspective, my first customer is just trying to add some kind of proxy between subsystems. The second and third are using a plain old facade. Nothing wrong with that. Yet no one is making the "right" choice: the wrapper is used to avoid fixing the real problem. We often say words like "postpone", but in software development, "postpone" usually means "don't do it".
So, again, would a theory of wrapping help? And what should this theory tell us? As is often the case, a good theory of software design should help us to make informed decisions, and like it or not, that means informed economical decisions. All too often, sound engineering choices are discarded in favor of cheap solutions, because we have no real economic model, or even a rough economic model, to calculate the (possibly negative :-) ROI of what we propose.
The real, long-term economical consequences for my first customer are way too complex, and I have little hope that we could ever develop a theory that could even come close to help with that. However, I believe the bigger long-term cost factor of the proxy-based solution would be in the increased debugging effort that would fall on the shoulders of all the other programmers working on the same project (about 100 people, I guess). This problem, somehow, could be highlighted in a theory of wrapping. A proxy, especially when doing threads-fibers-apartments magic, makes it hard to get a clear picture of what's going on just by looking at the stack (which is a per-thread, per-fiber structure). Unfortunately, the impact of this problem seems very hard to quantify.
My second customer is facing a much simpler scenario. I think we could eventually build an economic theory that could model the maintenance cost of keeping the legacy code as-is, the risk of building a leaky abstraction as we quickly build a facade over the legacy db, thereby increasing the mass of code that we'll have to change later, as we finally get to create a better database, and compare that with the savings of not doing it. We should also be able to factor in the increased maintenance cost of keeping the facade in-synch with any changes to the db required by the evolving application. It's not rocket science. Or maybe it is, but we can actually send a rocket to Mars :-). A good economic theory should recommend, in this specific context, to go with (3). Why? Because that's what I did :-)).
The third problem, I think, is more of a process problem. There was nothing wrong in the original wrapper. However, it wasn't designed for reuse, and is should not have been reused as-is, or by tweaking. This is a direct consequence of a lack of control over design choices; the team is, well, wrapped :-)) on itself. Unfortunately, lack of control over design issues is exactly what the team wants. A good process is meant to keep that kind of disfunctional behaviour out. Note that it doesn't have to be an heavyweight process. Just a good process :-).
Unfortunately, I don't have Theory of Wrapping to offer. At least, not yet :-). So, for the time being, I'll keep dealing with wrapping using informal reasoning, mostly based on experience and intuition. Got some good idea? Leave me a comment here!
Wrappers are routinely created during software development, yet not all forms of wrapping are benign. Some may look convenient in the short term, but will come back to haunt us in the long term.
Would a theory of wrapping help? Indeed, we already have some organized knowledge on wrapping: several patterns are built upon the idea of wrapping an object or a subsystem. Looking at the GoF patterns alone, Adapter is a wrapper, Facade is a wrapper, Proxy is a wrapper. Decorator, although somehow similar to proxy in implementation, isnt't really a wrapper, as it adds new responsibilities.
Looking at wrapping through patterns, however, doesn't provide much guidance about the long-term consequences of wrappers. So, let's move to anedoctal knowledge for a while.
My first troubled customer is trying to solve an architectural problem by wrapping a few functions, and perform some magic inside those functions. The magic involves threads, fibers, apartments, and stuff like that. As any true form of magic, it must not be revealed to the general public :-)), so I won't.
Magic isn't well-known for reliability, but there is chance that magic might indeed work, which in a sense is even worse. We know the real problem is elsewhere: it has been known for more than 10 years, but the troubled area has never been fixed, just hidden under several layers. The real fix would entail changing 100 to 150 classes. Personally, I would work toward making that change as painless as possible, and then do it. They would rather go the wrapping way.
My second, less troubled customer has a much simpler problem: a legacy database, which in turn is mostly a mirror of the in-memory data structures of a legacy application (still maintained and developed). We need to provide a web front end, and the general agreement is to outsource that development. We basically have three choices:
1) ask the contractor to write the web app against the existing, ugly db. That requires some documentation effort on the company side, as the db can't be used without a detailed knowledge about fields (and bit-fields inside fields).
2) clean the database (in-house), clean the legacy app (in-house), let the contractor write the web app against the clean db. Sounds nice, but requires a lof of in-house work, and even worse, it would delay the contractor. Cleaning the legacy app seems daunting, and sooner or later we want to scrap that code anyway.
3) keep the ugly db, but provide a wrapper, in the form of a facade object model. Ask the contractor to write the web app against the facade. Delay cleaning the db for a while (possibly forever) and hope that a quickly developed facade will withstand the test (or ravages) of time. Because yeah, well, we ain't got much time, or we would go with (2). By the way, we could write the facade in-house, or write the same kind of documents as in (1) and ask the contractor to write the facade.
I would love to recommend (2), but being reality-based, I recommended (3), with the facade written by the contractor. So (dare I say it!!) I actually recommended that we spend our valuable in-house time writing documentation. How non-agile is that :-)). But the thing is, there is only one guy who knows the db, and that's bad risk management. Also, if at some point we want to redesign and clean the db, a documentation of what is currently hidden inside bit-fields stored as integers would be quite valuable. Oh, by the way: we did a little experiment to estimate how long is gonna take to write that doc: about 10 man/days, easily broken in short tasks, which can partially overlap the calendar time consumed by the contractor to build the facade object model. Not so bad after all, except we still keep a crappy db and application.
My third customer doesn't really feel troubled :-). Well, in fact, he's not really troubled: I am troubled :-). Years ago, a small team ventured into building an application-specific framework. Although I often preached about creating a set of small, loosely coupled mini-frameworks, people on that team weren't so interested in listening. So they went on and created a large, tightly coupled framework (which is much easier to build, and much harder to learn, change, etc).
When the company decided to build the first (web) application based on that framework, the application developers found out (guess what :-) that the ambitious design of the large framework was quite hard to understand, to the point that their main goal was surprisingly hard to reach. I proposed that the framework developers could create a simple facade, closer to our problem and therefore easier to use. They did, the application was completed, and is still in use today. So far so good :-).
A few years went by, and more applications have been written against that framework. The original framework developers moved to application development (or leaved the company), actually leading application development. Recently, I discovered that all the subsequent applications have been written against "my" facade, which was never designed to be general-purpose. However, it was so much simpler to use than the framework that people opted to use it anyway. They tweaked the facade when necessary, so we now have multiple versions of the facade around.
Again, the "right" thing to do would have been to make the framework easy to use on the first place. The facade was my backup plan because I never managed to make a dent in the framework developers' minds. Sure, it was instrumental in writing the applications, but somehow, it backfired: it became a superstructure of its own, living well beyond my expectations. Unfortunately, it was never designed to be a general-purpose component.
Of course, not every form of wrapping is evil. For instance, I often add a small facade between my code and any third party components and libraries. That shields me from many instabilities in interfaces, and in many cases allows me to change supplier if needed. That's harder with GUI components making heavy use of design-time properties, but there are techniques to deal with that as well (if warranted). Again, some wisdom is required: it makes little sense to wrap a pervasive library or framework; it makes little sense to invest in wrapping when you're developing a short-lived corporate application, and so on. Still, as someone said (exact quote needed :-), every programming problem can be solved by adding one level of indirection, and in some cases a wrapper provides a useful level of indirection.
Can we learn a general lesson from experience? From the pattern perspective, my first customer is just trying to add some kind of proxy between subsystems. The second and third are using a plain old facade. Nothing wrong with that. Yet no one is making the "right" choice: the wrapper is used to avoid fixing the real problem. We often say words like "postpone", but in software development, "postpone" usually means "don't do it".
So, again, would a theory of wrapping help? And what should this theory tell us? As is often the case, a good theory of software design should help us to make informed decisions, and like it or not, that means informed economical decisions. All too often, sound engineering choices are discarded in favor of cheap solutions, because we have no real economic model, or even a rough economic model, to calculate the (possibly negative :-) ROI of what we propose.
The real, long-term economical consequences for my first customer are way too complex, and I have little hope that we could ever develop a theory that could even come close to help with that. However, I believe the bigger long-term cost factor of the proxy-based solution would be in the increased debugging effort that would fall on the shoulders of all the other programmers working on the same project (about 100 people, I guess). This problem, somehow, could be highlighted in a theory of wrapping. A proxy, especially when doing threads-fibers-apartments magic, makes it hard to get a clear picture of what's going on just by looking at the stack (which is a per-thread, per-fiber structure). Unfortunately, the impact of this problem seems very hard to quantify.
My second customer is facing a much simpler scenario. I think we could eventually build an economic theory that could model the maintenance cost of keeping the legacy code as-is, the risk of building a leaky abstraction as we quickly build a facade over the legacy db, thereby increasing the mass of code that we'll have to change later, as we finally get to create a better database, and compare that with the savings of not doing it. We should also be able to factor in the increased maintenance cost of keeping the facade in-synch with any changes to the db required by the evolving application. It's not rocket science. Or maybe it is, but we can actually send a rocket to Mars :-). A good economic theory should recommend, in this specific context, to go with (3). Why? Because that's what I did :-)).
The third problem, I think, is more of a process problem. There was nothing wrong in the original wrapper. However, it wasn't designed for reuse, and is should not have been reused as-is, or by tweaking. This is a direct consequence of a lack of control over design choices; the team is, well, wrapped :-)) on itself. Unfortunately, lack of control over design issues is exactly what the team wants. A good process is meant to keep that kind of disfunctional behaviour out. Note that it doesn't have to be an heavyweight process. Just a good process :-).
Unfortunately, I don't have Theory of Wrapping to offer. At least, not yet :-). So, for the time being, I'll keep dealing with wrapping using informal reasoning, mostly based on experience and intuition. Got some good idea? Leave me a comment here!
Labels: design, pattern, process, profession
Tuesday, December 18, 2007
Problem Frames
I found the concept interesting, and a few years later I decided to dig deeper by reading another book from Jackson (Problem Frames: Analyzing and structuring software development problems). Quite interesting, although definitely not a light reading. I cannot say it changed my life or heavily influenced the way I work while I analyze requirements, but it added a few interesting concepts to my bag of tricks.
Lately, I've found an interesting paper by Rebecca Wirfs-Brock, Paul Taylor and James Noble: Problem Frame Patterns: An Exploration of Patterns in the Problem Space. I encourage you to read the paper, even if you're not familiar with the concept of problem frame: in fact, it's probably the best introduction on the subject you can get anywhere.
In the final section (Assessment and Conclusions) the authors compare Problem Frames and Patterns. I'll quote a few lines here:
A problem frame is a template that arranges and describes
phenomena in the problem space, whereas a pattern maps forces to a solution in the solution space.
Patterns are about designing things. The fact that we put problem frames into pattern form demonstrates
that when people write specifications, they are designing too—they are designing the overall system, not its
internal structure. And while problem frames are firmly rooted in the problem space, to us they also suggest
solutions.
If you read that in light of what I've discussed in my latest post on Form, you may recognize that Problem Frames are about structuring and discovering context, while Design Patterns helps us structure a fitting form.
When Problem Frames suggests solutions, there is a good chance that they're helping us in the elusive game of (to quote Alexander again) bringing harmony between two intangibles: a form which we have not yet designed, and a context which we cannot properly describe.
Back to the concept of Problem Frames, I certainly hope that restating them in a pattern form will foster their adoption. Indeed, the paper above describes what is probably the closest thing to true Analysis Patterns, and may help analysts look more closely at the problem before jumping into use cases and describe the external behaviour of the system.
Labels: analysis, article reference, book reference, form, pattern, requirements
Tuesday, June 26, 2007
Got Multicore? Think Asymmetric!
A few months ago, I was consulting on the design of the next generation of a (server-side) banking application. One of the modules was a batch processor, basically importing huge files into a database. For several reasons (file format, business policies), the file had to be read sequentially, processed sequentially, and imported into the database. The processing time was usually dominated by a single huge file, so the obvious technique to exploit a multicore (use several instances to import different files in parallel) would have not been effective.
Note that when we think of parallelism in this way, we're looking for symmetric parallelism, where each thread performs basically the same job (process a request, or import a file, or whatever). There is only so much you can do with symmetrical parallelism, especially on a client (more on this later). Sometimes (of course, not all the times), it's better to think asymmetrically, that is, model the processing as a pipeline.
Even for the batch application, we can see at least three stages in the pipeline:
- reading from the file
- doing any relevant processing
- storing into the database
You can have up to three different threads performing these tasks in parallel: while thread 1 is reading record 3, thread 2 will process record 2, and thread 3 will store [the processed] record 1. Of course, you need some buffering in between (more on this in a short while).
Actually, in our case, it was pretty obvious that the processing wasn't taking enough CPU to justify a separate thread: it could be merged with the read file operation. What was actually funny (almost exhilarating :-) was to discover that despite the immensely powerful database server, storing into the database was much slower than reading from the file (truth to be said, the file was stored in an immensely powerful file server as well). A smart guy in the bank quickly realized that it was our fault: we could have issued several parallel store operations, basically turning stage two of the pipeline into a symmetrical parallel engine. That worked like a charm, and the total time dropped by a factor of about 6 (more than I expected: we were also using the multi-processor, multi-core DB server better, not just the batch server multicore CPU).
Just a few weeks later (meaningful coincidence?), I stumbled across a nice paper: Understand packet-processing performance when employing multicore processors by Edwin Verplanke (Embedded Systems Design Europe, April 2007). Guess what, their design is quite similar to ours, an asymmetric pipeline with a symmetric stage.
Indeed, the pipeline model is extremely useful also when dealing with legacy code which has never been designed to be thread-safe. I know that many projects aimed at squeezing some degree of parallelism out of that kind of code fails, because the programmers quickly find themselves adding locks and semaphores everywhere, thus slowing down the beast so much that there is either no gain or even a loss.
This is often due to an attempt to exploit symmetrical parallelism, which on legacy, client-side code is a recipe for resource contention.Instead, thinking of pipelined, asymmetrical parallelism often brings some good results.
For instance, I've recently overheard a discussion on how to make a graphical application faster on multicore. One of the guy contended that since the rendering stage is not thread-safe, there is basically nothing they can do (except doing some irrelevant background stuff just to keep a core busy). Of course, that's because he was thinking of symmetrical parallelism. There are actually several logical stages in the pipeline before rendering takes place: we "just" have to model the pipeline explicitly, and allocate stages to different threads.
As I've anticipated, pipelines need some kind of buffering between stages. Those buffers must be thread safe. The banking code was written in C#, and so we simply used a monitor-protected queue, and that was it. However, in high-performance C/C++ applications we may want to go a step further, and look into lock-free data structures.
A nice example comes from Bjarne Stroustrup himself: Lock-free Dynamically Resizable Arrays. The paper has also a great bibliography, and I must say that the concept of descriptor (by Harris) is so simple and effective that I would call it a stroke of genius. I just wish a better name than "descriptor" was adopted :-).
For more predictable environments, like packet processing above, we should also keep in mind a simple, interesting pattern that I always teach in my "design patterns" course (actually in a version tailored for embedded / real-time programming, which does not [yet] appear on my website [enquiries welcome :-)]. You can find it in Pattern Languages of Program Design Vol. 2, under the name Resource Exchanger, and it can be easily made lock-free. I don't know of an online version of that paper, but there is a reference in the online Pattern Almanac.
If you plan to adopt the Resource Exchanger, make sure to properly tweak the published design to suit your needs (most often, you can scale it down quite a bit). Indeed, over the years I've seen quite a few hard-core C programmers slowing themselves down in endless memcpy calls where a resource exchanger would have done the job oh so nicely.
A final note: I want to highlight the fact that symmetric parallelism can still be quite effective in many cases, including some kind of batch processing or client-side applications. For instance, back in the Pentium II times, I've implemented a parallel sort algorithm for a multiprocessor (not multicore) machine. Of course, there were significant challenges, as the threads had to work on the same data structure, without locks, and (that was kinda hard) without having one processor invalidating the cache line of the other (which happens quite naturally in discrete multiprocessing if you do nothing about it). The algorithm was then retrofitted into an existing application. So, yes, of course it's often possible to go symmetrical, we just have to know when to use what, at which cost :-).
Labels: algorithms, article reference, C++, concurrency, multicore, multithreading, pattern, profession
