Know your "N"

I once was working on some performance analysis and came to the developers asking how their code was consuming a disproportionate amount of time. At low load, the code was say 5% of non-idle CPU usage, but at high load, the code was now 50%. The developers noted that the code contained an algorithm that was O(n^2), but they had only run n=1,2,...10. My high load was n=1000, which exposed the scaling issues of their code. The developers had done everything right, except knowing the scope of the problem (and to be fair, their code was originally for desktops and I was testing servers).

Another time a developer came and discussed memory limitations, due to using 64-bit counters. I asked about how large the input was and learned it was under a billion elements. Well, a billion fits into 32-bit counters and now the memory consumption is cut by half. (Maybe I need more stories, as this was also in Bit Packing.)

The first step to any good performance analysis is selecting an algorithm, based on the problem (including its size). Bubble sort an array of 10 elements, but not 10,000. In fact, ask whether the problem really requires sorting at all.

I will continue to strongly urge developers to measure the performance of their code, before trying to tune their code. But part of this measurement is knowing the "size" of the inputs.

The Minimum of Computer Science

The NY Times ran an article at the start of last month on what CS education is required for non-majors, Computer Science for Non-Majors. Is the knowledge of how to write a (simple) program so vital to modern work that it should rank with multiplication tables, English grammar, etc? And if so, how much knowledge and in what language(s) should this be taught?

Should someone learn the basics of javascript, so they can add to webpages? Perhaps a little python to do simple processing of data? But probably not C, as the language expresses what the computer is to do and not what the computer should do.

Edit: A strong response to this general question here.