[Music]
good afternoon australians time from
sydney welcome back from lunch i hope
everybody's had a good lunch a good
break a bit of a walk
chase the dog whatever you needed to do
i had cheese and crackers for the
wallace and grommet friends out there
and we welcome back this afternoon for
our first session after lunch uh with
david and he's joining us all the way
from the sunny u.s in the center
san francisco bay area
so i'll introduce david now before i
hand him over
so ordinarily we think about things like
converting numbers between the way we
see them and the way computers use them
as they solve a problem
and for many purposes they are
as data volumes grow and people's
patience doesn't
we see sometimes find that there is
still room for improvement
and proving them is fairly
novice low-level coders can
when our time together is done
david will have taught us how that we
can use some of the recent advantages in
a few areas
a few of these things that he's brought
together a postgres sql
some of the things to consider when
attempting such improvements and looking
at the world from a new perspective
thanks david and please do ask questions
in the chat during the session and david
will be hanging around in the chat room
afterwards if you've got another
question you didn't quite get finished
before our timer runs out so over to you
david thank you thanks so much
um greetings from yesterday and from the
unseated territory of the olani people
or castro valley as i usually refer to
it
thanks to all of you for coming i
hope to earn your attention and your
wakefulness in the coveted post lunch
spot
i'd like to shout out ivan uh my
employer who pays me to work on open
source software and perhaps yours if if
you're interested we can talk later
about that if you are
you can leave your impressions now or
later in the venulis channel called uh
post talk chat womanjeka theater hope i
got that at least not too mangled
um
so let's get started
apparently i'm across from my retro
computing talk
i hope
somebody recognizes this this this is
now what we call retro computing
or as my
13 year old self used to call it
computing
we had resources available
they included a concise instruction set
we'll see what i mean by concise
presently
there were some registers i don't recall
exactly how many offhand
it's been a while
but not terribly many
there was a whole 64 kb of memory
and if everything went badly wrong there
was
the floppy disk
so concise
well the 6502 was originally built to be
a
machine controller i i believe
and it turns out that concise did not
include
this instruction
i think it's called mull on modern
machines
uh well
in order to simulate this instruction
people tried the usual approaches first
iterating and adding
but this turned out to be far too slow
so eventually they went with
pre-computing or currying if you want to
use some
i guess slightly gatekeeping terminology
but i guess that's what people do so
they
used an algebraic identity
this is not a class in algebra please
don't stare at this slide and try to try
to read it right now i'll put it up
later anyhow the upshot is that we can
pre-compute some lookup tables about two
kilobytes worth in order to do those
uh multiplies
um
we are using these to avoid
executing some instructions because the
most efficient instruction is the one
you don't execute
and in this case we're doing some
instructions that aren't actually
contained in the
isa
okay so this was kind of a background
thing that i i dimly remembered
years past
um
right about this time there was this
band called akadaka with a new singer
and it becomes famous in the northern
hemisphere
um
also
a
database system
done by some of the people
who had done ingress
was released
it's called postgres
then
a decade later it gets its sql layer and
with it the worst name in the business
data volumes
keep growing
over this time
and
people
get impatient or at any rate start to
express their impatience a little bit
more
and they say things like
beta export is
slow
well it's slow is one of those very
interesting uh challenges in computing
you just never know where to lead
it turned out that
sending integers to standard out
was taking
significant time in these exports
the code looked kind of familiar
um
it had a loop
and
what turns out to be
kind of an expensive operation
at this level
um which was uh which was that little
divide
that you see right after the word value
there
um
and so
i
i got to work
um this kind of looked like something
that i'd seen before and i'd hoped that
i could sort of use
sort of mixture as before which is a
lookup table
um
i applied this to figuring out um how
many decimal digits were in
the number
so that we could avoid some of those
expensive operations have some digit
pairs to hand
the situation
is a little bit different to be fair
the apple 2e had just one core that we
really cared about
i mean there were other processors off
to the side that you could use and and
people did
i just uh
i just wasn't quite that
that advance at that time
and
given the
dearth of cores
it didn't have a branch predictor that
we needed to worry too much about
and so we didn't have to
we didn't have to tiptoe around it
but
we do now and this is one of the things
that
we think about doing
is avoiding that branch predictor or at
any rate
assuaging it
so
with those lookup tables we can
do
branchless computing
or at any rate
limit the kind and limit the no amount
of branching
that we do
so
um
i think there's more that we can do
we should be able to um
to make it faster and for this i would
like to thank
professor
daniel lumiere who's out of
eastern canada
his
his blog is always fascinating on this
kind of score
and
it's uh it it's
some of the future work that i'm her
work that i hope to get
into the postgresql code
is based on things that he's
collaborated with other people
to write
so
we're going to
do more caching or currying or whatever
you want to call the the
process of
computing first holding on to some of
that computation
and then using it later
many many times
so
one of the things that
we can make faster
is
when we have
a binary
integer let's
for simplicity let's say it's
it's an integer and it's unsigned
so
for a 32-bit integer
um
the
binary representation will have its
most significant bit
in
one of 32 places
or one of
64 places depending on the size of the
integer
each of those places
represents a range of numbers that has
at most
two different numbers of decimal digits
in its representation
so for example
a number with its left most one position
four
represents digits from eight which is
one decimal digit
to
15 which is two
so
we can use
a count leading zeros instruction
to find out where that significant one
is
then we use
uh
some cleverness which we need to
document carefully in the code so people
understand what we're doing
we add a magic number from this
short
table that we've we've constructed
that magic number is guaranteed to be
um
larger when added to the number we're
looking at than the original integer
size
so we have this say a 32-bit integer
and then we add this magic number to it
and
what hap what happens is that
um it would it overflows into the next
larger size
so it's no longer inside the lower
32 bits let's say
and when we look at the ones beyond the
width of the original number we get
the number of decimal digits
in the
original number
um so we can do this in
a lot fewer instructions
i think
we can get it down to well i know for 32
bits we can get it down to
one
clz
one table lookup
and i hope to keep that
from
overrunning um
our cache lines or or at any rate from
overrunning them too much
and one add
and one
shift
um
and what we're left with
is
this
little guy
which
um that's the
that's what the new code looks like and
uh yes it's a little bit confusing and
this is where
uh
we're a facility and write writing
english and then getting good feedback
on how that's coming across
will really help to to do this this is
uh
this is not the kind of thing that you
want to have sitting there on its own
the way i have it here on the screen
um
so
can we get it faster
i don't know for sure
but i suspect that it's possible
and then there's other things that are
uh a part of
printing decimal
uh printing decimal representations to
standard output that i haven't covered
here
and i would
love to
work with some other people to figure
out what uh where where best to to shave
that back and to make the
the user experience um
helpful for for uh for all our users out
in the world
i would love your input
uh
with um
as i was doing this i was thinking that
you know postgres isn't all that special
i mean i've been working on it for some
time but
maybe this shouldn't be bespoke code for
that and i would love to figure out ways
to get this into
glib c or other
lib cs
that are upstream
of where i am
and
oh my goodness i had time this for uh
more interaction and questions and stuff
so i guess i'll
i guess i'll i guess we'll do those now
hey thanks for the great presentation i
haven't had any questions come through
in the chat line so if you are thinking
of a question please bring them through
um i was reminiscing the apple 2e at the
front and
i will confess that i actually covered
it in apple ii gs when they first came
out but we couldn't afford one of those
when i was in
senior school so i ended up on a x86
secondhand xx86 compatible hyundai
with a lovely orange screen and then we
got the paper white but yeah
some good nostalgia for me and
[Music]
i lost my date to introduction to
database books at some time i long
across the line but yeah a little bit of
sql still in my hair there somewhere
yeah well it turns out that
all these sql things are i mean they
they kind of hide the
the
underlying sort of
regular computer science that you think
of the data structures the algorithms
the
you know parsing
execution engines compilers
they they kind of
they kind of
help you pretend that those things
aren't still there
but they're there and and if you want to
dig there they're pretty easy to find
wonderful we've actually had two
questions come through now so the first
one is maybe the problem with
sd out or standard out would be
maybe there's a problem with std out
would a socket be better
uh
so
probably
um
that that but um
since i found an improvement in
actually changing the code that that
that does the computation
that that actually
does the instructions i suspect that
it's not all standard out and and so
um sockets might not
uh fix this
because we're
we're generally doing an awful lot of
these things they're they're they tend
to be sort of a dump of a database or
the
setting up a new replica somewhere and
so
huge volumes of data are going through
um
so i don't know that it would
i i thought that sockets would help you
more with a sort of latency issue
um maybe i'm maybe i'm mistaken about
that this is more of a throughput issue
um
let's see benchmarks um i
do
i vaguely recall i got about five
percent out of this which was kind of
amazing
um
the let's see there
might have trouble getting it upstreamed
in g lipsy well uh i have not tried it
yet so i don't know
so i'll i guess i'll find out um but i
i'd uh i'd like to get something that's
a little bit um
more sort of fully
fully baked before i do that
because i yeah i don't know that this is
specialty code it's just more efficient
and i also want to make sure that it is
more efficient on things that are not
intel 64-bit
because of course that would be
important in in the upstream
of c's
a table of magic numbers and more about
where their
where their values derive um
let me see if i can
hold that up here they're basically the
differences between 2 to the
n and 10 to the m
um
and they they're the the property is
that for the largest
um
uh power of 10
they will
um
they will add up to
um
one number and for uh the nine the all
nines number below it they will add up
to they they will they will make the the
higher
part of the the sum
um
a different number so that's the that's
where those
that that's where the magic is
um
i don't i'm not pulling it up right here
but i can send it
in
the the
pr that i had
um originally sent for postgres 14 which
didn't make it because i still needed to
do some work
uh was there something in my current
domain that prompted this research
um well i i wanted to to see uh to to
improve my uh my c skills and i from the
bottom would help
i i realized that
that
making exports and maybe someday imports
a little faster would have the
largest impact on the largest number of
people
the uh
size of the array this is one of those
things that i think may be improvable
um because right now i have uh 32
entries in there for 32-bit
um
numbers for calculating those those uh
those law of integer log tens i guess
you could call them
and so i think it i should be able to
get
whatever it is uh
whatever the size is in bits divided by
four i think because that's
that's the that's the largest number of
uh
base 10 digits that are sorry each
um
each set of four bits can have at most
one
transition or what well is guaranteed to
have one transition between one number
of decimal digits and another
so
um so i think it should be possible to
get something that uses
um
n by four
uh bits or somewhere pretty close to it
sorry n by four entries or something
pretty close to it for uh an end it
integer
um
thanks david i'm happy to read the
questions out if you like i'll give you
a few more seconds to think about them
you will use the politicians trick read
the question and then repeat it back see
more thinking time
apologies if i pronounce anything wrong
how big is the array instructions can
provide div and mod in one
saving multiply by 10
uh
yeah i sorry i thought i was um i
thought i was
you know
speaking to that so basically the
the
the array
is right now
the
uh the um
a number of elements which is the number
of bits in the
uh number so for 32-bit numbers it has
32 entries each of which is an n64
and this is all this is all done with
basically plus count leading zeros and
uh shift
so
maybe there's something more efficient
that takes fewer clocks that's certainly
possible
excellent thank you the next the next
question we've got is there a link to
the limia post
that motivated the improvement
uh
let me see if i can
[Music]
quickly find that
here we go
[Music]
um
so that was
sorry um
let's see if i dump this in
the chat here with that help
i think there may be
there may be a follow yeah there there
may be a follow-up one
um
that
is more recent no i think this is yeah i
think this is the most recent one
um so yeah so so this uh
so uh
um
rare in my experience of academics
anyway uh
professor lemieux
tends to get
really into things as they actually
execute on actual machines
and then test them and then you know
publish
things that even somebody like me can
follow
good
there's hope for me yet then
excellent thank you that's all the
questions we've got that has come
through so far so are you um happy to
jump across to the chat channel post the
the meeting room of course
excellent so if people can
jump over to the chatting channel post
this conference
we're scheduled to finish in about
another 20 minutes maybe people can have
a long afternoon tea or maybe there's
that tricky question you can't quite
word at the moment and you need a few
more to think about it so thank you so
much for joining us from the other side
of the planet um your evening our
afternoon
and
for those of you who are watching the
recording we didn't have any surprise
visitors from david family that were
threatening to run through and surprise
him in the middle of the broadcast so
please do thank your family for taking
time out from your family time this
evening
all right have a good evening
see everybody back after afternoon team