Sergey Vojtovich writes:

just out of curiosity: is it possible to find out which functions cause highest amount of icache misses?

Yes, see the second post, the profiles marked "Icache misses (ICACHE.MISSES), before PGO" and "Icache misses (ICACHE.MISSES), after PGO". These are level 1 cache misses. You will see that the functions with high cache miss rate are more or less the same as the functions that execute a lot of instructions. Note however that according to Intel documentation, there is a large skid on those events, so one should not rely too much on the precise location reported.

Can it have anything to do with branch misprediction?

If you look at the same post, you will see profiles for BR_MISP_RETIRED.ALL_BRANCHES_PS. This is a precise event, so it points directly to the instruction after the mispredicted branch. We do get 12% or so less mispredictions, so it has some effect. In comparison, we get 23% fewer icache misses. Note that the main source of branch misprediction is frequently called shared library functions (due to the indirect jump in PLT), and virtual function calls. This suggests that the problem here is that the sheer number of branches executed causes eviction of otherwise correctly predicted branches. We are simply executing too much code per request for the CPU to handle efficiently, a common thing in server applications. Another improvement that I noticed is in make_join_statistics(). PGO uses calls to optimised memset() and memcpy() functions for large structure memory writes, instead of byte-by-byte "rep movsb" sequences. There are probably many small improvements that contribute to the overall speedup spread out over the code, it is hard to determine precisely with such a large code base. The reason I mention icache misses in particular is that 1. The performance counter measurements pre-PGO clearly shows that icache miss rate is the main bottleneck in the CPU. 2. PGO is well suited to reducing icache misses. 3. Indeed, measurements post-PGO show a significant reduction in icache misses. - Kristian.

Sergey Vojtovich writes:

Still a questions mostly to educate myself. According to proc mysqld executable size is something like: VmExe: 12228 kB VmLib: 6272 kB

I assume the above refers to overall instructions. Level 1 instruction cache size is like 32Kb, right?

Yes, 32Kb.

When you say that we're executing too much code per request, did you mean the above?

No. I was refering to the actual code that is touched by the given load. In my sysbench read-only benchmarks, we run around 40000 instructions per query. But some of those are in loops, so it is unknown how many distinct instructions need to be fetched (maybe cachegrind could help determine this). If the live set, that is the actual instructions executed in a given load, would fit in L1 instruction cache, then we would see a large gain in performance. That might not be possible to achieve, though. My hypothesis is that the reduction in icache misses from PGO comes from the compiler being able to re-arrange the basic blocks of the code so that the actual benchmark load ends up with fewer and larger straight-line code execution paths. This would help reduce the number of half-used cache lines in the icache, and also help the hardware prefetcher being able to reduce the impact of icache misses. The actual size of the executable does not matter much, only the parts that are actually executed during a given load.

Do you think we can get similar speedup by putting compiler hints (e.g. likely/unlikely) and code optimizations?

I do not know for sure, but I think it is unlikely. We may be able to get some of the speedup with such hints. But as I remember the GCC documentation, there are a number of optimisations that are only enabled if actually using profile-guided optimisation. But it is hard to say for sure... - Kristian.

Axel Schwenke writes:

Wow. 25% is a lot. Have you also tried compiling MySQL 5.6 with PGO?

No.

Because if that gets the same improvement, we haven't won anything in the comparison.

On the contrary, if the same works for MySQL 5.6 (and it seems likely it will), then we have won double - both users on MariaDB _and_ users on MySQL 5.6 will benefit from increased performance. (I know what you mean, of course, but seriously - the goal is to improve performance for as many users as possible, not to "win" in some marketing stunt. For me, it is.)

This is interesting. By definition, PGO should work best if the workload used for profiling matches the production workload. I hadn't expected that a partial match gives such good results too.

This is something that needs more tests.

Agree that more tests would be good. Even if the workload is not identical, there should be many common code paths, which would explain that there is still some improvement. If PGO would increase only one particular workload and slow down the rest, then it would be unattractive. My tests so far seem to show that this is not the case, but more testing would be good.

Yes, I'll certainly do that.

Cool. Let me know if you need any help - hopefully the procedure I wrote in the earlier mail will work for you. Note that currently, the gen_profile_load program needs the build directory to be a directory inside the source directory, IIRC (eg. mariadb-10.0/build/).

