My presentation is about probably the most pointless thing the software can do is about moving
bytes around memory copies.
But in general, let's take a look how to write fast code.
You can do high level optimizations and flow level optimizations.
All L-optimizations are about choosing the right algorithm using the right data structures,
the right interfaces.
And flow level optimization is about removing unnecessary copying, using the right instruction
set, making sure the data layout and memory is right.
But actually sometimes it's not easy to figure out what is high level and what is low
level optimization.
For example, let's imagine you profile your simple stuff code this is tough and you
see this.
And this is terrible dynamic cost and again dynamic cost and string serialization and
SDDLKL and whatever string streams, how do I change it?
I don't know, I speak loud enough.
Is it okay?
So you see this, typically when you profile some simple aspect code that not you have written,
but someone else have written.
And this is my impression when I feel this.
So the first step in the optimization is removing trash.
Removing all of this dynamic cost SDDLKL copies, string streams and so on, but this is just
basics.
Then when you optimize all of this trash, and it's unclear if it is high level or low level
optimization, it is just removing trash.
When you do this, the profile might look like here.
And here at the top we have memory copy.
And the second function is copy user generic string and do you know what it is?
It's also my memory copy.
But it happens in the Linux kernel.
And then we have some real stuff like decompression and string serialization.
But it is typical to find memory copy at the top when you profile your code.
So reasonable question, should we optimize memory copy?
Not necessarily.
Sometimes you can remove memory copy from the profiling just by copying less data, which
is not always possible and not always needed.
So I think you do less copies and your code will be faster.
But sometimes you need to do memory copies just because some algorithms expect the data
to be laid out in a certain way.
Like you arrange the data in a certain way with memory copies and then you do some fast
algorithm that will process data continuously in a single batch.
So sometimes you do instead like your copy data just to optimize your code.
And the second argument against of trying to optimize memory copy is that this function
is so popular it is so often at the top of the profiles.
So maybe thousands of people already tried to optimize memory copy and maybe it will be
pointless and maybe you think too much of yourself if you think that you can optimize it.
But let's dig into more details.
So memory copy is the world most popular function one all programmer's love.
Actually I disagree.
I don't love this function every time I see this function in the profile I want to get
read of it.
How can I style out this function but okay.
Let's start to look at interesting facts about memory copies.
The first fact is that sometimes this function is not called it's not being unlocked.
Instead it is just a built-in.
Then a compiler sees a memory copy with a constant size like in this example 8 bytes.
It will generate this assembly code without any function call.
You can disable it if you want using the parameter built-in memory copy.
You can enable it explicitly but it is enabled by default with optimizations.
And also you can invoke built-in compiler built-in function explicitly using underscore
build-in memory copy.
But if the size is unknown at compile time it will not be effective it will still
do a function call.
Okay the next fact it works even for like unusual and even sizes.
If you do 16 bytes copy you see the compiler will use symptoms traction at least SSE to
copy 16 bytes at once.
The compiler has to use un-line extraction instructions because it does not know if the
date is aligned.
If you copy 15 bytes the compiler will do something interesting.
It will do two copies of 8 bytes that overlap.
One of these bytes will be like copy twice but it does not matter.
It is fairly optimal and the compiler is probably smart enough to choose this specific
code.
You can always check it on Godbolt for example to see the assembly.
Okay the next fact if you try to write your own memory copy like this function f that
will invoke a loop that copy is data byte by byte.
The compiler can recognize this pattern and replace it just to a call of memory copy.
So you try to write a memory copy and compile a memory copy like this and insert it
to memory copy as you want it and your code is pointless in this case.
Look how disabled this behavior using again f built in.
I'm copy or f3 loop distribute patterns.
The question for the audience what does it mean I'm copy and present PLT not and present
at PLT exactly this exactly what does it mean look up the procedure look up what yeah so
procedure look up table for what for a call yeah but why why the compiler has to use
the procedure look up table yeah relocations for third libraries yeah exactly we
which is not exactly optimal but we will go to this later so well interesting fact what
will happen if you write your own memory copy like this you will get segmentation falls
from stack or flow because this memory copy function will invoke again memory copy okay the
next fact glipsy which is used by default if you compile your program one almost any
opponent on Linux specifically for glipsy it actually can invoke one of this one to three
four five six nine nine different implementations of memory copy and it does it with a
very interesting trick so it uses the shared library logic mechanism to substitute
the most optimal supposedly the most optimal implementation at the time of
relocations so at loading time the program has to do these relationships for shared library and
it can substitute the function using this i funk mechanism so glipsy is already really smart
it can use like name copy avx512512 unaligned avx512 unaligned eRMS and avx512
no way v0 upper and it will be very interesting to figure out why does it have all three of these functions
let's take a look so which instructions to use for memory copy actually
the implementation for memory copy already exists inside the CPU
so Intel CPUs since 1978 already has have this instruction rep move sb which does actually
memory copy actually it includes something like move a byte increment a counter until some
condition happens but it is memory copy and it exists since 1978 which means that this
memory copy is older than me but it is not so simple because in 2012 the CPUs get a new flag
name it eRMS which means enhanced rep move sb so the previous implementation was really slow
and they enhanced it that but it was not enhanced enough and in about 2017 some CPUs get a flag
name it f as fs are m like this which I will tell you about just in a few minutes
okay how to optimize memory copy I would say that every self respecting the water already tried
to optimize memory copy at least once in a life by the way how many self respecting the
well preserving the room quite of you actually I like it yeah I would like to know how
did you succeed okay after this presentation I would like to ask you okay so let's try let's try
to optimize memory copy but the first question you should have be prepared you should have
reproducible performance test and ideally on some products on applications on some products
work load because otherwise you will over optimize memory copy for a particular scenario like
copying one megabyte of memory or copying from four kilobytes to eight kilobytes of memory
with random distribution and random distribution is not representative constant distribution is not
represented the only representative distribution is the distribution from your production
and it depends on many many factors like we are exactly the data will be copied how frequently
it will be accessed how at what time after copying it will be accessed and so on and often you
don't need to optimize memory copy because you sometimes we need something else other than memory copy
some different variations of this function because memory copy does exactly what
it represents copy specific amount of bytes from specific location to specific other specific
collections but what if you have some assumptions in the code like you can copy this chunk of memory
to another chunk of memory and then immediately copy another chunk after straight after that and then
you can use a function that will overwrite some memory past all the request buffer because the
next location will also overwrite this memory and about the standard name copy function you cannot
do this assumption inside your code maybe you can take a few assumptions and use a different
function it's like a file a follow-up call up the direction okay our goal is to optimize the
standard function now the question which language should we use probably we should imagine
ourselves like really hardcore engineer like gray beard engineer and write it in assembly
but if you write it in assembly like you create a file name copy dot test
the upside you basically control everything every single instruction but this function will not
in line and sometimes specifically for smaller sizes it's really important to
make sure that some invocations will get in line it and in time optimization also
will not work maybe if you will write in the elevator I'm assembly maybe you will get
something like working quick time optimization but it is out of scope also you can write in the
in C maybe with a certain in line assembly can actually you can write name copy in C++
just use external C and then you use your favorite language you know maybe you can even write
I'm not sure about it should you write name copy in Rust
let's take a look what is the essence of memory copy typically it has some instruction
to instructions to process tales or heads of your data like you have to copy a chunk of memory of
130 bytes and it means typically that you can do a fast loop for 128 bytes and also you
have a tail of two bytes or maybe you have a head of certain bytes if you want to use a line
instructions so you do something like loop peeling to align the main loop and you have the main loop
and you have to optimize both of them okay so what about what should we focus on
oftentimes my copy is involved in logged on small sizes like for SD disk string
when you copy SD disk string which should not do but it's inevitable in many cases
and you store something like I don't know URL or names or whatever company names in a
system it will be maybe 50 bytes maybe 100 bytes something like that and at this size it depends
on the cost of actually calling the copy the cost of function call and if the function is
located in a shared library you call you pay for this procedural laptop table which is not
a big cost but it's still noticeable for these small sizes and if a function is in a different
translation unit either using time optimization or it is not going to be in line it
and even according to convention makes sense because you have to say for register you have to
register and so on what matters for large sizes the instructions said should you use
SSE like in the previous presentation that was demonstrated should you use AVX should you use AVX512
it's a big question should you use this rep of SD loop and rolling matters the order of
copying data like should you copy forward or backwards there is an interesting story when
so tried this and I'm copy was implemented like copying byte by byte in for in a forward
direction and some people abused memory copy to copy intersection ranges which is not allowed by
the standard it is undefined behavior but some people did it and when the implementation of
memory copy was changed to copy data backwards they were really disappointed about bugs in their program
and even tried to convince lip see authors to change it to not optimize memory copy fortunately
they did not convince lip see authors are really hard to go guys so
difficult to convince them okay and so there are a lot of variability like should we use a
line of instructions or not a line should we use non-temporary stores like there are specific
instructions that tell you that you write data somewhere and this data should not be in the
CPU cache it should go directly into memory because this data will not be accessed soon
and everything depends on the particular CPU model and particular data distribution so the
testing will be especially hard the first example this single instruction the rep and e move
sb one instruction in all CPUs it is implemented with microcode and it is really slow and you should
not use it in more modern CPUs it works fast but only for large sizes it has a large startup overhead
but a new CPUs with this f as m flag it supposedly should work well for all cases but still
it not the fastest option and still you have to figure out on which CPU do you run just to decide
if you have to invoke this instruction or you should do something else another example if you use
a the action instructions for memory copies for most CPUs it they will be faster but they will
be faster if you use this v0 upper instruction after finishing with your ethics code because otherwise
all other codes like non-events might be SSE we'll suddenly slow down you do your fast memory
code and all other codes slows down but in newer CPUs you don't have to use this v0 upper instruction
because they optimized the CPUs and now it works okay and this is why there are so many different
implementations a VX5 12 is also not easy in many not modern CPUs it was not faster than
a VX for multiple reasons today interesting fact that on mdcpus a VX5 12 works often
better than on Intel CPUs where it was originated but still we get latency spikes
one way due to the usage of this instruction and this is my reaction to all of this it is so complex
so many so many difficult details so what to do what should we do
another example non-temporary stores should we use non-temporary stores to bypass cache
if you run your benchmark and your test your web copy most likely you will get an impression that
yes non-temporary stores improves everything until you put this implementation into production
when it will actually slow down the code why because non-temporary stores are intended for the case
when data is not accessed after it was copied at least for a long time in production code typically
the data is copied to be used almost immediately so it is almost completely pointless in production
okay so better not to optimize memory code not even try you will optimize it for your machine
you will write a blog post about your amazing page mark and your amazing implementation
and your software will slow down on someone else machine but I will try to optimize memory
copy anyway okay so for benchmark we will use different buffer sizes different sizes
memory copy called different random distributions with actually different probability
distributions different number of threads and different directions different relative positions
between buffers and we have a lot of existing deliberations nine variants from jlipsi
memory copy from cost map all tonlipsi rep and I move SB simple loop with different options
once the range and implementation of the input I found on a chinese website
yeah two different chinese variants one and a traditional chinese
simplified chinese my own implementation and also imitation from string zilla library
and I have to test it and for testing I have all machines from iWS all recent generations
which includes at least four different Intel CPUs and at least three different AMD CPUs
to do this benchmark I have a 42 thousand measurements for pin total to compare
and I basically test all variants for realism data sizes plus multi-plied by the number of machines
and when I tested all of this the result was that none of these implementations are actually the best
there are good implementations but under certain conditions one implementation wins
under certain conditions and other wins for example memory copy from cost map point of
nipsi is really good but not for small sizes string zilla is really great and zlipsi is also
not much slower and sometimes faster but zlipsi cannot be in line and I really want to
in line my memory copy implementation for small sizes so I still have a hope that I can make my own
the best memory copy how to do it if none of these implementation are the best
the idea is to make a generalize the memory copy so I will generate this code in c
which is similar to c++ because I use something similar to templates but
yeah with markers I just include the same file many many times with different values of this
markers vector size the enabling of v0 upper instruction and something else
and how many times to unroll the loop
and this code in c generates a code in in line assembly
so I have Microsoft for register name for instruction name if it is a line at
the size and so on and it looks something like this yeah we have function and in line assembly
and actually in line assembly can have markers and this is really handy for me can you write this code in
Rust yes yes I wanted to say there is at least nothing how C++ and C in this case
is better than Rust but maybe there is nothing okay it's just not just normal code yeah
and different options work better and different conditions so I thought maybe I can implement
self tuning memory copy because even if I do dynamic display for CPU model I still cannot decide
and there will be too many too many things to decide and it inevitably will be outdated with the
next CPU model so what about one interesting trick to make this memory copy like self driven
so for large sizes for small sizes we will have small like constant in line code but for large sizes
we will invoke different variants and calculate statistics we will really quickly calculate which
variant took which number of instructions and then we will kind of urge to the best
statistically the best option and everything was this at runtime so let's do it for at least
30,000 30 kilobytes if the buffer smaller than 40 kilobytes we will just use regular implementation
and why 30 kilobytes because I calculated memory copy in L1 cache should be at least like 100
gigabytes per second actually should be more today because this was long time ago and if we
and we have like a budget for our statistic progression just like a few 10 nanoseconds maximum
how to do it maximum 10 nanoseconds so this looks like as follows in my memory copy
I calculate I have a counter a thread probably it's a thread local maybe it's just counter on a
yeah thread local variable like count and depending on a threshold I invoke either exploration or
exploitation mode with exploitation mode I invoke this selected variant and in the exploration mode
there is a function explorer that calculates hash function and depending on this hash function it will
invoke a random variant and it basically calculates the time where it imprecises me but still
it's not probably not the right way to calculate the time but okay and guess if it helped it was at the
first option it must be definitely the best option and I must definitely invent the fastest
memory copy so it worked successfully and it was the best at the benchmark then I put it
in production and start testing real queries and it was slow actually it was quite okay comparable
to other memory copy implementation but no speed up no expected speed up so self tuning magical memory
copy that I spent so much time implementing it was almost completely useless
and this is my impression why why was it useless so one hypothesis is that if you have a
amount to try to work a lot and say you have a CPU with let's say 64 cores 128 threads
and this is something like md epic with eight memory channels let it be dr5
and dr5 has whatever let's say 50 gigabytes per second per channel right and if you multiply by eight
we will get 400 is it 400 yeah gigabytes per second per one socket
but if you take 128 threads and here hyperthreading is okay logical threads can do
can issue this instructions with memory you will get saturated by memory and in this amount to
try to work lots it is not really important to switch from one memory copy implementation to
another memory copy implementation for large sizes but for small sizes it is really important
and in line with memory copy makes sense so what all of these users no not quite I still replace
at one memory copy implementation with another that I have written not with in line assembly but with
actually C++ yeah so it is a function with x-term C it is entirely in the header file so it is
in line it and it uses CMD instructions in 36 and today it uses actually just SSI2 so nothing fancy
but again it is not final we found out that if I use masket load stores from avx512
it makes sense it gives benefit and maybe I should continue my work but the problem is
all of our production in clickhouse cloud runs on arm and I spend so much time on this and I have to
spend even more to optimize memory copy on arm so conclusions top to mice your code
don't be afraid try crazy ideas and never give up
thank you for talking now it's time for questions rise your hand and I will pass my phone
I see I see I see I'm coming
hi thanks that was fantastic I have one important question about
okay I have two questions one is so at the beginning you showed a birth bench for a lot of
so at the beginning you showed a profile made with birth of mmcopy being I think 10% or more
of the runtime yeah so at the beginning you showed a profile with birth of mmcopy being more than 10%
of your runtime yeah does that include in-line mmcopies no if I in-line it will it does not show
in-line so at least in a birth at least by default it will show up inside different functions
okay and my second question was will you able to record the real world distribution of the mmcopy
sizes yeah that's a really good question and I thought about it and even I tried to do it
record the addresses and sizes into a file but I did not get to incorporating it
benchmark although it's a really good idea that I wanted to try
so one thing that I have seen in my application is that the compiler is clever
as long as you know the size but if you don't have the size and know it as a programmer that you
have varying sizes and small sizes then it's of better to do the loop on ruling yourself so for
example I have some code that which commonly just takes between six and 50 bytes and so I made an
outer loop and outer check for the size and if it's the smaller size then I manually unlooper
and roll it which is much faster than using the the one function that you said that cannot be
in-line the mmcopy AVX which is normally used it's really really hard to hear the question
but I almost I almost got the question so what to do is the size is like small but not not
known at compile time or yeah interesting that in this case mmcopy looks similar to
in one sense it is similar to the dev device so you have a few like jumps depends on
one's the remainder of the size into into a loop that has a few white instructions like
simple instruction center few small instructions and this pattern is typical in many
implementation including my implementation including cost-mopolitan dipsy all of them have
some very similar to the dev device
but I'm afraid maybe I did not hear the question well
yeah another question sorry absolute I cannot hear maybe you can like this can you hear me yeah
okay did you look at any interpersonal optimization on with a compiler to see if you could avoid
some of the main copy do have some inter procedural optimization right isn't the question
now the question was if you use a bit the compiler with the inter position the IPO
the inter procedural optimization so really difficult to check you would just
sorry I'm not sure how does it sound in the do you hear the question I can answer about
the inter procedural optimization so we use the final tip in a slank in a realist build
it does not help with memory copy but it helps with many other functions
maybe can you hear me maybe just to follow up the question just asked the if you
happened that we use all two probably inter procedural optimization has been carried out by the compiler
if you use the class so if you I know if you tested like your code that I like the original
copy as low down if you enable the optimizations like inter procedural optimization
part of the optimization pipeline we will do one of three yeah actually we use all three in slank
and we try to enable some extra stuff we also use some stuff like we
disabled the API compatibility because we have all the source code bundled and we enable
just a bit of stuff that the new stuff that appears in slank I'm not sure if we include the
that particular optimization that you mentioned maybe we can ask the room yeah the experts
see plus plus expert about specific new inter procedural optimization that are not enabled by default
in all three modes
another one sorry just the last one a fun fact are have you tried the main copy attribute for
you can see me I'm cop from what library in gc there's a compiler attribute that is main copy
and then it understands that's a main copy so you can do even more optimization things again
so it's just a fun fact if you want to do more compiler stuff on top just add the attribute
main copy and then see if it performs even better it can do things like using main copies
and stuff like that yeah it's really interesting although we started using gcf you years ago
so now you'll still ask what slank should have compatible optimization
also you might be if you are kind of gcc please don't don't be worried
it's good actually I think maybe it's in plan to they normally like the attributes are
possible but thanks I'm sure we are out of time so let's move further thank you for talking