well hello friends welcome back to the
show
today we are gonna do some relaxing
profiling and optimization work so
um i figured we would take a look at the
javascript
test suite that we have so currently
while i'm recording it completes in
1.5 seconds and that is pretty fast for
from test suite but i figured why don't
we profile this
and see what we can find and see if we
can't make it go a little faster
see just by profiling it we made it go
faster
um but let's take a look at what it's
actually doing
so if we flip this thing upside down
we can see that the um
there's a lot of malloc and free going
on okay
and then we have um string unref
which is very suspicious
in a call to hash nonetheless
so let's see what is this we are hashing
creating a property table in javascript
and then the function that hashes
a string or symbol for some reason is
manipulating the ref count of a string
so that's should be completely avoidable
and so we'll probably be able to get rid
of at least this particular branch
and um
[Music]
actually probably these all these
branches here
so that looks pretty promising um maybe
we'll start with that one
and then we have um
[Music]
gc heap allocations when we
are putting properties into objects
and changing prototypes okay
and here we have more string
ref count manipulation again when
hashing string or symbol
so yeah that one's definitely going to
be our first
target the string or symbol helper so
let's see
and let's see if this thing shows up in
malloc as well
it is here um stringer symbol although
this is appending to
um the singly linked list so
our hashmaps currently are
built out of singly linked lists that
hang off of
hash buckets so this one is
is not straightforward to fix although i
would like to
switch to uh what is it called closed
hashing at some point
but anyway that that one is a bit of a
bit of a bigger issue
um but we do have here string creation
again in two string or symbol
um so string or symbol is definitely um
the place we're gonna go look
so what is going on with this class so
string or symbol by the way
is what we use as a key in object
property tables
in lib.js because
an object a property can have either a
name
or a symbol as the key so
that's why we have this sort of helper
class that wraps
either a string or symbol as you could
guess from the name
um and internally it's just a void star
and then depending on the
bottom bit like the least significant
bit in this pointer
um we we use the that bit to determine
if it's a symbol or a string so you can
see it right here
and of course that's a very common trick
since pointers are
are guaranteed to to have the bottom two
bits
zeroed out normally so you can you can
put stuff in the
bottom of pointers if you need to
smuggle some extra bits
you just have to take care to actually
mask off those bits
when you are dereferencing the pointer
anyway
so i think let's see so i saw this thing
right here that's the
create uninitialized um and string
will create so that's when we're
converting a property name
let's see property name
to string or symbol
um so this should not necessitate
any kind of string copy
i think
because if if this property name is a
string then we can just
um use the existing string because
strings are immutable in serenity so
here
we are unnecessarily creating a string
impul which is the immutable
inside of a string so instead of doing
that we can just say
string impulse
um i think
like that and then we need to
ref it so that would be
a static cast to string impul
and putter
or the const okay all right
um yeah
yes
that's fine so in this case here when
we're just getting um
like a character array or a c string
then we have no choice but to construct
a string input but if we are past the
string
string always has um or it doesn't
always have but it is string
is a wrapper around string input right
so we can just reuse
the string input of the string provided
now that
string we are provided should never be a
null string so let's just assert
that it's not null otherwise
this would make us very sad what we're
doing here
okay so let's see this should get rid of
the
this path right here this allocation so
i guess we can confirm that
by just checking
because then we have all the all the
reference count manipulation
um when hashing
we have hashing here so we have traits
for
string or symbol which
implements hash then if key is a string
then key as string hash okay so
key as string returns
returns a string by value so um
this will definitely this will construct
a new string
which is a wrapper or a string impul and
that string object
will rough and unref the string impulse
so that's where the
um hashing is coming from i think but
let's just verify the malloc
thing and then move on to the
um hash stuff
all right so
invert malloc
all right we have string and pull here
but
um the string or symbol is gone
so now we just have other ways of
constructing string angles but that's
okay
um okay great
so
let me see let's just run the javascript
tests here on host to make sure that
we're not
doing something dumb but it seems fine
don't avoid
unnecessary string copy in
string copy and string or
symbol from string
yeah okay
and then here if the key is a string
um ask string
hmm
so we probably want to have
i mean we can't really return a close
reference to a string
right because we don't have a string
object here we just have a void star
what we could do instead is
[Music]
we can just make a hash function i guess
so here's what this thing does
uh key to the hash
and then
because then we are inside here and we
have
a bit more maneuverability so
we can do static cast con string
impulse
um
hash yes we can just call hash on the
string
otherwise if it's a symbol
what does ask symbol do it just returns
the pointer with the bottom bit
masked off right so
and in this case we know that it's if
it's not a string we know that it's a
symbol so we don't even need to check
that
and we can simply do that
so i think this should get rid of the
rough count churning and hash
but we'll verify
hmm
u64 well i wonder why this is working
with 64.
and why not u and put her t
because that seems sub-optimal in a
32-bit build
anyway um
okay so
um unref is here okay
but now we are in equals rather than in
the hash
itself so
what are these uh linked list
that's probably fine um
string or symbol constructor string or
symbol constructed from a string or
symbol is still heavy
why is that
[Music]
it's doing nothing but calling ref on
the string and pull okay so that one is
kind of
unavoidable so it's probably just the um
assertions here that are hitting us
we could might benefit from from
always inlining this but i think it's
not the end of the world it's not
particularly heavy
it's a little bit heavy um
what is it doing here let's take a look
at the assembly
so the hottest uh
piece is this um
let's see it's an x exchange add and
then
a test so i'm guessing
that is manipulating the ref count so x
add
fetch at this one
wait what are we testing here
we're asserting that the old ref count
is
greater than zero
oh and it's unsigned so i guess that's
why it's um zero flag check
okay that makes sense
because with an unsigned type um only
zero
there's in this case is like only zero
and non-zero
there's no negative
so we only need to check the z flag
um so it's probably this assertion
and i don't particularly want to mess
with that assertion
anyway
so this is probably a good change
hmm don't
or um avoid a string and pull rough
picture rough count try
hashing string or symbol
yep um actually we can write a little
bit more
helper function so we can
compute the hash
without having to construct a temporary
string
cool oh actually now i forgot about the
equals
so that's the um
second second phase of hash lookups
of course first when you do a hash
lookup in serenity hash maps or hash
tables
um first we um hash the thing you're
looking for
and how we search through all the
buckets and if we find something with
the same hash
we also do an equality comparison so
it's the second phase
so this is just the first step of
checking
we're doing a hash lookup um and then
we'll also
do equals checking on it
and since we're not specializing equals
we'll just use the generic
traits here which simply does a
equal equal or an operator equal
um so
that would be this guy
and in the case it's two strings
then what we'll do is
um we'll do a string a string okay so
that's going to produce yet
more temporary string objects which is
going to be heavy
so let's see if we can fix that up
so if other is not string
then it's not a match
and otherwise
um let's see
um
this simple is die cast
other impul is the other guy's m putter
and then let's see so if this simple
um length is not the same as other
impulse length
then it's not a match so let's get that
out of the way first
and then otherwise we will simply do a
lem comp
uh other impul characters
this length
and we don't have memcomp um
so let's just give ourselves mao kong
with this i think we should no longer
see
um equals generating more reference
count
calls
but we'll verify that of course
i wonder if um if you're comparing two
strings
and you have a cached hash for both of
them
like is it worth comparing the hash
before going into the um character
compare
like obviously if if you have to compare
long strings against each other for
equality then
if they both have a hash in cache then
you could use that to quickly
reject mismatch strings at least
um but i'm not sure about that but it's
something to think about
okay 1.2 starting to
scratch a little bit here at the surface
of time
um riff count unref
so this is the clearing of the singly
length list
um
i guess that's probably during the
construction of the property table but
but this is the linked list stuff
um i don't see
any equals here
um blue string or symbol is here
but that's probably okay
or
ask the string this will still produce a
string
oh what but this is a
fly string by const reference
so why would that turn the ref count
it should generate a ref but not an
unref
maybe oh maybe it's an overload issue
maybe we are this thing
doesn't have a fly string overload so it
takes this constructor overload here
which invokes the implicit construction
of a string
from a fly string right here
which even goes out of line and
does a rough putter copy
so we can probably avoid that
but one thing at a time so let's see
js um
avoid creating a temporary
string in string or symbol
operator
okay and then we can simply give this
guy
an overload for fly string
and
i think that will probably work out
we'll get rid of a little bit more ref
ref counter
just um very systematic approach to this
today
but i think um
i think it's nice to to sort of iterate
on a profile like that so
you make one little fix and then you see
what comes up next and you just keep
going and going and
shaving off things until
um until you run out of things
um okay so unref
no longer have any
property name to string or symbol so
that's great
so what else are we looking at here
it's the constructor but ignore him
um ensure property table
and malloc and in free
so why are we here
but somebody called property count
wait why does property count call insure
property table
oh oh we compute the property count
in an object by realizing
the property table like forcing it into
existence
um we can definitely avoid that
so let's see
add string or symbol constructor that
takes
a apply string
some voids count turn from
implicit conversion in some
places cool all right so
to count the number of properties in an
object shape
um instead of
reifying the property table what we'll
do is
right here we should probably call
property count as well
so instead
um what do we want to do i guess
we can just keep track of it
okay
so um
how do we keep track of this size t m
property
count so whenever we add an property to
an object
uh when you do something like um o.f
something like that then this is a put
on this object and that will turn into
a put transition on the shape if we
didn't already have
an f property and then when you keep
going like this we'll just put more
properties into the shape and every time
we add a new property
to the object shape
we need to bump up the property count
and
let's see so that would be when we
create a put transition
that's when we construct a new shape
so let's see allocate a new
shape this guy right here
so we're transitioning from the previous
shape to a new shape
and the new shape will have
property count is going to be previous
shape and property
count plus one boom
okay i wonder if it's really that simple
because we have um there are three types
of transition
in the engine at the moment so i mean
there's invalid but there's
put configure and prototype and put is
when you add a new property to an object
that you didn't the object didn't have a
property with that name before
and then configure is when you change
the parameters of
um of a property somehow like you can
make it
writable or innumerable or whatever or
change the state of those flags
that's a configure transition so that
one does not add a property
um that did not work out quite well okay
and then prototype is when you change
the prototype
of a of an object
anyway let's see meta
so this crashes
and then we catch sega board so we don't
actually know what happened
it's kind of annoying um
so let's just not catch
that all right let's not work hmm
yeah let's just disable this code for
now
okay so what does valgrind tell us
and that's in
blah blah blah
asserting in get own properties
property table ordered
wait did we do a live okay so we're able
to run many tests
successfully it's just that we
eventually fail
[Music]
so let's see what we can learn about
that
wait what was that oh it's a function
property table ordered
so i changed this thing to call property
count
i feel like that was not a mistake but
am i just thinking wrong here
let me let me back up on that restore
what was and see if that was
meaningfully different
because if so i have to think harder
about why
um no it still crashes okay
um
property count
and then we go out of bounds we try to
go out of bounds on this vector here
why is that
oh wait wait wait wait i know why um
when we did the plus one we didn't we
didn't look at the transition type
i was i was explaining it in the
voiceover but i was not
taking care to actually look at it so uh
we should not
um bump the prototype property count
unless it's a put
transition so
that would be if transition type is
transition type put
otherwise it's simply previous shape and
property count
still no good all right all right well
we're gonna find out why
property table ordered still failing
oh i guess i guess if i construct a
shape
from a previous shape i need to inherit
the property count there as well okay
okay i was just being sloppy here
previous shape
property count
um so it
has three constructors
are we still crashing in the same place
get on properties property table orders
all right
property table
so i guess here we can
[Music]
dump out the property count
debug
property count
count old way or um
yeah let's do it the old way as well so
property table
size
we'll see what the last thing that comes
out is
zero but if we do it the old way it
would come out as two
that's interesting
so why is it like that
um shape so if you
construct a shape there are these three
constructors
shape shape and shape
but this one has a property count of
zero
and if we reify
i wonder why
um
let's see what test does this run
test
i'm just going to dump out which test we
are testing so that we can see what's
going on
test colon jason pars reviver
that's the one that's failing all right
what's going on in there
huh that's um
let's just get a stack here instead
so where the heck are we we are
in reflect object own keys
really
wait who calls own keys
own keys okay
reflect oh wait wait it's part of the
test suite
own keys
deep so we're doing a deep object equals
and then
we iterate the own keys of
a and deep
equal check against b so that makes
sense
and i'm guessing that to equal here
is doing a beep check like that
um
hmm
but why
why would we end up with
wait maybe there's another way to the
other this is not the right way to go
about this
um because
if
we could have a shape that um
if you do it like a delete for example
um the shape becomes unique because um
when as long as you're only adding
properties to an object
um then the shape is only being like
incrementally built up right
but the moment you delete a property
from a shape
then we sort of give up on on trying to
coalesce
similar objects and we just say like
okay well this is unique
because delete is a fairly rare
operation anyway
and once an object is unique then it no
longer has a
shape transition chain to care about it
only has
a property table property table becomes
the canonical authority
and so that's probably why
we were seeing um
property count zero because we made a
unique object for some reason
so when do we set unique create unique
clone
and this would happen when you call
ensure shape is unique which we call
in a few cases for example when you have
more than 100 properties on an object
we stopped doing transitions we just
make it into a hashmap basically
and likewise when you delete something
we also
make the shape unique
and so yeah so that's basically a way to
disable shape sharing
and um it it will
exclude this object or this shape from
participating in certain optimizations
but
it tends to be favorable compared to
trying to
maintain a sane reality
in the face of disappearing properties
anyway
so i'm guessing that this is going to be
the issue
but let's verify so
[Music]
what we do we have that debug line here
right so if they are different property
count
is not property table or actually
let's verify it this way unique
is unique so if this says
that it is unique at least we know what
the problem is
make true okay good
so property count
is not reliable um if we are using the
property table directly
and do we do that somewhere
property table
oh it's exposed but it's const
um
property table property table blah blah
blah blah blah
but when you do a delete what happens
delete property
remove property from unique shape
yeah so here we go and remove it
[Music]
but when you add something add property
to unique shape okay okay okay so we can
actually keep tracking it here
um property count goes up
and wait so this thing will
tell us if something was removed right
yes remove
um i think that's probably an issue with
debug line
run file test
oh why are you crashing now
okay that's taking too long
property table ordered okay okay people
were not
as finished as i was hoping
um
let's see
that property count looks too large
um
it looks like we did a minus one on a
zero right up in here
um
now why would we go and do such a thing
clone you make a unique clone
then
oh we need to we need to actually
populate the property count
field let me make a unique clone
um new shape
property table size
still suspicious
still a very large number here
[Music]
oh wait did i not
wait wait wait wait wait i have to do
that after i
signed assigned to the property table
[Music]
ah there we go okay okay so that was a
little uh a little rough
but we made it through and let's see
so this should get rid of um
so the thing we wanted to fix originally
was the fact that property calling
property count on a shape
um forcibly um
created a property table just so we
could count the number of entries um
now this should no longer be necessary
because we'll track the number of
entries
in an integer so
let's see if we can
verify that look at the times
um
okay so malloc is still called by insure
property table
but it only happens in lookup not in
property count
so that's really good
um what do we have here ensure property
table
i mean yeah we're building the property
table from the shape transitions
so i don't know what to expect i guess
one thing is the fact that we are
seeing uh free when we're building a
property table which tells me that
we're not building it in the most
efficient way probably
we could
[Music]
we could pre-allocate space in the
property table
so that it will fit the
ensure capacity for property count
so that's one thing we can do i think uh
that should because
it shouldn't be necessary to free
anything while you're building up a
property table because we should only be
adding
the exact number of properties that we
have in our transition chain
but let's see if that actually gets rid
of the free
didn't crash
free ensure property tail
it's still there
why are we freeing here
i mean actually it's just free called by
a sure property table
so it could just as well be this vector
here
um which we could totally put on the
stack
in fact i'm not sure why i mean it's not
we can't put it on the stack completely
but we could
give him a little bit of in-line
capacity because
why not might get rid of um
malloc and free in some cases
or in any case where you have 64 or
fewer properties
in the transition chain
let's try that
so yeah it's pre-size the property table
and
give some stack capacity to the vector
here we make of the transition chain
we put that in a vector because of
reasons i guess because we want to
traverse it
backwards
[Music]
we want to traverse the transition chain
from the root
so that properties are added in
incremental order
because what happens is that when you do
like this right
then what happens here is that we start
out with o being an empty object and
then
when you add x we do a transition um
to to a shape that has
the property x and then when you add y
we transition to
a shape that has properties x and y when
you add z we transition to a shape
that has properties x y and z um
so shape x
let me write these out actually
so um
what we're doing here is that we are
walking
we are currently at this shape right
here
and in order to create the property
table
we have to
um
[Music]
we have to walk backwards we're not
backwards we have to walk forwards from
here
and we don't have a pointer from here to
here so
we do have a pointer from here to here
and we have a point from here to here
so that's what we do we just
flatten this linked list of shapes
into a vector so that we can traverse it
in
this order
and now we're just giving a little bit
of stack capacity
to that vector so let's see how that
works out
i think that's probably where the
matlock and free came from
but i may be wrong uh sure property
table is
still here
free is well i don't see it
so that's positive
um
i mean we still um
if we have more than 64 properties then
we we will malloc
and this will also malloc so
actually yeah this will malloc but
there's no free anymore
showing up on the profile so that's good
okay
so first let's do the property count
thing um
js um
don't um
don't force it force property
table reflection
on shape property count
um previously whenever you would
ask a shape how many properties
it had it would reify
a property table refine
the property table into
a hash map and
use hashmap size to answer
the question this
is often a huge
waste of time this
can be
so if if we don't need the
property table for anything else
so um
this patch um implements
property count tracking and
a separate
integer member of shape
okay
precise um
the hashmap and vector
used in shape ensure property table
okay so
wait then what did we want to do
i forgot we have unref here
um create put transition
string or symbol
okay what is that doing create put
stream or symbol property name
um it's doing a copy construct
and using the property name again here
yeah so that one is tough um
do we have some some dumb crap going on
somewhere maybe
um
maybe an allocation allocate cell is
pretty high up
create put transition calls allocate
which calls allocate cell
so this is our main allocator function
in the garbage collected heap
first it checks some flags um
checks if it's time for a periodic
garbage collection
and then this here is definitely not
very efficient so
um here we look for
um
we look for a suitable heat block to
allocate out of and
if something doesn't fit but we just
walk like the whole list of heat blocks
in order
and this could probably get pretty
chunky actually
looking through let's see
i am mixing up things here
yeah so it's looking through double
digits at least
heat blocks and
i don't know what's up with this error
message something new
i guess i can just use the old style
so let's see we look through all of
those blocks compare
until we find something where it fits
and then we call allocate on the block
allocate will simply pop from the free
list
this part is constant time but
the more heat blocks we have the slower
allocation will get
which is not unreasonable but
we could definitely be smarter um for
example we could
put um we could make
lookup tables for um the allocation
requested allocation size for example so
instead of having to walk
all of the blocks we would just index
into a lookup table
um with some quantized
version of the cell size that we're
looking for
and
fetch a suitable block that way and then
we could even have two
separate lists like um lists that are
known to be full and lists are known to
have
um empty or
free cells
same time it's like it's not
overwhelmingly many so
i don't know if it's the end of the
world exactly here
this in particular feels like it could
be in line
though like i don't know why this is out
of line
not that it was showing up but
we can definitely do this
we don't need you
also this is not entirely optimal
because like
we might end up putting a very small
cell into a
heat block with space for very large
things like we just
choose the first fit
so it could could in theory make the
allocator
more efficient by segmenting it better
anyway
let's take a look at these again look at
those times
hmm allocate cell
heat block constructor
what is it doing in allocate cell let's
see
um what's that compare here
so let's compare right here it's
probably the hottest instruction in that
function
yep
um sixty percent of the runtime is spent
in this comparison here
so it's definitely
worth improving that but
i feel unfortunately i i'm running out
of time for today so
i'm gonna have to punt on that but
yeah that'll be something to improve
next um at least we were able to go down
from
1.3 something to almost one second
which is a respectable progression for
um
one evening of poking at this a little
bit
so i don't think i'm gonna i'm gonna
commit that one because i kind of like
it
even though it's not the most important
thing oops
yes
the js always in line
block allocate this
thing is so simple
and slightly and um
sits on the hot path so just in mind
um yeah okay
good good good good good um
right so i think this is going to be the
end of today's video
so if you made it this far then i thank
you for watching
and hanging out i it was a little bit
different today
than what we normally do but i hope that
it was interesting
um now it's
yeah speed is varied a bit but
these low times are very nice um
yeah this type of work is fun to do
sometimes and i do feel like
we could do a little bit more of it
because
we've been adding so many things lately
and didn't really
um stop to work on performance for quite
a while
so it's good to get to take a break
and polish it up
anyways thank you for hanging out and
i will see you next time bye