From: Miao Xie Subject: Re: [PATCH V2 1/3] lib: introduce some memory copy macros and functions Date: Wed, 08 Sep 2010 19:05:47 +0800 Message-ID: <4C876E0B.7010505@cn.fujitsu.com> References: <4C7F3A2A.2000007@cn.fujitsu.com> <877hj4o76p.fsf@basil.nowhere.org> <4C7F7853.6000400@cn.fujitsu.com> <20100902104008.GB17167@basil.fritz.box> Reply-To: miaox@cn.fujitsu.com Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Cc: Peter Zijlstra , Ingo Molnar , Andrew Morton , "Theodore Ts'o" , Linux Kernel , Linux Ext4 , Linux Btrfs To: Andi Kleen Return-path: Received: from cn.fujitsu.com ([222.73.24.84]:64336 "EHLO song.cn.fujitsu.com" rhost-flags-OK-FAIL-OK-OK) by vger.kernel.org with ESMTP id S1752726Ab0IHLGM (ORCPT ); Wed, 8 Sep 2010 07:06:12 -0400 In-Reply-To: <20100902104008.GB17167@basil.fritz.box> Sender: linux-ext4-owner@vger.kernel.org List-ID: 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