Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | 88888 Dihedral <dihedral88888@googlemail.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Performance of hand-optimised assembly |
| Date | 2011-12-26 11:52 -0800 |
| Organization | http://groups.google.com |
| Message-ID | <16367787.1074.1324929127614.JavaMail.geo-discussion-forums@pruu23> (permalink) |
| References | <0.d0ecd8f477637819bed2.20111223184332GMT.87pqffjfhn.fsf@bsb.me.uk> <4ef565dc$0$1388$4fafbaef@reader2.news.tin.it> <4ef81bc7$0$1380$4fafbaef@reader2.news.tin.it> |
io_x於 2011年12月26日星期一UTC+8下午3時05分16秒寫道：
> "io_x" <a@b.c.invalid> ha scritto nel messaggio
> news:4ef565dc$0$1388$4fafbaef@reader2.news.tin.it...
> >
> > "Ben Bacarisse" <ben.u...@bsb.me.uk> ha scritto nel messaggio
> > news:0.d0ecd8f477637819bed2.20111223184332GMT.87pqffjfhn.fsf@bsb.me.uk...
> >> I'm starting a new thread, but it is prompted by this remark from 88888
> >> Dihedral <dihedr...@googlemail.com> about a short binary search
> >> function I posted:
> >>
> >> | Do you consider to convert 5 to 10 lines of C to assembly?
> >> | I did that 20 years ago on X86 cpu.
> >> | It was a piece of cake to gain the 20-40% speed required if paid
> >> | well.
> >>
> >> I've felt (it's only a feeling) that hand coding for speed (rather than
> >> to access features not available in C like extra wide multiplies and so
> >> on) was a thing of the past. But maybe I'm wrong. Is it still possible
> >> to get a significant speed-up over C by hand coding? How much depends
> >> on the processor? How good are the modern optimising compilers that
> >> would have to be beaten?
> >
> > i modified your code for handle the C library bsearch and compare it with
> > my asm binsearch
> > my asm one is more slow[it seems 20% slower], but i like my 'slow' asm one
> > and don't like the C library one
>
> the .asm one is 2x time slower than the C one
> but i like the .asm one
> i don't know it this is right...
> ------------------
> ; return (u8*)-1 error, 0 not found, address of the found element in array
> ; if return 0 [not found]
> ; in ecx return the address element of the array < than key if exist
> ; else ecx=0
> ; in edx return the address element of the array > than key if exist
> ; else edx=0
> ; would be like the C library one, with the only
> ; difference return (u8*)-1 for error
> ;u8* __stdcall
> ;binSearchR(u8* InPKey, u8* InBase,
> ; u32 nElmBase, u32 SizeElmBase, i32 cmp(u8* elm1, u8* elm2) );
> ; 0k,4j,8i,12b,16ra, 20InKey,24InBase,28P_nElmBase,32P_SizeElmBase,36P_cmp + 64
> ; 84 88 92 96 100
> align 4
> binSearchR:
> push ebx
> push esi
> push edi
> push ebp
> sub esp, 64
> ;int3
Don't you use fastcall or direct embedding to save the push and pop
mess in the calling overheads ?
> mov dword[esp+ 4], 0
> mov dword[esp+ 8], 0 ; in ^4 and ^8 thre is the last element >
> and <
> cmp dword[esp+ 84], 0
> je .e
> cmp dword[esp+ 88], 0
> je .e
> mov edi, dword[esp+ 92]
> mov ebx, dword[esp+ 100]
> cmp dword[esp+ 96], 0
> jle .e
> cmp edi, 0
> je .nf
> mov esi, 0
> jl .e
> cmp ebx, 0
> je .e
> dec edi
> jmp short .2
> .nf: xor eax, eax
> clc
> jmp short .z
> .e: xor eax, eax
> dec eax
> stc
> jmp short .z
> .2: cmp esi, edi
> jg .nf
> mov ebp, esi
> add ebp, edi
> shr ebp, 1 ; k=(i+j)/2
> mov eax, dword[esp+ 96]
> mul ebp
> mov ecx, dword[esp+ 84]
> cmp edx, 0
> jne .e
> add eax, dword[esp+ 88]
> jc .e
> mov dword[esp+ 0], eax
> push ecx
> push eax
> call ebx
> add esp, 8
> cmp eax, 0
> jle .3
> dec ebp
> mov ecx, dword[esp+ 0]
> mov edi, ebp
> mov dword[esp+ 4], ecx
> jmp short .2
> .3: jz .4
> inc ebp
> mov ecx, dword[esp+ 0]
> mov esi, ebp
> mov dword[esp+ 8], ecx
> jmp short .2
> .4: mov eax, dword[esp+ 0]
> clc
> .z: mov edx, dword[esp+ 4]
> mov ecx, dword[esp+ 8]
> lea esp, [esp+64]
> pop ebp
> pop edi
> pop esi
> pop ebx
> ret 20
>
> ;0ra, 4P1, 8P2
> align 4
> cmpi32:
> mov eax, dword[esp+ 4]
> mov edx, dword[esp+ 8]
> mov ecx, [eax]
> cmp ecx, [edx]
> jge .1
> mov eax, -1
> jmp short .z
> .1: jz .2
> mov eax, 1
> jmp short .z
> .2: mov eax, 0
> .z:
> ret
>
> ;u32 binsearch(i32 arr, u32 len, i32 key)
> ;0k,4j,8i,12b,16ra, 20P_arr,24P_len,28P_key
> align 4
> binsearch:
> push ebx
> push esi
> push edi
> push ebp
> mov eax, dword[esp+ 20]
> mov edx, dword[esp+ 24]
> lea ecx, dword[esp+ 28]
> push cmpi32
> push 4
> push edx
> push eax
> push ecx
> call binSearchR
> jnc .2
> .e: mov eax, 0
> jmp short .z ; error
> .1: mov eax, -1
> clc
> jmp short .z ; not found
> .2: mov ecx, dword[esp+ 20]
> cmp eax, 0
> je .1
> sub eax, ecx
> shr eax, 2
> clc ; indx=(res-base)/4
> .z:
> pop ebp
> pop edi
> pop esi
> pop ebx
> ret 12
> ------------------
> #include <stdio.h>
> #include <stdlib.h>
> #include <time.h>
> #define u32 unsigned
> #define i32 int
> #define u8 unsigned char
> #define R return
> #define P printf
> #define F for
> // const, how is smart...
> #define cn const
>
> /*
> ;return (u8*)-1 error, 0 not found, address of the found element in array
> ;if return 0 [not found]
> ; in ecx return the address element of the array < than key if exist
> ; else ecx=0
> ; in edx return the address element of the array > than key if exist
> ; else edx=0
> would be like the C library one, with the only difference return (u8*)-1 for
> error
> */
> u8* __stdcall
> binSearchR(u8* InPKey, u8* InBase, u32 nElmBase, u32 SizeElmBase,
> i32 cmp(cn u8* elm1, cn u8* elm2) );
> i32 __stdcall binsearch(int a[], size_t length, int key);
>
> i32 Cbinsearch(int a[], size_t length, int key)
> {
> size_t low = 0, high = length;
> while (high > low) {
> size_t middle = low + (high - low)/2;
> if (key == a[middle])
> return middle;
> else if (key > a[middle])
> low = middle + 1;
> else high = middle;
> }
> return -1;
> }
>
> i32 cmpu32s(const void* elm1, const void* elm2)
> {u32 m1, m2;
> m1=*(u32*)elm1; m2=*(u32*)elm2;
> if(m1<m2) R -1;
> else if(m1>m2) R 1;
> else R 0;
> }
>
> int main(int argc, char** argv)
> {time_t in, fin;
> double d;
> u32 v[]={1, 2, 5, 7, 8, 8, 9, 13, 20}, val=4, *w, *ww, i;
> i32 ix, ixx;
> u8 *r;
>
>
> if(argc==2)
> {int n=atoi(argv[1]);
> int *data = (int *)malloc(n * sizeof *data);
>
> if(data)
> {int i, length, step, key;
> long int sum;
>
> for(i=0; i<n; i++) data[i]=2*i+1;
> // Include one zero-length search for correctness testing
> r = binSearchR(data, data, 0, sizeof(data[0]), cmpu32s);
> if(r) printf("Error r=%p\n", (void*) r);
> sum=0; time(&in);
> for(length=1; length<=n; length++)
> for(step=1; step<=length; step++)
> for(key=0; key<=2*length; key+=step)
> {r=binSearchR(&key, data, length, sizeof(data[0]), cmpu32s);
> if(r) sum+=(r-(u8*)data)/sizeof(data[0]);
> }
> time(&fin);
> P("myBsearch=%.3f ", (double) d=difftime(fin, in));
> printf("sum=%ld\n", sum);
> sum=0; time(&in);
> for(length=1; length<=n; length++)
> for(step=1; step<=length; step++)
> for(key=0; key<=2*length; key+=step)
> {r=bsearch(&key, data, length, sizeof(data[0]), cmpu32s);
> if(r) sum+=(r-(u8*)data)/sizeof(data[0]);
> }
> time(&fin);
> P("libsearch=%.3f ", (double) d=difftime(fin, in));
> printf("sum=%ld\n", sum);
> free(data);
> }
> }
>
> if(argc==2)
> {int n = atoi(argv[1]);
> /* cast so C++ compiled code can timed */
> int *data = (int *)malloc(n * sizeof *data);
> if (data)
> {int i, length, step, key;
> long int sum;
>
> for (i = 0; i < n; i++) data[i]= 2*i+1;
> /* Include one zero-length search for correctness testing */
> time(&in);
> sum = binsearch(data, 0, data[0]);
> for(length = 1; length <= n; length++)
> for(step = 1; step <= length; step++)
> for (key = 0; key <= 2 * length; key += step)
> sum += binsearch(data, length, key);
> time(&fin);
> P("AsmBsearc=%.3f sum=%ld\n", (double) d=difftime(fin, in), sum);
> time(&in);
> sum = binsearch(data, 0, data[0]);
> for(length = 1; length <= n; length++)
> for(step = 1; step <= length; step++)
> for (key = 0; key <= 2 * length; key += step)
> sum += Cbinsearch(data, length, key);
> time(&fin);
> P("C Bsearc=%.3f sum=%ld\n", (double) d=difftime(fin, in), sum);
> free(data);
> }
> }
> R 0;
> }
> --------------
> C:>bins 3000
> myBsearch=15.000 sum=-1433105604
> libsearch=15.000 sum=-1433105604
> AsmBsearc=16.000 sum=-1488664059
> C Bsearc=8.000 sum=-1488664059
> --------------
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-23 18:43 +0000
Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-23 19:40 +0000
Re: Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-23 21:26 +0000
Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-23 22:02 +0000
Re: Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-24 02:52 +0000
Re: Performance of hand-optimised assembly 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-23 20:32 -0800
Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-24 13:09 +0000
Re: Performance of hand-optimised assembly James Harris <james.harris.1@googlemail.com> - 2011-12-24 05:49 -0800
Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-24 15:30 +0000
Re: Performance of hand-optimised assembly James Harris <james.harris.1@googlemail.com> - 2011-12-24 08:15 -0800
Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-24 17:10 +0000
Re: Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-24 23:25 +0000
Re: Performance of hand-optimised assembly jgk@panix.com (Joe keane) - 2012-01-04 03:24 +0000
Re: Performance of hand-optimised assembly jacob navia <jacob@spamsink.net> - 2012-01-04 09:59 +0100
Re: Performance of hand-optimised assembly jgk@panix.com (Joe keane) - 2012-01-04 20:57 +0000
Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2012-01-04 23:04 +0000
Re: Performance of hand-optimised assembly Noob <root@127.0.0.1> - 2012-01-05 13:32 +0100
Re: Performance of hand-optimised assembly Philip Lantz <prl@canterey.us> - 2011-12-24 15:29 -0800
Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-24 12:42 +0000
Re: Performance of hand-optimised assembly Jens Gustedt <jens.gustedt@loria.fr> - 2011-12-24 16:58 +0100
Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-24 13:55 +0000
Re: Performance of hand-optimised assembly Seebs <usenet-nospam@seebs.net> - 2011-12-24 19:24 +0000
Re: Performance of hand-optimised assembly Geoff <geoff@invalid.invalid> - 2011-12-24 13:44 -0800
Re: Performance of hand-optimised assembly Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-12-29 02:53 +0200
Re: Performance of hand-optimised assembly Rui Maciel <rui.maciel@gmail.com> - 2011-12-29 02:11 +0000
Re: Performance of hand-optimised assembly jgk@panix.com (Joe keane) - 2011-12-24 01:36 +0000
Re: Performance of hand-optimised assembly "io_x" <a@b.c.invalid> - 2011-12-24 06:44 +0100
Re: Performance of hand-optimised assembly "io_x" <a@b.c.invalid> - 2011-12-24 09:52 +0100
Re: Performance of hand-optimised assembly "io_x" <a@b.c.invalid> - 2011-12-26 08:05 +0100
Re: Performance of hand-optimised assembly 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-26 11:52 -0800
Re: Performance of hand-optimised assembly "io_x" <a@b.c.invalid> - 2011-12-27 07:28 +0100
Re: Performance of hand-optimised assembly Willem <willem@toad.stack.nl> - 2011-12-24 12:48 +0000
Re: Performance of hand-optimised assembly 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-24 04:56 -0800
Re: Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-24 23:39 +0000
Re: Performance of hand-optimised assembly James Harris <james.harris.1@googlemail.com> - 2011-12-24 06:01 -0800
Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-24 14:55 +0000
Re: Performance of hand-optimised assembly James Harris <james.harris.1@googlemail.com> - 2011-12-28 03:46 -0800
Re: Performance of hand-optimised assembly 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-28 04:52 -0800
Re: Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-25 00:07 +0000
Re: Performance of hand-optimised assembly James Harris <james.harris.1@googlemail.com> - 2011-12-28 03:21 -0800
Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-28 13:19 +0000
Re: Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-28 16:01 +0000
Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-28 17:45 +0000
Re: Performance of hand-optimised assembly 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-28 18:56 -0800
Re: Performance of hand-optimised assembly Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-12-29 03:32 +0200
Re: Performance of hand-optimised assembly Tim Rentsch <txr@alumni.caltech.edu> - 2012-01-25 17:03 -0800
Re: Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-01-26 22:08 +0000
Re: Performance of hand-optimised assembly Tim Rentsch <txr@alumni.caltech.edu> - 2012-01-31 22:20 -0800
Re: Performance of hand-optimised assembly James Kuyper <jameskuyper@verizon.net> - 2011-12-28 08:24 -0500
Re: Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-28 14:27 +0000
Re: Performance of hand-optimised assembly Tim Rentsch <txr@alumni.caltech.edu> - 2012-01-25 16:50 -0800
Re: Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-01-26 21:59 +0000
Re: Performance of hand-optimised assembly James Harris <james.harris.1@googlemail.com> - 2011-12-28 11:12 -0800
Re: Performance of hand-optimised assembly Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-12-29 03:12 +0200
Re: Performance of hand-optimised assembly jacob navia <jacob@spamsink.net> - 2011-12-29 10:02 +0100
Re: Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-29 12:06 +0000
Re: Performance of hand-optimised assembly Tim Rentsch <txr@alumni.caltech.edu> - 2012-01-25 17:07 -0800
Re: Performance of hand-optimised assembly Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-02-13 01:18 +0200
Re: Performance of hand-optimised assembly Tim Rentsch <txr@alumni.caltech.edu> - 2012-03-08 10:54 -0800
Re: Performance of hand-optimised assembly jacob navia <jacob@spamsink.net> - 2011-12-29 10:02 +0100
Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-29 12:06 +0000
Re: Performance of hand-optimised assembly Keith Thompson <kst-u@mib.org> - 2011-12-29 11:44 -0800
Re: Performance of hand-optimised assembly Tim Rentsch <txr@alumni.caltech.edu> - 2012-01-25 17:23 -0800
Re: Performance of hand-optimised assembly James Harris <james.harris.1@googlemail.com> - 2011-12-29 08:37 -0800
Re: Performance of hand-optimised assembly Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-01-05 22:19 +0200
Re: Performance of hand-optimised assembly James Dow Allen <gmail@jamesdowallen.nospam> - 2011-12-24 16:21 +0000
Re: Performance of hand-optimised assembly Weland <weland@otaku.freeshell.org> - 2011-12-25 10:54 +0000
Re: Performance of hand-optimised assembly "christian.bau" <christian.bau@cbau.wanadoo.co.uk> - 2011-12-24 14:52 -0800
Re: Performance of hand-optimised assembly jacob navia <jacob@spamsink.net> - 2011-12-25 20:12 +0100
Re: Performance of hand-optimised assembly 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-25 11:36 -0800
Re: Performance of hand-optimised assembly jacob navia <jacob@spamsink.net> - 2011-12-25 21:35 +0100
Re: Performance of hand-optimised assembly Stephen Sprunk <stephen@sprunk.org> - 2011-12-26 14:24 -0600
Re: Performance of hand-optimised assembly jacob navia <jacob@spamsink.net> - 2011-12-26 21:36 +0100
Re: Performance of hand-optimised assembly Stephen Sprunk <stephen@sprunk.org> - 2012-01-04 11:59 -0600
Re: Performance of hand-optimised assembly jacob navia <jacob@spamsink.net> - 2012-01-04 20:22 +0100
Re: Performance of hand-optimised assembly Dann Corbit <dcorbit@connx.com> - 2012-01-04 12:59 -0800
Re: Performance of hand-optimised assembly James Harris <james.harris.1@googlemail.com> - 2012-01-04 15:32 -0800
Re: Performance of hand-optimised assembly Stephen Sprunk <stephen@sprunk.org> - 2012-01-05 23:47 -0600
Re: Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-01-04 22:47 +0000
Re: Performance of hand-optimised assembly jacob navia <jacob@spamsink.net> - 2012-01-05 00:47 +0100
Re: Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-01-05 00:22 +0000
Re: Performance of hand-optimised assembly 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-04 23:44 -0800
Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2012-01-05 12:16 +0000
Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2012-01-05 12:49 +0000
Re: Performance of hand-optimised assembly jgk@panix.com (Joe keane) - 2012-01-05 21:26 +0000
Re: Performance of hand-optimised assembly "io_x" <a@b.c.invalid> - 2012-01-07 10:32 +0100
Re: Performance of hand-optimised assembly jacob navia <jacob@spamsink.net> - 2012-01-05 00:58 +0100
Re: Performance of hand-optimised assembly 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-05 13:39 -0800
Re: Performance of hand-optimised assembly 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-07 02:15 -0800
Re: Performance of hand-optimised assembly 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-10 01:07 -0800
Re: Performance of hand-optimised assembly jgk@panix.com (Joe keane) - 2012-01-07 00:49 +0000
Re: Performance of hand-optimised assembly jacob navia <jacob@spamsink.net> - 2012-01-07 08:54 +0100
Re: Performance of hand-optimised assembly jacob navia <jacob@spamsink.net> - 2012-01-07 10:11 +0100
Re: Performance of hand-optimised assembly "io_x" <a@b.c.invalid> - 2012-01-07 10:51 +0100
Re: Performance of hand-optimised assembly jgk@panix.com (Joe keane) - 2012-01-07 20:09 +0000
Re: Performance of hand-optimised assembly Stephen Sprunk <stephen@sprunk.org> - 2012-01-06 23:39 -0600
Re: Performance of hand-optimised assembly jacob navia <jacob@spamsink.net> - 2012-01-07 10:33 +0100
Re: Performance of hand-optimised assembly Stephen Sprunk <stephen@sprunk.org> - 2012-01-07 07:36 -0600
Re: Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-01-07 21:03 +0000
Re: Performance of hand-optimised assembly Stephen Sprunk <stephen@sprunk.org> - 2012-01-07 16:42 -0600
Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-25 20:23 +0000
Re: Performance of hand-optimised assembly jacob navia <jacob@spamsink.net> - 2011-12-25 21:50 +0100
Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-25 22:10 +0000
Re: Performance of hand-optimised assembly 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-25 13:11 -0800
Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-25 22:07 +0000
Re: Performance of hand-optimised assembly 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-25 16:39 -0800
Re: Performance of hand-optimised assembly "io_x" <a@b.c.invalid> - 2011-12-26 05:55 +0100
Re: Performance of hand-optimised assembly "io_x" <a@b.c.invalid> - 2012-02-17 17:58 +0100
Re: Performance of hand-optimised assembly "Wolfgang.Draxinger" <Wolfgang.Draxinger@physik.uni-muenchen.de> - 2012-01-10 18:00 +0100
csiph-web