Seeping Matter

Uh, this is a programming post.  Just so you know.

The Problem

Okay, so let’s start this discussion with a simple linked list that contains the ingredients for Bill Cosby’s Chocolate Cake for Breakfast:

Fig. 1 - Linked list of ingredients for Chocolate Cake for Breakfast

Normally we’d use a linked list in programming when we know we may have to arbitrarily insert items later on.  For example, I just realized that this cake does not contain chocolate, so I should be able to insert that into the list by shuffling a little bit:

Fig. 2 - Chocolate Cake for Breakfast, with Chocolate Added

This seems like a much tastier recipe.  But there can be a slight problem with this.

Suppose the linked list is serving as a model for your recipe view.  You have a UI that accessess the model and then displays the results in some sort of view that you can see on your laptop in the kitchen.  Suppose further that you decide to go even crazier and not just stop with adding chocolate, but you are also going to add sugar and frosting.  INSANE!

This is not a problem yet.  Likely your UI offers the ability to add new ingredients through the UI, so you just add them and the model gets updated, and when your view refreshes you see the new list:

Fig. 3 - Chocolate Cake for Breakfast - Dessert Style!

That sounds like a great chocolate cake.  But now suppose Mr. Cosby is on stage in Winnemucca doing his Chocolate Cake for Breakfast routine, and for some reason that nobody can understand the teleprompter that reminds him of the routine is using your data model to render the view – right at the exact moment in time that you are changing the recipe.

Uh-oh.

I’ve run into this problem a number of times in my software development career, where I have a data structure that is being accessed by more than one user at the same time.  In our case, we have one read-only accessor and one read/write accessor.  At first glance it doesn’t seem like this should be a problem.  But unfortunately, even though the reader isn’t making changes to the model, the reader still depends on the model having a constant state.

There’s a couple of fairly simple ways to address this problem.

First, we can make a copy of the model for each user.  We can have a resource that provides a copy when a user requests the copy.  Then that user can do whatever they want with the model – read or write.  When they are done, they can either discard their copy, or turn it back to the resource for the changes to be merged into the whole.

This might work for some implementations.  In our trivial example here it would probably be just fine.  But if I have a data structure with two million 50-byte records, this isn’t such a great idea.  It isn’t just that I don’t want to make a copy of a 100 Mbyte (okay, 95 for you technicality folk) data structure – I don’t want to double my memory usage from 100 Mbytes to 200 Mbytes (or 95 to 190, sheesh).  So making a copy won’t always work.

Another option is to lock the structure.  Using some sort of a mutual exclusion primitive I can lock the data structure so that only one user can access it at a time.  I can’t just hold the lock per-access, though – I have to maintain sessions and locks for the entire session.  In other words, I have to make sure that nobody can change the recipe at all throughout the duration of Mr. Cosby’s act.  This high level of granularity in the locking of the data structure makes it hard to use.  And it is particularly frustrating for read-only users who are thinking, “Why can’t I access the structure?  All I want to know is what is in it!”

Versioning

One way I’ve successfully solved this problem in production code is to use a versioned container and versioned iterators for that container.  I used these at Volera, for example, for some reason that doesn’t matter now, because Volera is DEAD.  Anyway, here’s how they work:

Versioned Containers act pretty much like regular containers – vectors, lists, hashtables, etc.  The difference is that each link from one element in the container to the next has an associated version number on the link.  Any given element can have a number of “next” links – even a singly linked list, like in our example.  Each link would have a different version number.  The container itself also has a version number, which corresponds to the highest numbered link in the container.

Versioned Iterators go along with the versioned container.  When you request an iterator from a container, it gives the iterator a version number which corresponds to the current version number of the container at the time of request.  The user requesting the iterator can also request a different version number.

Here’s what our data structure might look like if it were versioned:

Fig. 4 - Chocolate Cake for Breakfast with Versioned Containers and Iterators

