Time Travel Debuggers Talk

Hello everyone! This is a recording of a talk I've done at some Atlanta local events about Time Travel Debuggers. It was the first time in years that I'd give a tech talk in public. It was very nostalgic. I was also very happy to be able see the reactions of the audience live! Although I won't be able to see your reactions live, you may give it to me via the comment section.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : let's talk about time travel
00:02 : debuggers this is what we're going to
00:04 : cover first I'll introduce some
00:07 : Inspirations for my work then I'll show
00:10 : off some of my
00:12 : inventions then uh taking a detour I'm
00:16 : going to uh show you a technique called
00:18 : record
00:20 : replay and then I'll show you some time
00:23 : travel debugging techniques finally a
00:27 : concept called
00:28 : omniscience
00:30 : so let's get
00:33 : started this guy's name is Brett Victor
00:36 : and he's giving a talk uh entitled
00:39 : inventing on principle uh this is one of
00:43 : the all-time computer science Classics
00:46 : um if you haven't seen this talk I envy
00:49 : you uh for the ability to see it for the
00:52 : first
00:54 : time uh without giving away his talk too
00:57 : much uh this was one of the highlights
01:00 : of his talk uh so he's showing off a
01:02 : video game but actually it's more of a
01:06 : video game programming environment where
01:09 : you have access to this scrubber
01:11 : timeline at the top that can allow you
01:13 : to go backwards in time or
01:17 : forward uh and you can also edit the
01:20 : code here as he shows using like edit
01:24 : the velocity value for example and that
01:27 : is directly connects to
01:30 : what happens when you scrub back and
01:32 : forth but there's more there's another
01:35 : button here which if you click it you
01:37 : can actually see the position of the
01:41 : character throughout the entire
01:44 : execution of the program so basically at
01:46 : all points in time you have the
01:49 : character but there are sort of the
01:51 : inklings of the character behind him and
01:54 : in front of him we call that its past
01:57 : and its future the moment you edit his
02:00 : velocity for example you can see his
02:02 : future change right away this is
02:06 : extremely helpful for when you're trying
02:08 : to get the exact right value for what
02:11 : you're trying to achieve here this was a
02:14 : mindblowing experience to have seen this
02:17 : for the first time for me uh but another
02:20 : source of inspiration for me was the
02:22 : Redux
02:24 : framework um and this is how Redux Works
02:28 : Redux is a state manager system where in
02:32 : order to make a change to the state of
02:35 : the program you are asked to go through
02:39 : this thing called the reducer so the
02:42 : reducer here is a function that takes
02:45 : the previous state of the program as
02:48 : well as an action which
02:51 : unambiguously defines what about the
02:54 : state to change and then its job is to
02:57 : spit out the what the next state of the
02:59 : program program should be and uh every
03:03 : single time the application has to
03:05 : change state it has to call the reducer
03:09 : uh with it the current state pass in as
03:13 : the previous state parameter and then
03:15 : whatever the reducer spits out as the
03:17 : next state that is put back into the
03:20 : current state um and that's how the
03:23 : application updates One requirement is
03:26 : that the reducer must be implemented as
03:29 : a pure
03:30 : function and that means you can actually
03:33 : put the states into a timeline like this
03:37 : so when an update happens we call the
03:39 : reducer in order to get from s0 say to
03:44 : S1 and then with U2 we call the reducer
03:48 : again to get from S1 to S2 um getting
03:52 : the next state does not have to mutate
03:55 : the previous state because the reducer
03:58 : is a pure function
04:00 : and that has enormous consequences as we
04:04 : will
04:06 : see so around 2009 I was working as a
04:10 : mentor and I was helping some Junior
04:13 : developers um one of the things I did
04:16 : was work with them on debugging
04:19 : difficult problems and I got a deep
04:22 : appreciation for how difficult the art
04:26 : of debugging is and most of us are
04:29 : either doing print debugging or
04:31 : brickpoint debugging uh and when you're
04:34 : doing print
04:35 : debugging um you're writing a lot of
04:38 : these log statements which are temporary
04:41 : in nature and you don't really want to
04:44 : check these in so you kind of feel a
04:46 : little bit dirty and you have to do a
04:49 : second pass later to clean them up uh
04:52 : but another problem is sometimes you get
04:55 : so many logs that it becomes hard to
04:58 : wait through them the signal to noise
05:01 : ratio can become a
05:04 : problem the issue with breakpoint
05:07 : debugging is that choosing where to put
05:10 : your breakpoint is like playing the
05:12 : prices right uh you want to try to get
05:16 : as close as you can but without going
05:19 : over because if you go over then you're
05:22 : going to have to start the session all
05:25 : over again which is why the contestant
05:28 : on the right has chose
05:30 : to um just pause the program at line
05:33 : number one because that is what works
05:35 : for
05:37 : her the last thing that's really
05:39 : difficult about a debugging is the
05:42 : presence of heisen bugs a heisen bug is
05:45 : the type of bugs where if you try to
05:48 : take a closer look at them they just
05:53 : disappear how are you supposed to fix a
05:56 : bug when you can't even get your hands
05:58 : on it
06:04 : around this same time I was working on a
06:07 : programming language on the site and I
06:11 : had this realization that I can build
06:14 : something like a Redux system in the
06:18 : core of the language thereby enabling
06:21 : statement level time
06:24 : traveling so if you remember this
06:26 : diagram so if every single one of these
06:30 : State objects contained all the
06:33 : variables of the program the stack frame
06:36 : any Heap objects like arrays or
06:39 : objects uh all the threats if you're you
06:42 : have multiple threats if you just save
06:45 : every single one of these states into a
06:49 : file somewhere then you can trivially
06:52 : Implement time travel debugging this
06:56 : seems crazy to store so much information
06:59 : right but you know what the heck it's a
07:03 : toy programming language let's try it
07:05 : and see what happens and that's what I
07:07 : did so this is me giving a demo of it
07:12 : and you can see with this simple
07:14 : Fibonacci program like this um you can
07:16 : see this little arrow here that allows
07:19 : you to kind of step forward and
07:21 : backwards in time let me show that again
07:24 : so this Arrow can go into functions out
07:28 : of functions backwards forwards and when
07:32 : I convinced myself that it worked I was
07:35 : amazed um then I tried to make it do
07:37 : more substantial things like this is a
07:40 : tic-tac-toe program with a minia Max AI
07:44 : algorithm uh at first this just ran out
07:48 : of memory when I tried to run it so I
07:51 : had to do some reengineering of some
07:54 : major parts but eventually I got this to
07:57 : work I will show the debugging session
08:01 : for this later on in the talk uh because
08:04 : that will be glorious and I want to save
08:07 : the best for last uh but incidentally
08:09 : here it did manage to beat my friend
08:16 : hii later on after this experience I
08:20 : wanted to implement the same feature in
08:23 : Python however with python it was
08:26 : Impractical to save every single State
08:30 : because I would have to gut the Python's
08:34 : entire system in order to do it so what
08:38 : I did instead was to save the updates
08:42 : that were coming in um because if you
08:46 : can manage to save these updates and
08:49 : each one of them contained information
08:52 : that allowed you to replay them onto a
08:55 : previous state and you can just use some
08:57 : starting State as zero that is the as
09:01 : the default and if you can replay all of
09:03 : these update arrows then you can
09:06 : actually regenerate all the successive
09:09 : States on this timeline after the fact
09:12 : and that's what I did for
09:14 : python the python interpreter is written
09:17 : in C so I had to brush up on my C
09:19 : programming skills and I found all the
09:22 : places where State mutation was
09:26 : happening inside the the interpreter in
09:30 : including when dictionaries are updated
09:33 : when lists are updated when functions
09:35 : are being called etc etc etc so so it
09:40 : was implemented as a mod of python and
09:43 : so instead of using python to run your
09:46 : program you would use py rewind its code
09:48 : name and after having run the program it
09:52 : would generate a log file like this and
09:55 : then you would run another program
09:58 : called recreate
10:00 : which would read back that log file and
10:03 : recreate all of the intermediate states
10:05 : of the program save it to a database and
10:09 : then with that database you can debug
10:12 : the program so this is a debugging
10:14 : session uh using this text based user
10:17 : interface um and it works just like a
10:20 : any step debugger but this can step
10:24 : forward or backwards in time and a key
10:26 : difference between this and a normal
10:28 : step bugger is that when you're using it
10:31 : you're not actually running the program
10:33 : but you're just stepping through uh the
10:35 : different states that are in the
10:38 : database which have already been
10:42 : precomputed I was so excited about this
10:45 : when I got it working I emailed my
10:47 : former professor at Georgia Tech about
10:51 : it and he pointed me to the prior art in
10:54 : this
10:55 : space it turns out that I am not the
10:58 : first first person to have done this
11:01 : there have been a large body of work
11:05 : around time travel debugging and I went
11:08 : to work and I dug into this
11:18 : literature so RR is a time travel
11:21 : debugger for C and C++ um although it
11:25 : only works on lenux is one of the best
11:29 : time traveling debuggers and and maybe
11:31 : the only one that I consider to be at a
11:34 : production level um so I have used it um
11:40 : for my work with pi rewind um because as
11:44 : you know the python interpreter is
11:45 : written in C so I can use RR with python
11:49 : every time I use it I feel like I'm
11:51 : living in the future and not only has it
11:55 : helped me solve some very difficult
11:58 : problems it has also helped me a lot in
12:02 : learning the code base a code base which
12:05 : I previously was not familiar with a
12:09 : debugger in my opinion can very much Be
12:12 : an Effective educational
12:15 : tool so how does it work so it's based
12:19 : on a technique called deterministic
12:22 : replay so the idea of
12:25 : determinism is that for the most part
12:29 : programs are deterministic as that's to
12:32 : say that if you have a program like this
12:35 : you run it 100 times it'll spit out the
12:38 : same thing every single
12:40 : time but there are also sources of
12:43 : nondeterminism as well so you don't know
12:46 : ahead of time what the user is going to
12:49 : do these are some other sources of non
12:52 : determinism that you might have
12:55 : encountered so what we're going to do is
12:58 : model our our program as a deterministic
13:01 : machine that is going to talk to the
13:04 : non-deterministic world so for example
13:07 : if this was one run of your program uh
13:11 : it send some messages back and forth
13:13 : between it and the
13:15 : world what we can do is capture the
13:19 : messages it received from the world
13:22 : along with their time stamps and if we
13:26 : do that we can run it again second time
13:30 : but this time connect it to these
13:33 : pre-recorded
13:34 : responses that we recorded from the
13:37 : first time so in its Essence we run your
13:40 : program in two different modes the first
13:43 : is called the record mode we run it
13:47 : while recording the responses you get uh
13:51 : from the non-deterministic world but the
13:53 : second time while you're debugging we're
13:55 : going to run your program in replay mode
13:59 : where all the responses you get are
14:03 : actually just coming from a pre-recorded
14:06 : tape and if you look at this picture now
14:10 : you realize that the entire system is
14:13 : now
14:14 : deterministic we've sort of eliminated
14:17 : the non-deterministic
14:19 : element uh which
14:21 : means we can say goodbye to the
14:24 : heisenbugs
14:27 : nice okay so now that we have a record
14:30 : replay system how do we get a time
14:32 : traveling debugger from that well let's
14:35 : look at this example again so say if we
14:38 : run this program in record mode and the
14:40 : user types in the number
14:43 : seven um it's going to run this Loop
14:46 : this many times and let's number these
14:50 : statements say we have a step debugger
14:53 : and we're paused on statement 16 if we
14:57 : want to step backwards in time time what
14:59 : we can do is set a break point on the
15:02 : previous line and then we're going to
15:04 : just start over again from the beginning
15:06 : of the program when it hits statement 15
15:09 : we will pause um this is a bit hand wavy
15:14 : and obviously there are optimizations to
15:16 : be done I think this is good enough
15:19 : explanation for the given time we
15:24 : have so this is another project um it's
15:27 : a it's called replay replay IO and it's
15:31 : a uh it's a debugger for JavaScript uh
15:35 : which you can try out um this also
15:38 : started out as a Mozilla project s did
15:41 : RR and uh this one features a replayable
15:46 : video of the other the screen of the
15:49 : page as well as a retroactive console.
15:52 : loock
15:55 : statement having worked with some
15:57 : different uh time travel debuggers I
16:00 : have collected some uh techniques so I
16:04 : will like to share some of those so one
16:07 : is called back up and drill down with a
16:10 : step
16:11 : debugger sometimes you're not sure
16:13 : whether you should drill down to a
16:14 : function or step over it but when you
16:18 : have access to time travel debugging you
16:20 : can always casually just step over
16:23 : functions and then after each function
16:26 : call you can inspect the result or the
16:28 : state overall of the program to see if
16:31 : there's anything fishy going on and if
16:34 : there were let's say the summary object
16:38 : looks wrong what you can do is just step
16:40 : backwards to before this do thing to
16:44 : happened and then you can drill down
16:47 : into that function and figure out what
16:49 : went wrong in more
16:52 : detail um another technique is called
16:55 : start at the end so let's say you
16:57 : encounter a runtime exception uh this
17:00 : case is a assertion error uh what you
17:03 : could do is start debugging at the
17:06 : location of the error uh in in my
17:09 : debugger that's what it does by default
17:12 : whenever there's a runtime error so you
17:14 : start here and what you do is you just
17:18 : step backwards by
17:21 : one um and in this case um it's step
17:25 : backwards by one to line 11 and I look
17:28 : at that and it took me a just a second
17:31 : before I realized I'm in the wrong
17:33 : Branch I really wanted it to go to line
17:37 : 13 but it didn't it went to line 11 so
17:41 : it helped me realize what the problem
17:43 : was very quickly in this
17:47 : case so those are a couple of the
17:49 : techniques you can use with time travel
17:52 : debuggers but there's
17:57 : more
18:01 : I consider Bill Lewis to be the father
18:04 : of time travel debugging uh due to this
18:07 : paper he wrote in 2003 in it he coined
18:13 : the term omnicient debugging and the
18:16 : word
18:17 : omniscience means all knowing but Bill
18:21 : uses it to mean that you have access to
18:25 : the state of the program at all points
18:27 : in time
18:30 : beforehand and when you have this
18:33 : capability it allows you to rethink what
18:36 : the user interface of a debugger can be
18:40 : in Brett Victor's demo uh here he showed
18:43 : us one of these examples here we can see
18:46 : the position of the character at all
18:49 : points in
18:51 : time b as himself he's going to show us
18:54 : another example so I was fortunate to
18:58 : get get a zoom call with him and here he
19:00 : shows me this thing which he calls the
19:04 : historical outline of the program so
19:07 : this looks like a stack Trace but unlike
19:11 : normal stack traces which only indents
19:15 : to the right this one actually outd Dan
19:18 : back to the left and the reason it does
19:21 : that is because we have already executed
19:24 : the program from beginning to finish
19:26 : which means every single method that has
19:30 : started running you know how it ends as
19:33 : well so you can see every single method
19:36 : we that was called we can also know its
19:39 : return value and every open tag also has
19:45 : a end tag as well similar to HTML so you
19:49 : can click around on this timeline to
19:51 : jump to different places in the
19:54 : program's execution and in the center
19:57 : here it'll also jump you to the line of
19:59 : the source code at that point in time in
20:02 : the outline as well as all the local
20:05 : variables what their values were at
20:08 : those points in
20:11 : time I was fascinated with this concept
20:14 : and I uh took this idea and I gave it a
20:18 : different take this is what I called the
20:22 : zoomable debugger it's inspired by the
20:26 : Mando Brad set fra as well as Google
20:29 : Earth so here we're looking at the entry
20:32 : point of the program which is the main
20:34 : function and we can zoom down onto it
20:38 : and when we get close enough then we can
20:41 : see what actually happened within the
20:44 : function um and we are calling another
20:47 : function called play game so we will
20:49 : zoom into that and see what actually
20:52 : happened and here we can see the tic tac
20:56 : toe game being played and we can see it
20:59 : move my move what happened I UNR the
21:03 : wild loops and this allows us to see
21:06 : sort of the progression of the game all
21:09 : within one plane rather than having to
21:13 : click nycks and Nyx and I like the idea
21:16 : of debugging at the high level first if
21:19 : something looks wrong at a high level
21:22 : then you can drill down by zooming in to
21:27 : see how that move went wrong for example
21:31 : so if we suspect Something Fishy went on
21:34 : we can see how the AI actually
21:36 : calculated its move here we can see it's
21:39 : imagining some different moves and
21:42 : evaluating them with some sort of
21:44 : scoring system and so
21:47 : forth another feature that's possible
21:50 : with omniscience is the object timeline
21:53 : uh so here bill is showing me uh he's
21:57 : singling out this Vector which in Java
22:00 : that's like a synchronized array so you
22:03 : can just think of the vector as an array
22:05 : that has a number of element to it and
22:08 : there are these forward and backward
22:11 : buttons that if you click them it'll go
22:13 : to the next or previous update of this
22:17 : Vector you see you click next and then
22:20 : we got another element inside of the
22:23 : vector and you can press previous to get
22:27 : the previous state
22:28 : and not only that it'll jump you in the
22:30 : source code to the line of code that
22:32 : caused that update you can imagine this
22:36 : being extremely helpful because many
22:39 : many times in debugging you're
22:42 : confronted with this erroneous value the
22:45 : next question you would ask is who put
22:48 : this here with this feature you can just
22:51 : hit the back button the the previous
22:54 : button it it'll jump you backwards until
22:58 : the moment where this erroneous value
23:00 : got put into this object and it'll also
23:03 : show you the exact line of code that did
23:07 : that there's another omniscient debugger
23:10 : called pronostico which is from the
23:14 : people who brought you RR also built on
23:17 : top of RR so a couple of features I want
23:19 : to show off one is called data flow um
23:24 : data flow is um a way of tracking how a
23:29 : value got here so in this case there was
23:33 : a zero a null value that was unexpected
23:37 : caused a crash so you can click on this
23:40 : null value and then here down at the
23:43 : bottom left you can see all of the data
23:46 : copy operations that caus this no value
23:50 : to be here at this point in time and
23:53 : this is something that you would have
23:55 : had to do in a very manual way like why
23:59 : is this no value here you read the
24:02 : source code and try to find where this
24:07 : variable got its value from previously
24:10 : in the code and probably either using
24:13 : print debugging or brickpoint debugging
24:15 : and you probably have to restart the
24:17 : program several times but here it just
24:20 : automated all of that for you and gave
24:22 : you a list of the entire Callo
24:26 : chain another feature in prosco is the
24:30 : call history so you can search for the
24:33 : name of a function and it'll show you
24:36 : all of the times that this function has
24:38 : been called throughout this run of the
24:41 : program and it'll also show you all the
24:45 : different parameters that this function
24:47 : was called with and you can click into
24:49 : them and when you do it'll jump you into
24:54 : that line of code along with all the
24:56 : variables on the stack
25:00 : Etc so looking back it occurred to me
25:04 : that some of the most important advances
25:07 : in computer science are actually coping
25:10 : mechanisms for the fact that debugging
25:13 : is hard if you think about how many
25:18 : human hours that have been put into
25:20 : these
25:22 : Technologies what if we took some of
25:25 : those resources and put it in into
25:28 : solving debugging
25:30 : itself what if debugging was not hard
25:34 : anymore what would Computing be like