Knuth's Challenge: Analyze everything your computer does in one second
1–10 of 52 posts
Re: Knuth's Challenge: Analyze everything your computer does in one second
#2I 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.
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.
Re: Knuth's Challenge: Analyze everything your computer does in one second
#3I 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. Another thing is that he was surely envisioning a program written in C or the like - a straightforward translati…
> I think perhaps some alterations would really be necessary to make this analysis tractable.
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...
Re: Knuth's Challenge: Analyze everything your computer does in one second
#4I 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. Another thing is that he was surely envisioning a program written in C or the like - a straightforward translati…
Since Apple IIs were manufactured until 1993 or so, I guess I could use one for the challenge. It's perfectly doable.
Re: Knuth's Challenge: Analyze everything your computer does in one second
#5I 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. Another thing is that he was surely envisioning a program written in C or the like - a straightforward translati…
> I think perhaps some alterations would really be necessary to make this analysis tractable. 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 w…
You might find the following interesting.
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
Re: Knuth's Challenge: Analyze everything your computer does in one second
#6> 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?
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.
Re: Knuth's Challenge: Analyze everything your computer does in one second
#7I 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?
Re: Knuth's Challenge: Analyze everything your computer does in one second
#8I'd like to see this applied to Windows 7 and find out why it has become mysteriously slow, even on fast computers, after Windows 10 came out.
Re: Knuth's Challenge: Analyze everything your computer does in one second
#9> 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? 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 d…
> We'd be better off following the trail of breadcrumbs back to the source
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.Re: Knuth's Challenge: Analyze everything your computer does in one second
#10This and similar questions is a very good question for a job interview (as a theoretical thought experiment in the interview)