Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Knuth's Challenge: Analyze everything your computer does in one second

gaxun.net

Post reply on HN
Print view View original

31–40 of 52 posts

Re: Knuth's Challenge: Analyze everything your computer does in one second

#31

Post by wyldfire »

gpderetta wrote: post #18
SapphireSun wrote: post #16

Earlier quoted context omitted.

GPUs are definitely in the performance at the expense of correctness bucket. It's common for errors to occur in the LSB which isn't a big deal for colors, but might be a big deal for data.

Aren't the last few generations of GPUs fully IEEE compliant?

I assume that SapphireSun refers (primarily) to individual manufactured device faults not a problem where the design fails to comply with the floating point standard. EDIT: although the faults I'm referring to would be just as likely in the MSB so maybe not.

SapphireSun, these are mitigated in large part by ECC. It was offered by both major manufacturers and now at least one of them still offers it.

Re: Knuth's Challenge: Analyze everything your computer does in one second

#32

Post by contingencies »

ideonexus wrote: post #13

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?” 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: https://news.ycombinator.com/item?id=8902105

Sad that it has 57 issues and 27 pull requests, and begins with When you just press "g" the browser receives the event and the entire auto-complete machinery kicks into high gear... ... not exactly a low level explanation.

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.

Re: Knuth's Challenge: Analyze everything your computer does in one second

#33

Post by drdrey »

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): http://bitblaze.cs.berkeley.edu/temu.html

The problem of course is that this is not analyzing the physical machine but rather the behavior of programs in a virtual environment.

Re: Knuth's Challenge: Analyze everything your computer does in one second

#34

Post by Klathmon »

Someone wrote: post #30

"The computer will execute several hundred thousand instructions during that second; I'd like you to study them all." 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…

Couldn't you adjust the amount of time that you look at to preserve the "purpose" of the exercise?

Make it 1/10th of a second, or 1/1000th if needed.

Re: Knuth's Challenge: Analyze everything your computer does in one second

#35

Post by hderms »

Klathmon wrote: post #34
Someone wrote: post #30

"The computer will execute several hundred thousand instructions during that second; I'd like you to study them all." 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…

Couldn't you adjust the amount of time that you look at to preserve the "purpose" of the exercise? Make it 1/10th of a second, or 1/1000th if needed.

Interesting question as I'm guessing the ratios of instructions would probably be different owing at the very least to the vast difference in CPU power to IO that has grown over time.

Re: Knuth's Challenge: Analyze everything your computer does in one second

#36

Post by chriswarbo »

gaxun wrote: post #15
khedoros wrote: post #12

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. In 1989, we'd've also been looking at code running on a single core with a single-task or cooperative-multitasking OS (for…

> simpler hardware that an individual could completely understand 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.

My first computer was an 14MHz Amiga 1200 in the early 90s. In some ways the performance difference isn't too noticable, e.g. the GUI was often more responsive than those I use today.

In other ways it's clearly different; e.g. waiting minutes for a JPEG to decode, as the scanlines slowly appeared one after another.

Re: Knuth's Challenge: Analyze everything your computer does in one second

#37

Post by GFK_of_xmaspast »

gaxun wrote: post #15
khedoros wrote: post #12

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. In 1989, we'd've also been looking at code running on a single core with a single-task or cooperative-multitasking OS (for…

> simpler hardware that an individual could completely understand 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.

> a little bit on performance

I don't know how anybody who used a computer in the 80s, 90s, or 00s could say this.

Re: Knuth's Challenge: Analyze everything your computer does in one second

#38

Post by moyix »

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.

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...

Re: Knuth's Challenge: Analyze everything your computer does in one second

#39

Post by rwallace »

gaxun wrote: post #15
khedoros wrote: post #12

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. In 1989, we'd've also been looking at code running on a single core with a single-task or cooperative-multitasking OS (for…

> simpler hardware that an individual could completely understand 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.

I could say 'gained a little bit on performance' is a wild understatement, because the actual gain is several orders of magnitude, but that in itself would be a wild understatement. It could be taken to suggest that a second of work on a modern PC could be duplicated on a 1989 PC if you were willing to wait all day, but in reality it couldn't; very little of what I use computers for today could be done on the machines I had in 1989 at all no matter how long I was prepared to wait.

Re: Knuth's Challenge: Analyze everything your computer does in one second

#40

Post by pm215 »

moyix wrote: post #38

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. We recently added some machinery [2] for using debug symbols to map each instruction back to its source line. So, assum…

This is getting perilously close to "attempting to extract performance information from a program running under a simulator/CPU model", which is really tricky to do in a way that gives you results that apply to actual hardware. In particular, the performance characteristics of QEMU are wildly different from real hardware in several significant ways: (1) the emulated FPU is incredibly slow, so the results will overweight anything that's FP-intensive (2) there is no modelling of CPU caches, TLBs or branch predictors, so these major influences on real-hardware performance won't be visible (3) because the emulated CPU is very slow, interrupt handler and similar code which runs triggered by timers or other external events will take up more time in the trace than it would on hardware.

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.

Post reply on HN