The software development final exam: Computer Architecture and Operating Systems

http://www.daemonology.net/blog/2012-10-09-software-development-final-exam-part-2.html

by cperciva • 14 years ago

61 69 14 years ago

cperciva8• 14 years ago

Some FAQs: I'll be posting the third and fourth parts at 9 AM UTC on Wednesday and Thursday (and submitting the links to HN).

I got just over 100 responses to part 1, and I'm almost halfway through grading them. I'll be sending out a batch of emails (form emails, I'm afraid, to save time) once I've caught up with the part 1 grading.

I will be posting my answers, my grading scheme, and an analysis of the results next week.

I will not disclose any individual's performance (except to them) without their permission.

jsnell2• 14 years ago

Thanks for taking the time to do this, I think it's an interesting experiment (even if one can't read too much into the results due to the sampling bias).

peteretep• 14 years ago

I am enjoying these, but as a poster on your previous thread predicted, you're moving further away from anything resembling what 99% of today's programmers ever see...

Need a car analogy? Fine: you pitched this as "what every driver should know about driving", and you're talking about the intricacies of combustion engines. That is to say, it's interesting, may pin together some pieces of other knowledge, but of no real practical use to anyone who doesn't also fit in to the "and I'm a mechanic" demographic.

Ensorceled2• 14 years ago

I like that analogy but it's worse than you say:

2 of the questions are about drift racing (mutexs) 2 of the questions are about the design of the fuel injection control chip 1 question is a subtle question about the fuel injection control chip

antidoh• 14 years ago

"What every pilot should know" might be a better analogy. Pilots are more directly responsible for keeping their vehicle within safe conditions, and to do that they need to know more about their vehicles than car drivers.

Programmers affect and determine the operation of the computers their code runs on much more than a driver driving inside the lines.

randomdata2• 14 years ago

I really like the first analogy, actually. A driver who knows all the details of how each engine works will be able to choose the car that provides the best fuel economy and performance, but in the end, the driver's status will really only be judged on the style and features of the car they choose.

i.e. the developer who chooses the slower zeroarray algorithm that still completes in reasonable time, but provides a better user interface and better feature set is still the better software developer (but perhaps the poorer computer scientist).

kamaal• 14 years ago

I am pretty sure pilots don't master fluid mechanics in detail.

jrajav• 14 years ago

I'm excited and motivated to learn by these posts, and I can tell others feel the same way, but I share this sentiment. To me, it even seems a little too fair to compare it to drivers and mechanics. It's more like a pitch to drivers about how to be a better car mechanic, when the target demographic actually includes drivers, stock car drivers, car mechanics, automotive designers, motorcyclists, motorcycle mechanics, pilots, submarine engineers, rocket scientists...

thaumaturgy2• 14 years ago

Colin, I've been programming for about 25 years now, in more languages and architectures than I can ever readily remember, and you're making me feel like a noob.

Thank you for that. :-)

nandemo• 14 years ago

That's the spirit! I don't understand why people get so defensive.

I have a BS and a master's degree in CS and I didn't know about MESI cache coherence. And I've never run into it in 7+ years of professional experience. But that doesn't mean it's a useless question. I don't feel compelled to learn all about it right now, but at least I'll get acquainted with the Wikipedia-level facts. One day I might study it further.

mgkimsal• 14 years ago

"But that doesn't mean it's a useless question."

Is it a useful question, just because it was asked?

michael_h• 14 years ago

I have liked these questions, even if I think a few of them are a little narrow. It's certainly sparked a bit of motivation for me. However, the intro blog post is worded very poorly, which is what I'm assuming is causing a lot of the problems. It reads less as a call to personal improvement and more as a shaming/institutional snobbery - whether that was intended or not.

wrath• 14 years ago

I don't know if I should feel "okay" about not knowing the answers or if I should feel "dumb". Is this something as a system programmer today really need to know?

jaimzob3• 14 years ago

No. They can be interesting things to read about, and knowing a little about the themes each question comes from (i.e. how does a processor cache work) will make you a better programmer, but don't worry about cramming your head with trivia such as "what does MESI stand for?"

LinaLauneBaer• 14 years ago

Can someone explain why zeroarray2 is so much slower than zeroarray1 (regarding question 2)? I have profiled the two functions and it turns out for inner for-loop and the line which zeros out the entry in the array are much slower... (optimisations turned off). The only real difference is the name of the variables. Right? Has this something to do with memory alignment?

andyjohnson02• 14 years ago

