Parser Performance Story

I tell my story and show the results of improving the performance of the jsonr parser (github.com/airportyh/jsonr) written using Nearley.js. This video demonstrates parser code in a real world scenario and also gives performance tips regarding Nearley.js and beyond.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hello there uh i wanna share with you
00:03 : a um a story of how
00:06 : i uh managed to improve the performance
00:10 : of a parser
00:11 : that i i built
00:14 : um first a little bit of a backstory so
00:17 : as some of you might know i'm working on
00:20 : uh something i called the
00:21 : time traveling debugger which
00:25 : uh sort of works by
00:28 : basically taking the snapshot of the
00:30 : state of the program
00:32 : at every single step uh that the program
00:35 : takes
00:36 : so um uh so to give you an example um if
00:40 : you
00:41 : so this tic-tac-toe game has been
00:44 : written
00:44 : in a programming language that supports
00:48 : this debugger
00:49 : and and if you play the game
00:53 : against the computer
00:58 : so uh there's actually a bug here i
01:00 : don't know
01:01 : what the bug is i'm not gonna bother
01:03 : trying to debug it that's not
01:04 : the point of this video i was trying to
01:06 : click on this empty square and it didn't
01:08 : take for some reason
01:10 : i'm gonna ignore that um the point is
01:14 : uh as it's going through the steps
01:17 : uh that are required to carry out this
01:20 : game
01:21 : uh it actually logs the snapshot of the
01:25 : game
01:27 : into this history array
01:31 : if i use this copy command i could copy
01:34 : this history object like this and then
01:38 : i would end up with um
01:41 : i'm on mac so there's a program on mac
01:44 : there's a command line program on mac
01:46 : that allows you to access your clipboard
01:50 : which is pb paste and pb copy
01:53 : so i do pb paste i paste the
01:57 : this json string that i copied
02:01 : um which is
02:05 : in this json like format
02:08 : and this is not exactly json because
02:10 : this is actually in a format
02:13 : called json r it's
02:16 : json with refs so the point of it is
02:19 : you can give an id to any object or an
02:22 : array and then later on refer to that
02:24 : exact same
02:25 : object or array via the id so this
02:29 : and is defines this object to be
02:32 : one and then this star one refers back
02:35 : to that same object so
02:37 : it's possible to have references in this
02:40 : js json-ish format
02:44 : okay so that's basically the context
02:47 : um the json r library contains a parser
02:50 : for
02:51 : parsing files of this
02:54 : format and the
02:57 : the snapshots that we're taking we've
03:00 : serialized them
03:02 : into a file of this format
03:06 : um and i've had trouble with the
03:10 : performance of the parser in particular
03:14 : when i was working on the zoom debugger
03:17 : which
03:18 : works by first loading in
03:21 : a file in this json r format
03:24 : using the json r parser in some cases it
03:27 : was taking
03:28 : more than a minute to just to parse the
03:31 : file
03:32 : um so i was really annoyed because every
03:35 : time i had to work on this
03:38 : piece of software i had to wait
03:41 : every every time after i change my code
03:44 : reload the browser i have to wait for a
03:45 : whole minute and that's just
03:47 : unacceptable so i had a
03:51 : very huge motivation to fix this
03:53 : situation
03:55 : so basically i i played a game like this
03:57 : and then i
03:58 : captured the history of that came from a
04:02 : game
04:03 : and i saved it in a file i called it
04:06 : tic-tac-toe
04:07 : 700k because this file is approximately
04:10 : 700k
04:12 : in size and if we look at it
04:15 : it is in this json r format
04:19 : and it you can see some of the objects
04:22 : or some of the variables that are used
04:25 : in the program
04:26 : as represented in this format
04:31 : i'm going to show you four versions of
04:34 : the parser
04:34 : i have a branch for each of the versions
04:38 : i'm going to start with version a
04:43 : so in all but in all but
04:47 : one of the versions of this
04:50 : um of this parser
04:54 : um the parser was written in
04:57 : nearly js um i have
05:00 : i have made us videos on
05:03 : nearly js and how to use it to build a
05:06 : parser
05:06 : so if you if you're not familiar with
05:09 : neolijs
05:10 : uh that's where you can get uh to learn
05:14 : more about what it is if you are already
05:16 : uh knowledgeable about nearly js
05:18 : um then there's something i need to tell
05:21 : you
05:22 : um okay if you're using a repeating
05:26 : pattern such as an array
05:30 : this is members this is actually object
05:32 : so object is a repeating pattern just as
05:35 : arrays are because objects can have any
05:38 : number of
05:38 : members within it so
05:41 : an object consists of the
05:45 : opening and closing brackets and then
05:47 : members what is
05:48 : members member is a one single member
05:52 : which is a string followed by colon and
05:55 : followed by
05:55 : element but there could be multiple
05:58 : members
05:59 : delimited by a comma like that right
06:02 : so initially in version a
06:06 : of this parser it was written in this
06:09 : way
06:10 : so we're saying what's a members a
06:13 : members
06:14 : is first a member and then a comma and
06:16 : then more members
06:19 : because the the symbol to the
06:23 : right hand side is referring to the
06:25 : original symbol
06:26 : members this is a recursive
06:30 : rule um so
06:34 : i'm gonna generate this
06:37 : parser uh take this grammar and generate
06:41 : it
06:41 : to produce a javascript file and use
06:44 : that
06:45 : to parse this seven
06:49 : file let's actually time this
06:54 : execution here
06:58 : on unix you can use this time command
07:01 : right before the actual command you want
07:02 : to execute and at the end
07:04 : it will tell you how much time it took
07:07 : to actually do that
07:10 : and while it's going i'm actually going
07:11 : to read for you
07:13 : some an article on the nearly.js website
07:19 : under the article called how to grammar
07:21 : good
07:22 : one of the sections is called don't shy
07:25 : away from left recursion
07:27 : if you i'm going gonna read this for you
07:30 : um
07:30 : if you were a good little student and
07:33 : you paid attention to your professors
07:35 : when they told you never to write
07:37 : grammars like
07:39 : a a goes to a and then something
07:43 : this is left recursion as in contrast to
07:47 : the
07:47 : right recursion that i used
07:51 : and and i indeed i was being a good
07:54 : little student because
07:55 : indeed my professors
07:58 : told me to not recurse on the left
08:03 : and recurs on the right and the reason
08:05 : is in
08:06 : other types of parsers in particular
08:09 : recursive descent parsers
08:12 : which i do plan to cover in the future
08:15 : but uh with recursive
08:16 : descent parsers this left recursion
08:19 : simply will not work
08:21 : so but he's saying nearly of course
08:24 : is much better so you don't have to
08:25 : worry about that he's saying if you're
08:27 : paranoid about efficiency
08:29 : you should actually prefer a left
08:32 : recursion overwrite recursion
08:34 : because it's very slightly faster
08:38 : in any case that's how you deal with
08:40 : left or right associativity
08:42 : for binary operators he's saying if
08:44 : you're using nearly js
08:48 : instead of doing recursive descent
08:49 : parsing then you
08:51 : should actually prefer doing left
08:53 : recursion which i
08:55 : did not do because i was following
08:58 : the best practices of you know the
09:02 : more conventional way of writing parsers
09:05 : which
09:06 : was to do uh recursive descent
09:09 : as we were traditionally taught anyway
09:12 : okay so that process finished and it
09:14 : actually took
09:16 : two minutes and ten seconds let me let
09:19 : me actually like
09:20 : write this down here uh when you're
09:23 : doing
09:23 : uh performance analysis or
09:26 : like very complicated kind of debugging
09:29 : you should keep
09:30 : your notes so i'm gonna make a file i'm
09:33 : gonna
09:34 : call this perf
09:38 : numbers and it's august
09:42 : 24th
09:45 : okay so this is it was uh ran on version
09:48 : a
09:50 : on the file the file was called tick
09:55 : tack toe 400k
09:58 : that history i want to also want to note
10:01 : how many lines were in this
10:05 : file tic-tac-toe history file using the
10:08 : wc command and it told me that there are
10:11 : 45 thousand and 320
10:16 : lines
10:19 : okay um so version a
10:23 : gave us this performance um
10:28 : real it's saying user time is actually
10:30 : three minutes
10:32 : and 20 seconds i'm not sure what what is
10:35 : actually the
10:36 : more better time for me to use
10:39 : but system time i guess system time is
10:42 : just the
10:43 : time that other operating system took
10:46 : real time refers to
10:48 : actual elapsed time user and cis
10:51 : refer to cpu time used
10:54 : only by the process
10:57 : if anyone watching who understands why
11:00 : user time is more than real time
11:03 : please enlighten me on that in any case
11:07 : so version version a of my code
11:11 : this was the state it was in and it as
11:14 : you can see it took
11:15 : like more than a minute in this case two
11:17 : minutes just to parse that humongous
11:19 : file
11:21 : so um i
11:24 : i learned that not not just from not
11:27 : just
11:28 : from uh nearly js this nearly js article
11:32 : but also
11:33 : from um another article which i might
11:36 : link but i have to go dig it up
11:38 : uh learn in detail about the early
11:42 : parsing algorithm
11:43 : that left recursion should indeed be
11:46 : preferred
11:47 : how much should it be preferred well i
11:49 : will let
11:50 : you decide after you see
11:53 : the result of switching to left
11:55 : recursion so
11:57 : i'm gonna bring out
12:00 : version b of this code and
12:03 : version b of this code we switch from
12:05 : write recursion to left recursion now
12:08 : uh the
12:12 : sort of symbol to the left of this comma
12:14 : is referring to
12:16 : itself as you can see so
12:22 : now i'm going to regenerate the parser
12:25 : and then rerun this test
12:27 : [Music]
12:36 : it took 5.9
12:40 : seconds user time is 7.7
12:44 : seconds so i'm actually curious so
12:48 : i'm gonna print out the date before and
12:50 : after this command
12:56 : 24 and 18 it's about six seconds
13:00 : maybe the real time is more correct so
13:04 : anyway
13:06 : i guess the important thing is version
13:10 : version b with left recursion
13:15 : version b is much much faster
13:19 : how much faster is it well
13:23 : 2 minutes and 10 seconds is
13:28 : 190 seconds
13:31 : divided by 5.9 seconds 32 times
13:36 : faster
13:43 : 32 times faster version b s
13:47 : just by switching to left recursion so
13:49 : um
13:50 : i would actually say this word
13:54 : vary slightly faster that's a
13:57 : huge understatement and
14:01 : perhaps a little misleading i think he
14:03 : should recommend
14:04 : left recursion much more strongly than
14:07 : that
14:08 : okay the next optimization that i try
14:12 : uh because even six seconds is still
14:15 : not that great i ideally want things to
14:18 : be
14:19 : like under one second the next thing i
14:22 : tried is adding
14:23 : a lecture i did make a
14:26 : video about about how to use a lecture
14:30 : along with nearly js um
14:36 : this version does not do that it does
14:38 : not use a lecture but
14:40 : version c does so let's switch to
14:45 : conversion c and for those of you
14:48 : watching at home i want
14:49 : you to take a guess as to how much
14:54 : how much difference it would make to use
14:56 : a lexer
14:57 : versus not elixir and to give you an
15:00 : intuition about what a lexur
15:02 : does it's it's uh it takes a string
15:06 : say string like this
15:10 : where each character is in a square like
15:13 : this
15:14 : okay what the lex address is groups them
15:17 : so
15:18 : this string block gets grouped into one
15:21 : token
15:25 : this uh left brace
15:29 : is its own token this is a
15:33 : colon and then this guy this string
15:36 : gets grouped into a string
15:40 : and this this right brace
15:45 : so instead of working with every single
15:47 : character
15:49 : the the parser doesn't have to do that
15:51 : the parser can work with
15:52 : these individual tokens
15:57 : lecture the lecture as a pre-processing
16:00 : step
16:00 : has done one step of the work of
16:03 : grouping
16:04 : these things together such as string
16:06 : literals or numbers
16:08 : as well so that's what a lecture does
16:10 : for you
16:11 : with regenerate the parser
16:17 : let's rerun this test with the
16:22 : the time command
16:30 : and we do get an improvement we improve
16:34 : to
16:34 : about four seconds for the parse
16:41 : so version c uh with lexer
16:46 : improves to four seconds how much faster
16:49 : is that
16:51 : well it's that divided by
16:58 : 4.026
17:04 : so 1.47
17:07 : let's say 1.48
17:13 : uh not as dramatic an improvement as
17:16 : the left recursion fix for sure um
17:20 : and then after version c i tried one
17:24 : more version but this version
17:25 : uh requires a larger departure from
17:29 : this code base because i actually
17:32 : rewrote
17:32 : the parser from scratch using recursive
17:36 : descent
17:37 : and more specifically using a
17:40 : technique called functional parsing or
17:43 : at least
17:44 : partially inspired by functional parsing
17:47 : there
17:47 : is a video on computer file
17:51 : talking about it and that's where i
17:53 : learned it from
17:58 : so the version d is the version that
18:01 : uses this
18:02 : functional parsing parser um and
18:05 : to give you a sense of the code i
18:10 : built up a bunch of building blocks
18:14 : for building the parser uh which look
18:16 : like sequins
18:18 : choice choices for like it's like an
18:21 : ore and a grammar like choice is like
18:24 : you either choose
18:25 : this path or this path whereas a
18:28 : sequence is like you first match
18:30 : this and then match this and then match
18:32 : this so
18:33 : with a bunch of small building blocks
18:35 : like this
18:36 : you can write the grammar
18:40 : in a very declarative fashion
18:43 : almost like a grammar in in
18:46 : in in this format uh but uh the
18:50 : in terms of the functions uh that are
18:53 : implemented to
18:54 : support these things i wrote them by
18:57 : hand
18:58 : and i'm not going to explain them
19:02 : at this point other than saying that is
19:04 : is
19:05 : using the recursive descent
19:08 : method to do the parsing but um
19:13 : yep so this is the code let's see what
19:15 : the performance is
19:20 : the performance is much better actually
19:24 : using this method
19:29 : so version c version d
19:34 : functional recursive
19:38 : descent method
19:42 : how much is it faster well it's 0.647
19:47 : now so
19:48 : this divided by 0.647
19:53 : is 6.2 times faster
20:00 : okay and if you want to compare
20:04 : the original performance which was
20:09 : [Music]
20:11 : 160
20:12 : times two
20:17 : oh i think i did the initial show
20:19 : calculation wrong 60 times 2 plus
20:22 : 10 130
20:25 : uh let's do divided by 0.647
20:32 : 135 times
20:36 : wait no 200 times
20:39 : faster
20:44 : than version a i think i did this
20:48 : calculation wrong though so this should
20:50 : be
20:52 : for this 32 times faster i think i did
20:55 : this one wrong
20:58 : this should be 21 times faster
21:02 : okay 21 times faster than version 8
21:05 : so um the the fastest one is the
21:08 : recursive descent
21:09 : one um which was written
21:13 : from scratch without using a parser
21:16 : generator tool such as nearly js
21:19 : um it would seem that
21:23 : this method is what you should prefer
21:26 : all the time although i would say it's
21:29 : not as clear-cut as that
21:32 : you don't necessarily always pick the
21:34 : tool
21:35 : that's most performant there are other
21:38 : considerations
21:39 : too for the case of
21:43 : nearly js there's a couple of big
21:46 : benefits to it in my opinion
21:48 : one is the ease of using this
21:51 : grammar the ease of learning how to
21:55 : write grammars like this without
22:00 : sort of learning exactly the internals
22:03 : of how
22:04 : the parsing algorithm works another
22:06 : benefit of this
22:08 : is the the you don't have to
22:11 : worry as much about um
22:15 : infinite recursion and stuff like that
22:18 : whereas with recursive descent
22:20 : there are some grammars that just cannot
22:23 : be just cannot be supported because of
22:26 : infinite recursion if you don't do it
22:28 : the right way then there's infinite
22:30 : recursion
22:31 : and also the nearly js
22:36 : we've been able to figure out a really
22:38 : nice
22:39 : ways to do error reporting with nearly
22:42 : js
22:44 : which we have not figured out for the
22:48 : recursive descent
22:49 : method yet although i am planning to
22:52 : work on that sometime in the future
22:55 : i think the biggest takeaway with
22:58 : performance work is measurement is
23:01 : really important
23:03 : you don't really truly know if what you
23:05 : did
23:06 : gave you better performance unless you
23:09 : have a very specific
23:10 : way of measuring it and it's very
23:13 : specific
23:14 : data to measure it with although one
23:17 : caveat to that
23:18 : is that the performance the the
23:21 : performance techniques
23:22 : that you use that really work for your
23:25 : specific case
23:27 : may not work as well in a different
23:30 : scenario uh this is possible
23:33 : another thing is more specific to
23:36 : parsing and more even more specifically
23:40 : to nearly js is you should always prefer
23:44 : left recursion overwrite recursion that
23:47 : actually makes a very very big
23:49 : difference
23:51 : and using a lecture will also help
23:54 : although not quite as dramatically as
23:57 : the left recursion
23:59 : situation so if you
24:02 : if you have a limited time to work on
24:04 : performance
24:05 : uh i would definitely recommend you go
24:07 : for the left recursion
24:09 : and finally if you hand coded your
24:12 : parser you can actually achieve
24:13 : even greater performance so that's all i
24:16 : have for you in this video
24:18 : thanks for watching