Re: [PATCH V2 1/3] lib: introduce some memory copy macros and functions
From: Miao Xie
Date: Wed Sep 08 2010 - 07:06:16 EST
Hi, Andi
On Thu, 2 Sep 2010 12:40:08 +0200, Andi Kleen wrote:
So I improve the generic version of memcpy and memmove, and x86_64's memmove
which are implemented by byte copy.
One should also add that most memmove()s and memcpy()s are actually
generated by gcc as inlines (especially if you don't use the
"make my code slow" option aka -Os) and don't use the fallback.
The fallback depends on the gcc version and if gcc thinks the
data is aligned or not.
Sometimes one can get better code in the caller by making sure
gcc knows the correct alignment (e.g. with suitable
types) and size. This might be worth looking at for btrfs
if it's really that memmove heavy.
Right! But the src address and dest address is not fixed, so it is hard to
tell gcc that the address is alignment or not.
The problem is memmove is very inefficient in fact, and it is used at some fast path,
such as: it is used to do metadata copy for filesystem, so we must improve it.
I have some systemtap scripts to measure size/alignment distributions of
copies on a kernel, if you have a particular workload you're interested
in those could be tried.
Good! Could you give me these script?
ftp://firstfloor.org/pub/ak/probes/csum.m4
You need to run them through .m4 first.
They don't measure memmove, but that should be easy to add.
I used your script to measure size/alignment distributions of copies on a kernel when
I ran the btrfs test, and got some data:
memmove
total 325903
length
value |-------------------------------------------------- count
1 | 0
2 | 0
4 | 3
8 | 0
16 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 57062
32 |@@ 5903
64 |@@@ 7296
128 |@@@@@@@@@ 18868
256 |@@@@@@@@@@@@@@@@@ 33790
512 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 64886
1024 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 98450
2048 |@@@@@@@@@@@@@@@@@@@@ 39645
4096 | 0
8192 | 0
length upto 50
value |-------------------------------------------------- count
2 | 0
3 | 0
4 | 3
5 | 0
6 | 0
~
21 | 0
22 | 0
23 | 24
24 | 0
25 |@@@@@@@@@@ 57037
26 | 0
27 | 0
~
29 | 0
30 | 0
31 | 1
32 | 3
33 | 78
34 | 215
35 | 1865
36 | 432
37 | 0
38 | 0
39 | 0
40 | 0
41 | 130
42 | 0
43 | 80
44 | 0
45 | 0
46 | 0
47 | 0
48 | 80
49 | 0
50 | 1077
>50 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 264878
src unalignments
value |-------------------------------------------------- count
0 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 23173
1 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 17623
2 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 23760
3 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 17372
4 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 19185
5 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 26264
6 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 20288
7 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 18474
8 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 20160
9 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 17754
10 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 21450
11 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 18127
12 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 23075
13 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 18582
14 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 21879
15 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 18737
16 | 0
dst unalignments
value |-------------------------------------------------- count
0 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 28566
1 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 17449
2 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 20980
3 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 17239
4 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 17171
5 |@@@@@@@@@@@@@@@@@@@@@@@@@@@ 15691
6 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 20558
7 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 18590
8 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 20644
9 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 21459
10 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 20384
11 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 19460
12 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 23087
13 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 19656
14 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 26330
15 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 18639
16 | 0
same unalignments
value |-------------------------------------------------- count
0 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 5695
1 |@@@@@@@@@@@@@@@ 1815
2 |@@@@@@@@@@@@@@@@@@@@@@@@@ 2850
3 |@@@@@@@@@@@@@@@ 1819
4 |@@@@@@@@@@@@@@@@@@@@@@@@ 2791
5 |@@@@@ 573
6 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 3358
7 |@@@@@@@@@@@@@@@@@@@@@ 2411
8 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 3340
9 |@@@@@@@@@@@@@@@@@@@@@ 2404
10 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 3475
11 |@@@@@@@@@@@@@@@@@@@@@@@@@@ 3019
12 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 4153
13 |@@@@@@@@@@@@@@@@@@@@@@@@@@ 3052
14 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 4212
15 |@@@@@@@@@@@@@@@@@@@@@@@@@@ 3011
16 | 0
different unalignments
value |-------------------------------------------------- count
0 | 0
1 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 41652
2 |@@@@@@@@@@@@@@@@@@ 25447
3 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 69946
4 |@ 1800
5 |@ 1701
6 |@ 1573
7 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 62478
8 | 810
9 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 49180
10 | 684
11 | 148
12 | 1148
13 |@@@@@@@@@@ 15298
14 |@@ 3459
15 |@ 2601
16 | 0
According to the data, the length of the most copies is >=128.
Besides that I did some tests for various condition on my x86_64 box.
The test is doing 500 bytes memory copy for 50000 times.
The test result is following:
dest < src || dest >= src + len:
Length Src Unalign Dest Unalign Without Patch Patch applied
------ ----------- ------------ ------------- -------------
8 0 0 0s 223086us 0s 230612us
8 0 3 0s 133857us 0s 138364us
8 0 6 0s 133852us 0s 138364us
8 3 0 0s 133845us 0s 138365us
8 3 3 0s 133845us 0s 138364us
8 3 6 0s 133841us 0s 138363us
8 6 0 0s 133848us 0s 138364us
8 6 3 0s 133842us 0s 138363us
8 6 6 0s 133840us 0s 138360us
16 0 0 0s 133847us 0s 138364us
16 0 3 0s 133851us 0s 138362us
16 0 6 0s 133842us 0s 138368us
16 3 0 0s 133849us 0s 138360us
16 3 3 0s 133844us 0s 138362us
16 3 6 0s 133839us 0s 138365us
16 6 0 0s 133845us 0s 138359us
16 6 3 0s 133841us 0s 138368us
16 6 6 0s 133841us 0s 138363us
32 0 0 0s 160914us 0s 165435us
32 0 3 0s 160925us 0s 165427us
32 0 6 0s 160898us 0s 165443us
32 3 0 0s 160930us 0s 165432us
32 3 3 0s 160898us 0s 165434us
32 3 6 0s 160919us 0s 165433us
32 6 0 0s 160909us 0s 165436us
32 6 3 0s 160914us 0s 165425us
32 6 6 0s 160910us 0s 165439us
256 0 0 0s 294756us 0s 299280us
256 0 3 0s 500777us 0s 505367us
256 0 6 0s 655671us 0s 660232us
256 3 0 0s 497769us 0s 503386us
256 3 3 0s 497790us 0s 502358us
256 3 6 0s 500793us 0s 505253us
256 6 0 0s 497751us 0s 503097us
256 6 3 0s 497773us 0s 502242us
256 6 6 0s 497769us 0s 502192us
1024 0 0 0s 457170us 0s 461843us
1024 0 3 1s 655705us 1s 660707us
1024 0 6 2s 388031us 2s 391429us
1024 3 0 1s 652717us 1s 660362us
1024 3 3 2s 755214us 1s 657005us
1024 3 6 1s 655735us 1s 660939us
1024 6 0 1s 669425us 1s 662643us
1024 6 3 1s 653472us 1s 659986us
1024 6 6 1s 653559us 1s 662163us
dest > src && dest < src + len:
Length Src Unalign Dest Unalign Without Patch Patch applied
------ ----------- ------------ ------------- -------------
8 0 3 0s 45029us 0s 45775us
8 0 6 0s 43634us 0s 48014us
8 3 0 0s 43625us 0s 43993us
8 3 6 0s 44324us 0s 45081us
8 6 0 0s 43613us 0s 44014us
8 6 3 0s 43620us 0s 44011us
16 0 0 0s 67680us 0s 49631us
16 0 3 0s 67677us 0s 77417us
16 0 6 0s 67671us 0s 81879us
16 3 0 0s 67676us 0s 52492us
16 3 3 0s 67675us 0s 75199us
16 3 6 0s 67677us 0s 81215us
16 6 0 0s 67673us 0s 52490us
16 6 3 0s 67676us 0s 77304us
16 6 6 0s 67676us 0s 79712us
32 0 0 0s 115800us 0s 49632us
32 0 3 0s 115812us 0s 81214us
32 0 6 0s 115792us 0s 85728us
32 3 0 0s 116488us 0s 60198us
32 3 3 0s 115803us 0s 79709us
32 3 6 0s 115798us 0s 85726us
32 6 0 0s 115844us 0s 60202us
32 6 3 0s 115805us 0s 81212us
32 6 6 0s 115802us 0s 84228us
256 0 0 0s 815079us 0s 91737us
256 0 3 0s 815075us 0s 194652us
256 0 6 0s 815079us 0s 198521us
256 3 0 0s 815074us 0s 171470us
256 3 3 0s 817181us 0s 114299us
256 3 6 0s 816478us 0s 198524us
256 6 0 0s 815822us 0s 173566us
256 6 3 0s 814936us 0s 196515us
256 6 6 0s 815152us 0s 118811us
1024 0 0 3s 125598us 0s 244644us
1024 0 3 3s 132574us 0s 590261us
1024 0 6 3s 125613us 0s 595143us
1024 3 0 3s 128452us 0s 568743us
1024 3 3 3s 124862us 0s 263189us
1024 3 6 3s 127440us 0s 595515us
1024 6 0 3s 122370us 0s 569479us
1024 6 3 3s 127429us 0s 590554us
1024 6 6 3s 126732us 0s 269415us
Though there is little regression when the length is <=16, theperformance
is quite well when the length is >=32.
Thanks!
Miao
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/