In zeroarray1 the address to be zeroed goes linearly from 0 to (1024^2)-1. This generates less cache misses because the address is much more likely to already be in the cache, which is in turn because the address only differes by one from the previous value of the address.

zeroarray2 jumps around (0, 1024, 2048, 4096, ..., 1, 1025, 2049, 4097, ...) in a way that intentionally makes life difficult for the cpu's cache manager, and generating lots of cache misses.

dagw3• 14 years ago

Also worth noting that this is language dependent. What you say is true in C (which is admittedly what the question was about), but not true in for example Fortran.

edit: Ignore. I'm wrong, see below

lrobb• 14 years ago

On the one assembly language I vaguely remember, it has to do with how mul is implemented. The 2nd function has to swap out the i repeatedly.

ww5203• 14 years ago

A simple rule of thumb is contiguous memory access = cache friendly => fast operations. zeroarry2's access to memory jumps by 1024 for every assignment. Far apart non-contiguous memory access is not cache friendly at all.

alexberghage• 14 years ago

I'm still learning my way around caches and memory timing, so if someone better educated than I could correct me if I'm wrong, I'd be very appreciative. That said, here's what I'd say:

The core of the issue is with cache-friendly access patterns. This is a simplified explanation, but here goes: CPUs only have so much cache, and the processor needs to keep enough data in that cache that it won't be left waiting for too long before the next batch of data requested from ram is available. To that end, when you access a chunk of memory, the CPU will grab the requested region and then some, hoping that most of your work for the next few microseconds will be within that region. The second implementation jumps by 1024 x sizeof(double) at each access (so, on my system that's 8k), which is plenty far to blow through whatever memory was prefetched with your access, and in so doing force the processor to sit around and wait for another memory location to be cached.

There's another, probably less significant way in which this is a pathological access pattern: alignment. When, in the first implementation, the processor operates on contiguous blocks of memory it is free to prefetch memory in nicely sized chunks that begin and end on convenient numbers, which is important because memory today is nothing if not a tower of multiplexed access -- asking for a few extra bits over the edge of a row, wherever those borders happen to be for your system (probably the width of the memory bus is a good guess), may not seem like much, but if it means the memory controller has to access a row of ram that it otherwise wouldn't, that involves first writing the data in the starting row, then waiting for the appropriate delay to save that data before switching rows and repeating the process. Looking at zeroarray2 in that context, you're asking the memory controller to save sizeof(double)*8 bits of zeroes, a fraction of a row, at once before moving on to another row only to revisit the first some time later.

Answers to the questions pertaining to memory (rather than concurrency) can all be found in Ulrich Drepper's excellent tour of contemporary memory systems, "What Every Programmer Should Know About Memory" ( http://www.akkadia.org/drepper/cpumemory.pdf ).

edit: fixed accidental italics, added useful additional reading link.

tcbawo• 14 years ago

I believe when traversing memory in a predictable, linear fashion the CPU will prefetch data. I thought the CPUs are smart enough to do that for the more complex examples as well, but maybe not for steps of 1024.

kd0amg• 14 years ago

Intel Core architecture has a stride prefetcher, but it will not prefetch across page boundaries (which you hit pretty often with a 1k step size).

philbarr4• 14 years ago

For those who are reading this and are new to software development, please don't let these questions put you off or take them as some sort of test of your skills. The questions pertain only to the poster's particular CS degree and to his particular experience, which for some reason he thinks is the only CS degree and experience that is valid.

Also note that you will come across people like this quite a lot in the software industry and you have to be careful not to let them get under your skin. They can be very difficult to work with. If you are a team lead and identify someone like this on your team then it can be very difficult to place them and you often have to gently coerce them into their own "special" area where they feel their talents are best used.

arethuza• 14 years ago

"They can be very difficult to work with."

Don't you think that is a bit harsh? From what I have seen of Colin's work and contributions here on HN he seems like a pretty knowledgeable and decent chap to me. I rather enjoyed myself contemplating these questions - although I haven't had the nerve to submit completed answers!

philbarr4• 14 years ago

The red flag was this line in the blog that led to the questions: "If you can't answer the majority of the questions on these four papers, and you're working or intend to work as a software developer, you should ask yourself why".

This assumes an air of authority that the poster clearly cannot posses; that is, he does not have the right to judge whether someone is a valid software developer or not. Someone claiming this level of superiority seems to fit the personality type I described. Of course - I could well be wrong but that's what it sounded like to me.

