Messages in this thread | | | From | Denys Vlasenko <> | Subject | Re: [PATCH 0/1] vsprintf: optimize decimal conversion (again) | Date | Wed, 28 Mar 2012 12:13:07 +0200 |
| |
On Wednesday 28 March 2012 07:56, roma1390 wrote: > On 2012.03.27 18:42, Denys Vlasenko wrote: > > On Tue, Mar 27, 2012 at 2:08 PM, roma1390<roma1390@gmail.com> wrote: > >> On 2012.03.26 21:47, Denys Vlasenko wrote: > >>> > >>> Please find test programs attached. > >>> > >>> 32-bit test programs were built using gcc 4.6.2 > >>> 64-bit test programs were built using gcc 4.2.1 > >>> Command line: gcc --static [-m32] -O2 -Wall test_{org,new}.c > >> > >> Can't compile reference for arm: > >> $ arm-linux-gnueabi-gcc -O2 -Wall test_org.c -o test_org > >> test_org.c: In function ‘put_dec’: > >> test_org.c:101: error: impossible constraint in ‘asm’ > >> test_org.c:101: error: impossible constraint in ‘asm’ > >> test_org.c:101: error: impossible constraint in ‘asm’ > > > > Please find a modified test_header.c attached. > > I tested and it builds in my arm emulator. > > > Run on same: > 2.6.32-5-kirkwood #1 Tue Jan 17 05:11:52 UTC 2012 armv5tel GNU/Linux > GCC version: > gcc version 4.4.5 (Debian 4.4.5-8), Target: arm-linux-gnueabi > Compiled with: > arm-linux-gnueabi-gcc -O2 -Wall test_{org,new}.c -o test_{org,new} > > > run default priority on almost idle machine:
Hmm, results are not good. Up to 8-digit conversions we were winning, but when we start converting larger numbers, we lose big time:
123456789:2388000 2^32:2268000 2^64:1400000 123456789:1168000 2^32:976000 2^64:532000
Since ARM is 32-bit, we are using algorithm #2.
It's not like algorithm #2 is intrinsically bad: on i386, it is a win on both AMD and Intel I tested it on.
Either it's just the difference between ARM and x86, or gcc is generating suboptimal code for it.
I would like to ask you to do a few things.
First: email me both test_org and test_new binaries. (Privately, to not spam the list).
Second: run arm-linux-gnueabi-gcc -O2 -Wall test_{org,new}.c -S and email me resulting test_{org,new}.s files.
Third: switch to algorithm #1 and test whether it fares better. To do that, go to test_new.c and replace #if LONG_MAX > ((1UL<<31)-1) || LLONG_MAX > ((1ULL<<63)-1) with #if 1 ////LONG_MAX > ((1UL<<31)-1) || LLONG_MAX > ((1ULL<<63)-1) (there are two instances of this line there), then recompile and rerun the test, and post the result.
When I disassemble ARM code produced by _my_ compiler, I don't see any obviously bad things.
put_dec_trunc8 is the function which works well for you.
put_dec_full4 and put_dec are used for printing 9+ digit numbers, and your testing says they are slow. I don't see why - see disassembly below.
I need to look at _your_ gcc's output...
00000000 <put_dec_trunc8>: 0: e92d40f0 stmdb sp!, {r4, r5, r6, r7, lr} 4: e59f6188 ldr r6, [pc, #392] ; 194 <.text+0x194> 8: e0843691 umull r3, r4, r1, r6 c: e1a03004 mov r3, r4 10: e1a0c003 mov ip, r3 14: e1a02083 mov r2, r3, lsl #1 18: e1a03183 mov r3, r3, lsl #3 1c: e3a04000 mov r4, #0 ; 0x0 20: e0822003 add r2, r2, r3 24: e2811030 add r1, r1, #48 ; 0x30 28: e0621001 rsb r1, r2, r1 2c: e15c0004 cmp ip, r4 30: e1a05000 mov r5, r0 34: e3a07000 mov r7, #0 ; 0x0 38: e4c01001 strb r1, [r0], #1 3c: 0a000052 beq 18c <put_dec_trunc8+0x18c> 40: e084369c umull r3, r4, ip, r6 44: e1a03004 mov r3, r4 48: e1a02083 mov r2, r3, lsl #1 4c: e1a01183 mov r1, r3, lsl #3 50: e1a0e003 mov lr, r3 54: e3a04000 mov r4, #0 ; 0x0 58: e0822001 add r2, r2, r1 5c: e28c3030 add r3, ip, #48 ; 0x30 60: e0623003 rsb r3, r2, r3 64: e15e0004 cmp lr, r4 68: e5c53001 strb r3, [r5, #1] 6c: e2800001 add r0, r0, #1 ; 0x1 70: 0a000045 beq 18c <put_dec_trunc8+0x18c> 74: e084369e umull r3, r4, lr, r6 78: e1a03004 mov r3, r4 7c: e1a02083 mov r2, r3, lsl #1 80: e1a01183 mov r1, r3, lsl #3 84: e1a05003 mov r5, r3 88: e3a04000 mov r4, #0 ; 0x0 8c: e0822001 add r2, r2, r1 90: e28e3030 add r3, lr, #48 ; 0x30 94: e0623003 rsb r3, r2, r3 98: e1550004 cmp r5, r4 9c: e4c03001 strb r3, [r0], #1 a0: 0a000039 beq 18c <put_dec_trunc8+0x18c> a4: e0843695 umull r3, r4, r5, r6 a8: e1a03004 mov r3, r4 ac: e1a02083 mov r2, r3, lsl #1 b0: e1a01183 mov r1, r3, lsl #3 b4: e1a0c003 mov ip, r3 b8: e3a04000 mov r4, #0 ; 0x0 bc: e0822001 add r2, r2, r1 c0: e2853030 add r3, r5, #48 ; 0x30 c4: e0623003 rsb r3, r2, r3 c8: e15c0004 cmp ip, r4 cc: e4c03001 strb r3, [r0], #1 d0: 0a00002d beq 18c <put_dec_trunc8+0x18c> d4: e1a0220c mov r2, ip, lsl #4 d8: e042210c sub r2, r2, ip, lsl #2 dc: e082200c add r2, r2, ip e0: e1a03302 mov r3, r2, lsl #6 e4: e0623003 rsb r3, r2, r3 e8: e1a03103 mov r3, r3, lsl #2 ec: e083300c add r3, r3, ip f0: e1a03083 mov r3, r3, lsl #1 f4: e1a0e823 mov lr, r3, lsr #16 f8: e1a0208e mov r2, lr, lsl #1 fc: e1a0118e mov r1, lr, lsl #3 100: e0822001 add r2, r2, r1 104: e28c3030 add r3, ip, #48 ; 0x30 108: e0623003 rsb r3, r2, r3 10c: e15e0004 cmp lr, r4 110: e4c03001 strb r3, [r0], #1 114: 0a00001c beq 18c <put_dec_trunc8+0x18c> 118: e1a0320e mov r3, lr, lsl #4 11c: e043310e sub r3, r3, lr, lsl #2 120: e1a02203 mov r2, r3, lsl #4 124: e0833002 add r3, r3, r2 128: e083300e add r3, r3, lr 12c: e1a0c5a3 mov ip, r3, lsr #11 130: e1a0208c mov r2, ip, lsl #1 134: e1a0118c mov r1, ip, lsl #3 138: e0822001 add r2, r2, r1 13c: e28e3030 add r3, lr, #48 ; 0x30 140: e0623003 rsb r3, r2, r3 144: e15c0004 cmp ip, r4 148: e4c03001 strb r3, [r0], #1 14c: 0a00000e beq 18c <put_dec_trunc8+0x18c> 150: e1a0320c mov r3, ip, lsl #4 154: e043310c sub r3, r3, ip, lsl #2 158: e1a02203 mov r2, r3, lsl #4 15c: e0833002 add r3, r3, r2 160: e083300c add r3, r3, ip 164: e1a0e5a3 mov lr, r3, lsr #11 168: e1a0208e mov r2, lr, lsl #1 16c: e1a0118e mov r1, lr, lsl #3 170: e0822001 add r2, r2, r1 174: e28c3030 add r3, ip, #48 ; 0x30 178: e0623003 rsb r3, r2, r3 17c: e15e0004 cmp lr, r4 180: e4c03001 strb r3, [r0], #1 184: 128e3030 addne r3, lr, #48 ; 0x30 188: 14c03001 strneb r3, [r0], #1 18c: e8bd40f0 ldmia sp!, {r4, r5, r6, r7, lr} 190: e12fff1e bx lr 194: 1999999a ldmneib r9, {r1, r3, r4, r7, r8, fp, ip, pc}
00000198 <put_dec_full4>: 198: e1a0c201 mov ip, r1, lsl #4 19c: e04cc101 sub ip, ip, r1, lsl #2 1a0: e1a0320c mov r3, ip, lsl #4 1a4: e08cc003 add ip, ip, r3 1a8: e1a0240c mov r2, ip, lsl #8 1ac: e08cc002 add ip, ip, r2 1b0: e08cc001 add ip, ip, r1 1b4: e1a0c9ac mov ip, ip, lsr #19 1b8: e1a0320c mov r3, ip, lsl #4 1bc: e043310c sub r3, r3, ip, lsl #2 1c0: e083300c add r3, r3, ip 1c4: e1a02303 mov r2, r3, lsl #6 1c8: e0632002 rsb r2, r3, r2 1cc: e1a02102 mov r2, r2, lsl #2 1d0: e082200c add r2, r2, ip 1d4: e1a02082 mov r2, r2, lsl #1 1d8: e1a02822 mov r2, r2, lsr #16 1dc: e92d4070 stmdb sp!, {r4, r5, r6, lr} 1e0: e1a0e202 mov lr, r2, lsl #4 1e4: e04ee102 sub lr, lr, r2, lsl #2 1e8: e1a0320e mov r3, lr, lsl #4 1ec: e08ee003 add lr, lr, r3 1f0: e1a0408c mov r4, ip, lsl #1 1f4: e1a0318c mov r3, ip, lsl #3 1f8: e0844003 add r4, r4, r3 1fc: e08ee002 add lr, lr, r2 200: e2811030 add r1, r1, #48 ; 0x30 204: e0641001 rsb r1, r4, r1 208: e1a0e5ae mov lr, lr, lsr #11 20c: e1a04000 mov r4, r0 210: e4c41001 strb r1, [r4], #1 214: e1a06000 mov r6, r0 218: e1a05182 mov r5, r2, lsl #3 21c: e1a0018e mov r0, lr, lsl #3 220: e1a01082 mov r1, r2, lsl #1 224: e1a0308e mov r3, lr, lsl #1 228: e0833000 add r3, r3, r0 22c: e0811005 add r1, r1, r5 230: e28cc030 add ip, ip, #48 ; 0x30 234: e2822030 add r2, r2, #48 ; 0x30 238: e2840001 add r0, r4, #1 ; 0x1 23c: e061c00c rsb ip, r1, ip 240: e0632002 rsb r2, r3, r2 244: e28ee030 add lr, lr, #48 ; 0x30 248: e5c6c001 strb ip, [r6, #1] 24c: e5c42001 strb r2, [r4, #1] 250: e5c0e001 strb lr, [r0, #1] 254: e2800002 add r0, r0, #2 ; 0x2 258: e8bd4070 ldmia sp!, {r4, r5, r6, lr} 25c: e12fff1e bx lr
00000260 <put_dec>: 260: e92d4ff0 stmdb sp!, {r4, r5, r6, r7, r8, r9, sl, fp, lr} 264: e3530000 cmp r3, #0 ; 0x0 268: e24dd00c sub sp, sp, #12 ; 0xc 26c: e1a08002 mov r8, r2 270: e1a09003 mov r9, r3 274: e1a0e000 mov lr, r0 278: 8a000009 bhi 2a4 <put_dec+0x44> 27c: 0a000003 beq 290 <put_dec+0x30> 280: e1a01008 mov r1, r8 284: e28dd00c add sp, sp, #12 ; 0xc 288: e8bd4ff0 ldmia sp!, {r4, r5, r6, r7, r8, r9, sl, fp, lr} 28c: eaffff5b b 0 <put_dec_trunc8> 290: e3e034fa mvn r3, #-100663296 ; 0xfa000000 294: e2433aa1 sub r3, r3, #659456 ; 0xa1000 298: e2433c0f sub r3, r3, #3840 ; 0xf00 29c: e1520003 cmp r2, r3 2a0: 9afffff6 bls 280 <put_dec+0x20> 2a4: e1a07828 mov r7, r8, lsr #16 2a8: e1a0c187 mov ip, r7, lsl #3 2ac: e1a02287 mov r2, r7, lsl #5 2b0: e08c2002 add r2, ip, r2 2b4: e0822007 add r2, r2, r7 2b8: e1a03182 mov r3, r2, lsl #3 2bc: e1a0a829 mov sl, r9, lsr #16 2c0: e0822003 add r2, r2, r3 2c4: e1a04809 mov r4, r9, lsl #16 2c8: e1a04824 mov r4, r4, lsr #16 2cc: e1a00202 mov r0, r2, lsl #4 2d0: e1a0118a mov r1, sl, lsl #3 2d4: e1a0328a mov r3, sl, lsl #5 2d8: e0815003 add r5, r1, r3 2dc: e1a09184 mov r9, r4, lsl #3 2e0: e0620000 rsb r0, r2, r0 2e4: e1a01808 mov r1, r8, lsl #16 2e8: e1a03304 mov r3, r4, lsl #6 2ec: e0800007 add r0, r0, r7 2f0: e1a01821 mov r1, r1, lsr #16 2f4: e0693003 rsb r3, r9, r3 2f8: e085200a add r2, r5, sl 2fc: e1a02202 mov r2, r2, lsl #4 300: e0800001 add r0, r0, r1 304: e0833004 add r3, r3, r4 308: e0800002 add r0, r0, r2 30c: e59fb164 ldr fp, [pc, #356] ; 478 <.text+0x478> 310: e1a03383 mov r3, r3, lsl #7 314: e0800003 add r0, r0, r3 318: e088209b umull r2, r8, fp, r0 31c: e1a086a8 mov r8, r8, lsr #13 320: e1a01388 mov r1, r8, lsl #7 324: e0411108 sub r1, r1, r8, lsl #2 328: e0811008 add r1, r1, r8 32c: e1a03101 mov r3, r1, lsl #2 330: e0811003 add r1, r1, r3 334: e0401201 sub r1, r0, r1, lsl #4 338: e1a0000e mov r0, lr 33c: e58dc004 str ip, [sp, #4] 340: ebffff94 bl 198 <put_dec_full4> 344: e1a03284 mov r3, r4, lsl #5 348: e1a02104 mov r2, r4, lsl #2 34c: e0822003 add r2, r2, r3 350: e1a0630a mov r6, sl, lsl #6 354: e1a0350a mov r3, sl, lsl #10 358: e0663003 rsb r3, r6, r3 35c: e1a01282 mov r1, r2, lsl #5 360: e0822001 add r2, r2, r1 364: e06a3003 rsb r3, sl, r3 368: e0642002 rsb r2, r4, r2 36c: e59dc004 ldr ip, [sp, #4] 370: e1a03183 mov r3, r3, lsl #3 374: e1a02182 mov r2, r2, lsl #3 378: e06a3003 rsb r3, sl, r3 37c: e04cc087 sub ip, ip, r7, lsl #1 380: e0833002 add r3, r3, r2 384: e083300c add r3, r3, ip 388: e0833008 add r3, r3, r8 38c: e087239b umull r2, r7, fp, r3 390: e1a076a7 mov r7, r7, lsr #13 394: e1a01387 mov r1, r7, lsl #7 398: e0411107 sub r1, r1, r7, lsl #2 39c: e0811007 add r1, r1, r7 3a0: e1a02101 mov r2, r1, lsl #2 3a4: e0811002 add r1, r1, r2 3a8: e0431201 sub r1, r3, r1, lsl #4 3ac: e046620a sub r6, r6, sl, lsl #4 3b0: ebffff78 bl 198 <put_dec_full4> 3b4: e1a03286 mov r3, r6, lsl #5 3b8: e0866003 add r6, r6, r3 3bc: e0499084 sub r9, r9, r4, lsl #1 3c0: e06a6006 rsb r6, sl, r6 3c4: e1a02189 mov r2, r9, lsl #3 3c8: e1a03106 mov r3, r6, lsl #2 3cc: e0663003 rsb r3, r6, r3 3d0: e0692002 rsb r2, r9, r2 3d4: e0822003 add r2, r2, r3 3d8: e0822007 add r2, r2, r7 3dc: e084329b umull r3, r4, fp, r2 3e0: e1a046a4 mov r4, r4, lsr #13 3e4: e1a01384 mov r1, r4, lsl #7 3e8: e0411104 sub r1, r1, r4, lsl #2 3ec: e0811004 add r1, r1, r4 3f0: e1a03101 mov r3, r1, lsl #2 3f4: e0811003 add r1, r1, r3 3f8: e0421201 sub r1, r2, r1, lsl #4 3fc: ebffff65 bl 198 <put_dec_full4> 400: e1a03185 mov r3, r5, lsl #3 404: e0653003 rsb r3, r5, r3 408: e083300a add r3, r3, sl 40c: e0944003 adds r4, r4, r3 410: e1a01000 mov r1, r0 414: 0a000010 beq 45c <put_dec+0x1fc> 418: e083249b umull r2, r3, fp, r4 41c: e1a066a3 mov r6, r3, lsr #13 420: e1a01386 mov r1, r6, lsl #7 424: e0411106 sub r1, r1, r6, lsl #2 428: e0811006 add r1, r1, r6 42c: e1a03101 mov r3, r1, lsl #2 430: e0811003 add r1, r1, r3 434: e0441201 sub r1, r4, r1, lsl #4 438: ebffff56 bl 198 <put_dec_full4> 43c: e3560000 cmp r6, #0 ; 0x0 440: e1a01000 mov r1, r0 444: 0a000004 beq 45c <put_dec+0x1fc> 448: e1a01006 mov r1, r6 44c: ebffff51 bl 198 <put_dec_full4> 450: e1a01000 mov r1, r0 454: ea000000 b 45c <put_dec+0x1fc> 458: e2411001 sub r1, r1, #1 ; 0x1 45c: e5513001 ldrb r3, [r1, #-1] 460: e3530030 cmp r3, #48 ; 0x30 464: 0afffffb beq 458 <put_dec+0x1f8> 468: e1a00001 mov r0, r1 46c: e28dd00c add sp, sp, #12 ; 0xc 470: e8bd4ff0 ldmia sp!, {r4, r5, r6, r7, r8, r9, sl, fp, lr} 474: e12fff1e bx lr 478: d1b71759 movles r1, r9, asr r7
-- vda -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |