![Programming Programming](http://a.fsdn.com/sd/topics/programming_64.png)
![Technology Technology](http://a.fsdn.com/sd/topics/technology_64.png)
![IT IT](http://a.fsdn.com/sd/topics/it_64.png)
Hindsight: Reversible Computing 178
One of the more interesting tech pieces that came out this week has been Hindsight [PDF]. Hindsight is made by Virtutech and is billed as the "the first complete, general-purpose tool for reverse execution and debugging of arbitrary electronic systems." The demos were received extremely well and it just looks cool.
Sounds good - but expensive. (Score:5, Informative)
Hindsight will go into beta sites in May, with production slated for July. Incremental cost over Simics is around $5,000 per seat, but Hindsight won't target single seats. A typical engagement, including Simics, Hindsight and some initial model development, is estimated at $200,000 to $300,000 for a software development group with 10 to 20 seats.
Not necessarily (Score:5, Informative)
Re:Sounds good - but expensive. (Score:2)
Especially when it turns two $100k/year engineers into one $50k/year engineer.
That's just nutty... (Score:4, Informative)
That would be quite nice... It almost seems like a shuttle head or what not for programmers... Rewind, play, slow motion and so on... I know they said it's the first complete one, but is there anything else out there like this?
Re:That's just nutty... (Score:2, Interesting)
http://www.lambdacs.com/debugger/debugger.html [lambdacs.com] I'm sure a Hindsight sales person would (correctly) say this isn't a complete solution, but its the closest thing I've seen before this article.
Re:That's just nutty... (Score:1)
In spite of all those things it was still extremely useful. As they say though, the devil's in the detail. Getting it to work in a general purpose
Re:That's just nutty... (Score:1)
Re:That's just nutty... (Score:3, Insightful)
Thus the only way to "back up" computation is to know the past of that machine, i.e. a state log of the execution of the program.
B
Re:That's just nutty... (Score:4, Interesting)
At first I wasn't sure that your statement was true, but after thinking about it for 30 seconds or so, I realized it definitely was. Every instruction produces a deterministic calculation and can be reversed, right? If we have "ADD EAX, EBX", and know the current values of EAX and EBX, going backwards is easy, right?
Well, one really difficult case is jumps. How do you know what the previous instruction executed was? On X86 this would be pretty difficult since the encodings are non-regular, but even on an ISA with regular encodings it would be non-trivial because it would be difficult to figure whether you got to the instruction via a jump (which could be anywhere in memory), or from the previous instruction.
Add things such as Self-Modifying Code, and you have a real headache. Yes, you definitely need to track state as you go, though I'm not sure you'd need to save anything more than just the Instruction Pointer (which X86 does have a mechanism for). If you know what instructions were executed, it should be pretty easy to backtrack in time. I think.
Re:That's just nutty... (Score:3, Insightful)
Re:That's just nutty... (Score:2)
As an analogy consider the P4's lookahead. If the execution will not enter the branch that does an i+=rand(), the value of i must still be unchanged.
Re:That's just nutty... (Score:3, Interesting)
Try this UTM program:
Re:That's just nutty... (Score:3, Insightful)
Wrong.
Basically any code that moves any data is crunching some other data. Given that RISC and CISC processors are Load/Store based architectures, that makes for pretty much a majority of cases.Re:That's just nutty... (Score:2)
You're also not taking into acount all the data and sates a piece of software may have traveled through, which is not as simple as just back-traking through the execution.
There are also other fun little things like interrupts, threads, processes, etc. It can get quite complicated very quickly.
In some instances you'd be able to get away with an IP back-trace, but with the complexity of mo
Re:That's just nutty... (Score:3, Informative)
Re:That's just nutty... (Score:3, Informative)
Yes, in the museum.
The debugger that came with BS3 on the TR440 [vaxman.de] had an option that enabled you to step back a defined (small due to lack of space for saving) number of steps if you set the appropriate switch when compiling. Very cool feature - 30 years ago !
CC.
Re:Turbo Debugger (Score:2)
UI (Score:5, Interesting)
My question is how UI interactions are handled. If the execution between the checkpoint and current-1 instruction includes a UI interaction, it might be very confusing to the programmer to know what or how many UI interactions need to be carried out to accomplish the backstep.
Re:UI (Score:1, Interesting)
Re:UI (Score:2)
Don't the video game emulators already do this?
Re:UI (Score:2)
Yeah. To create a movie they save the state and log the following input, so the game can be replayed exactly. ZSNES also has a rewind key, but I haven't messed with it.
Re:UI (Score:3, Interesting)
Those bugs might be catched if the environment would record instructions one-by-one, but as is you may find a bug in your execution, roll back to the checkpoint and find that the bug is gone in the replay. Hey, that would be funny if it happened on a TV football game...
Re:UI (Score:2, Interesting)
The trick is to have a simulator fast enough so that you can do UI interactions, because the user isn't in the simulated world. As it happens Simics is fast enough and this is exactly how it works. I'm on the Simics product team, and one way we have of proving the point is to run operating systems and their applications backwards for which we cannot have the source
Mirror (Score:5, Informative)
Never underestimate the Slashdot Effect!
Virtualization layer for checkpointing and steppin (Score:5, Informative)
checkpoint the hard disk too? (Score:4, Insightful)
"Last Technical Hurdles"? (Score:2, Interesting)
How in the world did they pull this off?
The trick... (Score:2, Funny)
Re:"Last Technical Hurdles"? (Score:2, Troll)
Assuming most slashdotters are lazy f*cks, a condensed explanation: it takes a snapshot every couple of seconds, then when you want to go backwards it moves all the way to the previous snapshot, then runs forwards ignoring sleep() to appear instant.
But what about external events (Score:5, Interesting)
Re:But what about external events (Score:5, Informative)
Re:But what about external events (Score:3, Interesting)
It's exactly an example of an external packet containing a wrong checksum.
If the system is in isolation, you would have to come up with the idea of sending a malformed packet yourself instead of just letting it run until it crashed. that doesn't seem a very likely thing to try.
Re:But what about external events (Score:4, Funny)
This product is a cleverly disguised time machine.
You can actually rollback and reverse to actually see the initial "First post!" remark, and undo the slashdot effect.
If you look closely, you can also see the cognative response from Hemos as he clicked Accept on this submission.
Re:But what about external events (Score:2)
So, if it does a virtual DMA to get the network packet the first time, copy the data from that DMA into a log. When you're re-executing, copy the DMA from the log instead of from the NIC.
It's similar ReVirt (my project), which was slashdotted here [slashdot.org].
The downside, of course, is that you need to log *all* network data; so if you actually need that 1Gb ethernet, you
Too good to be true... (Score:5, Insightful)
Therefore, I can't see their approach being foolproof, and the over-obvious advertisement (this is what normal debugging toolbars look like, but they don't have a nifty step-one-back feature) seems too bright to be withot caveat. At $5,000 a seat I'd say buyer beware.
Re:Too good to be true... (Score:1)
It stores a snapshot every now and then, and when you want to go back it actually goes forward from the first snapshot before the time index you want.
If you make snapshots 10 times a second and can forward-fill in a tenth of a second, the programmer will not notice this. (And if he does, make more snapshots)
HTH
--Blerik
Re:Too good to be true... (Score:1, Informative)
For example, if you're at point t=10, your previous checkpoint is at t=0, and you want to go back to t=9, their system first go back to t=0 and then reexecute the code until t=9.
The thing is that you have to log everything non reversible (I/O, interrupts, syscalls, etc.) and use the logged value when reexecuting.
Re:Too good to be true... (Score:4, Informative)
It also says in TFA that it doesn't actually calculate the reverse steps, so it doesn't matter if it's mathematically impossible.
What it does do is take complete snapshots every (for example) 100 steps. In order to move "backwards" a step, it returns to the previous breakpoint (a known state) and goes forward 99 steps.
Then it returns to the same breakpoint and goes forward 98 steps. And so on. So from your perspective, you see the 99th step, 98th, 97th, and on down. It only LOOKS like it's running backwards.
This would even work for the game of life.
So the performance tradeoff would be this:
More frequent breakpoints causes forward execution to be slower because it's spending more time saving data at regular intervals for breakpoints, but "reverse" execution would be faster because it has to iterate fewer steps from the previous breakpoint.
Re:Too good to be true... (Score:2)
Even more efficient, when "running backwards", go back to the checkpoint and re-execute everything while logging each instruction (log an instruction: record the previous value of anything this instruction overwrites, including the program counter if not the next instruction). Then you can do a direct "go backwards" mode. You still need to log each memory location that gets overwritten between snapshots (and use those values when re-executing).
Instead of snapshots, you could record state at the beginning
RTFA (Score:2, Informative)
Wow ! (Score:2, Funny)
I can hear it now, "Godlike!"
The Omniscient Debugger? (Score:3, Informative)
http://www.lambdacs.com/debugger/debugger.html/ [lambdacs.com]
Seems like this has been done before, at least for java apps...
BSOL? (Score:3, Funny)
That would be so cool...
Alan.
Re:BSOL? (Score:2)
Since it would be occurring backwards, wouldn't it be red?
Problems with platform emulalators (Score:3, Insightful)
What would be far more useful, would be to write tools that took advantage of many of the onboard hardware debugging capabilities of some of the common embedded chip architectures.
Re:Problems with platform emulalators (Score:2)
Also, you have better control of what goes on in an emulation, and that can help you find mysterious bugs that are very opaque on the real hardware.
Finally, there's certain situations where emulators are probably the only way to go- for example Space Shuttle software validation is done on
Re:Problems with platform emulalators (Score:2)
But you are absolutely right. In my own experience with embedded developement, emulators were often all you hand until the eval boards showed up and those were usually hogged by the bootstrap teams who could careless about emulation and were only interested in real hardware. Same deal with the prototype boards.
Tha
Re:Problems with platform emulalators (Score:2)
Thats simple... (Score:3, Funny)
Re:Thats simple... (Score:2)
Not by a decade. (Score:5, Interesting)
I read this usenet post [google.ca] every now and then when I'm trying to fix something, and it makes me want to cry every time I do.
Mod parent up (Score:4, Informative)
This has real potential. Beta versions of programs should run with this installed, so the core dump can be stepped backwards to the trouble spot. This could make Linux software significantly more reliable.
Re:Not by a decade. (Score:2)
Re:Not by a decade. (Score:2)
Maybe I'm misreading the information, but the impression I got is that it has the capability to setup a virtual machine so that you can
Hmm, that's cool. (Score:2)
I don't have time to do it all myself, but I can at least try to start the ball rolling...
Re:Not by a decade. (Score:3, Informative)
First, it was kind of silly to name the program the same as my user name, but I never found a better name for it than "my trace-and-replay debugger".
My original plan was to write this for Solaris and sell it, hence the insistence on tracing and replaying without modifying the target program or the operating system, and that's why the replay controller messes with gdb's mind, so that it can work with a stock gdb rather than needing gdb extensions.
I developed a Linux version first because
Bash VB all you want.... (Score:1, Informative)
Coupled with fix and continue, you have not only a more productive development environment, but an environment where you can press a prototype into
Reverse Execution of Code? Haha! Oh wait... (Score:2, Interesting)
We know the result, C. How do we know if A, B, or both was 1? We lost information (2 bits of info became 1), and cannot get it back. So at first I dismissed any ridiculous claims of reverse execution. But we aren't the 1st of April...
Re:Reverse Execution of Code? Haha! Oh wait... (Score:1)
It doesn't. It works inside a virtual machine.
Re:Reverse Execution of Code? Haha! Oh wait... (Score:2, Interesting)
There is a way to do this, although it is a bit ugly. The reverse-runner forks the program into 3, one for each of the possibilities. It then continues this until values have been solved.
It would produce a decision tree, and the debugger could work backwards.
Of course, this is purely theoretical. If A and B were strings, the number of processes would be infinite, in which case heuristics would be required, and it wouldn't be perfect.
Re:Reverse Execution of Code? Haha! Oh wait... (Score:3, Informative)
Reversible Computing != Reversible Execution (Score:5, Informative)
Anyway, the headline is misleading.
Re:Reversible Computing != Reversible Execution (Score:2)
Damn misleading articles. (Score:2, Informative)
Re:Damn misleading articles. (Score:2, Interesting)
I'm not trying to be an ass here, but isn't that why they call NOT a unary operation, because of one operand?
Re:Damn misleading articles. (Score:2)
Actually, you can solve the 2->1 folding problem quite easily. You just need to find gates that output as much information as they use. For example, an xor gate produces a single output, but if you invent the gate 'a,b' -> 'a, a^b' (xor*) then it is fully reversible and it is its own inverse.
The trick is to make the electronics themselves fully reversible, rather than emulating xor* using a standard xor and a wire. I don't know how this is done. My
Re:Damn misleading articles. (Score:2)
Who cares anyway, it's just bit picking. (nit picking is base e
OCaml anyone? (Score:4, Interesting)
And what about GUI and other side effects? Debugging a program in which such side-effects are deeply interleaved with algorithmics can be tricky indeed, although smart timestamping from the debugger will reduce glitches. But if you don't know better than randomly mixing algo and front-end in the first place, then you'd better fix the programmer than the program...
Coding C in Eclipse? (Score:1)
Does that include a C programming environment for eclipse or do they use the CPE project? I didn't know that was at a usable state yet.
I use eclipse for java and it is excellent.
Re:Coding C in Eclipse? (Score:1)
Worth it if it works... (Score:1)
Seriously, if this really works, the $5K/seat could well be worth it. Now, if they could convince Intel/AMD/IBM to somehow provide advanced support in the hardware...
-k
Re:Worth it if it works... (Score:2)
If this company was smart, they'd sell it for $500 and sell 100 times more copies.
Visual Basic (Score:1)
Any relation to ReVirt? (Score:5, Interesting)
ReVirt [umich.edu]:
Elephants never forget (Score:5, Interesting)
In this paper, he proposes the Elephant language [stanford.edu] that can refer to the past in computer programs.
Pretty cool stuff!
Refering to the past would be really handy (Score:2)
I didn't follow the link, but I imagine new constructs such as do over and go back - closely related to the just kidding clause.
And what about memory leaks? Programs that can't remember their past are doomed to loop forever!
Call Stack (Score:2)
Re:Call Stack (Score:2)
Re:Call Stack (Score:2)
Give me a break. The assertion of your original post (that a call stack is usually enough) was based entirely upon your personal experience. There was absolutely no deductive arguments or additional premises to support your conclusion. The only thing that could be refuted was your implicit assertion that you have the necessary experience to make such a decision.
While some people do have enough karma capital to get away
Re:Call Stack (Score:2)
Is This Really New? (Score:3, Interesting)
Being able to trace backwards ware extraordinarily useful, and it's one thing I miss in modern compilers. I always assumed that this capability was taken out with the advent of event-driven (GUI) programming. That's when a lot of this kind of functionality seemed to disappear.
Obligotory jwz reversible gdb link (Score:1, Interesting)
(Actually someone has already posted [slashdot.org] the links jwz was talking about)
Hmm... (Score:2, Funny)
reversible computing == low energy computing (Score:2)
Re:reversible computing == low energy computing (Score:3, Informative)
I think you got it just the wrong way.
Traditional computers generate entropy because of the information destroyed. Entropy created is necessarily associated with heat. With reversible computing there is no entropy increase, which in theory means less heat produced and less energy consumption.
The title threw me off a bit (Score:2)
At first glance, I thought I'd eventually take an "upgrade" path to a VIC-20 via "Reversible Computing"
Come from? (Score:4, Funny)
(See also the entry in the jargon file [catb.org].)
Re:Come from? (Score:2, Funny)
From the website... (Score:2, Funny)
They assume that programmers... DEBUG! Hah!
There are a few issues but... (Score:2, Interesting)
I not really THAT big of a deal... (Score:2)
And on top of that, most IDEs ha
Re:I not really THAT big of a deal... (Score:2)
after execution of A=B the state is A is 1, b is 1... tell me what was A before execution. Clobbering of data is not reversible and is very common (as in everytime there's an assignment operator used). Even things like
Re:I not really THAT big of a deal... (Score:2)
Replay with nondeterministic events (Score:2, Interesting)
The first language I know of that supported replay is the Abundance database language [mindprod.com], back in 1986. Also see http://c2.com/cgi/wiki?ReversibleProgrammingLangua ge [c2.com].
Re:hrmmm (Score:1, Interesting)
Where do they store the entropy? (Score:3, Interesting)
more seriously, that would mean that there is no crypto on these machines since all encoding would be reversible.
Re:Doesn't work for multi-threaded programs (Score:1)
Re:Oh Dear (Score:2)
Re:!tsop tsrif (Score:3, Funny)
It's friday people, lighten up
Re:Isn't this cheating??? (Score:2)
We're not even going to be making minimum wage!
But since we'll all be cyborgs, we'll probably get some renumeration for the tiny amount of computer power we are able to contribute to the hive from our own e-brain and attention.
Then again, consider: Just how much does a 3'x3'x3' cube for housing your brain cost?
Nice to think we'll all be vegan, finally, consuming our diet of proteins. Somehow, I don't think the present day vegans will be happy with this arrangement, t