00:12
hi my name is Pierre Vicco I'm a
00:15
software engineer at square and today
00:18
I'm gonna talk about shark and diving
00:20
into the guts of Li Canaries hedge
00:22
professor so I also have stickers so the
00:29
stickers here if you're interested in
00:31
getting a leak and art seeker talk to me
00:34
after the talk or any time during the
00:35
conference and I'm happy to give them
00:37
away to you so so I guess I'm gonna do
00:41
kind of show in hand how many people
00:43
have used the Qunari before I'm assuming
00:45
you're here because you know what it is
00:47
because otherwise it's kind of a weird
00:48
talk to go to so let's see couple months
00:53
back in April I released Lee canary too
00:56
and so it was a completely rewrite we
01:00
wrote everything to cut Lynn but we also
01:02
reword the edge professor and so there's
01:07
essentially a new hidden parser and it's
01:10
called shark and so shark stands for
01:14
smart hip analysis reports for Catlin I
01:16
just I really wanted to use chalk as an
01:19
acronym and so I had to figure out a way
01:20
to make it make it fit in so essentially
01:26
it's the same as before but rewritten
01:28
from scratch and way faster and way less
01:30
memory it also comes with a command-line
01:34
interface which I know if you can read
01:36
from here it has a nice ASCII art thing
01:40
but you can also run comments where you
01:42
can you can ask it as the command line
01:44
from your desktop to run the dictionary
01:46
and I just use on an on an app that
01:48
doesn't even have the library so it's
01:52
it's pretty interesting it's getting
01:54
kind of difference so today we're gonna
01:57
look into what's inside shark and
01:59
hopefully we're gonna learn a few things
02:01
from that so I guess the first question
02:05
is what is a heap dump parser
02:08
what is that doing exactly in in the
02:10
culinary right like so we have to talk a
02:12
little bit about how the canary works so
02:15
since V 2 essentially the way you use it
02:18
is all you do is you add
02:19
dependency and that's it it works out of
02:22
the box you just added dependency you
02:23
don't even have to write any code and it
02:25
just works it's using a content provider
02:28
hack to would strive itself on app
02:30
startup and then what it does is it
02:35
installs an activity lifecycle called
02:37
back on the epicly application class and
02:40
whenever an activity is destroyed it
02:43
passes that instance to an object
02:45
watcher and what the object watcher does
02:49
is it creates a weak reference to the
02:51
activity instance and that weak
02:53
reference go into a reference queue and
02:55
then if the after a while if the weak
02:59
reference isn't clear the the object is
03:02
considered retained and when that object
03:05
is considered retain we call an Android
03:08
API which is a pretty cool API that's
03:10
called debug that's dumped each probe
03:13
data and that actually calls into an
03:16
avid native API behind the hood behind
03:18
the hood and under the hood and that
03:21
actually copies the entire memory of the
03:23
entire heap of the VM into a file and
03:26
that's called an H proof or a heap dump
03:28
that's the same thing if you were to if
03:31
you're actually curious about how it's
03:33
happening is actually happening within
03:34
your process in the native code and
03:36
there's this file H proof that CC that
03:38
has all the details about how that's
03:40
happening it's not very useful for your
03:41
day-to-day development but it's kind of
03:44
cool so after that we can re the heap
03:49
parser will parse that file and that's
03:51
what we're going to talk about today and
03:52
output the dictionary results that you
03:55
know and then you can use that results
03:57
to find your leaks or maybe you find a
03:59
leak in a osv and you submit tickets and
04:04
maybe someday it will be fixed we're
04:08
hoping for that anyway so let's talk
04:12
about how hit dumb parsing works and how
04:16
we can find memory leaks but to do that
04:19
we have to talk about garbage collection
04:21
so who has some vague idea of how the
04:25
garbage collector works oh great
04:28
everybody I don't really need to talk
04:30
about this then let's get into some
04:33
the details so the best way to explain
04:37
garbage collection is to read Wikipedia
04:40
so in computer programming tracing
04:43
garbage collection is the form of
04:45
automatic memory management that
04:46
consists in determining which objects
04:48
should be de-allocated garbage collected
04:50
by tracing which objects are reachable
04:52
by a chain of references from certain
04:55
routes objects considering the rest as
04:58
garbage and collecting them it's
05:01
interesting because tracing garbage
05:02
collection is the proper word there's
05:03
other ways to do garbage collection like
05:05
reference counting I think I owe a thing
05:08
we we have it way easier with our
05:11
tracing garbage collection just magic
05:13
right Wikipedia also has this really
05:15
nice gif which shows how it goes from
05:19
the roots and then explores the graph of
05:21
objects through the reference between
05:23
objects right and then everything else
05:26
gets everything that hasn't been mark
05:29
gets sweeps it's the mark and sweep
05:32
algorithm you may have heard that before
05:34
so that's cool and then the next
05:39
question is what is a GC roots what's
05:41
that's we keep talking about that right
05:43
and Wikipedia again a distinguished set
05:48
of roots objects that are assumed to be
05:49
reachable so essentially they're saying
05:52
it's variables on the call stack and
05:54
global variables so static fields the
05:58
most common one is static fields and
05:59
that's why if you put an activity in a
06:01
static field guess what it's not gonna
06:02
be garbage collected right and then you
06:04
have an activity leaking okay thanks
06:08
Wikipedia so we know how garbage
06:12
collection work in practice it's a
06:14
little bit more complicated than that
06:15
but it's kind of the general idea and if
06:19
a heap dump is a copy of the memory the
06:21
heap dump really sees the same thing
06:23
that the Garlic garbage collector sees
06:24
so what we're gonna do is our hip dumb
06:28
parser is gonna be very similar to what
06:30
the garbage collector does with the live
06:32
memory and essentially so this is a
06:36
graph that represents something in
06:38
memory at the top you have a bunch of
06:39
garbage collection routes and then you
06:42
have they have references to objects we
06:44
have references to other objects so in
06:47
references so if we were to run a mark
06:49
and sweep the GC with mark would mark
06:52
all of the objects and the other ones
06:53
would be swept because they were not
06:55
reached from the roots so that's cool
07:01
the GC went through it garbage collected
07:03
everything that's really cool and then
07:07
turns out one of these objects that is
07:09
referenced is an activity that is that
07:12
has em destroyed true
07:13
it's a destroyed activity but it wasn't
07:16
garbage collected because there's a
07:17
reference that's reaching it right it's
07:19
a ritual object but we know that a
07:21
destroyed activity should not be
07:23
reachable it should be garbage collected
07:25
and that's where laconic dictionary
07:28
comes in why right we we had a weak
07:29
reference to the activity so we know it
07:31
should have been garbage collected and
07:32
it wasn't so we make a copy of the
07:34
memory and now we need to find the paths
07:38
from the roots to that activity so we
07:43
want to find why this instance is kept
07:45
in memory and to do that we really have
07:47
to do exactly like the garbage collector
07:49
we have to traverse the graph of objects
07:52
so here if I was to ask you if you look
07:55
and you're like well why is this object
07:56
still in memory your brain is actually
07:59
really good at doing pest fighting and
08:01
it will immediately tell you well you go
08:03
from here and maybe you take that or row
08:04
and that row and that's how you get here
08:05
right so we can do that in code and it's
08:11
not really not that hard our brain
08:13
aren't that smart anyway so it turns out
08:19
that here I try to draw the the all of
08:21
the paths from the GC roots to the
08:23
object and you can see that there can be
08:24
many in practice we could look at all of
08:28
the bus but we only care about one it
08:30
doesn't really matter which one we know
08:32
that if there is a leak the leak is
08:34
going to show up on all of the paths so
08:36
we pick one and what we do is we pick
08:38
the shortest simply because it's less
08:40
information to look at so let's pick the
08:44
shortest one and this is kind of what
08:47
leak energy shows you on the on the on
08:50
this side you see the typically canary
08:52
UI and on that side it's kind of the
08:55
representation that I had one of the
08:58
interesting things is that Li canary
08:59
also runs some heuristics to tell
09:01
I think this object is leaking this
09:03
object is not leaking which helps it
09:04
understand which parts which references
09:07
are potentially bad so you can say well
09:09
I here's the pass but actually I know
09:12
this and these are probably where the
09:14
problem is cool so now we know what the
09:20
heap analyzer in the canary does so
09:25
let's talk about heap parsing when I say
09:26
heap analyzer in here parsing I mean he
09:28
parsing is like parsing the file and
09:29
then doing the smart stuff on stuff on
09:31
top is a kind of a heap analyzer so if
09:36
you've used Android studio
09:38
okay who's used a memory profiler in
09:41
Android studio like this this nice
09:42
beautiful charts Wow everybody that's
09:44
amazing so there's a button there it
09:47
doesn't look like much it's kind of a
09:49
square with an arrow and it means dump
09:51
the heap and what it does is what we
09:53
talked about could be the memory heap
09:55
into the in the Java heap into a file so
09:57
you can do that and if you do that you
10:00
will see this which is kind of useful
10:04
but not really but that's what Android
10:06
studio provides you with to analyze that
10:09
memory and what's happening under the
10:12
hood is they have their own heap dump
10:14
parser and that that's what's used to
10:17
represent that information what's really
10:20
interesting here and something that I
10:22
encourage you to look at is the Collins
10:25
so allocation is the number of objects
10:28
that exist of that specific type shallow
10:30
size is the so this is a sum so you have
10:34
two months so basically every object in
10:36
memory has a uses a chunk of memory
10:39
right I need eight bytes for long I need
10:42
four bytes for a bit for an inch and
10:43
then you do the sum of that and that's
10:46
the shallow size of that object and then
10:48
here they multiplied it by the
10:49
allocation so you know you have you know
10:51
six bags of object erase what's way more
10:56
interesting is the retain size so let's
10:59
talk a bit about that
11:01
so I zoomed in on the graph that we had
11:04
before the retain size this is a
11:07
Wikipedia again I think returns or maybe
11:09
some other website retain size of an
11:10
object is it's shallow size plus the
11:12
shallow size of all of the objects that
11:15
directly or indirectly only from these
11:18
objects in other words the retain size
11:20
represents the amount of memory that
11:21
will be freed by the garbage collector
11:23
when this object is collected right so
11:26
here if we remove the reference from the
11:27
top all of a sudden this is isolated it
11:29
all gets garbage collected and we would
11:32
reclaim 6 times 32 bytes I don't know
11:35
how much that makes is too hard to
11:37
compute so yeah it's some of the shallow
11:42
sites and so what's kind of interesting
11:43
here is that how do you compute retain
11:47
well it's something called dominators
11:50
it's kind of a interesting word but you
11:54
you do what's called computing
11:56
dominators and essentially what you do
11:57
is for each object you try to find which
12:02
objects you have to go through to get to
12:04
it right and this and if I have another
12:07
object and you if I have a first object
12:09
and a second object and you have to go
12:11
through the first object to get to the
12:13
second object then the first object is a
12:15
Dominator of the second object and so I
12:18
can take the shallow size of that second
12:19
object and add it to the retain size of
12:21
the first objects and so that's that's
12:27
interesting because it's gonna tell us a
12:28
lot about where our memory problems are
12:30
which is what we're gonna dive into in a
12:32
little bit so if we look back so this
12:36
was the this is the thing that's in
12:37
Android studio when this came out I
12:40
realized that this was a heap dump
12:41
parser and I needed one for leakin re
12:43
and so this is a backed by a library
12:46
called per flip which leaves in AOSP
12:48
so I essentially repackaged it and
12:51
called it heap what is it headless
12:55
Android heap analyzer but short for haha
12:58
and yeah I like good library names and
13:03
it worked really great and I didn't have
13:05
to write heap the parser so that was
13:07
amazing I just had one out of the box I
13:09
just had one little problem
13:12
out of memory error we kept having
13:16
people reporting out of memory errors on
13:18
big hit dumps we also had the same issue
13:20
so let's dive in let's figure out why we
13:26
have an out of memory error
13:28
with our hip Dom parser that's supposed
13:30
to help us prevent out of memory errors
13:31
is kind of ironic so what I did is I
13:35
wrote an instrumentation tests I took
13:38
two edge profile so those are again
13:40
copies of the memory there's a large
13:42
dump and a huge dump one of them is for
13:45
Team X the other one is 160 Meg's and
13:48
then let's let's start the test and run
13:51
the profiler so you probably have
13:53
noticed this if you try to profile a
13:55
test there's no way to say well there is
13:58
an entry that says profile this test but
14:00
the profit of the test is not gonna wait
14:02
for the profiler so by the time the
14:04
profiler initializes the test is already
14:06
done and it's kind of like sad so the
14:08
way we work around that is freeze thread
14:10
that sleep and that way we have enough
14:12
time to hook up the profiler great hacks
14:16
okay so so for the large dump so let's
14:21
see this is what I what I got so you can
14:26
see it's kind of like analyzing its
14:27
parsing the heat dump and then it's
14:28
gonna start analyzing it so here you can
14:32
see this about you cannot see probably
14:33
because it's too small but there's about
14:34
140 Meg's of Java memory used and 180
14:41
total there's other there's about 40
14:45
Meg's of other memory let me talk about
14:48
that in a minute but essentially you're
14:51
like that's already kind of a lot okay I
14:55
just before we go into other things I
14:57
wanted to mention there's a new
14:58
benchmark library from Google that's
15:00
supposed to be really good for these
15:02
kind of things or just benchmarking and
15:05
performance tests the problem is that it
15:10
does two things it warms that it
15:11
basically locks the CPU so that it's
15:14
always a hundred percent and it's
15:15
constant and you don't have variations
15:17
there and then it runs the code as many
15:19
times as necessary to show that to make
15:23
sure that there's no statistical
15:24
difference the problem is as many times
15:26
as necessary is a lot of times and the
15:27
canary takes you know about a minute or
15:29
two to run so if you try to wait for it
15:32
to run I don't know ten thousand times a
15:33
minute like nobody has time for that so
15:37
you can't really customize the duration
15:39
so the benchmark library so
15:41
useful that hasn't been useful to me I
15:43
guess another library worth mentioning
15:46
is nano scope and I just completely
15:49
forgot to look at it but it's
15:50
essentially a modified version of of
15:53
Android it's like it's a specific
15:56
emulator that has the ability to do
15:58
performance measurements without
16:00
overhead because it's directly in the OS
16:02
and that's pretty cool okay so let's
16:05
look at the huge dump alright so same
16:11
same kind of deal except now we're the
16:13
I'm when I'm reading is 350 400 400
16:16
megabytes and 550 total and that goes
16:19
for about its accelerated of course
16:21
we're not wait all day it goes for about
16:24
four minutes and then it goes up and it
16:28
stops you're like cool did it take four
16:31
minutes and 500 Meg's to succeed well if
16:35
you look at the logs you realize that
16:37
what it's actually doing is just running
16:39
the GC all the time until it says I got
16:42
an out of memory error and then the
16:44
actual error is I got an out of memory
16:46
error trying to throw an out of memory
16:47
error so I can't even give you a stack
16:49
trace so that's that I was like okay
16:53
cool I'll try to open so in Android
16:55
studio you can save the edge profiles
16:57
and then you can we empower them later
16:58
so I try to open that same huge file
17:01
into Android studio this was the memory
17:03
before so that's like the baseline it's
17:05
using about six hundred Meg's then it
17:07
opened it I waited I waited I waited and
17:11
then it was done and I have about two
17:13
gigs of memory used just to parse and
17:16
analyze that 160 megabytes each probe so
17:21
it's like oh that's a lot so let's start
17:25
doing performance optimization and
17:28
focusing on the memory side of things so
17:30
we're gonna take a heap dump of our heap
17:32
parser and we're going to start
17:34
analyzing that and it's kind of meta do
17:38
that well here I just again put a
17:40
threaded sleep and that way the thing
17:44
was waiting at the right time right
17:45
after parsing and I could click the
17:47
little button and get a hip done except
17:50
I did not exceed that heap dump in
17:52
Android studio because Android studio
17:55
gives you like a list of classes in
17:56
there sighs and that's it there's
17:58
nothing else that as far as I I've been
18:01
able to explore the tool I haven't found
18:03
a lot of useful things there's another
18:06
tool called your kits which is kind of
18:09
old but works really well unfortunately
18:12
it's not free you have to pay for it
18:15
get a license or if you're doing open
18:17
source work they give you a free license
18:20
so I did that I imported into into your
18:24
kit and I opened this view called the
18:27
top dominators so now you know what a
18:28
Dominator is you can it essentially
18:32
tells you where the objects that if
18:34
there were garbage collected you would
18:35
reclaim the most memory and here it's
18:37
telling me well 94% of your memory would
18:39
be reclaimed if that object was garbage
18:41
collected and that's the step snapshot
18:43
which is essentially the object that
18:45
wraps the parts parts to heip them so
18:49
that's cool and then we can say hey your
18:51
kids show me for that one objects show
18:54
me the composition of the different
18:56
types that is hauling not not just
18:59
directly but also transitively to kind
19:03
of understand what the memory is made of
19:05
and here we can see that there's about
19:10
so I kind of there's again two columns
19:13
this time I sorted by shallow size
19:16
because what I'm interested in is the
19:18
raw size of every type cumulated by you
19:20
know the number of instances so I can
19:23
see I have a hundred 125 Meg's of class
19:27
instance and class instance is
19:30
essentially so what's going on is this
19:32
in this heap dump is that it was taken
19:34
not theirs to hit thumbs here right
19:36
there's the one that we're looking at
19:37
which is of the hidden parser and
19:39
there's two hip them that the hip hit
19:41
the parser was parsing so I'm talking
19:42
about that other one it was parsing a
19:44
heap dump with about 1.4 million objects
19:48
and that use about 125 just those are
19:52
just the instances of class instance
19:54
which represents it's like object in
19:56
Java but in the hip dam world that was
19:59
120 Meg's then there's ArrayList it's
20:02
using about 80 Meg's array is instance
20:06
which wraps an array is about 70 Meg's
20:08
so you can see it's kind of a lot and we
20:11
have a lot of essentially to hit them
20:13
with a lot of objects and therefore its
20:14
overall using a lot of memory one of the
20:18
interesting thing with array list is the
20:21
shallow size is very close to the retain
20:23
size we see 80 Meg's of shallow size 115
20:26
makes of retained size what's actually
20:28
happening here is that every single
20:32
class instance has a reference own
20:35
creates an empty list and it keeps a
20:37
reference to an empty list and so you
20:39
have 1.4 million empty lists and so just
20:45
like these things add up when you're
20:46
looking at millions of instances and
20:49
this is what a class instance look like
20:50
and so you can see there's a bunch of
20:51
fields and so now we get into how much
20:54
memory does my object use and that's
20:57
that's always interesting so in Java the
21:02
answer is always it depends right and in
21:05
this specific case it depends but
21:09
essentially on the 32-bit VM the object
21:14
in memory will use 12 bytes for the
21:19
header so that's going to be a reference
21:21
to the class a bunch of random things
21:23
that are in there and then four bytes
21:26
for every to every reference if it's a
21:28
64-bit VM a would be sorry eight bytes
21:33
so here if you did the count you'd end
21:36
up with 88 bytes so every class instance
21:38
is taking eighty eight bytes multiplied
21:40
by you know 1.4 million that's a lot of
21:42
megabytes as I was looking at this code
21:46
I noticed that one of the interesting
21:48
things about classes stands is that it
21:50
does not actually hold the the list of
21:52
fields and their contents it holds a
21:55
pointer into the file this is December
21:58
use offsets and when you try to read the
22:01
contents of an instance it actually goes
22:03
to that file and reads that and I
22:05
thought that was an interesting
22:06
interesting idea that we could take
22:07
further and essentially remove a lot of
22:10
the data in class instance and a bunch
22:12
of other objects and just keep the
22:14
pointer and I have a map of an object ID
22:17
to the pointer in the file and that way
22:19
when we need it which is good enough I
22:21
uses way less memory so to kind of
22:26
understand how we are going to use that
22:30
we need to talk about what the cannery
22:32
does next like the finding the pass from
22:35
the GC roots to the leaking instance so
22:40
we're gonna do something called a
22:41
breadth-first search which is a scary
22:46
name that you know reason it's like oh
22:48
you're about to do a google interview
22:50
but it turns out no and it's not that
22:55
hard so we're gonna get through that
22:56
together the general idea is that we're
22:59
gonna have a queue first in first out
23:02
queue so what's the queue I could be an
23:04
ArrayList it's just that you know it's
23:06
just an array of things and you put
23:07
things on one end and you take things
23:09
from the other end and what that queue
23:12
will contain is it will contains the
23:14
temporary paths that you're building as
23:16
you're exploring the graph so we're just
23:19
gonna go and we're gonna put the GC
23:20
roots in that and then we're gonna take
23:22
the first GC root out and we're gonna
23:24
say well okay where do you go to what
23:27
are the things your points you okay
23:28
we're gonna take those things create a
23:30
new path that has those new things on
23:31
top put that back in the queue pop up
23:34
the next thing which is another GC roots
23:35
etc etc and progressively the queue will
23:37
contain longer and longer paths until we
23:40
find the instance we're looking for and
23:42
then that path is what we need so let's
23:46
get into actual code so we have a
23:49
reference pass node it's what is that
23:51
well it's just the thing that holds an
23:53
object ID and then so it's still a sill
23:57
class in Catalan and it's got two
23:58
subclasses one of them is root node it's
24:01
just the object ID and then shine node
24:03
is a node that has a parents and so pass
24:06
is essentially which I know that points
24:08
to parent node that points to parent
24:10
node that points to a root node and so
24:13
how do we do this it's really really not
24:17
that hard we create an array deck I
24:21
think of it like an ArrayList it's a
24:22
it's a it's a double entry queue that is
24:24
backed by an array and in a hash set of
24:28
what we visited so that we don't keep
24:30
visiting the same nodes otherwise we're
24:31
just going to turn forever
24:33
and then we like I said we include the
24:35
GC root so we go over every one of them
24:37
and we put them in the queue and in the
24:39
visited list and then while there are
24:42
stuff in there in that queue we keep
24:45
going and what we do is we get the entry
24:48
at the top of the queue and we say is
24:50
this the thing I was looking for yes
24:52
okay well then I have my path I have
24:54
this channel that's planning to fire a
24:55
parent node pointing to a parent node
24:57
etc if not then I'm gonna read that
25:00
object get its references and the
25:04
reference is that it points to and I'm
25:06
gonna add each one of them if I haven't
25:08
visited them yet I'm gonna create a new
25:10
node that points to the parent node and
25:12
I'm gonna put that back in the cube if I
25:15
haven't ever if I went through the queue
25:17
and there's nothing left then I couldn't
25:19
find the instance there's no pass and
25:21
that's it we just did a breast first
25:23
search and if you understood that with
25:26
all the noise and you know you're tired
25:28
from your lunch and all of that then
25:30
you're ready for I don't know if you're
25:32
ready for the Google interviews you're
25:33
ready for the square interviews for sure
25:35
just throwing that out there so who has
25:42
actually who's so who studied breasts
25:45
first search or saw it before like it's
25:47
something that's is it something that's
25:48
kind of okay a good part of the the room
25:51
cool so so okay we know we only need
25:55
like a map of an object ID to its
25:57
position in the file and we realized
25:60
that perfectly is reusing way too much
26:02
memory so we're gonna need to write our
26:05
own hip dumb parsers and it took me I
26:07
think it took me about three years not
26:09
doing it but for three years I was like
26:12
I don't want to do it I don't want to do
26:14
it until I finally cave and I started
26:16
looking and so I was like I'm gonna look
26:18
at the spec of how the edge performer
26:21
works right it's gonna be nice and very
26:23
well detailed and this is the spec it's
26:27
an HTML file from file from the 90s it
26:32
it's kind of long it's got a lot of
26:35
things in there so if we kind of dive in
26:38
they tell you okay so at first you have
26:41
a string that represents the version and
26:43
you basically have a bunch of characters
26:45
until you have a zero
26:46
and that's when you were you know when
26:47
you know that it's the end of the string
26:48
then you have the size of 8-inch fires
26:51
so like I said on 32-bit I don't know if
26:56
I said that on 32-bit VMs a reference
26:59
takes four bytes on 64-bit vm a
27:01
reference takes eight bytes and so this
27:04
tells you well it takes four bytes or 8
27:06
actually they supposedly you can have
27:09
two byte references or any number now
27:12
which is kind of insane and then we
27:15
don't care about number of milliseconds
27:17
whatever and then essentially what's
27:19
what's inner hip dump is a tag that says
27:21
here is a record of this type and then
27:24
the the lens like how many bytes it's
27:27
gonna be for that record and then the
27:29
contents so it's just byte arrays and in
27:33
there you have stuff like strings so
27:35
these are not your Java that leg nut
27:38
string that you have in your program
27:39
there are actually strings that are the
27:41
name of the names of the classes and the
27:43
names of the fields and only that and
27:47
you have things like load class which is
27:49
just essentially a map from a class ID
27:52
to a string ID so that you can associate
27:55
a class with its name you have things
27:58
like your class dump which contains two
27:59
details of the class but it does not
28:01
have an ID for the string that's the
28:04
name of the class so you have to find
28:05
the load as the class dump and the
28:07
string ID if you want to know the name
28:09
of a class and you know the details of
28:13
the static fields and how many bytes
28:16
they use and that kind of stuff okay so
28:19
that's kind of cool and this is
28:20
primitive arrays so we can get started
28:23
so to kind of help you visualize what
28:26
this is about I rendered it so this is
28:31
an H edge profile obviously it's super
28:35
useful that way and I'm sure you can
28:37
totally understand it so I'm not gonna
28:39
go into details it's so obvious so I'm
28:44
just kidding but I'm still not gonna go
28:47
into details this is a feature that I
28:48
added in the Qunari and there's no good
28:50
reason for it I just found it cool to be
28:52
able to visualize what the H prof looks
28:54
like and it's the different types of
28:57
records that are in the
28:59
five so how do we parse it hit them
29:01
where we're gonna use okie IO because
29:02
okay i/o is amazing and also it's
29:05
actually fairly easy I have a file I
29:07
have this cuttin extension method that
29:09
gives me an input stream so far so good
29:10
and then ochio provides other extension
29:13
methods on the input stream to get a
29:14
buffered source which is essentially
29:17
something that that reason chugs so okay
29:21
I got that I need to read that string so
29:23
we basically locates the first zero and
29:25
everything that's before is the string
29:27
the version of the name of the version
29:29
and then sorry the name of the type of
29:32
each probe and then we skip one because
29:34
we want to skip that zero then we read
29:36
an int okay to know the size if it's
29:40
four bytes or eight bytes for references
29:42
the timestamp so far so good
29:45
and then we essentially just loop on the
29:49
source until there's no bytes left we
29:52
read a tag and so this looks like magic
29:55
I wrote this code but I did not quite
29:58
understand it because I was could be
29:59
pasting things so I sat down to to
30:01
understand what I was doing so what are
30:04
we doing what's happening here is I'm
30:06
trying to read a tag and the tag is an
30:07
unsigned byte unsigned means there is no
30:11
bit for the sign so it's only positive
30:14
but Java does not support unsigned types
30:16
so when I ohnoki io echo I call or read
30:20
bite it reads all the bits and returns
30:24
me a bite but it's representation isn't
30:26
is assigned by it and not an unsigned
30:28
byte which means it doesn't actually
30:30
correspond in terms of value so we're
30:34
going to convert it back to an unsigned
30:37
bytes by putting the bites into an int
30:40
so let's see how we do that
30:41
so the imagine that I had in my file I
30:44
had those eight bits and it's an
30:47
unsigned byte that represents 214 when I
30:50
do read bytes I get the same bits but
30:53
it's now - 42 because Java is like well
30:57
you have you have the sign bit is set so
31:02
this is a negative number
31:02
okay cool so then I call 2-inch on it
31:06
and it's the same exact value acceptance
31:09
in a bigger type and so now it's like a
31:13
and then I do an ends and essentially so
31:18
0xff is a bunch of zeros and then eight
31:22
ones and by doing an end with that it
31:26
erases the first three bytes and now I
31:30
have my original number so this is how
31:33
you can you know turn a you know kind of
31:36
like turn about it to inside unsigned
31:38
byte into a bigger container so we're
31:40
gonna skip some memory we're gonna read
31:43
the length and then essentially there's
31:44
code like that it goes on it's like oh
31:46
this is a string so we need to read
31:48
based on the size of the identifier
31:50
maybe I need to read about it maybe I
31:51
need to read a short because there's
31:53
gonna be more and then here's the string
31:55
lengths and I'm gonna read this string
31:57
so I'm kind of moving forward on that
31:59
but with that we can we can read all the
32:01
edge profit curves and build an index
32:03
and with that we can have a silk class
32:05
that's going to be like index objects
32:07
and it's gonna have the position in the
32:10
file and you're gonna have a map of
32:12
object ID to position in the file and
32:15
then you can have difference still the
32:17
subtypes one for instance is ones for
32:20
classes and you can imagine how we can
32:21
add metadata that we care about let's
32:23
keep the rest and keep the types small
32:26
okay so we have this little class that's
32:28
cool we create indexes essentially there
32:31
are maps of like for this object ID
32:33
here's the data here's the object and
32:35
then in there there's also the position
32:37
so I can go and read more about it and
32:40
then we need to move around the files so
32:41
we essentially use Java and I oh I
32:46
didn't know how to do that but turns out
32:48
it's also really easy with okay I owe
32:49
you take your input stream and you get a
32:52
channel from it and that's an Java and
32:55
IO thing and then you position the
32:57
channel to a different position and then
32:58
you just tell okie are you to clear its
32:59
current buffer and now you're ready to
33:01
read again from a different position
33:02
than the file okay cool so been putting
33:08
off you know data for three years I
33:09
wrote the thing and it turned out not to
33:13
and I was really happy and I was like
33:17
how good are we doing now so I I run the
33:21
memory profiler again and this was on
33:23
the large dump and it took about four
33:26
instead of a minute it was really fast
33:29
and use 30 megabytes then that's not bad
33:33
because before we're using 180 megabytes
33:36
right so I was like oh that's really
33:38
cool what about the huge dump it took
33:42
also took less time it sold quite some
33:44
what's interesting though is so before
33:48
we were going and then crashing was out
33:50
of memory error so I had no idea and
33:53
Android studio was using two gigabytes
33:54
so I wasn't sure how much he would be
33:56
using and here we're back to you about
33:58
250 megabytes of cash and a bunch of
34:01
other things and the thing is on Android
34:03
that's still too much so I started
34:06
looking at its do a heap dump and look
34:07
again what do we see so if we look in we
34:11
see that this index that we have those
34:13
Maps we're still taking two hundred
34:15
forty megabytes okay what's that made of
34:19
right and what's the composition oh the
34:21
top object is hash map entry link to
34:24
hash map entry and there is about you
34:27
know 87 megabytes and there's 2 million
34:29
of those so also it's linked - map
34:33
because when you call multiple immutable
34:34
- map mutable map map of in cutley and
34:37
you get a link - map which the
34:39
difference between hash map and the
34:40
attachment linkage map is a hash map the
34:42
main difference is that link - map keeps
34:44
the order of insertion so when you read
34:47
through the entries it's going to
34:48
iterate in the same order that you added
34:49
them to the map we have about 2 million
34:54
Long's and so we're not talking about
34:56
the primitive time we topic we're
34:58
talking about the wrapper type so along
35:01
is a bytes but the wrapper type is is
35:06
like what is it so it's 12 byte header
35:09
plus a plus the a bytes right so here we
35:13
would normally use 16 megabytes if we if
35:15
we had pretty primitive types we're
35:17
using 52 because it's actual Java
35:19
objects and if you keep going we have
35:23
all all these objects or the index
35:25
objects and if we look at their their
35:26
details right this this index instance
35:29
that has a position in a class ID so
35:31
there's 12 bytes of header on every
35:34
object and then 8 bytes for the first
35:36
long 8 bytes for the second long that
35:37
gives me 32 bytes when I really only
35:40
two Long's right so I wanted to see 16
35:43
bytes and I'm already using 32 bytes but
35:45
then when you think about it the
35:47
position in the file well maybe I don't
35:49
need that many right I don't need a long
35:51
because maybe the file is small and it's
35:53
the position is only going to go so far
35:54
right so it turns out for a 160 megabyte
35:59
file I only need 4 bytes the class ID
36:02
it's an ID so it's a reference
36:05
essentially and so idea is same thing
36:08
like I said they can they use 4 bytes on
36:10
32-bit VM eight bytes on 64-bit VMs so
36:13
here the class ID does not have to be
36:16
long it could only use 4 bytes so
36:18
essentially we're using 32 bytes instead
36:20
of 8 bytes for this so objects when
36:24
there's a lot of them kind of sucks
36:28
hashmap so that's that's kind of an
36:32
there's a bunch there's like five a
36:33
hashmap arrays we have five index so you
36:35
kind of get where that's coming from
36:37
and that's using 14 megabytes so how
36:41
does hash map work who's like looked at
36:44
the implementation of hash map before I
36:46
have a couple events nice so it's
36:50
actually pretty simple it's an array of
36:52
linked lists that's it so hash map is an
36:56
array of linked lists let's look at the
36:59
actual details so this is in the hash
37:00
map you have an array of node it's
37:03
called table and then a node has a hash
37:06
a key and a value so that's where the
37:08
your keys and your values are held so
37:10
you know your how you have to implement
37:12
equals and hashcode if you do that then
37:16
the hash code is run through a hash
37:20
so hash code is in it it's run through a
37:21
hash function and then it's done modulo
37:23
of the size of the table and that gives
37:25
you an inch and that's the index in the
37:27
table and so that's why it's important
37:29
that you implement your hash codes
37:30
correctly and you don't always return
37:32
two or whatever because what happens
37:35
then is a bunch of objects not gonna
37:36
have the same index because they have
37:38
the same hash and the first one is going
37:42
to be the node in that table and then
37:44
it's gonna have its then second one is
37:47
going to be the next on that node and so
37:48
you have like a linked list in the table
37:52
so if we cannot summarize and the other
37:54
thing that's kind of interesting about
37:55
hashmaps is that they keep growing at
37:57
you add stuff but they don't really have
37:59
to if you think about it you could just
37:60
keep the table a single size and you
38:02
could just add to the list but as it
38:04
linked lists get longer
38:05
it becomes slower and slower to find an
38:08
object because you have to go through
38:10
so typically we typically use a load
38:13
factor of 75 percents and then the size
38:16
is actually the next power of two of
38:19
that load factor so that's a lot of
38:22
wasted space what it means is that
38:24
there's always going to be it's
38:25
important for hashmap to work to be
38:27
efficient it's important that there's a
38:28
lot of empty empty spaces in the array
38:33
and so it we also saw that the key is
38:37
like here these are objects and so the
38:39
keys and objects we want along we'd only
38:41
care about the primitive types all of
38:43
that to say that and this is linked list
38:46
but all of that to say that there's a
38:47
lot of memory that's wasted here so hash
38:53
map is a lot of waste every entry is a
38:55
lot of extra metadata when we just want
38:58
to bytes or yeah eight bytes I think
39:01
there's another way to build a map that
39:04
does not necessarily waste as much space
39:07
if instead of being a hash map where so
39:10
hash map you know you cons you compute a
39:11
hash for for your keys and that's where
39:14
that's where the entry is in the array
39:16
the other way to do that is to sort to
39:19
create a sorted array
39:20
where every key because every key if
39:23
your key is a primitive type then it
39:26
will be able to be sorted right and if
39:29
you have an array of sorted keys then
39:31
you can actually find them in a
39:35
relatively fast so the idea is instead
39:37
of a instead of doing your hash and
39:39
finding a location in the array instead
39:41
you do a binary search if you have a
39:43
sorted array you can do binary search to
39:45
find where the key that you're looking
39:46
for is in the array and that's log n
39:49
instead of constant time but that's
39:50
actually a reasonably fast so the second
39:55
idea so let's use a sorted array
39:57
the second idea is what if instead of
39:60
objects we just use bytes what if we had
40:02
a sorted array of bytes
40:05
where every entry is just a bunch of
40:08
bytes where the first for the first X
40:10
bytes are for the keys and the the next
40:12
n bytes are for the values and then we
40:14
just use that then we don't have any
40:15
object overhead so to kind of like go
40:18
through that the idea is here we would
40:20
have an array and the first four bytes
40:22
in that example would be the object ID
40:24
and the next four bytes would be the
40:26
position four class instance or in next
40:30
four byte would be the class ID and
40:34
that's it and so then you can sort the
40:36
arrays so what does that get us it gets
40:42
us to 40 Meg's so we went from 240 Meg's
40:46
to 40 Meg's by using bytes instead of
40:48
using objects if you look at the details
40:52
this is sorted by bytes map it's in the
40:54
canary you can check it out online but
40:56
essentially it's just one giant array
40:59
and there's information about how many
41:01
bytes four key how many bytes for value
41:04
one of the interesting things is that
41:06
when you look again you're like oh but
41:07
then so can we compress that even more
41:10
we're still using 40 Meg's well it turns
41:12
out the map of of strings is using 13
41:17
megabytes but all these strings they're
41:19
all share the same prefix is because
41:21
it's package names so I haven't done
41:24
that yet but it would be interesting to
41:25
start figuring out ways to compress that
41:29
so in summary I guess I hope you learned
41:34
a few interesting things today I know
41:36
this is not your typical here is how to
41:37
use a library talk if there's some takes
41:41
away takeaways I think one of the one of
41:44
them with those is don't be afraid of
41:46
algorithms and data structures sometimes
41:49
people use complicated words for things
41:51
that are actually if you're used to
41:52
coding you'll figure them out pretty
41:54
easily use the provider and whenever you
41:58
have memory problems your kids is
42:00
actually a great tool and it can give
42:02
you really good insights it's just the
42:05
UX is kind of hard and as always you
42:08
know don't optimize early start with
42:11
measuring don't randomly change local
42:15
variables to something else or
42:17
make decisions without looking at the
42:19
overall picture and that's it I hoped
42:24
you enjoyed diving into the guts of the
42:26
Qunari I'll finish by saying I do have
42:29
so many canary stickers and I'm not paid
42:32
to give them to you I'm just I'm just
42:34
happy I love I love the new logo and
42:36
also square is hiring of course and
42:39
there's this quite booth over there so I
42:41
want to talk to us we're usually by
42:43
there yeah that's it thank you