This ends up working out pretty cool.  Mr. Cosby can request a versioned iterator of the view when his show begins that displays the model as it is when his show starts.  Let’s say that his iterator is version 1.  That iterator traverses the list by only following links where the version number is less than or equal to the version number on the iterator.  So it first goes to “eggs”, then follows link 1 to “milk”, then follows link 1 to “wheat”, then ends.  It can be doing this at the same time that another user is changing the data structure, first by inserting “chocolate,” which creates the version 2 link from “milk” to “chocolate” and the version 2 link from “chocolate” to “wheat,” and later by inserting “sugar” and “frosting” as version 3.  A version two iterator on the structure would start with “eggs” then follow the version 1 link (remember – less than or equal to the iterator version) to “milk.”  But then it would follow the version 2 link instead of the version 1 link, so now it goes to “chocolate” instead of going directly to “wheat.”

The same goes for the version 3 iterator, which gives us everything in the data structure.

There’s a couple of issues you have to deal with when you implement a structure like this.  First off, you need some sort of a scheme to go through the structure and prune it of old traversal versions.  If I remember correctly, a scheme that will work to do this is to have the container itself remember how many users are accessing it and what versions they are at.  When one iterator goes away, the iterator should report this back to the container.  The container then looks to see if that iterator is the lowest-version-number iterator that it knew about.  If it is, the container can go through and prune all of the links that are versioned at that number and below, as well as nodes in the structure that are only included in the structure by links at that version and below.  So there’s a little bit of housekeeping that has to go on, but the container should be able to do this after iterators go away.

In other words, once Mr. Cosby’s show ends, the data structure that previously looked like Fig. 4 should end up looking more like Fig. 3.

Another problem to consider is this:  If the data structure lives for a long time and has lots of accessors, it is possible for the version numbers to overflow.  The overflowing isn’t necessarily a problem, though, as long as you keep track of what is really the oldest version in the data structure.  Another way to do this is, as you prune the table, you can take the liberty of reversioning the table if there are no accessors to the table.  Depending on your situation, you may never have a chance to lock the whole structure in order to reversion it, but the first option should be workable.

Lastly, since you have to version the links themselves, you might not be able to directly use standard containers; for example, if you are using C++ you might have to create your own linked list template with a list of versioned next pointers in each node, instead of implementing your versioned list container in terms of the STL list container.  I never tried this so I’m not sure how it would work.  When I did this, I did it using a tree container that was implemented in STL style, with versioning in the pointers and iterators.  It was pretty cool.

I went to the doctor again today to see him about my back. I did not tell you about my back before, because frankly my personal health is none of your business, Mr. Internet.

I went to see him again, because the first time I saw him he told me if it was still hurting in two weeks to call and make another appointment.  So after two weeks when it was still hurting I called to make an appointment and they said, “Oh, he is on vacation.”  So I waited two more weeks to see him today at 10:00.

HAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHA!!!!!!!

Actually, that is when I was scheduled to begin sitting in the public waiting room.  Once I checked in they informed me that it was about a one hour wait, which in retrospect was incredibly optimistic, percentage-wise, as I waited over 90 minutes for my name to be called.

Of course, that was the amount of time you had to wait to go to the private waiting room, where the wait times are only about 1/2 as long.  I waited there for another 45 minutes for the doctor to come in.  I will now quote for you the entire session.  Okay, not really.  But pretty much.  Okay, here goes:

Doctor:  So, your back still hurts?

Me:  Yep.

Doctor:  How long has it been?

Me:  6 1/2 weeks.

Doctor:  Correct.

(That was the quiz part, to see if I’m really the correct patient.)

Doctor:  Okay.  I think you should go to physical therapy now.  Here is a referral.

There is no possible way my actual appointment lasted longer than five minutes.

But hey.  Why get mad?!  I decided before I even got there that I was not going to be one of those people that complains about the wait time, because who cares?  Not the receptionist!  So instead I said to myself, “What can I learn from this?”

And then it hit me – I can apply this to my own profession!  And so here you have it – the MDMethod for Software Development Estimation ©.

