DTrace: qsort use in Firefox
I’ve talked about OpenIndiana a bunch. I’ve mentioned several of its features. Let me tell you about my 
DTrace experiments from today. Inspired by Con Kolivas, I decided to see how Firefox uses the qsort C function.
First things first, let’s look at what the function signature looks like.
void qsort(void *base, size_t nel, size_t width,
int (*compar)(const void *, const void *));
The second argument contains the number of elements.
Now, let’s take a look at DTrace. We want the pid provider, which lets us instrument a specific process. In my case, Firefox was pid 1069. pid1069:libc:qsort:entry is the name of the probe that will fire every time qsort in libc.so is called by Firefox (pid 1069). Let’s aggregate the second argument (the number of elements). To keep things sane, I used the llquantize function. It is a log-linear quantization function that was rather well explained by Bryan Cantrill. (Base 10 with buckets between zero and one million seemed reasonable enough.) Additionally, I wanted DTrace to give me the current histogram every minute — that’s why there is the tick-60sec probe.
# dtrace -n 'pid1069:libc:qsort:entry{@=llquantize(arg1, 10,0,6,20)} tick-60sec{printa(@)}'
...
1 78738 :tick-60sec
value ------------- Distribution ------------- count
< 1 | 2
1 | 0
2 | 21
3 | 2
4 |@@@@ 365
5 | 1
6 |@ 132
7 | 0
8 |@@@@@@@@@@@@@@@@@@@@@ 1923
9 | 0
10 |@ 135
15 |@@ 194
20 |@ 134
25 | 9
30 |@@@ 246
35 | 31
40 | 8
45 | 0
50 | 0
55 | 10
60 | 1
65 | 10
70 | 39
75 | 2
80 |@ 112
85 |@ 56
90 |@ 82
95 | 1
100 |@ 132
150 |@ 90
200 | 0
250 | 0
300 | 4
350 | 0
Interesting! After several minutes of browsing various websites, we can see that Firefox really likes to sort 8-element arrays. (The value column is the bucket for the various array lengths. The count column specifies how many times there was a qsort call for each bucket.) Let’s dig a little deeper. Sorting 1 byte array elements is very different from sorting 1 MB elements. It would be really nice if we could break the histogram down into several histograms — one for each size. Well, guess what? DTrace lets you do that very easily.
Note that the command changed only a little. Now, in addition to looking at the second argument (the array length), DTrace breaks down the distribution based on the value of the third argument (the array element size). Since I visited different websites and Firefox does caching, the distribution of qsorts is a bit different — but it is still close enough.
# dtrace -n 'pid1069:libc:qsort:entry{@[arg2]=llquantize(arg1, 10,0,6,20)} tick-60sec{printa(@)}'
...
4 78738 :tick-60sec
52
value ------------- Distribution ------------- count
1 | 0
2 |@@@@@@@@@@@@@@@@@ 60
3 |@@ 9
4 |@@@@@ 17
5 | 0
6 |@@@@@@@@@@@@@@@ 55
7 | 0
8 |@ 3
9 | 1
10 | 0
8
value ------------- Distribution ------------- count
< 1 |@@@@@@@@@@@@@ 2
1 | 0
2 | 0
3 | 0
4 | 0
5 | 0
6 | 0
7 | 0
8 | 0
9 | 0
10 | 0
15 | 0
20 | 0
25 | 0
30 | 0
35 | 0
40 | 0
45 | 0
50 | 0
55 | 0
60 | 0
65 | 0
70 | 0
75 | 0
80 | 0
85 | 0
90 | 0
95 | 0
100 | 0
150 | 0
200 |@@@@@@@@@@@@@@@@@@@@ 3
250 | 0
300 |@@@@@@@ 1
350 | 0
4
value ------------- Distribution ------------- count
< 1 | 12
1 | 0
2 | 1
3 | 0
4 |@@@@@@@ 1351
5 | 0
6 |@ 247
7 | 0
8 |@@@@@@@@@ 1868
9 | 0
10 |@@@ 594
15 |@@ 422
20 |@ 230
25 | 4
30 |@@@@@@ 1193
35 |@@ 466
40 | 57
45 | 63
50 | 1
55 | 18
60 |@ 190
65 |@@ 341
70 |@ 207
75 | 2
80 | 56
85 |@ 158
90 | 46
95 | 0
100 |@@ 350
150 |@ 206
200 | 3
250 | 10
300 | 8
350 | 0
400 | 0
450 | 0
500 | 0
550 | 0
600 | 0
650 | 0
700 | 1
750 | 10
800 | 0
850 | 0
900 | 0
950 | 0
1000 | 0
1500 | 0
2000 | 0
2500 | 0
3000 | 8
3500 | 0
As you can see, there are now three histograms printed — that’s because DTrace saw 3 unique values of arg2. The first histogram is for 52-byte array element sorts. There weren’t many of those over the few minutes of browsing I did. The second is for 8-bytes elements — there are six of those total! The third distribution is where things get interesting. These are all the sorts of 4-byte array elements. Now we know that the large amount of 8-element sorts Firefox performs are on 4-byte element arrays. I wonder what that’s about. We also see that there were eight times that Firefox ended up sorting an array that had somewhere between 3000 and 3500 4-byte elements. Eeek!
DTrace is a really powerful tool. It lets you inspect the operation of a system with minimal disruption (the performance overhead is rather small). I hope to post more analyses of various software in the future.
I should add, this experiment was conducted with Firefox 3.6.12 on OpenIndiana 151a.
Comment by Dr Lou — October 2, 2011 @ 15:34