Click here to Skip to main content
13,198,727 members (41,336 online)
Click here to Skip to main content
Add your own
alternative version

Stats

10K views
8 bookmarked
Posted 21 Jan 2017

Combinatorial Explosion - A cautionary tale

, 22 Jan 2017
Rate this:
Please Sign up or sign in to vote.
My experience of the disastrous effects of a bad OO design. In particular what happens when combinatorial explosion arrives knocking on the door.

Introduction

Years ago I worked for a telecoms company in England. This was just at the time that the telecoms market re-invented the snake oil business. Money was pouring into these companies, and we had the chance to work on some amazing HP-UX machines to create systems for network management. This basically meant providing a GUI based front end, with multiple processes running asynchronously in the background, all doing their communicating via IPC, and all doing clever and complex stuff with multiplexors and other telecoms kit out in the street.

It was a great time, our customers, other telecoms companies like us, could control their whole infrastructure from a single room, and the day of the man with a screwdriver and a van out in the street changing multiplexors were finally over ! But, just as the aforementioned man with the van left, just as he closed the door on us, he muttered 2 words that eventually ground everything in my department to a halt..."combinatorial explosion...", well I definitely heard the word explosion anyway.

Background

Combinatorial explosion is a state that an OO design can get in. It's caused when designers of OO hierarchies over design. They end up with too many classes in hierarchies, as they believe that extending a system should just be about adding new classes, with just a little bit of extra code. Code that is so obvious to write, that it will reduce bugs and ambiguity, thus improving quality. They also thought they could force the software engineers to implement correct code because they were bound by strict contracts. So any time a new type of something needed to be managed simply drop in a few classes, the engineers could infer from the class names the exact behaviour, and boom! A Miracle Gro software solution with a tenth of the dev budget, meaning QA can go back to being a hand full of testers, as no existing classes would be touched, so very little regression testing was needed.

This type of strict, overbearing design, is great for programmers. They can infer from the type that they are coding in (the class name) exactly how that class should behave, i.e. I am in the pushbutton telephone class, therefore my function to draw the buttons will do this, and when I am in my dial telephone class my draw function will do that, nice and easy. But when inserting another type of base class, it can result in you having to implement a whole sub set of derived classes for your design to carry on working, especially if you make them full of abstract functions (pure virtuals in C++, or functions with no implementation, part of an interface - a contract basically).

 

Real Life Situation

So in the aforementioned telecoms company, we had OO modeled our multiplexors and their environment. We had a GUI based app that had a class for each type of multiplexor we sold. We had many multiplexors, and they could have different firmware on them. Each multiplexor was a fixed type, so it couldn't be migrated from one type to another. This was great, as no migration strategy was needed of persistent OO classes for the mux type. But the firmware could be upgraded, so we did have some migration to perform. The firmware type sat on the mux controller card in real life, but we thought that because there was only one mux controller card per multiplexor, the firmware type could just be an attribute of the Mux class, besides it saved another level of function indirection, going through a Mux->Card call to get the firmware type, we could now know directly in the Mux class the firmware type. Now let's talk about the classes we started with.

We had a base class called Mux, then SDH and PDH derived from this. These were two methods for sending network data traffic. From these two base classes we had our concrete classes, i.e. SMA1, SMA4, SMA16 etc. However soon enough (a year or so) we realised we had lots of C++ software switches on the firmware type in the code. So for example a typical function would look like this : 

[__strong__]void SMA1::Draw()

{

if (firmware.IsA1.0() == true)

{

   drawNormal ();

}

else if (firmware.IsA2.0() == true)

{

  drawDoubleThick();

}

else if (firmware.IsA3.0() == true)

{

  drawTrebleThick();

}

}

So the Draw function would have conditional logic that would draw the cards normally for firmware 1.0, twice as wide if it had firmware 2.0, and three times as wide for 3.0. Obviously this is just an example, the code wasn't that simplistic (we used switches - haha that's a joke ! ).

It's easy to look at this function and say "Wow ! that's awful code", but this code crept into this state. New people joining the team, they grep for 1.0 : 

grep 1.0 *.cpp > work_to_do_for_new_firmware_type.omg

grep 1.0 *.h >> work_to_do_for_new_firmware_type.omg

All the functions with switch on firmware type would be extended, another case for the switch statement or putting an || (or)  in the if statement (if the new firmware behaved the same as an existing one.) Remember someone didn't write this function all at the same moment in time.

The way the company operated was typical of a hardware manufacturer. Bear in mind that when firmware 3.0 came along we in the software management team had a month to add support for it. The firmware team released new versions of firmware almost every month, driven by an insatiable marketing vision and peer pressure. The hardware team bought out new hardware every year, as it was much more expensive and risky to create new products altogether, better to extend existing ones. New products required management risk, and as we all know that doesn't happen much, better to stick with no risk, as even though there is no reward, there is no failure, right ?