It is mostly like other kinds of software development estimation, which is to say, some combination of voodoo, magic, and recently used hay.  Here are the key points:

• There is no correlation between when something could be delivered, when it should be delivered, and when it will be delivered.
• Feel free to ignore reality and set unrealistic expectations.  Use an attractive woman to do this; her clothes should show cleavage and she should sit at about mid-torso level of a standing average-height man.  Teach her the expression “Blinking Bambi Eyes” – this should be used once expectations have not been met, at which point she simply says, “Yeah.  I’m really sorry about that!” in a sympathetic voice that seems sincere.
• Actual delivery of value can be offered within a confidence interval of reasonable estimate time plus a fudge factor of about 3000%.  The doctor in my case beat the margin of error by about 300% – it took 135 minutes to deliver to me my five minute appointment, which is a margin of error of 27 times or 2700%.

Here’s how I might do this in practice:

• Since I am not an attractive woman, I hire an attractive woman to set unrealistic expectations for me.  My wife is the best candidate for this job, but I respect her too much, so I will have to settle for another less-than-ideal candidate.  From this point on I will refer to this person as “Janice,” which seems like a good receptionist name.
• Let’s assume that you represent the company.  You ask me to deliver a feature.  I tell Janice to inform you that I could get started on that in two weeks and that it should take about a week to implement.
• When two weeks pass and you ask Janice how I am doing, she says, “Oh, he is on vacation.  He will be back in two weeks.”  When you say, “Wow, that is upsetting, because he said he could start on this in two weeks, two weeks ago,” Janice will then deploy Blinking Bambi Eyes and say, “Yeah, I’m really sorry about that!” in a sympathetic voice that seems sincere.
• In two weeks when you come back and asks Janice how I am doing, she says, “Yes, he is starting on that today.  The wait time for that is three months.  We will let you know when he is ready!”  She says this in a cheerful and playful tone and does not necessarily mind if you happen to notice her cleavage.  When you say, “Wow, that seems like a long time to wait; I wish we had known it would take this long earlier,” Janice again deploys Blinking Bambi Eyes and says, “Yeah, I’m really sorry about that!” in a sympathetic voice that seems sincere.
• After you wait for four months and I still have not started, you go to see Janice, who does not try to conceal her cleavage while you express your dissatisfaction at the fact that you are still waiting for me to start on your project.  At this point the initial two week wait doesn’t seem so bad now does it!  Anyway, Janice again deploys Blinking Bambi Eyes and says, “Yeah, I’m really sorry about that!” in a sympathetic voice that seems sincere.  By now you are just a little bit irritated – not really mad, just slightly irritated – because you have been sitting in the waiting room for four months.  But how can you be angry at Janice?  The face!  The Blinking Bambi Eyes!  The cleavage!  It is not her fault anyway!  So you just keep waiting.
• Finally, after four and a half months, Janice happily informs you, “Matt is nearly prepared to start thinking about when he might be able to begin working on your project now!”  This excites you so greatly that you forget all the time you’ve waited.
• Six weeks go by, but this is nothing.  You are surely on the home stretch.  Finally, I show up.  I say, “Hey, you know that project you asked me to do?”  You say, “Yes.”  I say, “When did you ask me to do that?”  You say, “Six months ago.”  I nod my head because you have passed the test – you are indeed the person who asked me to do this project.  Then I say, “Well, I did it.”  And then I leave.
• You are thrilled and happy to pay lots of money for my professionalism and high quality of service.

This seems like such a good idea.  I am going to start using this technique at Mozy right away.  I will follow up with all of my success stories so you know how well it is working.

P.S.  I was just kidding about the cleavage.  I am happily married.  I did not notice all of that cleavage.  At all.

My inbox is overflowing with emails from people asking, “Matt, how can I be more like you?”

Honestly, that is only sort of true.  Some of the emails say, “Lose 30 pounds in 12 minutes!”  And some say, “I am the prince of Nigeria!”  And some say, “I am lonely and looking for a purely physical relationship!”