ilcavero• 14 years ago

great conextualization philbarr, also I would add that CS is just one of the foundations of software engineering but certainly not the only one and many would think not even the most important one.

Having said that if these questions tickle your intellectual curiosity go ahead and figure out their answers, just throw away the belief that you can become a valid/invalid software developer just because you can/cannot answer some questions.

ww5203• 14 years ago

The questions are actually quite basic. It has nothing to do with CS degree. Anyone desires to learn would have learnt them. It just makes you a better developer. And people who know them are not difficult to work with. If you as a team lead feels threaten by people who posses basic CS knowledge, you don't qualify to be a team lead.

Is this what we are coming to? The dumbing down of software development? Have the mainstream anti-intellectualism been spilled over into software development?

philbarr4• 14 years ago

The point is that you can be a software developer without knowing this stuff off the top of your head. Naturally I would encourage anyone who doesn't know the answers to these questions to go ahead and learn them if they want to, but you're probably not going to need them day to day, so his assertion that you're not a software developer unless you can answer his "final exam" is incorrect and demonstrates a certain level of ego I find unsettling.

I didn't say "people who know the answers to these questions are difficult to work with", I said, "people who declare their knowledge as an absolute requirement are difficult to work with".

dagw3• 14 years ago

There is a huge difference between not knowing the answers off the top of your head and not being able to learn and understand the answers given 30 minutes and access to Google. If you fail the former that's fine in my book, if on the other hand you fail the latter then that might be reason for concern.

jaimzob3• 14 years ago

Hear, hear. Obsession with trivia and a supercilious tone are sure signals of a B-player in my experience. "Name and describe the four states in MESI cache coherence"? Sorry, memorising an algorithm for determining if a graph is bipartite pushed that knowledge clean out of my head...no doubt I'm very stupid.

jules• 14 years ago

I thought that the bipartite graph algorithm question was the best so far. It was a question that, in addition to remembering what a bipartite graph is, required a little bit of thinking instead of just rote memorization (if you know what a bipartite graph is you can come up with the algorithm on your own -- no need to memorize that). Question #2 in this set is also pretty good.

dfox• 14 years ago

"Name and describe the four states in MESI cache coherence" is mostly about having at least basic idea of how multiprocessor systems work that is pretty crucial to any seriously meant multi-threaded programming. It's something that anyone who wants to call himself a programmer has to know (or at least have some idea that something like that is happening, which is almost equivalent to knowing how it works, because it's really straightforward).

gjm11• 14 years ago

For what it's worth, I'd never (so far as I can remember) known the four states in MESI cache coherence, but worked out roughly what they had to be; when I checked after submitting my answers, it turned out I was right. And I've no idea whether anyone's ever told me an algorithm for checking whether a graph is bipartite, but I worked one out.

On the other hand, I know nothing about pthreads, made a handwavy guess about that question, and got it very wrong. The underlying failure was a bad guess about the semantics of condition variables. I could whinge about that, but I bet that if I spent more of my life writing multithreaded software -- which is, make no mistake about it, an important skill -- then I wouldn't have made that wrong guess even if I'd still never used pthreads. My answer might still have begun "I've never used pthreads, but ..." but that would have been followed by a better guess than it actually was.

