Gunnar Kudrjavets

Ternary search trees

2004-10-01T03:57:00Z

About a year ago I was in pretty embarrassing situation because I had no clue what ternary search trees are and I had to write some code to implement efficient way of searching and storing strings. Jon Bentley’s and Robert Sedgewick’s article "Ternary Search Trees" was published in DDJ and is a very good paper to start with. Unfortunately to access the article you need to be DDJ subscriber but if the source code is enough for you then the demonstration program by authors is located here. Ternary search trees are extremely helpful in solving an entire class of searching related problems which may come up in real life.

"The Apprentice" for software developers

2004-09-30T22:40:00Z

Lately it seems that to be part of any social discussion you need to be watching "The Apprentice". I’ve been noticing the similar phenomena during last couple of years when it comes to "The Sopranos" and it made me feel like a total outcast because I haven’t seen a single episode of "The Sopranos" and I don’t intend to ;-) However, to blend in I’ve been following "The Apprentice 2" and my colorful imagination tells me that what will be really cool ;-) is the similar show about software developers. You can already imagine the following dialogs in the boardroom:

...
Participant 1: We lost because Participant 2 never wrote any unit tests and therefore our application crashed.
Participant 2: No, you’re wrong. We lost because you told me not to bother adding any assertions to our code. If I would’ve added the assertions we would have won.
The Guy Who Runs The Show: Participant 3, what do you think? Whose fault it is?
Participant 3: I think it is leader’s fault. He told us not to install low-level debuggers because GUI tools will be enough and I told him that Real Programmers don’t use GUI tools.
The Guy Who Runs The Show: Participant 1, you’re fired because you used variable names like lpszfoobarCount.
...

The extra bonus will be seeing before any given task all these people with CS degrees utilizing the game theory trying to figure how to behave properly to maximize their chance of winning. That’ll be the show geeks will watch ;-)

Tips for survival in agile software development world ;-)

2004-09-28T19:58:00Z

Even if you don’t have any clue about agile software development, SCRUM, TDD, XP etc., here are some things which will help you to look smarter:

Use a word "refactoring" whenever words "changing", "modifying", "updating" etc. are used. Some examples: "I refactored the project’s schedule to include this new task.", "Should we refactor our meeting for this afternoon?", "Triage team will refactor all the bugs with the new triage date." It won’t always make sense but you’ll at least look cool and knowledgeable and maybe even agile.
Use a word "agile" to prefix some nouns and replace it with adjectives you would normally use. Some examples: "This is pretty agile meeting.", "You’re looking agile today.", "This is an agile bug.", "There have been some agile developments going on recently."
Use a word "extreme" like a word "agile" in previous bullet-point. You would need to be more careful though not to scare people off.
Whenever you’re talking about testing then use "unit testing". Some examples: "She is currently unit testing this new interface.", "When your performance unit testing will be done?", "What’s a career path for unit tester?"
You can also try to prefix "development" with "test driven". Some examples: "How’s life in test driven development team?", "Are you a test driven developer for this new feature?"
Use "pair" to prefix "programming". Some examples: "I had to go to meetings all day and therefore I didn’t get any pair programming done.", "My friend is a C# pair programmer.", "Pair programming this task will take at least three days."
Replace "scenario" with "user story". Some examples: "Does the specification contain all the user stories for this product?", "What are the most important user stories we should be testing?"

If anyone has additional extreme tips then let me know and I’ll refactor this blog entry to include them ;-) Link of the day: http://c2.com/cgi/wiki?ExtremeProgrammingForDummies

Now playing: Melotron, "Manchmal".

Having majority of the tests implemented before feature is added to the code base

2004-09-26T23:34:00Z

One of the things we’re currently trying to do is to align development and test processes and schedules more closely. The fuzzy description of initial problem statement is the following: “Whenever the implementation of some feature is added to the code base then at the same time majority of tests for this feature must be also implemented and some specific criteria about the quality of the feature must be met.”