So new features were mostly added in firmware (if they could be), and if we didn't manage those new features in the software management team, then the customer didn't see any benefit from spending any more money, and our sales team couldn't drive profits up for Mr Shareholder (who basically was sitting on a billion dollars of worthless pyramid scheme paper). So we had a job to do, and quickly. So we did it, and eventually all our functions looked like the one above.

Just to remind you that the firmware was an attribute of the base MUX class. 

Here is what our design looked like :

 

"So let's refactor !", we cried in unison, not literally cried of course, no, that came a bit later.

We took out the firmware attribute type altogether, because we decided we would use more of OO the way it was intended. The class would tell us the type, we didn't need to have code that was conditional and ask the type, we could infer what we were by where we were writing the code. So in essence, if I was in the class SMA1 I knew I was an SMA1, so let's do things accordingly. We changed the design to add what we thought was an acceptable number of classes. Now our hierarchy looked like this ( this is just a sub-set for brevity):

So we had new classes hanging off the SMA1,SMA4, SMA4c and SMA1c. And as we had all our functions virtual, Draw became overridden specifically for new firmware types. So the SMA1_FIRMWARE_VERSION::Draw functions became :

[__strong__]void SMA1_1.0::Draw()
{
   drawNormal ();
}

void SMA1_2.0::Draw()
{
  drawDoubleThick();
}

void SMA1_3.0::Draw()
{
  drawTrebleThick();
}

Wow, look at how we reduced the amount of conditional code. This was super clean, and everyone did rest for the day, and take solace etc...

To instantiate our classes we had factory functions.

Then this happened :

"What does this guy want ?"

"He has come bearing good news, we have been so successful we are releasing lots of new products called SMA32, SMA64, VCTS2, VCTS4. And there will be 3 new firmware types this quarter, and they are splitting the mux controller card, that means they can have a dual firmware mode."

