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.
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.
I think we've reached a sort of "chicken and egg" point in computing history where we can only understand any given device with the help of other machines, though not necessarily with AI or Machine Learning.
Maybe that sounds obvious, given that VLSI tools have been around for a long time, but I think the point is that there is no such thing is as full knowledge in this realm and we are already totally dependent on our computing devices to understand our computing devices.
It's an interesting thought - how would one implement this? I think the closest thing that comes to mind so far is the DARPA Cyber Grand Challenge work, some of which is open source (https://github.com/mechaphish) and a good starting point at the software level anyway, where the question was similar in some ways: describe what's happening in this code path at time t, but also take it a step further and generate a patch to fix a bug(s).
>only be performed by other machines
JTAG allows in-device debugging. Of course you need another machine, by some definition, to view the results or you would indefinitely apply recursion.
Our hardware now is so much more complex, what has it gained us? The quick answer is performance, but is it true? What about correctness? Hard to prove either way, but my guess is we've gained a little bit on performance and lost on correctness.
There are more parts of the computer (again, both hardware and software) that are undocumented. Taken as a whole, the system is more capable, but closed hardware and software makes me wonder about capabilities in my computer that serve someone that isn't me.
In other ways it's clearly different; e.g. waiting minutes for a JPEG to decode, as the scanlines slowly appeared one after another.
I don't know how anybody who used a computer in the 80s, 90s, or 00s could say this.
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.
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).
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.
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.
In this post, I presented the idea as if it was "easy", but Knuth seemed to be proposing it as a rather large undertaking. I skipped some parts of his original prompt for brevity, but since you bring this up, I can summarize a bit more here. I also found a copy of the address in PDF form online [0], if you want to read the whole thing. This is from the last few pages.
He compared this task to researchers who documented every square meter of a large tract of land to see how different factors affected plant growth. He also mentioned a study of 250,000 individual trees in a rain forest. It's not supposed to be easy.
Yes, we've doubled many times since then, but our power to analyze large piles of data has also improved dramatically.
> I'm not really sure that this exercise would be worth it today
I think it really depends on what kind of system you are going to analyze. He was probably thinking of big systems running a school or business back then. These days there are just so many more types of machines. Most are probably not interesting at all. Maybe some kind of life-or-death devices, though?
> correctness is more important than performance
One neat thing about this kind of lowest-level analysis is that you can probably check on both at the same time.
[0] http://www.sciencedirect.com/science/article/pii/03043975919...
In Carl De Marcken's Inside Orbitz email [1] he has the following item:
> 10. ... We disassemble most every Lisp function looking for inefficiencies and have had both CMUCL and Franz enhanced to compile our code better.
In 2001 there was a series of three panel discussions on dynamic languages [2] that are an absolute goldmine: about six hours worth of listening, with various luminaries discussing deep ideas and fielding questions from the audience. Knuth is cited several times on different topics. This is also where I learned about the idea of stepping through every line of code you can get to (Scott McKay brought this up in the panel on runtime [3]. You ought to be able to find the other two panels (compilation and language design) from that one. Anyway, they discuss a lot of idea behind performance, for example
a) code that is locally bad but globally good
b) optimizing for locality and predictability of memory access (David Moon, in the Compilation panel, I think)
c) speculation that performance improvement could be gained via having an efficient interpreter residing in cache, over optimized compiled code (Scott McKay again, in the panel on runtime - incidentally I think this idea is proven in Kdb+ - at least, I understand that is their secret to performance, or one of them)
[1] http://www.paulgraham.com/carl.html
[2] http://www.ai.mit.edu/projects/dynlangs/wizards-panels.html
[3] https://www.youtube.com/watch?v=4LG-RtcSYUQ
Edit: cleaned up formatting Edit 2: and more clean up
[1] https://en.wikipedia.org/wiki/Apple_II
EDIT - Sorry, Wikipedia was wildly incorrect; I have updated the page
https://github.com/alex/what-happens-when
Would love to see Knuth's Challenge setup in a repo for collaboration.
HN Discussion on the above link:
I was expecting non-keyboard input methods, keyboard scan codes, keymaps, input modes, fonts, glyph selection, screen resolution and rendering. Scan codes are mentioned in the next paragraph, but the rest are ignored (OK, they finally mention DOM rendering, but leave out the earlier screen updates). Two seconds later they are discussing ARP... really? What about virtualization, sandboxing, firewalling, link layer selection, use of multiple concurrent link layers for a given network-layer address range, non-ARP link layers, existing transport-layer sessions to the relevant hosts, VPNs, proxies, offline mode, caches and load balancers (possibly multiple layers), non DNS-based name resolution, differences between available IPv4 and IPv6 address classes (mobile IP), layer 2 transparent proxying (eg. proxy ARP/heartbeat), switch ARP caches, etc.
I also think this is an excellent interview question for any internet-related engineering role, as it really gives people a chance to show their degree of comprehension of many layers.
> Would love to see Knuth's Challenge setup in a repo for collaboration.
Go for it!
That "several hundred thousand" has grown by about four orders of magnitude since then, even more if we consider multi-threading, GPU, CPUs in the network controller, etc.
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.
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.
Make it 1/10th of a second, or 1/1000th if needed.
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.
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.
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!
[1] https://github.com/moyix/panda
[2] https://github.com/moyix/panda/blob/master/qemu/panda_plugin...
You'd probably find something interesting in the general sense from looking at what's going on in a QEMU emulation for a fixed time period, but you'd need to be rather wary about how applicable what you saw might be to a real hardware run. At minimum you'd want to cross-check against what perf on real hardware revealed.
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.
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".
> Can it be done with an emulator like QEMU?
Yes, that's probably an alternative if sampled isn't sufficient.
I'm thinking this is what was intended. Did something get lost along the way with all the layers of translation from "human problem" to machine language? Here's another quote from the source passage, linked elsewhere in this thread:
The sequence of operations will be too difficult
to decipher unless you have access to the source
code from which the instructions were compiled.
University researchers who wish to carry out such
an experiment would probably have to sign
nondisclosure agreements in order to get a look
at the relevant source code."It might be shocking if an erroneous program was discovered, but it could certainly happen."
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")?
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.
The problem of course is that this is not analyzing the physical machine but rather the behavior of programs in a virtual environment.
OOO speculative superscalar hyperthreaded multicore CPUs now are 2.5GHz.
Of course, just doing this would be illegal on most proprietary operating systems.
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.
"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.
Here are some real reviews of a real book of fictitious reviews of fictitious books [2]:
KristenR rated it really liked it. Shelves: science-fiction, short-stories, male-author.
This volume had 3 essays, each with an interesting concept.
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...
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.
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.
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.
Rich Meyer rated it: really liked it. Shelves: read-in-2014.
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.
[1] https://en.wikipedia.org/wiki/Stanis%C5%82aw_Lem%27s_fictiti...
[2] http://www.goodreads.com/book/show/28771.One_Human_Minute