However unclear this requirement may be it immediately raises a number of questions and implications for the entire software development process. Let’s look at some of them:

Testability. For now let’s use the simplistic model where we define a software product as just a set of features. To meet this requirement above we need to focus more than ever on testability of every individual feature. The features need to be designed so that there’ll be way of testing them in isolation. It definitely won’t be possible in every single case, but the alternative with lots of interdependencies is very frightening. No more you can check in the interface IFoo and say that you can use it, but it won’t possible to properly test it before IBar is implemented two weeks from now. Of course mock objects will help us tremendously.
Psychological impact. The well-known software development models like the waterfall model and spiral model have very clear distinction between development and testing. Now the development and testing will become a gray area where it’s very hard to formally determine when some feature is actually done. As everything unknown and new is usually frightening for people then there’ll be probably lots of problems with skepticism targeting this approach.
Collective responsibility. No more it’s “Feature F is coded, so development is done and ball is now in test organization's court, go and test it.” The completeness of feature set becomes a responsibility of the entire team and developments vs. test attitude should be fading.
Exact metrics. How do we explicitly specify that desired amount of testing is done? Is it number of test cases (extremely bad measurement)? Is it specific percentage of code coverage (I don’t like this one also)? Is it some percentage of use cases automated? Is it all priority 1 and priority 2 test cases automated (how much priorities should we have?)? Is it some collective gut feeling which tells that feature is tested and it is "good enough"?
Impact on morale. If getting both product and test code implemented is a collective responsibility then Alice and Bob as developers may think that automating these API test cases isn’t what they signed up for and collective mutiny against this approach may take place ;-)
Office moves. Very frequent interaction between development and test team will be required to accomplish the end goal properly. Should we start planning for office moves and try to make sure that people working on the same feature set have their offices located nearby. Please, no communal workspace ;-)
Impact on the entire testing process. Are the test plans even necessary anymore or should the test code be the only documentation? What about manual test cases? Should we try to automate everything which is possible no matter what the cost is?

This list can go on with number of additional questions but it’s wise to stop here because I don’t have currently answers, just questions. Now I need to go and talk with some smart people and figure out how to solve these problems or get the confirmation to the fact that I'm just overreacting ;-)

Now playing: Depeche Mode, "Behind the Wheel [Remix]".

Diaries of a former caffeine addict ;-)

2004-09-26T01:17:00Z

More than three months ago I decided to stop drinking coffee and switch to the green tea. I stopped drinking soda already years ago and currently my average intake is a can of Coke once in two-three months. Welcome to almost caffeine-free lifestyle ;-)

Coffee has been one of my best friends since teenage years and became an irreplaceable beverage during the university years when during daytime I attended lectures and during nighttime I wrote code. About five years ago I experienced something which could be called caffeine overdose – 7-8 cups of coffee every day. Needless to say that consuming so much coffee had some side-effects ;-) and I cut it back to 4-5 cups per day. This year my consumption of coffee has reached again somewhere near 6-7 cups per day and finally in the interest of preserving good health and sanity I decided to do the radical change and stop drinking coffee at all. For the purposes of entertaining other people I took some notes during last three months. Here they are:

Week 1: First day without coffee feels pretty bad. In the mornings I experience some doziness. Smell of fresh cup of Starbucks coffee causes cravings. I don’t understand how people can drink green tea. No difference in depth of sleep. No headaches. No nausea.
Weeks 2-3: Practically the same, no negative symptoms except drowsiness. Sometime there are cravings for coffee. Green tea tastes much better. I start drinking about 4-5 cups of green tea per day. Guess I’m hooked on a new substance ;-) Sleeping slightly better.
Week 4: First violation of the rules – I drink one cup of vanilla latte because of the social reasons. It tastes like the best cup of coffee I ever drank. Green tea doesn’t bother me anymore. Sleeping much better.
Weeks 5-6: Don’t have many cravings for coffee anymore. Drink four lattes during these two weeks because of social reasons. Green tea actually tastes pretty good. Start convincing my girlfriend to stop drinking coffee. She laughs at me but drinks green tea with me a couple of times.
Weeks 7-10: Sometimes when I smell fresh cup of coffee I still have cravings. Feel much better and relaxed. No problems falling asleep at all. I start enjoying green tea and finally have five different types of green tea at home. I discover that there is actually a difference between various teas.
Weeks 11-now: Bye-bye coffee. No more cravings.