Speaking of regressions - if we plan to deliver binaries built with PGO, we must also test the influence of different architectures. I.e. how behaves a binary built on Intel when being run on AMD.

Hm, yes it would be good to test, but do you expect any issues here? I did not use any cpu-specific options, and the profiling output should be independent of the underlying cpu, I think? - Kristian.

Axel Schwenke writes:

I propose the following change to make it work with MariaDB releases before 10.0.4 (and MySQL) that lack the SHUTDOWN statement:

Nice, thanks Axel! - Kristian.

Axel Schwenke writes:

Benchmark 1 is good old sysbench OLTP. I tested 10.0.7 vs. 10.0.7-pgo. With low concurrency there is about 10% win by PGO; however this is completely reversed at higher concurrency by mutex contention (the test was with performance schema disabled, so cannot say which mutex, probably LOCK_open).

Ouch, pgo drops the throughput to 1/2! That's a pretty serious blow to the whole idea, unless there is not just a fix but also a good explanation. I will investigate this, thanks a lot for testing! I must say it is totally unexpected. I would have expected the effect of pgo (whether positive or negative) to be most pronounced at low concurrency, since at high concurrency lock contention dominates, which mainly happens in kernel and library code. And it is strange that a performance improvement at low concurrency manifests itself as a loss at high concurrency. Maybe pgo re-arranges data to optimise cache sharing? And this introduces more false sharing? But this needs to be checked properly.

The other benchmark is purely single threaded and runs Q1 from DBT3 for memory based data. Here I include data for many MariaDB and MySQL versions for comparison. The plot is a classical box-and-whiskers plot where the box contains 50% of the data points (25-75 percentile) and the whiskers mark minimum and maximum.

If I understand correctly, the noise in those tests is really too big to tell much one way or the other, right? Well, low-concurrency tests also shows the effect of single-threaded performance just fine. But clearly, unless there is some explanation for the hit at high concurrency, the PGO idea is not looking attractive... Again, thanks a lot for looking into this, I will try to find time soon to investigate more. - Kristian.

Hi Kristian On 04/22/2014 04:11 PM, Kristian Nielsen wrote:

As a side effect, if we improve the code performance of a single thread, we effectively increase the concurrency in the critical spots - threads spend less time executing the real code, hence more time in concurrency bottlenecks. The end result is that _any_ change that improves single-threaded performance causes throughput to decrease at concurrency levels where the code falls over.

I have a more "education" focused question, rather than commenting on the issue or the results/arguments. What do you mean with the phrase [code|server] "falls over"? Also a quote from https://lists.launchpad.net/maria-developers/msg07210.html :

Basically, the server "falls over" and starts trashing instead of doing real work, due to some kind of inter-processor communication overhead.

I understand the concept of a program spending increased time in a) switching or scheduling switches b) communication between threads during increased concurrency levels. I am simply wondering if you mean anything more specific. Forgive my ignorance, and the thread hijacking :) Regards Vangelis

Hi Kristian On 04/30/2014 02:11 PM, Kristian Nielsen wrote:

Vangelis Katsikaros writes:

...

What do you mean with the phrase [code|server] "falls over"?

I am refering to a common phenomenon in high-concurrency benchmarks. See for example the graph in this email:

https://lists.launchpad.net/maria-developers/msg06799.html https://lists.launchpad.net/maria-developers/gifSCfeVH5OFW.gif

As the concurrency (number of client threads) increases, throughput also increases; this is what we call "scalability". At some point, we have sufficient concurrency to fully utilise all machine resources, and throughput no longer increases with more concurrency, this is expected.

But if you look at the bars marked "10.0.7-pgo" in that graph, you see that the troughput actually dramatically _decreases_ with increasing concurrency. Such behaviour is rather undesirable. Imagine a real system that gets temporarily overloaded. New requests start arriving faster than they can be satisfied, effectively increasing concurrency. If increasing concurrency causes decreasing throughput, this can get into a negative feedback loop, eventually making the system almost unable to satisfy any requests.

This behaviour, where the throughput does not remain mostly flat as concurrency increases, but instead dramatically decreases, is what I somewhat sloppyly refer to as "the server falling over".

Thanks for the detailed explanation! I hadn't noticed the _drastic_ decrease in throughput and I thought you were referring to something else. Regards Vangelis