The code running on the CPU isn't the only thing the computer is doing in that one second, the X86{,_64} opcodes we could capture aren't necessarily exactly what the CPU is doing, and code being run by extra controllers and processors isn't likely to be accessible to anyone but the manufacturer.<p>In 1989, we'd've also been looking at code running on a single core with a single-task or cooperative-multitasking OS (for most home computers, anyhow), with simpler hardware that an individual could completely understand, and it would run at a speed where analyzing a second of output wouldn't be completely beyond the pale.<p>I've analyzed CPU logs from DOS-era programs and NES games. I certainly haven't analyzed a full second of the code's execution; I'm usually focused on understanding some particular set of operations.
This is totally doable. PANDA [1], e.g., takes recordings of full-system execution by recording non-deterministic hardware inputs in a modified QEMU. This is much more compact than a full instruction trace, but you can then replay the recording to produce instruction traces, memory traces, whatever.<p>We recently added some machinery [2] for using debug symbols to map each instruction back to its source line. So, assuming you can get debug symbols installed for every userspace program, every library, and the kernel, I think you could come very close to tying every instruction back to a source line.<p>There are caveats, though – the overhead of QEMU and the recording infrastructure mean you only end up getting around 200 million instructions / second, which is nothing compared to modern bare metal. You could capture a longer trace, though, and do the same thing to get up to the same amount of code executed as on real hardware.<p>If someone wants to try this I'd be very interested to see the results and happy to help answer any questions that come up!<p>[1] <a href="https://github.com/moyix/panda" rel="nofollow">https://github.com/moyix/panda</a><p>[2] <a href="https://github.com/moyix/panda/blob/master/qemu/panda_plugins/pri_trace/pri_trace.cpp" rel="nofollow">https://github.com/moyix/panda/blob/master/qemu/panda_plugin...</a>
This line stood out to me:<p>"It might be shocking if an erroneous program was discovered, but it could certainly happen."<p>Is anyone actually under the impression that the thousands or tens of thousands of components that interact with each other at any given time on a typical desktop computer would be "correct", even for generous definitions of that word (well, that are less generous than "most of the time generally do what the designers set out to, generally, accomplish")?<p>It seems to me that all components in computers of at least the last decade, not to mention their interactions, are so complex that they almost certainly are full of small and not so small errors; they are deployed as soon as the most obvious and obnoxious errors have been removed but there must be heaps of things going on that most people would agree on are "errors". I'm continually amazed that we manage to build (or rather, 'assemble') systems that most of the time work at all.
I think perhaps some alterations would really be necessary to make this analysis tractable. He wrote this in 1989, so how many doublings in performance have we had since then? The duration should be adjusted accordingly, so analyze everything the computer does in say a thousandth of a second, or even less.<p>Another thing is that he was surely envisioning a program written in C or the like - a straightforward translation from the program to executable with some optimization, and all of the program optimized to the same level. With JITs, one would have to take a few steps back to determine whether the code had been optimized because the JIT had determined it would be a good idea, not optimized because it just wasn't important, or possibly not optimized _yet_ simply because the JIT had not seen enough of the program to decide whether to bother.<p>There's also the idea of memory hierarchies influencing how things are done in ways not necessarily obvious to someone focusing on the code being executed at the moment. I think any memory hierarchies (I'm thinking here of L1, L2, L3 caches in modern processors) have a much greater impact on how optimal code is written now than it was back then. Perhaps the code one examined could be done better for itself, but was done less optimally in order to not have detrimental effects on other code in the program that was more important (like perhaps displacing stuff that other code had cached).<p>I'm not really sure that this exercise would be worth it today, except in special cases, trying to wring every last bit of performance out of a program after less tedious avenues had been exhausted. I can't say that I have had a whole lot of need for such performance.<p>This idea of close analysis of a part of one's program does remind me of something else though: the idea that one should run one's program in a source-level debugger and step through every line of code one can get to, trying to get 100% code coverage, and contemplate the state of the program at every step. I think this would uncover many latent bugs, hidden assumptions and the like in most programs. I guess what I am trying to say here is that correctness is more important than performance, and perhaps easier to do in today's world.
<i>"The computer will execute several hundred thousand instructions during that second; I'd like you to study them all."</i><p>That <i>"several hundred thousand"</i> has grown by about four orders of magnitude since then, even more if we consider multi-threading, GPU, CPUs in the network controller, etc.<p>Because of that, that task has become a lot more work. It is doable for 10^5-10^6 instructions (certainly for someone with Knuth's work ethic), but for 10^9-10^10 instructions, I guess even he would need to write tooling to do it.<p>A problem with tooling is that it may hide interesting behavior that the programmer writing the tooling isn't aware of in the 'misc' category of code executed. I fear that may defeat the purpose of this exercise.
Fascinating question, reminds me of this one that made HN almost two years ago: “What happens when you type Google.com into your browser and press enter?”<p><a href="https://github.com/alex/what-happens-when" rel="nofollow">https://github.com/alex/what-happens-when</a><p>Would love to see Knuth's Challenge setup in a repo for collaboration.<p>HN Discussion on the above link:<p><a href="https://news.ycombinator.com/item?id=8902105" rel="nofollow">https://news.ycombinator.com/item?id=8902105</a>
TEMU is a tool based on QEMU that is (was?) aimed at doing exactly that, a dynamic analysis that captures instructions executed in every process (including the kernel):
<a href="http://bitblaze.cs.berkeley.edu/temu.html" rel="nofollow">http://bitblaze.cs.berkeley.edu/temu.html</a><p>The problem of course is that this is not analyzing the physical machine but rather the behavior of programs in a virtual environment.
> There are definitely people who profile their applications ... the entire system, though? Is there a utility I can use to log every instruction performed in one second for an operating system running on bare metal?<p>Kinda. oprofile and later perf use the hardware's performance counters. So, it's sampled and therefore it's not "every instruction performed" but the scope is indeed the entire system. If your hardware doesn't support it, then the kernel has a sampling feature on a timer. It's IMO representative and probably the sanest way to accept the challenge.<p>But Knuth questions make me wonder: how could we possibly reason about correctness from the samples? We'd be better off following the trail of breadcrumbs back to the source unless he means something terribly specific beyond "correct or erroneous".<p>> Can it be done with an emulator like QEMU?<p>Yes, that's probably an alternative if sampled isn't sufficient.
I like the idea of making a trace through a complex app (such as a browser) and the kernel and listing off all the open source developers whose code it passes through. Just how many people contributed to my 1s of Youtube cat video watching pleasure?
This just makes me miss SoftIce. Just hit ctrl+d and be immediately dropped into exactly what your machine is doing at any time.<p>Of course, just doing this would be illegal on most proprietary operating systems.
Analyze all CPU instructions even for one second is very hard. Good place to start is Dtrace FBT provider - capture and analyze all called functions for one second.<p>Perhaps it will be some useless work, which should not be done at all. But CPU time is cheap and programmer's time is expensive.
Reminds me of how Stanisław Lem went virtual and wrote fictitious reviews of a non-existent books that were far too vast to actually exist in the real world, including one called "One Human Minute" [1]:<p>"One Minute", for a faux book by J. Johnson and S. Johnson: One human minute, Moon Publishers, London - Mare Imbrium - New York 1985. The book is alleged to be a collection of statistical tables, a compilation that includes everything that happens to human life on the planet within any given 60 second period.<p>Here are some real reviews of a real book of fictitious reviews of fictitious books [2]:<p>KristenR rated it really liked it.
Shelves: science-fiction, short-stories, male-author.<p>This volume had 3 essays, each with an interesting concept.<p>One Human Minute: Lem has styled this piece as a book review...of a book that hasn't been written. One Human Minute is apparently a Guinness Book of World Records that is completely mundane, yet also amped up on steroids. Imagine a book that is full of tables upon tables and graphs and charts about everything that happens on earth per minute. How many babies are born, how many people get struck by lightning, how many people are tortured by electricity, how many orgasms are achieved per minute...<p>Definitely a philosophical piece, but seemed to be musing about the depravity of the human race. I'm not sure if I missed the point.<p>The Upside-Down Revolution: The evolution of military and warfare...written under the premise that the author has a history book from the future and publishes it in the present as science fiction. I lost interest partway through this one.<p>The World as Cataclysm: I have a fascination with astrophysics. I am fully aware that the bulk of it goes over my head and I have near zero retention, but that doesn't stop me from reading/watching anything on the subject that is remotely geared towards the layman. Simply Fascinating. This piece goes into the probabilities of extraterrestrial life. I don't know what Stanislaw Lem's qualifications are, but as I was reading this I was nodding...uh huh, that makes sense...hmmm, I sense a little research project on Lem.<p>Rich Meyer rated it: really liked it. Shelves: read-in-2014.<p>An interesting trio of science fiction-tinged essays by one of the great science fiction writers. The title refers to one about a book that covers what happens on the planet every minute, and how the book is updated and computerized until it becomes a power unto itself. The other essays follow the search for intelligent life and the chances for finding it, and a look at the history of warfare from the point-of-view of a book from 2150, and manages to make some pretty accurate predictions.<p>[1] <a href="https://en.wikipedia.org/wiki/Stanis%C5%82aw_Lem%27s_fictitious_criticism_of_nonexisting_books#Provocation_and_One_Human_Minute" rel="nofollow">https://en.wikipedia.org/wiki/Stanis%C5%82aw_Lem%27s_fictiti...</a><p>[2] <a href="http://www.goodreads.com/book/show/28771.One_Human_Minute" rel="nofollow">http://www.goodreads.com/book/show/28771.One_Human_Minute</a>
How about use an FPGA for this? Use an architecture and ALU and implement a software which would monitor and output op code and ALU for any given time.