Comment by nkurz | Hacker News Reader

Comment by nkurz | Hacker News Reader

Deep within another thread, I had a conversation with 'nnethercote' regarding Richard's use of Cachegrind to optimize performance. My position is that it is no longer a useful approach, as the actual behaviour of modern processors has diverged so much from Cachegrind's simple simulation. Instead, I think it is much more productive to use tools like 'perf' that use the CPU's built in performance counters to measure the actual performance.

My conviction inspired me to repeat Richard's test to see how the numbers compared when run on a current Haswell i7-4770 processor. Here's what I got for the versions he compared when compiled with GCC 4.8.1 and using 'perf stat speedtest1 --size 5'[1] (sizes are for the sqlite.o lib only):

  Cachegrind per Richard:
  3.8.7a -Os: 953,861,485 cycles
  3.7.17 -Os: 1,432,835,574 cycles

  Haswell:
  3.8.7 -O3: 469,956,519 cycles (870,767,673 instructions, 1,069,032 bytes)
  3.8.7 -Os: 542,228,740 cycles (884,541,860 instructions, 648,360 bytes)

  3.17.7 -O3: 651,680,545 cycles (1,320,867,830 instructions, 1,002,192 bytes)
  3.17.7 -Os: 771,304,471 cycles (1,406,527,795 instructions, 605,976 bytes)

One can make of the numbers what you will, but here are some conclusions I drew:

While the improvement is about the same magnitude that Richard sees, the actual number of cycles is off by about a factor of 2.

Despite having a larger binary, and thus theoretically worse instruction cache behavior, -O3 beats -Os by about 20% in speed in both cases, at a cost of 40% (400K/1MB) in size.

'perf record -F100000 speedtest1 --size 5; perf report' is a really slick and easy way to figure out where the program is spending it's time. If I were optimizing this, I remain fairly certain it would be more a more effective approach than using Cachegrind.

[1] I had to comment out the "sqlite3_rtree_geometry_callback" line in speedtest1.c to get it to compile, which might affect my numbers slightly, but from the source comments I don't think it was actually being used.

The cycle-counts returned by cachegrind are repeatable, to 7 or 8 significant figures. That means that I can make a small change and rerun the test and know whether or not the change helped or hurt even if the difference is only 0.01%. I don't think perf is quite so repeatable, is it?

Also, the cg_annotate utility gives me a complete program listing showing me the cycle counts spent on each line of code, which is invaluable in tracking down hotspots in need of work. If perf provides such a tool, I am unaware of it.

Remember that I'm not trying to optimize for a specific CPU. SQLite is cross-platform. I want to do optimizations that help on all CPUs using all compilers. I'm measuring the performance on the "cachegrind virtual CPU" of a binary prepared using GCC and -Os because that combination gives repeatable measurements that are easy to map into specific lines of source code. But the optimizations themselves should usually apply across all CPUs and all compilers and all compiler optimization settings.

Nkruz is, of course, welcomed to use any tool he likes to optimize his projects. But, at least for the moment, I'm finding cachegrind to be a better tool to help with implementing micro-optimizations.

> The cycle-counts returned by cachegrind are repeatable, to 7 or 8 significant figures. ... I don't think perf is quite so repeatable

It can come close. I just tried, and for 'speedtest1' seemed to be getting 3 significant digits for the cycle counts, and 4 for the instruction count. You'd probably gain another one or two if you were to measure computation only and remove the printf() and other I/O statements. The underlying performance counters are pretty much cycle accurate.

> cg_annotate utility gives me a complete program listing showing me the cycle counts spent on each line of code... If perf provides such a tool, I am unaware of it.

Yes, that record/report combination I quoted above does just this, with insignificant runtime overhead. Unlike the total counts, this one is sampled, so you might get a little more variation. It's definitely good enough for quickly finding hotspots, and there are other (harder to use) tools that can use the precise "PEBS" events you need complete counts. These even allow you to do nifty things like track the number of times each branch statement is mispredicted.

> I'm measuring the performance on the "cachegrind virtual CPU" of a binary prepared using GCC and -Os because that combination gives repeatable measurements that are easy to map into specific lines of source code.

Absolutely, this is the right way to view cachegrind. My question would be whether it is the right generic CPU to be using, and whether optimizations made on it translate well to other modern CPUs. Many of them will, but I think you'd have faster turnaround time even better success with an approach that uses a real CPU and its performance counters.

> I'm finding cachegrind to be a better tool to help with implementing micro-optimizations.

Please realize I have the utmost respect for your work on SQLite. It's my most frequent answer when asked for an example of C code to study, learn from, and pattern after. I'm certain you will manage to optimize it with any tool you choose, but having spent many hours with GProf and cachegrind myself, I (will the zeal of a recent convert) think you'll be amazed with some of the things that are now possible with performance counters.

I find perf a very useful tool, and use it frequently.

At the same time, I don't see how your data supports your conclusion that perf is more effective than cachegrind here. The absolute cycle count is of limited interest. The most important thing these tools do is tell programmers where to look, and cachegrind seems to have done a good job of that here.

In my experience, perf and cachegrind are two tools in the toolbox. perf is stronger at optimizing for the particular CPU I'm on, and it runs faster. Cachegrind collects more detailed information, and while the model it uses isn't perfect for the CPU I'm on today, it's usually good enough to be useful, and it's good for optimizing things likely to matter on other CPUs too.

One problem with perf counters, in my experience, is that the results vary a lot in a quasi-random way. Trying to get repeatable results is a painful experience.

Reply on news.ycombinator.com