The software development final exam: Computer Architecture and Operating Systems(daemonology.net)
daemonology.net
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
12 comments
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.
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.)
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.)
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.
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.
Indeed, presenting this more 'guide to interesting things you should know' rather than 'here's an exam I've condescended to set for everyone dumber than me' would have worked out much better.
Maybe B-player is harsh but in my career I've worked with some very good programmers and some real stars. When I talk to the very good programmers I always feel dumber, but whenever I talk to the real stars I always feel smarter myself (though heaven knows that's not actually true). This seems to fall firmly in the "very good programmer" category.
Maybe B-player is harsh but in my career I've worked with some very good programmers and some real stars. When I talk to the very good programmers I always feel dumber, but whenever I talk to the real stars I always feel smarter myself (though heaven knows that's not actually true). This seems to fall firmly in the "very good programmer" category.
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.
Remembering the relation of a bipartite graph to graph coloring helped me coming up with an algorithm fairly quickly. Although that might in fact require a little familiarity with graphs and the associated terms. I guess most of my former fellow students who didn't hear a graph theory lecture won't really remember that.
"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).
I don't think the question as phrased is about having a basic idea of how multiprocessor systems work. It's a question about naming(!) of the component parts of a specific protocol. That's trivia. It's as if the question about the TLB was about the acronym rather than the function.
(So what's a good question to see if somebody understands cache coherency? Maybe describing a problem caused by cache-line contention, and asking for an explanation and fix to it?)
(So what's a good question to see if somebody understands cache coherency? Maybe describing a problem caused by cache-line contention, and asking for an explanation and fix to it?)
"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!
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!
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.
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.
Okay, so I agree that Colin's exam might be a bit too specific and that he might have phrased certain things poorly, i.e. "lucky enough to be working within a narrow area where your deficit doesn't matter". I think either his experiment will help him discover that "luck" (i.e. statistical distribution) doesn't lean the way he assumed or -- and this is more likely -- he'll obtain biased results because a lot of people will refrain from sending bad results.
That being said, I honestly prefer being judged by someone as accomplished as Colin Percival than hiding behind the attitude that we should not judge other people's abilities.
Let's face it, there's an abundance of downright bad and mediocre programmers. There aren't that many top-notch programmers, although each of us would love to think we're among that small group. This is what motivates us to speak out against any attempt to measure and assess abilities, especially if such an attempt is likely to rank us low.
I'm not ashamed to admit that, so far, I haven't been able to formulate an answer to more than 5 questions out of 10 he posted so far. While I freely admit that I don't consider myself to be a programmer in Colin's league, I think that's really beside the point here.
My knowledge is cached: what I work with all the time is easier to recall; what I've worked with or read about, but I'm not using all the time is not as easy; and, of course, there's a ton of things I don't know, have never worked with or read about. This means that I don't feel confident talking about B-trees without consulting Internet, but since I read about them previously, I do remember that they're a form of search trees and that databases use them (or their variations) a lot.
What's the point of this whole rant? Let's bottom-line it. I'm probably not as good as Colin overall and I'm definitely not as good as he is at what he, specifically, does. That doesn't mean I should feel threatened by his exam. Nor does it mean it has no validity whatsoever. Nor does it mean that Colin is "difficult to work with" or fits any specific personality type.
Those two claims about Colin's personality and intentions are what really bothered me about your reaction. I'm not a fan of straightforward ad-hominems, but I detest veiled ones even more.
That being said, I honestly prefer being judged by someone as accomplished as Colin Percival than hiding behind the attitude that we should not judge other people's abilities.
Let's face it, there's an abundance of downright bad and mediocre programmers. There aren't that many top-notch programmers, although each of us would love to think we're among that small group. This is what motivates us to speak out against any attempt to measure and assess abilities, especially if such an attempt is likely to rank us low.
I'm not ashamed to admit that, so far, I haven't been able to formulate an answer to more than 5 questions out of 10 he posted so far. While I freely admit that I don't consider myself to be a programmer in Colin's league, I think that's really beside the point here.
My knowledge is cached: what I work with all the time is easier to recall; what I've worked with or read about, but I'm not using all the time is not as easy; and, of course, there's a ton of things I don't know, have never worked with or read about. This means that I don't feel confident talking about B-trees without consulting Internet, but since I read about them previously, I do remember that they're a form of search trees and that databases use them (or their variations) a lot.
What's the point of this whole rant? Let's bottom-line it. I'm probably not as good as Colin overall and I'm definitely not as good as he is at what he, specifically, does. That doesn't mean I should feel threatened by his exam. Nor does it mean it has no validity whatsoever. Nor does it mean that Colin is "difficult to work with" or fits any specific personality type.
Those two claims about Colin's personality and intentions are what really bothered me about your reaction. I'm not a fan of straightforward ad-hominems, but I detest veiled ones even more.
Well said, but I'm still not inclined to send him my non-answers so that I can deliberately enjoy the feeling of inadequacy.
The author never judges whether someone is a valid software developer or not. He ASKS why people who work as software developers don't know the answer to (in his opinion) basic questions. Obviously, you would have to read the whole sentence and not just a part of it to understand the question asked here. For your convenience:
"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 — most likely you're either you're missing something you really should know, or you're lucky enough to be working within a narrow area where your deficit doesn't matter."
"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 — most likely you're either you're missing something you really should know, or you're lucky enough to be working within a narrow area where your deficit doesn't matter."
Not judging? "... most likely you're either missing something you really should know, or you're lucky enough to be working within a narrow area where your deficit doesn't matter."
Talk about reading just part of the sentence.
Talk about reading just part of the sentence.
[deleted]
Note that this refers to all four parts, not just the second. In this case one might lack detailed low-level knowledge of threading and a particular library used to do so on POSIX systems which may have no relation to performance in the other parts.
[deleted]
I liked the part of your comment where you cropped the rest of his sentence: "— most likely you're either you're missing something you really should know, or you're lucky enough to be working within a narrow area where your deficit doesn't matter."
I didn't crop that so as to take it out of context, I cropped it to keep the quote short. I don't agree with the bit you added either.
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.
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.
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?
Is this what we are coming to? The dumbing down of software development? Have the mainstream anti-intellectualism been spilled over into software development?
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".
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".
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.
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.
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.
"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.
Programmers affect and determine the operation of the computers their code runs on much more than a driver driving inside the lines.
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).
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).
I am pretty sure pilots don't master fluid mechanics in detail.
[deleted]
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...
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
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
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.
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.
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).
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. :-)
Thank you for that. :-)
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.
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.
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.
"But that doesn't mean it's a useless question."
Is it a useful question, just because it was asked?
Is it a useful question, just because it was asked?
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.
I'll admit that I couldn't answer many of these questions off hand; I hope the criticism doesn't come across as bitter.
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.
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.
A good point, considering a large portion of practicing programmers are self-taught.
Is this true in 2012? I would love to see a study or something. Not doubting you, just curious.
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.
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.
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.
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.
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.
Some of these questions aren't even necessarily relevant in getting a computer science degree let alone software development.
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?
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?"
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.
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.
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.
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).
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).
I did say that some of the questions are "type into google" questions. The bipartite-graph question isn't -- but most people will have never seen that particular question in class, either. That one is a "can you take material you should know and come up with something new" question... just like the TLB question in part 2 and another question in part 3.
I really don't think any of the questions are "type into google". For instance, take the question of the run time of quicksort. Someone could google this, but how well would their answer stand up to the slightest bit of probing if they didn't understand it?
For instance, suppose someone doesn't really remember the quicksort algorithm, but looks it up and is quickly able to determine the run time by analyzing the algorithm. To me, that's pretty much as good as knowing the algorithm's run time off hand. Maybe even better. For all I know, if you changed the question just slightly and ask if the run time has changed, the first student has shown the ability to analyze the run time of an algorithm - the second student's ability to do this is still unproven.
For instance, suppose someone doesn't really remember the quicksort algorithm, but looks it up and is quickly able to determine the run time by analyzing the algorithm. To me, that's pretty much as good as knowing the algorithm's run time off hand. Maybe even better. For all I know, if you changed the question just slightly and ask if the run time has changed, the first student has shown the ability to analyze the run time of an algorithm - the second student's ability to do this is still unproven.
how well would their answer stand up to the slightest bit of probing if they didn't understand it?
These aren't necessarily the questions I'd use in an interview -- I don't have the luxury of reading someone's answer and then probing further.
These aren't necessarily the questions I'd use in an interview -- I don't have the luxury of reading someone's answer and then probing further.
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?
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.
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.
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
edit: Ignore. I'm wrong, see below
I'm not doubting what you say, but could you elaborate on why Fortran is different?
I could understand a difference for two-dimensional (or more) arrays, where different languages lay-out the array contents in memory differently. Does Fortran lay-out the contents of one dimensional arrays in an unusual way?
I could understand a difference for two-dimensional (or more) arrays, where different languages lay-out the array contents in memory differently. Does Fortran lay-out the contents of one dimensional arrays in an unusual way?
Sorry, I screwed up. I skimmed the question and mis-remebered it when making my post. I thought the question looked like:
for(i=0...
for(j=0...
A[i][j]=0; for(i=0...
for(j=0...
A[j][i]=0;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.
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.
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.
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.
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).
You'll hit it every time given a typical x86 4KB page size and a step of 1024*sizeof(double)=8KB.
I would guess that the example was explicitly contrived so that prefetching would be useless.
I would guess that the example was explicitly contrived so that prefetching would be useless.
I would guess that the example was explicitly contrived so that prefetching would be useless.
Yes -- even if prefetching could happen, the first function would be faster than the second, but I thought removing the whole issue of prefetching would simplify the question.
Yes -- even if prefetching could happen, the first function would be faster than the second, but I thought removing the whole issue of prefetching would simplify the question.
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.
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.
I'm asking everybody to submit answers, and there are plenty of people submitting "I don't know"s.
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.
Quite true -- I'll definitely have to be careful in how I interpret the data. I'm hoping that the issue I'm most interested in -- comparing how people do on different questions, and comparing how different people do, will be less strongly biased by the poor sampling method.
What's the best textbook for this material (caching, concurrency etc.)?
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.
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.