droidcon NYC 2019
| Tweet |
|
droidcon News
Shark: Diving into the guts of LeakCanary's Hprof parser
By
Pierre-Yves Ricau
droidcon New York City 2019
LeakCanary, a memory leak detection library for Android, was slow and used a lot of memory. For LeakCanary 2, I wrote a new heap dump parser, Shark, which uses 10 times less memory and is 6 times faster. Come learn about the gory implementation details and performance tricks!
We'll dive to the byte level then build our way up to efficiently compute shortest paths and dominators (graph theory without any math!), then use profiling tools to optimize algorithms and data structures where it matters. And of course it'll be 100% Kotlin.
Transcript
en-us
00:00
[Music]
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:46
purple arrows
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
06:60
now
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:14
are accessible
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:46
size right
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:54
while
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:20
read it and how
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:05
bytes
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:12
bunch of ones
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:11
be that hard
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
seconds
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
time
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
want
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:31
interesting thing
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:19
function
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:09
that linked list
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
42:47
[Applause]
droidcon News
Tech Showcases, Developer Resources & Partners
EmployerBrandingHeader
https://jobs.droidcon.com/
jobs.droidcon.com
Latest Android Jobs
http://www.kotlinweekly.net/
Kotlin Weekly
Your weekly dose of Kotlin
https://proandroiddev.com/
ProAndroidDev
Android Tech Blogs, Case Studies and Step-by-Step Coding
/detail?content-id=/repository/collaboration/Groups/spaces/droidcon_hq/Documents/public/employerbranding/Zalando/Zalando
Zalando
Meet one of Berlin's top employers
/detail?content-id=/repository/collaboration/Groups/spaces/droidcon_hq/Documents/public/employerbranding/Academy for App Success/Academy for App Success
Academy for App Success
Google Play resources tailored for the global droidcon community |
Droidcon is a registered trademark of Mobile Seasons GmbH Copyright © 2020. All rights reserved.