More honestly, that pretty much comprises the bulk of the email I receive.  Nobody has actually asked how to be more like me, strangely enough.  But that day is surely coming, and since I am a computer scientist, or at least since USU says so, I could start with a list of books that you can read if you want to become a true nerd and rule the world the way I do, which is to say, not.

(So, in fairness, I haven’t actually read all of these or owned them. There are some that I haven’t read, but I read one like it; those are marked in blue. There are some that I haven’t read but think I should; those are marked in gray. There are some that where I read one like it, but I want to read that particular one – they are bluish-gray. And I didn’t list the probably 40-50 CS books I own or have owned and read that are not shown here. So cut me a break.)

Math and English

First off, in order to be a good software engineer and computer scientist, you have to be a good mathematician and a good writer.  Sorry.  You simply can’t be a competent software engineer without a solid mathematical background, and you can’t be an effective one if you can’t figure out how to express your ideas clearly in writing.

Learning to Program

Your next step is to learn basic programming concepts.  In my opinion, you should learn two languages at this point:  Python and C.  Python is a good beginning language, very easy to create real applications, easy to learn, and very versatile and useful in the real world.  C is the fundamental systems programming language.  Knowing Python and C will allow you to program just about anything and gives you a good fundamental background.

Computer Science Fundamentals

Having learned how to write basic computer programs, now is time to get into the science of computer science.

Programming Technique and Methodology

How to write software well.

General Programming

Two other languages you might want to know are C++ and Java.  C++ is much maligned, but widely used, especially for systems applications, games, and other high-performing software applications.  Java is an abomination in every sense of the word.  But it is also very popular and good to know.  If you are going to learn Java, you should also learn JNI, so you can get from Java back to C and get some real work done.

Systems Programming

If you are going to do systems programming, you’ve got to know the specifics of how to program to the environment in question.  It’s worth noting here that the UNIX books basically cover POSIX, which applies not only to UNIX but BSD, Linux, and Mac as well to varying reasonable degrees.  I’ve also included an internals book for the big three platforms (Windows, Linux, and Mac).  And if you are going to program for Mac, you will probably want to learn another language: Objective-C.

UNIX/Linux
Windows
Mac OS X

Other

Every good software engineer should clearly understand open source; hence The Cathedral and the Bazaar. You will find you are missing out on a number of inside jokes if you don’t read The Hitchhiker’s Guide to the Galaxy. And everyone should read The Code Book, simply because it is so interesting.

Image Credits: amazon.com and barnesandnoble.com

The movie “French Kiss” with Kevin Kline and that one chick is one of me and Amber’s favorite VHS movies.  (In our house, there are three time periods to movies – DVD movies, VHS movies, and pre-VHS movies.  No Blu-Ray yet.)  I like it, but the reason is not because it is a romantic comedy with that one chick in it.  And the reason is not because it says “French” in the title and I’m trying to suck up to my boss, Luis, who lives in France.  No, I like it because it has some really, really funny Canadians in it.  Like Strange Brew!

No.  Actually, not.  But it is a pretty funny movie.  And there is this part, which is not funny, where Luc is explaining to that one chick about what makes wines different from each other – that they take in elements from their environment that contribute to their unique flavor and texture.  For example, if you spill some wine in the dirt, and then scoop it up with your cup and drink it anyway, you will probably get some dirt crumbs in there, which changes the texture from “smooth” to “gritty” and just tends to get you even more drunk than you were before.  And that’s why I don’t drink.

Anyway, I was thinking about that today, and how similar that is to software engineers.  See, software engineers, also, take in elements from their environment that make them unique.  In fact, an easy way to say this is that software engineers who live in one part of the world are better than software engineers who live in another part of the world because of their superior geography.