If you’re more interested about coffee, caffeine, and health related information then Google will help you as usual. A couple of interesting links:

However, I still decided to keep the coffee machine in my office. You never know ;-)

Popular agile software development sites

2004-09-23T06:56:00Z

Today evening I had finally time to read through the September issue of ACM SIGSOFT Software Engineering Notes. In addition to the usual goodies they have a nice overview ("Surfing the Net for Software Engineering Notes" by Mark Doernhoefer, page 20) of most influential/known/popular sites about different agile software development methodologies. As I'm tired of trying to keep my bookmarks synchronized across the number of different computers I use, I'll publish this list and some additional sites here:

The New Methodology. RSS feed for the site is here and RSS feed for Martin Fowler's blog is here.
Agile Methods Wikipedia.
The Agile Manifesto.
The Agile Alliance.
Extreme Programming.
Scrum.
Crystal.
Dynamic Systems Development Method (DSDM).
Refactoring. RSS feed for the site is here.
The Fraunhofer Center eWorkshops.
The Official Agile Modeling Site.
The Pressman Downloadable Reference Library.
Agile Testing.
Agile Management.

Why I suddenly care about all these agile software development links? Because at the current moment I'm in the same side with agile software development and testing people. With very high probability I'll be talking quite a lot about my personal experiences with XP and related things during upcoming weeks and months.

The new era has come and the hot buzzwords are: agile, extreme, pair programming, refactoring, test driven, unit tests, and user stories. Use these words often and in every context and you'll certainly get some attention ;-)

Best practice - daily investigation of the test case failures

2004-09-21T04:54:00Z

When it comes to the best development practices then daily build and Microsoft are practically synonyms. Not a big surprise. Jim McCarthy says it’s the heartbeat of the project. Steve McConnell covers it thoroughly in his books. Even Edward Yourdon thinks it’s worth mentioning. Etc. etc. To summarize: daily build is A Good Thing.

In software testing things are more complicated. What is the must use practice which everyone should follow, the process which is efficient and which gives everyone an honest overview of the project’s current state of quality? If you ask me then one best practice I would nominate is daily investigating all the test results. Sounds kind of trivial, doesn’t it? There’s nothing to this, you just look at all the test case failures every day and if there are bugs then you enter bug reports. Well, using the same logic the daily build is simple also - you just compile and link everything every single day ;-)

In real life investigating all the test case failures requires huge amount of discipline and noticeable amount of intellectual effort. Imagine thousands of test cases running on n different editions of your product. Every failure needs to be properly investigated and if applicable then bugs opened. Every single one of them. Every day. In our team we established a simple rule: you investigate all the test case failures before you start working on anything else. Sometimes investigation process takes ten minutes, but sometimes it takes the entire day. Sometimes ten test cases fail. Sometimes hundreds of test cases fail. Sometimes people aren’t happy about this and sometimes it even causes internal schedules to slip. But it’s worth every penny invested into this effort.

The end goal we’re trying to achieve is that every day we have a mapping table between failing test cases and relevant bugs. Every day we know which features and scenarios work and which don’t. We also know why, who owns fixing the bugs, and when they’re going to be approximately fixed. Simple but extremely useful practice to have.

Is anyone (still) using CASE tools?

2004-09-20T03:52:00Z