Hahaha, so we would now have to have this hierarchy (again I'm not spending 4 hours drawing all of it ):

 

Note that for brevity I have left off all lots of concrete classes (you can figure out which ones), I've demonstrated the concept with the use of the SMA4c derived classes. Only a fool would fill in the rest, and we did. We had crossed the Rubicon, Alea iacta est ! There was no going back, the die was cast !

Two years later we had another 6 types of multiplexor, and we now had roughly 15 firmware types, so our hierarchy looked like this :

 

Ok, get the picture ? Yes the code did work, but surely this wasn't the way to KISS - "Keep IT Simple Stupid" ? Was it ?

The theoretically right thing to do in this situation 

Big chapter headings always make me curious. The books we pondered over next told us to avoid deep hierarchies ! Infact Zarathustra shouted out "Avoid inheritance as much as you can. Favour composition", said he, "Favour ?"  said I back.

So we analysed, and came up with the next solution. Take out all these classes, go back to having the Mux specific code into a Mux hierarchy, and have the firmware specific code in a separate hierarchy, and use composition. Go from a ISA to a HASA. So the Mux class Has A firmware version, whereas before we had a Mux ISA firmware version (and a mux version).

So the hierarchy looked like this. 

 

We had a much smaller design, and had successfully decoupled our bad design from mux type and firmware type amalgamated, splitting it into firmware and mux type independent hierarchies. The amount of coupling was not high, as were delegating the firmware specific code to the firmware hierarchy (imagine if we went back to saying Is1.0() inside the mux classes again ! Back to square 1). The draw function became :

 

void SMA1::Draw()
{
    firmware->Draw();
}

We had factory functions that would build the mux type and with it, the firmware type dependent on a passed in string from the users choice in the GUI. So our constructor would flow like this

SMA1::SMA1(string firmwareType)
{
   if (firmwareType=="1.0")
   {
      firmware = new firmware1_0();
   }
}

So we now had two hierarchies.

Reality Sucks

Obviously I would be lying if things were that simple, right ? Yes, so let's save my reputation, and discuss the next set of problems. We found that in reality, some things were a combination of mux type and firmware, so for example a SMA1 LED was blue for firmware 1.0, green for firmware version 2, and for an SMA 4 LED it was yellow and white respectively. So we couldn't have a function in the firmware hierarchy like this :

colour SMA1::GetColourLED()
{
    if (Firmware() == 1.0)
         return colour::Blue;
    else if (Firmware() == 2.0)
         return colour::Green;
etc.
}

Or this !

colour Firmware1_0::GetColourLED(
{
    if (GetMuxType() == SMA1)
          return colour::Blue;
    else (GetMuxType() == SMA4)
          return colour::Green;
}

As this would push us back to the original problem.

We knew we had to have another hierarchy for these things, so we tried to take a step back and say, "Well are the colours for something other than the type of the mux or firmware ?" And often these types of things were, so we had an LED hierarchy. For example the LED colour really represented the traffic speed, it just so happened the green and blue (2Meg and 4Meg) were on the SMA1 1.0 and 2.0 firmware respectively. And so we modeled the colours based on that, network traffic speed. You get the picture.

And so hereth endeth the tale of the explosion of classes in the telecoms management system. I should say this was around 1989, so things were a little different then, we were using Shlaer–Mellor (before UML came along), and it was a nascent industry ready for making mistakes. In the end we were good engineers and ready to admit we made big mistakes. But really the biggest problem was probably believing two other groups of people :

Marketing and Sales - "There won't be any more new firmware releases. We are going to settle for just one per year, so basically only when a new piece of hardware comes out."

Our Management -  "Don't worry we can throw all this in the bin in 3 months, and we can remodel that whole part of the system, just stick in this one last new Mux type."

The moral of the tale ? If something looks 50 times bigger than it should be, it probably is.

Thanks for reading.

Marcus

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

marcus obrien
Technical Lead
Canada Canada
I have a blog here

http://www.electricalengineeringschools.org/blog/

And my robotics web site is here :

http://www.roboticsfordreamers.com/

I have been a software engineer for over 20 years now. I'm an expert in writing scalable restful web API services, which I've been doing for over 7 years now for games companies such as EA and Ubisoft. I've also worked on several video games, including Skate 2 and 3, NHL, Need for Speed, various Assassins Creed games, Far Cry 3 and 4, Driver San Francisco and most recently with a team of 15 on EA's UFC free to play. On this latest project I designed, implemented, tested (including load tests in Gatling and JUnit on AWS), deployed and supported all the web services for the game client, supporting up to a half a million active sessions.

I am proficient at programming in C, C++, C#, Java etc. I've developed many types of games, applications, SDKs and web services in Linux, Unix, iOS, Android and Windows.

My spare time is spent teaching and lecturing computing languages and science. I have a PhD in Artificial Intelligence (specialising in knowledge representation - Semantic networks with inference engines).

Currently I am also building an A.I. general purpose robot. The brains behind it are a mix of 6 Raspberry Pi and Banana Pros, with 2 USB cameras, SATA drive, Router Switch with inter-pi Comms, 2 motorised track systems, plus various sensors including motion/pir/sound etc.

The six pi's are split according to functions, including eyes (image processing/recognition), ears (speech processing and simulated speech),motor (object avoidance, environment mapping, drives all movement), entertainment (web browsing, media playing etc), brain (knowledge system, and adaptive learning/memory systems) and development system ( logging, diagnostics, debugging).

I am available as a consultant, so if you need to get something out the door quick, or want to set down an expandable and resilient framework, ping me !

You may also be interested in...

Pro

Comments and Discussions

 
GeneralMy vote of 5 Pin
DrABELL25-Jun-17 7:19
professionalDrABELL25-Jun-17 7:19 
QuestionSounds like a need for Strategy pattern Pin
raddevus10-Feb-17 2:48
mvpraddevus10-Feb-17 2:48 
Questionkudos Pin
dmjm-h24-Jan-17 10:52
memberdmjm-h24-Jan-17 10:52 
PraiseThanks Pin
GilbouFR23-Jan-17 22:52
memberGilbouFR23-Jan-17 22:52 
PraiseOutstanding! Pin
koothkeeper23-Jan-17 14:10
professionalkoothkeeper23-Jan-17 14:10 
GeneralRe: Outstanding! Pin
marcus obrien23-Jan-17 14:17
membermarcus obrien23-Jan-17 14:17 
QuestionNo paradigm is perfect Pin
john morrison leon23-Jan-17 0:54
memberjohn morrison leon23-Jan-17 0:54 
AnswerRe: No paradigm is perfect Pin
D. Infuehr29-Jan-17 15:19
memberD. Infuehr29-Jan-17 15:19 
QuestionFun to read Pin
Bernhard Hiller22-Jan-17 23:23
professionalBernhard Hiller22-Jan-17 23:23 
QuestionIs it just me? Pin
Pablo Aliskevicius22-Jan-17 2:30
memberPablo Aliskevicius22-Jan-17 2:30 
AnswerRe: Is it just me? Pin
rreinheimer22-Jan-17 4:01
professionalrreinheimer22-Jan-17 4:01 
GeneralRe: Is it just me? Pin
marcus obrien22-Jan-17 10:13
membermarcus obrien22-Jan-17 10:13 
AnswerRe: Is it just me? Pin
marcus obrien22-Jan-17 10:19
membermarcus obrien22-Jan-17 10:19 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.171020.1 | Last Updated 22 Jan 2017
Article Copyright 2017 by marcus obrien
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid