TT Debugger Data Storage Optimization

In this video with Huiqi I describe a proposal for a change in the design of the time travel debugger's state storage mechanism, in hopes of improving the performance of the recreate program and the disk usage of the resulting history file.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : well basically the preference is i was
00:02 : working on
00:03 : i was working on um the next version
00:06 : of the terminal debugger and
00:09 : i got some amount of the way there
00:13 : as in
00:16 : i think it can do something like this
00:20 : now
00:20 : [Music]
00:23 : so i got this amount there i can step
00:26 : now nice i can step in i can step
00:30 : out step two step over
00:34 : i don't have the variable display yeah
00:37 : um
00:38 : and that's partially because uh i
00:42 : that's the part that i want to integrate
00:44 : your
00:45 : tree ui work okay and
00:48 : but also partial because of the next
00:50 : thing that i'm talking about
00:52 : is um oh and also
00:56 : previously it was the json like
01:00 : parser you need that to get the
01:03 : heap data structures in right
01:06 : but um but as i was working on this um
01:10 : the the it took longer and longer
01:14 : to recreate the past states
01:17 : for for the log file and i
01:20 : and i decided i i think i kind of have
01:23 : to do something about this
01:24 : if we're going to be able to do this
01:27 : for work on a day-to-day basis
01:30 : and even though it wasn't even though it
01:33 : wasn't really bad
01:34 : i i felt like like the longer i used
01:38 : the ui like the more times i stepped the
01:41 : longer it would take
01:42 : which which means like it's it's very
01:45 : soon going to be
01:46 : impractical that the more we do ui
01:49 : so i i want to as i thought about how to
01:54 : solve the problem
01:56 : and one of the things i learned
01:59 : from uh the chat with bill lewis
02:03 : is the way he does it is more efficient
02:07 : um in terms of space storage
02:10 : um so i'll show you what i mean
02:18 : oh and i oh let me let me go this one
02:27 : okay so something like that you if you
02:30 : scroll through
02:31 : like these are all the objects in the
02:34 : heap
02:35 : and i i represent the
02:38 : you know value of a composite object
02:42 : in this way it's like a sort of like a
02:45 : json object
02:46 : right but but the either the key or the
02:49 : value could be a reference to another
02:51 : object
02:52 : in this table which is signaled
02:55 : using this carrot um okay
02:59 : the problem is you can see there's kind
03:02 : of a lot of
03:03 : repetition of data right
03:06 : this row is mostly like this row is
03:08 : mostly like this row
03:10 : you can see there's one more entry at it
03:14 : right as i click down that means like
03:17 : maybe the dictionary is getting you know
03:20 : more and more entries
03:21 : as the program is progressing right
03:25 : but that does tell me there's a lot of
03:28 : repetition of data here
03:30 : and efficient use of dex
03:33 : uh storage space right
03:36 : so and also we have all of these
03:40 : you know all these objects that are
03:43 : even though you know this is kind of
03:46 : trivial
03:47 : but it is still the tag name is kind of
03:50 : long
03:50 : and there's a lot of repetition of this
03:53 : tag name
03:55 : um so um so my theory
04:00 : is that you know that the
04:04 : time it takes to
04:07 : generate the data in this database
04:10 : um a lot of it has to do with just
04:14 : the sheer amount of data we are writing
04:17 : into this database
04:19 : and if we can remove a lot of the
04:21 : repetition
04:22 : that means we'll get a much smaller
04:25 : database
04:25 : and also much faster run time
04:29 : needed to generate the database yeah
04:31 : that makes sense
04:32 : um so that's what so yeah like like this
04:36 : you see
04:37 : wow there's a lot of repetition here
04:39 : like something like this
04:41 : if we got rid of the duplication
04:44 : um we should just get much
04:47 : better size but
04:50 : much smaller size and also much better
04:53 : performance
04:54 : uh-huh so how does that
04:57 : work what's the proposed scheme um yeah
05:01 : exactly
05:01 : proposed scheme is um so the reason i
05:05 : did it this way is because i i came to
05:08 : this
05:09 : with the mindset of immutable data
05:11 : structures
05:13 : because i started off with you know
05:16 : redux that's where my head was i'm
05:19 : thinking about
05:20 : redux and you know functional
05:23 : programming
05:24 : immutable data structures that that's
05:27 : and get
05:28 : i really like how git does things and
05:31 : that's based on immutable data
05:33 : structures
05:34 : um and that's why i had things
05:37 : represented this way
05:39 : whenever i make a change to an object i
05:42 : make a new version of the object
05:44 : with the added change to it but instead
05:46 : of
05:47 : modifying the old one i make a new one
05:51 : um and there are ways
05:54 : to shrink things uh even
05:58 : you're gonna only uh record the change
06:01 : and then you just like go from like
06:04 : state zero and
06:05 : add a change in add uh great i i don't
06:08 : want to do that because if i did
06:10 : that that means in order to go back to
06:12 : any point in time i have to replay
06:14 : some of the things right that's true
06:17 : yeah and i don't want to have to do that
06:19 : because the point of this database is
06:21 : you can jump into any point in time very
06:24 : quickly
06:25 : without having to replay anything
06:29 : so the plan is actually to
06:34 : add a add one more level of indirection
06:39 : okay so
06:42 : so the key being composite objects and
06:46 : this is
06:46 : i i honestly i'm stealing this from bill
06:50 : lewis's omniscient debugger
06:53 : uh i read his paper and this is how he
06:56 : does it uh as far i can understand
06:59 : his language in his paper
07:02 : basically if you have any composite
07:05 : object
07:08 : which includes lists dictionaries
07:11 : objects
07:14 : uh you know in javascript terms
07:18 : maybe this is like this
07:24 : um so currently i'm saying you know if i
07:28 : add wanted to add
07:32 : one a new property i'm gonna have to
07:36 : just make a new object and save that but
07:40 : instead of doing it this way what i'm
07:42 : gonna say is
07:45 : i'm actually going to have an object
07:48 : first of all each object has an id
07:51 : oh is it like an expression like object
07:54 : 1 plus
07:55 : object 2 and then you get the object
07:57 : three but
07:58 : no no no uh
08:03 : i can see where you're going but then
08:04 : you have to remember
08:06 : what expressions uh give you the object
08:10 : you have to go back to compute the
08:12 : expression in order to
08:13 : get the object um
08:17 : i don't know but my plan is actually
08:20 : this
08:20 : uh okay this
08:23 : is like this is uh gonna be
08:27 : even if currently i have these
08:29 : references already
08:31 : right yeah i'm gonna make everything a
08:34 : reference
08:36 : even if it's a number or a string like a
08:39 : primitive
08:40 : type i'm gonna make these references
08:43 : okay and therefore if um
08:47 : now if so well okay so first of all if
08:50 : you
08:50 : change the age if you change the age
08:54 : then object 3 used to be 19
08:58 : we're gonna change object 3 to 20.
09:02 : um and you say how do you change it's
09:04 : immutable
09:06 : the way you change things in an
09:08 : immutable
09:09 : space is you add a version number
09:13 : okay so
09:16 : so like three at version one is 19
09:19 : and three at version two is 20 now maybe
09:22 : this is
09:23 : one one at version one right one
09:26 : one is this person object and one's name
09:30 : is pointing to two
09:33 : two at version one is bob correct
09:37 : and so forth so so the one more level of
09:40 : indirection
09:41 : here means means whenever i make a
09:44 : modification to the person object i'm
09:47 : i'm not changing the structure i'm just
09:50 : changing the leaf value but i'm by a
09:53 : change i don't mean change but i mean
09:56 : add a new version of the value at the
09:59 : leave level
10:01 : which does not disturb the parent level
10:03 : at all
10:04 : so what how what do you do when you add
10:07 : a property
10:10 : yeah yeah okay so when we add the
10:12 : property is more complicated
10:14 : because um so what i
10:18 : decided and you can critique me on this
10:20 : because um
10:22 : you know i just came up with this
10:25 : it might not be good so uh what my
10:28 : thought
10:29 : now is in order to deal with these you
10:31 : know
10:32 : any any composite object it's going to
10:34 : have any
10:35 : a number of key or a number of entries
10:39 : right inside a composite object
10:42 : now for for dictionaries you know the
10:45 : entry is a key value pair
10:48 : for this i can look at it still as a key
10:51 : value pair it's just the keys are
10:54 : integers okay um
10:57 : so that's the thought so
11:00 : so for each entry inside a composite
11:04 : object
11:05 : i'm going to have separate database rows
11:08 : in order to represent those so it
11:10 : actually becomes
11:12 : one is an object
11:16 : and then i'm gonna have an
11:19 : entry one
11:25 : name points to
11:29 : two entry one age
11:33 : points to three
11:37 : and so this represents the
11:40 : this is saying hey one has an entry
11:44 : of name and it points to the
11:48 : object two and one has the
11:51 : entry of age and
11:54 : it points to the object three
11:57 : um but but uh there's like a one
12:01 : penny basically it's like well it's like
12:03 : a one too many from
12:05 : an object to version and it's another
12:07 : one too many from
12:08 : version to property yeah yes
12:11 : that's what it is but in reality you
12:13 : know the key
12:15 : is not a string necessarily the key
12:18 : can be anything in python actually but
12:21 : anything
12:22 : that's hashable so so this
12:25 : this actually becomes another reference
12:29 : to another thing so like okay for
12:32 : the first version of four is the string
12:35 : name and then you know
12:39 : we have to do something like that and at
12:41 : this point it's
12:42 : like you're like wow this is a mind
12:45 : bender
12:46 : this is really this is like
12:49 : you know i have to follow a lot of leads
12:52 : just to get the full picture
12:54 : kind of thing right everything has made
12:57 : been made very indirect
13:00 : yeah and yeah i i would think
13:03 : that is that does make things harder to
13:06 : debug
13:07 : um unfortunately um yeah that's
13:10 : true but um and i don't i don't have a
13:14 : great answer to that necessarily i don't
13:15 : have a solution to that
13:18 : uh yeah there is a disadvantage of this
13:21 : approach whereas
13:22 : with the current approach the way it's
13:24 : implemented now
13:26 : debugging okay it's not extremely easy
13:29 : but it's
13:30 : relatively straightforward i can look at
13:32 : you know that
13:34 : object i can you know figure out
13:37 : the point in time of a certain
13:40 : you know heap object i can look up its
13:42 : version number to find out which object
13:44 : represents a state
13:45 : and go look up that object and i know
13:47 : what the object looks like
13:49 : whereas with this one i will need a sql
13:53 : query
13:54 : that will be able to combine the entries
13:57 : with the original object
13:58 : and then join it again to the actual
14:00 : values
14:01 : in order to in order to figure out what
14:04 : the object
14:04 : actually is um so yeah to answer the
14:08 : question if you want to add a gender
14:11 : and add another entry to this object
14:14 : we're gonna add
14:16 : you know another uh we're saying
14:20 : object one there's also a version number
14:24 : in there's also a version number
14:27 : inside the entries as well so version
14:30 : two
14:31 : of object one has a this entry
14:36 : and then maybe this is six and then it
14:38 : points to
14:40 : seven and then six
14:44 : is the string gender and then
14:49 : uh seven is going to be
14:52 : the string now so
14:55 : that's how that's how we add an entry oh
14:58 : so what's the
14:59 : difference between the two numbers after
15:02 : entry
15:03 : like which one is which one's version
15:09 : this one this one is the id
15:12 : of the container of the entry which is
15:15 : this guy
15:16 : okay and this you know empty object
15:20 : that doesn't mix doesn't doesn't really
15:23 : matter
15:23 : that you know it's md object plus its
15:26 : entries
15:27 : and then this is the version number
15:30 : version number is like
15:31 : the overall like it's a global number
15:34 : within the whole
15:35 : application is the state
15:39 : of all the objects that's what that
15:41 : represents
15:42 : so the state state one of the whole
15:45 : application
15:47 : uh you know i i
15:50 : basically gather all these
15:54 : other things that are tagged with that
15:56 : version
15:57 : or less that that's how i
16:01 : figure out what things are at version
16:04 : one
16:04 : of the history of this program well
16:08 : you did this for something before right
16:11 : like a similar thing but not for the
16:14 : object
16:15 : uh just yes you're right yeah right i
16:18 : did this for the heap
16:21 : i did this for the heap okay
16:24 : uh where like this this heap
16:27 : ref table is um
16:30 : means this heap ref is a reference to a
16:34 : heap object in the in memory of the
16:37 : program
16:38 : okay and this id is actually
16:42 : you know a unique identifier that
16:44 : identifies a
16:45 : a heap object in the program and a heap
16:47 : object is anything
16:48 : is a list is a dictionary is an object
16:51 : those are
16:52 : all objects in python um
16:56 : but in in more general terms a heap
16:58 : object is
17:00 : you know something that's allocated in
17:02 : dynamic
17:03 : memory instead of in the local
17:06 : variables of a function
17:10 : and it stays around for longer than
17:13 : then a function you know is finished um
17:19 : and this heap version yeah this heap
17:22 : version
17:23 : is again it's the state
17:26 : version number of the entire application
17:29 : so
17:29 : this is heap version 2 means you know
17:34 : not necessarily time to but it's it's
17:36 : the second
17:38 : version of the entire
17:41 : uh state of the entire application
17:45 : and anytime anything changes in the
17:47 : state of the entire application
17:49 : this version number goes up by 1.
17:54 : so this is basically and anytime you
17:57 : make a change
17:58 : to anything we're going to get a
18:02 : new entry here
18:05 : with the next version number
18:08 : is oh well i guess how i see it is like
18:10 : can you see like the
18:12 : whole state of the entire application as
18:14 : a big object
18:16 : yeah and then yeah it's just the same
18:18 : idea as what you
18:19 : did for the object this is just another
18:22 : player on top but it's exactly the same
18:24 : it is exactly the same i did this
18:26 : transformation because
18:28 : before i did this architectural change
18:31 : my heap was actually represented as a
18:34 : huge object
18:36 : and that was that was so ridiculously
18:39 : bad
18:40 : that i said yeah i have to do this but i
18:43 : think
18:44 : now i have to do this even at a finer
18:46 : grain level
18:47 : for for all the individual objects
18:50 : so i think that's not totally like
18:54 : oh like uncomprehensible
18:59 : what what like i guess that's
19:02 : that's i guess since you explained it to
19:04 : me last time about the heap
19:05 : now it's like kind of i can like
19:08 : basically understand this
19:09 : and then also just with one sql query
19:12 : you can
19:13 : get what you need so
19:16 : that's true it isn't that bad i
19:19 : i mean if it was really bad that i
19:22 : probably wouldn't do it but
19:24 : on the other hand it it does make
19:26 : debugging
19:27 : difficult because i imagine
19:31 : it will make it hard for me to just
19:33 : browse through this data
19:35 : and see what's going on you just have to
19:38 : use sql
19:39 : yeah i have to have this i have to have
19:42 : a bunch of
19:43 : little utility sql statements
19:46 : and then go in here and paste them in
19:49 : and then
19:49 : run them or maybe build some sort of
19:53 : tool some command line or graphical tool
19:56 : for me ultimately the debugger is the
19:59 : ultimate graphical tool that helps with
20:01 : all of that
20:02 : but that has to be bug free before it
20:05 : can be useful
20:07 : that's true yeah yep um
20:11 : yeah so that is the plan and uh
20:14 : i'm hoping um that they will give
20:18 : us a lot a big performance boost
20:21 : and and a much you know disc
20:24 : storage much smaller disc
20:27 : uh usage so
20:31 : but obviously if we do that that means
20:34 : like the json like language is out
20:37 : because we're not
20:38 : we're not even going to serialize the
20:40 : data anymore oh
20:42 : that's important yeah well
20:47 : it's so nice it's a nice uh cost
20:51 : for us to make the closure experience
20:55 : better yeah like yeah yeah so
20:58 : if you look at the log file right now
21:02 : log file is
21:08 : okay so the log file kind of looks like
21:10 : this uh
21:11 : you can see the generated sqlite
21:14 : database
21:15 : is roughly double the size of the log
21:18 : file
21:19 : okay it's 659 for the sqlite database
21:23 : 323 for the size of the log file
21:26 : okay another example you know this
21:30 : is the time nav tool i been working on
21:33 : 4.5 megabytes for the log file
21:36 : and 10.5 megabytes for the sqlite
21:39 : database
21:39 : so the sqlite database is even
21:44 : more than the log file which which
21:48 : or immediately tells you yeah there's a
21:50 : lot of data duplication
21:52 : right and i and
21:55 : because even this log file in this log
21:57 : file this log file is not
21:59 : that efficient in terms of
22:04 : serializing the data there's a lot of
22:08 : unnecessary characters
22:11 : in this vlog it is not very streamlined
22:15 : so so if even that is the case and your
22:18 : database
22:18 : is still double the size of this log
22:20 : file that's clearly
22:22 : inefficient so i'm hoping that we'll get
22:26 : a
22:27 : huge reduce
22:30 : in the size of the database maybe on the
22:33 : order of
22:37 : 5 to 10 times less oh wow
22:41 : that's that's my hope we'll see how it
22:44 : actually goes