Something may look like a trivia question but give much more information than just "does this person have the information stored in their brain right now?". In this particular case, Colin could (if he chose; he probably has better things to do than go into such detail on the hundreds of responses he's getting) guess that I haven't written much multithreaded software, don't spend a lot of time optimizing things for the memory subsystem but have a good grasp of principles, and am good with algorithms. Not so bad for three trivia questions.

And, whatever cperciva's failings (which may for all I know be many and serious) one thing he certainly isn't is a "B-player". (But then, in my experience talking about "B-players" is itself a bad sign.)

waterlesscloud• 14 years ago

He's definitely not a B-player, but that makes it all the more mysterious why this project is missing the target so badly.

I don't think the questions are awful, though they do tend to have a trivia component to them.

What I think has really happened is that the whole thing is completely mispackaged. By calling it a "software development final exam" and saying it's things every programmer should know, he's set up an idea that it would be fairly broad and comprehensive, when in reality it's fairly narrow.

Plus that terminology is a bit socially off-key since it sets people up to be defensive rather engaging in meaningful discussion.

Ensorceled2• 14 years ago

I graduated with good marks from a great school. And so far I'd have been, at best, 7 out of 10 on graduation day. After 20 successful years in the industry, I might get 4 or 5 depending on time constraints since I'd have to figure out some stuff from first principles.

Some of these questions aren't even necessarily relevant in getting a computer science degree let alone software development.

bentoner• 14 years ago

What's the best textbook for this material (caching, concurrency etc.)?

mdkess• 14 years ago

I found this http://www.akkadia.org/drepper/cpumemory.pdf to be a very good starting point for getting into serious low level development. It's a difficult read, so go through it slowly and with a pad of paper for notes, but very information dense and useful.

ww5203• 14 years ago

There aren't much relationship to OS concepts. The lock question can be arguably related but it's more for concurrency. They are pretty light weight questions.

OS questions would involve process/thread/fiber, scheduling, priority, multitasking, memory management, virtual memory, IPC, deadlock, distributed deadlock, interrupt/signal, input system, output system, GUI system, file system, disk system, IO caching, driver model, kernel space and user space, privilege and non-privilege operation, security model, user/process permission and privilege, file permission, authentication, authorization, etc.

cperciva8• 14 years ago

I was aiming for questions relevant to general-purpose developers, not questions relevant to operating system developers -- and a small number of questions at that.

I covered locking, race conditions, virtual memory, and processes; I think those are much more relevant to most developers than knowing the internals of how filesystems work or how interrupts are routed.

mmcnickle• 14 years ago

I think you have fallen into the trap by following your goal of wanting "questions which are easy to mark as right or wrong". You end up writing questions that are extremely narrow in scope and don't provide any opportunity for any interesting discussion. Anyone could memorise the states in MESI cache coherence, but does that really test their understanding of the material? That so many of the answers are one google away shows how shallow these questions are. All you're doing here is testing knowledge retention.

I'll admit that I couldn't answer many of these questions off hand; I hope the criticism doesn't come across as bitter.

randomdata2• 14 years ago

I did get the feeling the questions were chosen, perhaps unintentionally, to create a natural bias towards those who have a formal CS education.

Contrived example: Someone who came up with a quicksort algorithm independently, and is completely aware of its operating conditions, but chose to call it mysort instead, would be unable to answer the question in the last test despite having all the theoretical knowledge needed.

There is, of course, still something to be said about being able to use terminology that is shared with others, but that changes the nature of the test in ways I'm not sure the author intended.

JoeAltmaier• 14 years ago

A good point, considering a large portion of practicing programmers are self-taught.

geebee3• 14 years ago

So far, I've been enjoying reading these questions. However, I think that the format prevents using them to answer what might be a more interesting question - how long would it take someone with a different (non-CS) academic background to answer the question (with understanding, obviously, not through cut and paste). In other words, rather than asking whether someone knows the answer, ask how well prepared they are to research and understand the question.

cperciva8• 14 years ago

You're misunderstanding the purpose of these questions. It isn't to determine whether you are able to figure out the answers to these questions -- as many people have pointed out, some of these are simple "type into google" questions.

The point is that knowing the answers or being able to figure them out on your own is, I believe, strongly correlated with having a good understanding of the entire area the question is drawn from.

geebee3• 14 years ago

I didn't write the questions, so the purpose of them really isn't up to me. However, I don't really agree that they are simple "type into google" questions.

For example, suppose you let someone google around for a half hour to try to answer the question about how to determine if a graph is bipartite. Now, you spend about a half an hour doing an oral exam to see how well they understand what they just regurgitated.

I suspect that you would see a wide range of performance, but that people with certain academic backgrounds might do much better than others. That's the "more interesting question" that I had in mind.

Actually, suppose someone had never take graph theory came up with a novel but ultimately flawed attempt at an algorithm. That might be a stronger sign of talent in this area than someone who had taken the class and was able to reproduce an algorithm (even if that student showed a genuine understanding of it).

psykotic• 14 years ago

I sent in answers to help with your survey, but I'm highly skeptical of the statistical methodology. You are selecting for people who at least think they know the answers. My prediction is that you are going to see a rosy picture of the state of CS knowledge among software developers, even though the reality is probably closer to the exact opposite.

cperciva8• 14 years ago

I'm asking everybody to submit answers, and there are plenty of people submitting "I don't know"s.

tmoertel• 14 years ago

Even though you asked everybody to submit answers, you should expect people who expect themselves to do poorly to opt out. So your sample, I suspect, is strongly biased toward the answers from people who expected not to do poorly. And that bias is indeed likely to paint a rosy picture of the reality.

The software development final exam: Computer Architecture and Operating Systems

Related Stories