For example, you might have one software engineer, let’s call him Steve.  He might live in an peninsula that is called a valley, surrounded on three sides by ocean, with real estate that is unreasonably expensive.  Or you might have another software engineer, let’s call him Bill, who lives in a place where it rains all the time, in the land of Nirvana and Alice In Chains and Soundgarden and Pearl Jam and Starbucks.  Or another guy, named Nathan, who lives in an area with tight roads that wind all over creation, also with expensive real estate, elitist professional sports teams, and where nobody ever pronounces the letter “r”.

Compare these people to someone named Drew, for the sake of argument.  This guy, also a software engineer, lives in an area with big mountains, lots of Mormons, and secret sand dunes where someone exactly like myself can go riding motocross bikes.

Anyone can see that there is simply no way Drew will ever be able to measure up to the likes of Steve, Bill, and Nathan.  I mean, just take into account the geographic considerations!  How can big mountains ever hope to make you the kind of software engineer you could have been if instead you had been surrounded by ocean or Soundgarden?  The simple answer is:  they can’t.  I mean, be serious.  This, my friends, is the effect of geography on software engineers – geography can make the difference between you being really excellent and simply mediocre.  Secret sand dunes are really amazing, but they obviously cannot make you into the kind of software engineer you could have been if instead you were to replace those dunes with expensive real estate.

Mozy is hiring.  I mean, Decho is hiring.  Decho is the silly name given to replace the awesome of Mozy.  We still call it Mozy, we can’t help it.

Anyway, we’re hiring.  Specifically, my team, the client team, is hiring.  And since Mozy decided to make me the manager of the Windows client team, that means I’m participating in the interviews.  This is stressing me out, because I feel like I am deciding the fate of people.

The process of getting hired at Mozy (arrgh, Decho) goes something like this:

• Apply and submit a resume.
• If we like your resume we will do a phone interview.
• If you do well in the phone interview we will bring you in for on-site interviews.
• If you do well in the on-site interviews we will assign you a homework assignment.
• If you do well on the homework and you are the best candidate we have for the position, there’s a decent chance you’ll get an offer.

Development work at Mozy is primarily done in C++.  Objective-C on the Mac side.  Pretty much you have to know C and C++ and/or Objective-C to get a development job, unless you want to work for the web team, using Ruby.  But those guys are kinda weird.  They sit on a different floor in the building and everything.  We’re not talking about those guys.

So during the phone screen, we ask you to rate yourself on C++.

We explain the rating scale like this:  0 means you are my father, waiting for this computer fad to go away, and you haven’t really heard of C++.  1 means you wrote Hello World in C++ once, and might be able to do it again today.  On the other end of the scale, 10 means your name is Bjarne Stroustrup, or maybe Herb Sutter or Andrei Alexandrescu.  9 means you have written books on C++; 8 means you could write a book on it, or teach courses on it.

Please, people.  Do not flatter yourself on the C++ scale.

I interviewed with Google once, over the phone.  They asked me this same question with pretty much the same scale, except they made no mention of my father.  I told them I was a 6 or a 7.  And I actually have taught courses on C++.

Lately we’re asking people this question and invariably we’re getting people saying, “Oh, based on that scale, I’m a 7 or an 8.”  Even kids in college.  Now I’m not saying that kids in college can’t be a 7 or an 8 – just, keep in mind, we’re not seeing a lot of true 7′s or 8′s among experienced professionals.  I’m just sayin’.

When you say in your interview, “I’m a 7 or an 8,” what you are telling me is this:  “I know C++ better than you.”  Now, you don’t probably know me personally, so hey, maybe you are better.  All I’m saying is, you’d better be ready to prove it when we bring you on-site.

For example, you’d better know at least most of this stuff:

• How to define a template class
• How to correctly define the assignment operator for a class
• How to overload the insertion and extraction operators for a class you define
• How to iterate over an STL vector
• Whether ++i is better, worse, or the same as i++, performance-wise, and why
• What methods the compiler will create for you if you don’t create them yourself, and the implications of this
• How to indicate in your developer contract whether a class is meant to be subclassed, which methods are overrideable, and how you insist that only subclasses can be instantiated
• How to specify default values for parameters