Last weekend I was reading "No Silver Bullet" again and as a direct result of this I accumulated number of pessimistic thoughts and therefore I'll rant about one specific thing for a while. In my mind I classify different software engineering methodologies, tools, and approaches into number of categories. One of them is called "esoteric stuff." For example, formal methods in software engineering belong IMHO under this category. Lately I’ve been thinking about moving CASE (Computer-Aided Software Engineering or use your favorite meaning for this acronym) tools under this class also. Why? I believe that generally the world of software development is mostly self-regulating. If something is good and causes better productivity then people use it and over the course of time more companies/people start incorporating "this something" into their processes. If something is good on paper, but doesn’t work IRL then eventually less and less people will use the technology and finally it’ll disappear from the radar screen. For myself I’ve found a couple of reasons to distance myself from CASE tools:

Use what you preach. With for example TDD being hyped and tools like NUnit it’s kind of cool to see that the NUnit developers use the same methodology they preach. If you look at NUnit community page you’ll see that they explicitly say "As such we will accept no code changes without associated tests." Die-hard Borland Delphi fans also remember the time about nine-ten years ago when Borland was hyping Delphi with "Delphi is written in Delphi" slogan (probably they still do). With CASE I haven’t found many references to the CASE tools where for example version n + 1 has been built using version n or the tool itself has been used during its own development. Possibly I’ve been just sloppy Google user, so if anyone has links to some articles or studies then please let me know.
Is anyone doing this? If I look around at work then I've never seen anybody composing models, generating code from diagrams, maintaining huge data repositories etc. During the entire first version of Speech Server I saw maybe less than ten different UML diagrams describing either architecture or detailed design of the system. Possibly this is something to be ashamed of or on the opposite, maybe we should be proud about this? I bet that Mel, A Real Programmer would definitely be proud of us ;-) Generally, if you look around, how much big software companies do you know who claim that they use CASE tools in their daily software development process? Again, before somebody slaps my wrist, possibly I’m just demonstrating my own ignorance. On a separate note, my copy of "Rise & Resurrection of the American Programmer" by Edward Yourdon includes a nice chapter called "The Microsoft Paradigm" where the some of the related things are discussed.

At the same time I could also make a couple of contra arguments:

There are still software companies producing CASE tools and selling successfully their products. Therefore somebody must be using these tools. I haven't bothered to search for huge amount of success stories, but I would assume that every vendor has a couple of them where for example thorough drawing of collaboration diagrams saved some software project ;-)
Classical "toolbox argument". Maybe CASE tools are just not applicable for the type of software my team is producing. Maybe if I would be working on something else I would spend my entire day on generating code from models?

Anyhow, as always there's no absolute truth and this is just one opinion amongst many. Today is apparently just anti-CASE day ;-)

P. S. Before somebody asks - I spent about three years working on daily basis with Oracle Designer, Rational Rose, Select Enterprise, and number of other modeling tools being my best friends and was once big believer in modeling. Thinking about this I even used to run UML seminar for graduate students. I guess the childhood is finally gone.

P. P. S. Martin Fowler has written a very interesting article called "Is Design Dead?" which poses some more fundamental questions and slightly touches modeling.

Professional Development Handbook/Ladder and SWEBOK

2004-09-19T19:39:00Z

Probably most of the people who have ever read "Code Complete" or its second edition or any other book by Steve McConnell have browsed systematically through Construx’s web site. One of the most interesting pieces of information for me is their "Professional Development Handbook" and "Professional Development Ladder". Sure, Microsoft has its internal equivalent documents, but nevertheless it’s very educational for more complete world-view to understand what’s happening in other software companies or towards what industry is moving in general. I usually try to reread these documents every three months or so to understand how my personal thinking has changed ;-)

One other thing which has been in my TODO-list for long time now is to read through the latest version of SWEBOK. SWEBOK stands for "Software Engineering Body of Knowledge". Based on my personal experience when talking with different people about SWEBOK it seems to be one of these things with what professionals either agree with or violently disagree. Your mileage may vary of course.

Development:test ratio causing software quality to self-stabilize

2004-09-01T03:52:00Z

Today I attended one excellent talk covering software engineering culture in general, things which currently need improvement, some internal case studies etc. Test to development ratio was also pointed out in this talk and one interesting thought was mentioned during this presentation. Microsoft is different from most of the software companies by development and test organizations having very similar sizes. Hypothetical little feature team may consist of 6 SDE-s, 4 SDE/T-s and 1 STE for example. What would happen if ratio of testers and developers will be 1:10 for example and at the same time you would have a top notch development team who’ll be obsessive about code reviews, unit testing, proper engineering practices etc? Natural reaction is that the product quality will be doomed ;-) However, one of the projected outcomes was that the product quality will be self-correcting and will stabilize itself automatically to the level that would be acceptable for shipping? You know, all these factors like people developing the software understanding that they’re the ones responsible for product quality and there’s nobody else ;-) Major assumption is of course that peer pressure and strong personal accountability for the quality will be applied.

P. S. Everyone who has shipped any products where testing was done only by developers can claim that they’ve participated in this experiment already and if their product made enough money then they’ve succeeded ;-)

What is the desirable way to "close a bug"?

2004-08-31T05:49:00Z

This is one the subjects I have to explain very frequently so this blog entry is mainly for purposes of storing my answer somewhere in the permanent location. Let’s start with the moment where Alice (developer) fixed a bug and assigned it to Bob (tester) for closing. First of all, I never liked the term "closed/closing" when it comes to the bugs, IMHO the better term is "verified/verifying", but that’s not important right now. In ideal world Bob in general will do the following:

Inspect and understand all the changes which have been made to fix a particular issue and verify that these changes haven’t introduced any unwanted or erroneous behavior. Please note that this automatically implies that Bob understands the architecture, design, code, and overall system functionality enough to make any conclusions like this.
Verify that the bug doesn’t reproduce anymore under specific conditions where it was found. This includes setting up environment for reproducing the bug, running through the exact steps when bug was initially found, and confirming that nothing unexpected happens.
Looks at the unexpected test failures (if any) and uses his intellect to determine if any of the new failures are relevant to the changes made to fix the particular issue. This is usually very tricky because n different bugs get fixed every day and unless you have a private build with only this specific change then investigative work like this will take time.
Checks if there’s a test case which would have found the issue and if not then happily develops a new test case or set of test cases. This is the place where some people argue that developer should be the one developing appropriate unit test if applicable.
If Bob is really committed then he’ll dig into the root cause analysis part of the bug and check the entire code base for similar patterns which caused the original issue. If Bob is really paranoid then if applicable he tries to determine a pattern in the code and develop a plug-in for his favorite static source code analyzer to detect issues like this in future automatically.
Some ad hoc testing around the area where bug was found. I'm referencing Glenford J. Myers's quote "The probability of the existence of more errors in a section of a program is proportional to the number of errors already found in that section." (Page 15, "The Art of Software Testing")

Of course this isn’t easy and takes some time, that’s why I highlighted the words "in ideal world" ;-)

Another interesting blog on software testing and quality

2004-08-28T04:08:00Z

Through the discussion in internal e-mail alias I discovered James Bach’s blog. As he describes it: "Rapid, heuristic, exploratory software testing. An intellectual, anti-clerical approach to testing." I have now spent already significant amount of time reading through the entries and there’s plenty of good stuff ;-) Bach’s company has also pointers to a number of interesting articles and presentations.

In addition you may want to take a look at other blogs at Florida Institute of Technology. Most of them are unfortunately inactive, but what’s there is IMHO worth reading.

Beneficial use of LOC (Lines of Code) metric ;-)

2004-08-25T18:05:00Z

This is just a humorous story about how metrics can be sometimes (incidentally?) used even for programmer’s benefit. A number of years ago (before I joined Microsoft) I worked together with a programmer who had developed a piece of financial software and one financial institution wished to purchase full rights for this specific application. They wanted to be able to do whatever they wished with the source code and because of some reasons the programmer who wrote the code was to receive the noticeable percentage from the profit coming out of this deal.

At some point in the process there was a discussion about how to determine the price for the full rights to the source code? One high-level participant proposed that we should just count the lines of the source code and multiple them by some specific amount of money. His logic was simple: the more there is code, the more it should cost. AFAIK there were some people who agreed with him. Of course people discussing this weren’t programmers ;-)

I don’t know how the deal finally ended, I wasn’t privy to this information, but I would assume that if LOC was the major factor in this deal then the programmer who owned the code would have spent his entire time adding comments to the source code and changing the bracing style ;-)

Non-technical books read during my last vacation

2004-08-23T03:36:00Z

One of the funny problems software people experience IRL is that it’s kind of complicated to explain to other people what are the majority of books you’re constantly reading about (at this point any other representative of any other profession can scream "It's not only the software people, it's us too!") ;-) Here’s the sample conversation from the real life (I’m in the process of reading the John Robbins’s debugging book):

...
She: What are you reading?
I: Some sample code.
She (puzzled): What kind of code?
I: It’s mainly C++ and Win32 API.
She (still puzzled): What's this code about?
I: It teaches you how to implement your own debugger.
She (more puzzled): What's the debugger?
...

Unless your other side does professionally what you do then it’s kind of hard to have meaningful conversations about the books you’re currently reading. The example above could of course be reversed and I could be asking questions like "How this MMPI test thingy works?" etc. So, during my last vacation I decided it’s time to read something related to my girlfriend’s areas of expertise and after that have a discussion about this. I ended up with the following three books:

"Funky Business: Talent Makes Capital Dance" by Jonas Ridderstrale, Kjell Nordström, Kjell Nordstrom. Here’s their main web site. One of the coolest and funniest business books I’ve ever read (I haven’t read many, so don’t take my opinion too seriously ;-)).
"Girl, Interrupted" by Susanna Kaysen. If you have seen the movie (I actually had to rent the movie after reading the book to satisfy my curiosity) then I would strongly recommend reading the book also.
"Man's Search For Meaning" by Viktor E. Frankl. Quote from Amazon.com: "Man's Search for Meaning" by Viktor E. Frankl is among the most influential works of psychiatric literature since Freud.

Next level will be the stage when we both will drop stuff related to our profession and start reading something neutral ;-)

Paying money to people for finding bugs

2004-08-21T02:12:00Z

In the beginning of the August Mozilla Foundation announced the Mozilla Security Bug Bounty Program. Short summary: if you report a critical security bug and they agree with you then you’ll get $500 cash prize. What can I say; soon people will be selling bugs on eBay and it’ll be currency like any other ;-)

When it comes to exploring the power of money as a motivational factor and its effects on software testing, here’s one experiment I always wanted to do.

Two teams consisting of people with identical technical skills (as close as you can get) will have fixed amount of time to test a specific piece of software. They test exactly the same functionality and teams work in isolation. First team will get paid some amount of money for every bug they find. Let’s assume that triage committee will go through every bug and assign some weight to the bugs and for example priority 1 bugs will cost $100, priority 2 bugs will cost $75, priority 3 bugs will cost $50, and priority 4 bugs will cost $25 (the decomposition into priorities and specific monetary amount can of course be whatever you want it to be). Second team will be motivated just by the pure technical challenge and the spirit of competition.

Which team will finally discover more bugs? Which team will finally discover more "valuable" bugs? How different the results will be? Is it order of magnitude or is it less? How will be the results of experiment depending on the specific type of software? What happens if we reverse the teams and rerun the experiment again at some point in time? Will the results be different if triage committee will constantly triaging the bugs and letting the first team know that they’ve already earned $n? Will the results be different if the second team won’t know that first team will get paid for bugs?

Psychology graduate students with interest in software engineering, where are you ;-)