If you are a 7 or an 8, you probably should have read most of “The C++ Programming Language” and/or “Effective C++” and/or “Advanced C++” and/or a number of equivalents.  Having read “Design Patterns” would certainly help, although lately those have kinda lost their glimmer and so I don’t weigh on those like I used to.

Also:

• What const and mutable mean

Yeah.  const.  Don’t be like the self-proclaimed C++ expert I worked with at Enterasys Networks, who told the whole company he was the go-to guy for C++ questions, who, when asked, “Why does it say const after this method declaration?” replied, “Oh, they just do that a lot in C++; it doesn’t mean anything.”  Yeah.  Don’t be a doofus.

Don’t try to impress me by saying you are a 7 or an 8 if you aren’t.  Really – you don’t have to be a 7 or an 8 to get a job at Mozy (Decho…hrm).  If you say, “Oh, I’m probably a 5,” that tells me you are a good, solid C++ dude (or dudette, whatever) that knows how to write decent C++ applications.  You’ll probably get asked to come in for an interview anyway.

When we bring you in, it is my job (and Cody’s) to figure out how much of C++ you really know.  We will start out at the point you specified and go from there.  If you are really a 5 or a 6, but you said 7 or 8, you will feel like we’re being very brutal on you.  Hey, you are the one who said you knew your stuff.

Oh – one more thing.  Some of you experienced hires don’t think you should have to go through all of this to get a job with us.  Well, we make the rules.  Every one of us that works there has gone through it.  If you think the rules of Monopoly are dumb, nobody’s gonna think bad of you if you decide not to play.  But if you want to play but not follow the rules, well, don’t be too surprised if people take issue with that.  If you’re gonna try to work at Moz – uh, Decho, at least for my team, just go through the process like everyone else.

Okay, I feel better.  Whew.  Oh, and by the way, if you really are a 7 or an 8 (or better), I have a link for you.

After reading Jeff Atwood’s blog post “We Are Typists First, Programmers Second” on Coding Horror, I thought I’d better go see what my typing speed was.

I took the same online typing test that Jeff Atwood took, and managed to beat him:

We’d kinda hope that someone who writes software for a living could type with a reasonable speed. I’m curious to know if my mom, who types as part of her profession but is a non-programmer, could beat me.

Even more, I’m curious to know what my typing speed is when writing code. If you were to do a test like that, “mistakes” could be calculated by the number of syntax errors your code generates if you try to compile/run it. However, I’m not sure what a “word” would be, in calculating words per minute.

Surely your familiarity with the language would make a difference in your “speed.” What I find a bit interesting about this discussion is that your typing speed in this case does not necessarily equate to your delivery speed.

For example, if you, like much of the computing world, are a Javahead, in my opinion you have a bit of baggage to overcome in order to attain a reasonable delivery speed. Java’s mantra seems to be, “Why do something in one step when it can be done in two – or five?” Thus if you are a Java programmer, you’ve got some verbosity to overcome in order to attain productivity. Fast typing speed matters for you.

On the other hand, if you are a bit more sane and prefer a language like Python, the language is actually helping you out here. It is so easy to arrive at functional code in Python that perhaps the language makes up for typing shortcomings that a programmer might have.

What about a language like C? C is admittedly terse, but it doesn’t do a lot for you because it is comparatively low-level. If you don’t have libraries in hand to do what you need, writing them yourself kinda removes any advantage you may have gained because of the terseness of the language. Of course C is excellent based on other factors.

I do agree with the post though – typing is important to programmers. It is important for an additional reason – and that is because good software engineers should be expected to generate documentation – design documents, API documents, test cases, and SDK documents like tutorials and explanations of sample code. In short, there’s a lot more typing to be done in a software engineer’s job than just the typing of code.

Now, many of you are asking, so what does it mean if you type nearly 90 words per minute AND are not handicapped by a blind adoration for Java? What if you are a fast typist AND you prefer Python?
Well! That describes me quite clearly! And apparently, it means little. Sorry.

What we know so far: