Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #14925 > unrolled thread

Performance of hand-optimised assembly

Back to article view | Back to comp.lang.c

Contents

  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

Page 2 of 6 — ← Prev page 1 [2] 3 4 5 6  Next page →

#14960

"Ben Bacarisse" <ben.usenet@bsb.me.uk> wrote in message 
news:0.393ac02b1554cc6fda1d.20111224025213GMT.87ehvuk7fm.fsf@bsb.me.uk...
> "BartC" <bc@freeuk.com> writes:

> Well, it's not bad that you can beat 2 of the three compilers.

I've tried one more compiler, and the results, now normalised and for the 
fastest code (and using N=2500 for more accuracy), are:

gcc -O3      1.00  (using inlining)
My asm       1.12  (original without inlining or unrolling)
Pelles C -Ot 1.26
DMC -o       1.35
lcc-win32 -O 1.64

(Adjusted for loop overheads)

So while modern compilers might be ultra-sophisticated, most of these 
aren't! Admittedly they are all free downloads..

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#14975

On 2011-12-24, BartC <bc@freeuk.com> wrote:
> So while modern compilers might be ultra-sophisticated, most of these 
> aren't! Admittedly they are all free downloads..

The commercial compiler vendors usually regard gcc as a poor performer, I'm
told.

That said... One of the things compilers tend to be better at than humans
is *large* optimizations.  Consider sqlite; while it's distributed with a
reasonably normal structure of source files and such, actual compilation is
done by merging all the sources into a single large file.  Why?  Because
the compiled output runs noticably faster.

Compilers can afford to try experiments and optimizations that human users
usually can't.

-s
-- 
Copyright 2011, all wrongs reversed.  Peter Seebach / usenet-nospam@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
I am not speaking for my employer, although they do rent some of my opinions.

[toc] | [prev] | [next] | [standalone]

#14978

On 24 Dec 2011 19:24:14 GMT, Seebs <usenet-nospam@seebs.net> wrote:

>On 2011-12-24, BartC <bc@freeuk.com> wrote:
>> So while modern compilers might be ultra-sophisticated, most of these 
>> aren't! Admittedly they are all free downloads..
>
>The commercial compiler vendors usually regard gcc as a poor performer, I'm
>told.

They naturally would, wouldn't they? I would expect them to come up
with benchmarks and lots of nice slide presentations touting their
products against each other and against the freeware stuff. I would be
more impressed with a commercial compiler vendor stating that xyz
freeware compiler is a good performer. 

The trouble with GCC is that there are so many switches it's probably
impossible to test all the modes and actually come up with a truly
optimum configuration for a given target and application.

Back in the day, I was programming an embedded Z80/Z180 RTOS using
Microtec Research's MCC80. One day, I found an unusual bottleneck in a
function and nothing in the source could account for it. Examining the
generated assembly I found the thing was thrashing around with a
string of mov hl,hl; mov bc,hl; mov hl,bc; mov hl,hl; opcodes. Thirty
minutes on the phone with the maintenance programmer yielded
indication of a bug in the compiler. Fixed in another hour, emailed a
new release of the compiler. It's hard to do that these days.

[toc] | [prev] | [next] | [standalone]

#15141

"BartC" <bc@freeuk.com> writes:
> "Ben Bacarisse" <ben.usenet@bsb.me.uk> wrote in message
> news:0.393ac02b1554cc6fda1d.20111224025213GMT.87ehvuk7fm.fsf@bsb.me.uk...
> > "BartC" <bc@freeuk.com> writes:
> 
> > Well, it's not bad that you can beat 2 of the three compilers.
> 
> I've tried one more compiler, and the results, now normalised and for
> the fastest code (and using N=2500 for more accuracy), are:
> 
> gcc -O3      1.00  (using inlining)
> My asm       1.12  (original without inlining or unrolling)
> Pelles C -Ot 1.26
> DMC -o       1.35
> lcc-win32 -O 1.64
> 
> (Adjusted for loop overheads)
> 
> So while modern compilers might be ultra-sophisticated, most of these
> aren't! Admittedly they are all free downloads..

If you're running on an intel arch, you should at least try intel's icc 
too. I've practically never known gcc to beat icc.

Phil
-- 
Unix is simple. It just takes a genius to understand its simplicity
-- Dennis Ritchie (1941-2011), Unix Co-Creator

[toc] | [prev] | [next] | [standalone]

#15149

Phil Carmody wrote:

> If you're running on an intel arch, you should at least try intel's icc
> too. I've practically never known gcc to beat icc.

I suspect that gcc would beat icc if the code is compiled and executed on an 
AMD system.

http://developer.amd.com/documentation/articles/pages/4292005119.aspx


Rui Maciel

[toc] | [prev] | [next] | [standalone]

#14937

In article <0.d0ecd8f477637819bed2.20111223184332GMT.87pqffjfhn.fsf@bsb.me.uk>,
Ben Bacarisse  <ben.usenet@bsb.me.uk> wrote:
>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.

It's not.

If you can get your 0.01% of your code (and You're suRE it is really
that) that it gets 40% faster then it may be a useful thing to do.

[although when <chip manufacturer> comes out with a new chip you may
have actually made it *worse*]

[toc] | [prev] | [next] | [standalone]

#14940

"Ben Bacarisse" <ben.usenet@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 <dihedral88888@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

; return  -10 error, 0 not find, address of the found element in array
; would be like the C one, with the only difference return -10 for error
;u8*  __stdcall
;binSearchR(u8* InOutPKey, u8* InBase,
;           u32 nElmBase,  u32 SizeElmBase, i32  cmp(u8* elm1, u8*  elm2) );
; 0k, 4k, 8j, 12i, 16b, 20ra, 24InOutKey, 28InBase,  32P_nElmBase,
36P_SizeElmBase, 40P_cmp
binSearchR:
          push    ebx
          push    esi
          push    edi
          push    ebp
          push    ebp
;int3
          cmp     dword[esp+  24],  0
          je      .e
          cmp     dword[esp+  28],  0
          je      .e
          cmp     dword[esp+  36],  0
          jle     .e
          cmp     dword[esp+  40],  0
          je      .e
          cmp     dword[esp+  32],  0
          je      .nf
          jl      .e
          jmp     short  .1
.nf:      mov     eax,  0
          clc
          jmp     short  .z
.e:       mov     eax,  -10
          stc
          jmp     short  .z
.1:       mov     esi,  0
          mov     edi,  dword[esp+  32]
          dec     edi
          mov     ebx,  dword[esp+  40]
.2:       cmp     esi,  edi
          jg      .nf
          mov     ebp,  esi
          add     ebp,  edi
          jc      .e
          shr     ebp,  1       ; k=(i+j)/2
          mov     eax,  dword[esp+  36]
          mul     ebp
          cmp     edx,  0
          jne     .e
          mov     edx,  dword[esp+  24]
          add     eax,  dword[esp+  28]
          jc      .e
          mov     dword[esp+  0],  eax
          push    edx
          push    eax
          call    ebx
          add     esp,  8
          cmp     eax,  0
          jle     .3
          mov     edi,  ebp
          sub     edi,  1
          jmp     short  .2
.3:       jz      .4
          mov     esi,  ebp
          add     esi,  1
          jmp     short  .2
.4:       mov     eax,  dword[esp+  0]
          clc
.z:
          pop     ebp
          pop     ebp
          pop     edi
          pop     esi
          pop     ebx
          ret     20
------------------
PREPARSE MACRO2D

section DATA

hInstance   dd   0

;                9
arrayInt    dd   0,2,4,5,8,8,9,10, 11

export      binSearchR

section TEXT


; return  -10 error, 0 not find, address of the found element in array
; would be like the C one, with the only difference return -10 for error
;u8*  __stdcall
;binSearchR(u8* InOutPKey, u8* InBase,
;           u32 nElmBase,  u32 SizeElmBase, i32  cmp(u8* elm1, u8*  elm2) );
; 0k,4k,8j,12i,16b,20ra, 24InOutKey,28InBase,32P_nElmBase,36P_SizeElmBase,
; 40P_cmp
binSearchR:
<b,i,j,k,k
     ;int3
     ^24==0#.e|^28==0#.e |^36<=0?#.e
     ^40==0#.e|^32==0#.nf|<?#.e|#.1
.nf: a=0  |clc|#.z
.e:  a=-10|stc|#.z
.1:  i=0 |j=^32|--j|b=^40
.2:  i>j?#.nf
     k=i |k+=j  |jc .e  |k>>=1     ; k=(i+j)/2
     a=^36|mul k|r!=0#.e|r=^24|a+=^28|jc .e|^0=a
     b<(a,r)|a>0!?#.3|j=k|j-=1|#.2
.3:              =#.4|i=k|i+=1|#.2
.4:  a=^0|clc
.z:
>b,i,j,k,k
ret 20

Main:
    mov eax D$esp+8
    mov D$hInstance eax
    mov eax 1
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
// const, how is smart...
#define cn  const

u8*  __stdcall
binSearchR(u8* InOutPKey,    u8* InBase, u32 nElmBase, u32 SizeElmBase,
                                        i32  cmp(cn u8* elm1, cn u8*  elm2) );

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[]={0, 2, 5, 7, 8, 8, 9, 13, 20},  val=13;
 u8  *r;

 r=binSearchR((u8*)&val, (u8*)  v, 9, sizeof(u32), cmpu32s);
 if(r!=0) P("r=%p find=%u\n", (void*)r, *r);

 r=bsearch(&val, v, 9, sizeof(u32), cmpu32s);
 if(r!=0) P("r=%p find=%u\n", (void*)r, *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);
       printf("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=%f\n", (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("  bsearch=%f\n", (double) d=difftime(fin, in));
       printf("sum=%ld\n", sum);
       return  0;
      }
 }
 return  0;
}
__________________________
> prog  1000
r=0012FF3C find=13
r=0012FF3C find=13
r=00000000
myBsearch=11.000000
sum=1373176982
  bsearch=9.000000
sum=1373176982
__________________________

[toc] | [prev] | [next] | [standalone]

#14950

"io_x" <a@b.c.invalid> ha scritto nel messaggio
news:4ef565dc$0$1388$4fafbaef@reader2.news.tin.it...

this seems a little more slow than C library bsearch() function one

; return  -1 error, 0 not find, address of the found element in array
; would be like the C one, with the only difference return -1 for error
;u8*  __stdcall
;binSearchR(u8* InOutPKey, u8* InBase,
;           u32 nElmBase,  u32 SizeElmBase, i32  cmp(u8* elm1, u8*  elm2) );
; 0k, 4k, 8j, 12i, 16b, 20ra, 24InOutKey, 28InBase,  32P_nElmBase,
36P_SizeElmBase, 40P_cmp
binSearchR:
          push    ebx
          push    esi
          push    edi
          push    ebp
          push    ebp
;int3
          cmp     dword[esp+  24],  0
          je      .e
          cmp     dword[esp+  28],  0
          je      .e
          mov     edi,  dword[esp+  32]
          mov     ebx,  dword[esp+  40]
          cmp     dword[esp+  36],  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
          mov     eax,  dword[esp+  36]
          add     ebp,  edi
          shr     ebp,  1       ; k=(i+j)/2
          mul     ebp
          cmp     edx,  0
          jne     .e
          add     eax,  dword[esp+  28]
          mov     ecx,  dword[esp+  24]
          mov     dword[esp+  0],  eax
          jc      .e
          push    ecx
          push    eax
          call    ebx
          add     esp,  8
          cmp     eax,  0
          jle     .3
          dec     ebp
          mov     edi,  ebp
          jmp     short  .2
.3:       jz      .4
          inc     ebp
          mov     esi,  ebp
          jmp     short  .2
.4:       mov     eax,  dword[esp+  0]
          clc
.z:
          pop     ebp
          pop     ebp
          pop     edi
          pop     esi
          pop     ebx
          ret     20
-------------------
; return  -1 error, 0 not find, address of the found element in array
; would be like the C one, with the only difference return -1 for error
;u8*  __stdcall
;binSearchR(u8* InOutPKey, u8* InBase,
;           u32 nElmBase,  u32 SizeElmBase, i32  cmp(u8* elm1, u8*  elm2) );
; 0k, 4k, 8j, 12i, 16b, 20ra, 24InOutKey, 28InBase,  32P_nElmBase,
36P_SizeElmBase, 40P_cmp
binSearchR:
<b,i,j,k,k
     ;int3
     ^24==0#.e|^28==0#.e|j=^32  | b=^40 |^36<=0?#.e
     j==0#.nf |i=0|<?#.e|b==0#.e|--j|#.2
.nf: a^=a    |clc|#.z
.e:  a^=a|--a|stc|#.z
.2:  i>j?#.nf|k=i|a=^36|k+=j |k>>=1        ; k=(i+j)/2
     mul k|r#.e|a+=^28 |c=^24|^0=a|jc .e
     b<(a,c) |a>0!?#.3|--k|j=k|#.2
.3:               =#.4|++k|i=k|#.2
.4:  a=^0|clc
.z:
>b,i,j,k,k
ret 20
------------------------
C:>ba 100
r=0012FF3C find=13
r=0012FF3C find=13
r=00000000
myBsearch=0.000000
sum=460116
  bsearch=0.000000
sum=460116

C:>ba 1000
r=0012FF3C find=13
r=0012FF3C find=13
r=00000000
myBsearch=2.000000
sum=650808558
  bsearch=2.000000
sum=650808558

C:>ba 1500
r=0012FF3C find=13
r=0012FF3C find=13
r=00000000
myBsearch=5.000000
sum=-1984601096
  bsearch=5.000000
sum=-1984601096

C:>ba 2000
r=0012FF3C find=13
r=0012FF3C find=13
r=00000000
myBsearch=10.000000
sum=1373176982
  bsearch=9.000000
sum=1373176982

[toc] | [prev] | [next] | [standalone]

#15000

"io_x" <a@b.c.invalid> ha scritto nel messaggio
news:4ef565dc$0$1388$4fafbaef@reader2.news.tin.it...
>
> "Ben Bacarisse" <ben.usenet@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 <dihedral88888@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
          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
-------------- 

[toc] | [prev] | [next] | [standalone]

#15004

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
> --------------

[toc] | [prev] | [next] | [standalone]

#15017

"88888 Dihedral" <dihedral88888@googlemail.com> ha scritto nel messaggio 
news:16367787.1074.1324929127614.JavaMail.geo-discussion-forums@pruu23...
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 ?

#io_x
#i use the __stdcall, the one clear the stack at end the routine
#with retxx  e.g. here ret20 [4*5=20]
#for push and pop: i push and pop all registers ABI says i can not change
#out of this routine.
#
#someone can think about cmp function
#that is out my controll, can change all register but
#not the ones ABI say are not changable.
#
#in few word i don't like other way to do it e.g. use pushad
#or C calling convention except for printf like functions

>           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

[toc] | [prev] | [next] | [standalone]

#14956

Ben Bacarisse wrote:
) I'm starting a new thread, but it is prompted by this remark from 88888
) Dihedral <dihedral88888@googlemail.com> about a short binary search
) function I posted:
)
) <snip>
) On my laptop[1], gcc's optimiser (version 4.6.1) almost exactly halves the
) times.  clang's code is a little better at -O0, but the optimised code
) is a little worse:
)                  -O0     -O1     -O2     -O3
)   gcc         0.1128  0.0633  0.0571  0.0562
)   g++         0.1167  0.0633  0.0572  0.0564
)   clang       0.1033  0.0669  0.0672  0.0672
)
) These times are microseconds per call.  The loop overhead has been
) subtracted[2].

Have you tried enabling the processor-specific switches on gcc?

) [1] Intel(R) Core(TM)2 Duo CPU P8700 @ 2.53GHz, 3MB cache
) [2] Crude timing script available on request.

SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

[toc] | [prev] | [next] | [standalone]

#14957

On Saturday, December 24, 2011 8:48:05 PM UTC+8, Willem wrote:
> Ben Bacarisse wrote:
> ) 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:
> )
> ) <snip>
> ) On my laptop[1], gcc's optimiser (version 4.6.1) almost exactly halves the
> ) times.  clang's code is a little better at -O0, but the optimised code
> ) is a little worse:
> )                  -O0     -O1     -O2     -O3
> )   gcc         0.1128  0.0633  0.0571  0.0562
> )   g++         0.1167  0.0633  0.0572  0.0564
> )   clang       0.1033  0.0669  0.0672  0.0672
> )
> ) These times are microseconds per call.  The loop overhead has been
> ) subtracted[2].
> 
> Have you tried enabling the processor-specific switches on gcc?
> 
> ) [1] Intel(R) Core(TM)2 Duo CPU P8700 @ 2.53GHz, 3MB cache
> ) [2] Crude timing script available on request.
> 
> SaSW, Willem
> -- 
> Disclaimer: I am in no way responsible for any of the statements
>             made in the above text. For all I know I might be
>             drugged or something..
>             No I'm not paranoid. You all think I'm paranoid, don't you !
> #EOT

I think pass by register is faster. 
But if just  insert 10 to 20  lines of assembly can  make the code
to be faster. I'll go for assembly to eliminate the function call 
overheads. 

By the way swapping two registers  with or without a tmp register 
in 3 instructions is really hardware dependent. 
 

 
 

[toc] | [prev] | [next] | [standalone]

#14982

Willem <willem@toad.stack.nl> writes:

> Ben Bacarisse wrote:
> ) I'm starting a new thread, but it is prompted by this remark from 88888
> ) Dihedral <dihedral88888@googlemail.com> about a short binary search
> ) function I posted:
> )
> ) <snip>
> ) On my laptop[1], gcc's optimiser (version 4.6.1) almost exactly halves the
> ) times.  clang's code is a little better at -O0, but the optimised code
> ) is a little worse:
> )                  -O0     -O1     -O2     -O3
> )   gcc         0.1128  0.0633  0.0571  0.0562
> )   g++         0.1167  0.0633  0.0572  0.0564
> )   clang       0.1033  0.0669  0.0672  0.0672
> )
> ) These times are microseconds per call.  The loop overhead has been
> ) subtracted[2].
>
> Have you tried enabling the processor-specific switches on gcc?

As per Jens's post, I just tried -march=native and got:

                        -O0     -O1     -O2     -O3
  gcc                0.1127  0.0633  0.0571  0.0563
  gcc -march=native  0.1124  0.0633  0.0567  0.0561

The tiny improvement in the -O2 and -O3 times is repeatable, but the -O0
time varies by two or three in the last digits anyway.  It's not a
significant improvement on this processor.

> ) [1] Intel(R) Core(TM)2 Duo CPU P8700 @ 2.53GHz, 3MB cache

I can't at the moment test the AMD chip.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#14961

On Dec 23, 6:43 pm, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:

...

I don't understand some of your code. Queries below.

> Here is a test program:
>
> #include <stdio.h>
> #include <stdlib.h>
>
> size_t binsearch(int a[], size_t length, int key)

Why use size_t instead of unsigned int or unsigned long int,
especially as you add it to sum in the test harness which is long int?
Why not use unsigned for sum in the test harness?

> {
>      size_t low = 0, high = length;

Why not high = length - 1?

>      while (high > low) {
>           size_t middle = low + (high - low)/2;

Why not middle = (high + low) / 2?

>           if (key == a[middle])
>                return middle;
>           else if (key > a[middle])
>                low = middle + 1;
>           else high = middle;

Why not high = middle - 1?

>      }
>      return -1;
>
> }

The reason for the queries is I wrote an asm binsearch but when
comparing it with your code realised that you had some differences in
the approach.

James

[toc] | [prev] | [next] | [standalone]

#14965

"James Harris" <james.harris.1@googlemail.com> wrote in message 
news:aa4803f2-e4f3-4bae-8f4e-6134ed6c78da@p16g2000yqd.googlegroups.com...
> On Dec 23, 6:43 pm, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:

>>      while (high > low) {
>>           size_t middle = low + (high - low)/2;
>
> Why not middle = (high + low) / 2?

That form can cause an overflow when the numbers are high. Otherwise 
(high+low)/2 is marginally faster.

-- 
Bartc  

[toc] | [prev] | [next] | [standalone]

#15096

On Dec 24, 2:55 pm, "BartC" <b...@freeuk.com> wrote:

...

> >>           size_t middle = low + (high - low)/2;
>
> > Why not middle = (high + low) / 2?
>
> That form can cause an overflow when the numbers are high. Otherwise
> (high+low)/2 is marginally faster.

Understood, thanks. There's an interesting point here. The
straightforward code to implement that expression might be

  mov rmid, rhigh
  sub rmid, rlow
  shr rmid, 1
  add rmid, rlow

but that could be improved to

  mov rmid, rlow
  add rmid, rhigh
  rcr rmid, 1

because rcr will bring back in that 'lost' carry bit and IIRC rcr by
one bit is generally as fast as shifts and the rotates which don't
include the carry. (Rotates including the carry are not so fast if
multiple bit positions are moved at the same time.)

In the case in point since the top bits will not be set it can be
improved to

  lea rmid, [rlow + rhigh]
  shr rmid, 1

on most CPUs. The Intel Atom is the only one I am aware of for which
this would be slowed down by a stall if either rlow or rhigh were
generated just before the lea instruction. For the Atom, I think the
code above including rcr might be best (or rcr could be replaced by
shr).

James

[toc] | [prev] | [next] | [standalone]

#15106

James Harris於 2011年12月28日星期三UTC+8下午7時46分21秒寫道：
> On Dec 24, 2:55 pm, "BartC" <b....@freeuk.com> wrote:
> 
> ...
> 
> > >>           size_t middle = low + (high - low)/2;
> >
> > > Why not middle = (high + low) / 2?
> >
> > That form can cause an overflow when the numbers are high. Otherwise
> > (high+low)/2 is marginally faster.
> 
> Understood, thanks. There's an interesting point here. The
> straightforward code to implement that expression might be
> 
>   mov rmid, rhigh
>   sub rmid, rlow
>   shr rmid, 1
>   add rmid, rlow

EDX is still free. Thus one still can experiment to use 6 registers.




> but that could be improved to
> 
>   mov rmid, rlow
>   add rmid, rhigh
>   rcr rmid, 1
> 
> because rcr will bring back in that 'lost' carry bit and IIRC rcr by
> one bit is generally as fast as shifts and the rotates which don't
> include the carry. (Rotates including the carry are not so fast if
> multiple bit positions are moved at the same time.)
> 
> In the case in point since the top bits will not be set it can be
> improved to
> 
>   lea rmid, [rlow + rhigh]
>   shr rmid, 1
> 
> on most CPUs. The Intel Atom is the only one I am aware of for which
> this would be slowed down by a stall if either rlow or rhigh were
> generated just before the lea instruction. For the Atom, I think the
> code above including rcr might be best (or rcr could be replaced by
> shr).
> 
> James

[toc] | [prev] | [next] | [standalone]

#14983

James Harris <james.harris.1@googlemail.com> writes:

> On Dec 23, 6:43 pm, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
>
> ...
>
> I don't understand some of your code. Queries below.
>
>> Here is a test program:
>>
>> #include <stdio.h>
>> #include <stdlib.h>
>>
>> size_t binsearch(int a[], size_t length, int key)
>
> Why use size_t instead of unsigned int or unsigned long int,
> especially as you add it to sum in the test harness which is long int?
> Why not use unsigned for sum in the test harness?

int is better yet because the output will then be same across machines.
Using *any* unsigned type means the "not found" -1 return becomes a
value that can vary from implementation to implementation.  For this
test code I should have used int, but size_t is the "right" return type
for a binary search function like this and I did not think to change it.

>> {
>>      size_t low = 0, high = length;
>
> Why not high = length - 1? 

Explained below.

>>      while (high > low) {
>>           size_t middle = low + (high - low)/2;
>
> Why not middle = (high + low) / 2?

To avoid "overflow".  (Quotes because it's wrap-around with unsigned
types but it's still wrong.)  You'd need peculiar input to see this
in practise but it seems nicer to avoid the issue altogether.
 
>>           if (key == a[middle])
>>                return middle;
>>           else if (key > a[middle])
>>                low = middle + 1;
>>           else high = middle;
>
> Why not high = middle - 1?

Unsigned types, basically.  The symmetric version that adds or subtracts
one from middle always keeps the target index in [low..high].  That
means high must start at length - 1 which is annoying for unsigned types
like size_t (because length == 0 becomes a special case).  I keep the
target index in [low..high) (i.e. a half open interval) so high is set
to length at the start and to middle when the range is being cut to
lower portion.

There are lots of ways round this, but I think they all complicate an
otherwise algorithm.  Perhaps the simplest is just to test length first
and return -1 if it's 0 before doing any real work.  Maybe you have a
favourite method that can use size_t bounds?

>>      }
>>      return -1;
>>
>> }
>
> The reason for the queries is I wrote an asm binsearch but when
> comparing it with your code realised that you had some differences in
> the approach.

Obviously there's no need to copy the approach in the body of the
function, but I'd say you should copy the prototype (at least at first).
If it turn out that you can get 20% better performance with asm that
uses different argument and/or return types, then that's an interesting
fact and should not be ignored just because I used size_t.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#15091

On Dec 25, 12:07 am, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> James Harris <james.harri...@googlemail.com> writes:
> > On Dec 23, 6:43 pm, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:

...

> >> size_t binsearch(int a[], size_t length, int key)
>
> > Why use size_t instead of unsigned int or unsigned long int,
> > especially as you add it to sum in the test harness which is long int?
> > Why not use unsigned for sum in the test harness?
>
> int is better yet because the output will then be same across machines.
> Using *any* unsigned type means the "not found" -1 return becomes a
> value that can vary from implementation to implementation.

You mean -1 may have a strange value on a 1s-complement machine? On a
2s-complement machine wouldn't it always be all bits set even if
assigned to an unsigned variable?

>  For this
> test code I should have used int, but size_t is the "right" return type
> for a binary search function like this and I did not think to change it.

The thing is, when you add it to sum in the main routine if sum
(defined as long int) was the same width as size_t the calculation
would, AFAICS, be correct. But say size_t was unsigned 32-bit and long
int was signed 64-bit. Wouldn't that add 4 billion and odds rather
than subtract one?

...

> >>      while (high > low) {
> >>           size_t middle = low + (high - low)/2;
>
> > Why not middle = (high + low) / 2?
>
> To avoid "overflow".  (Quotes because it's wrap-around with unsigned
> types but it's still wrong.)  You'd need peculiar input to see this
> in practise but it seems nicer to avoid the issue altogether.

Understood. When I came to code this in 32-bit assembler I realised
that, since high and low can never have their top bits set, the simple
form would do. In general it seems that as long as they index multi-
byte quantities the sum cannot overflow.

It's a non-issue, though. In case anyone is interested, gcc -O3 seems
to have realised this and generated the shorter code.

...

> > Why not high = middle - 1?
>
> Unsigned types, basically.  The symmetric version that adds or subtracts
> one from middle always keeps the target index in [low..high].  That
> means high must start at length - 1 which is annoying for unsigned types
> like size_t (because length == 0 becomes a special case).  I keep the
> target index in [low..high) (i.e. a half open interval) so high is set
> to length at the start and to middle when the range is being cut to
> lower portion.
>
> There are lots of ways round this, but I think they all complicate an
> otherwise algorithm.  Perhaps the simplest is just to test length first
> and return -1 if it's 0 before doing any real work.  Maybe you have a
> favourite method that can use size_t bounds?

No, no favourite method. Now I understand your approach I can see why
you do it that way.

...

> Obviously there's no need to copy the approach in the body of the
> function, but I'd say you should copy the prototype (at least at first).
> If it turn out that you can get 20% better performance with asm that
> uses different argument and/or return types, then that's an interesting
> fact and should not be ignored just because I used size_t.

Timings vary on the machine I used possibly because it has other tasks
but taking an average by eye my best asm version was *slower* than
that that produced by gcc -O3. How much? It's hard to be accurate but
I would say there's an average of about 5% to 10% difference.

I puzzled over this for a while. My initial asm code had been almost
the same as the code that Bart posted earlier. (BTW, to make the test
fair I compiled binsearch_test and binsearch.c or binsearch.nasm
separately.) The thing is, it was all what I would call "good" code:
efficiently laid out, using the right type of instructions. So why was
gcc's code quicker? In the end I even compared the asm output from the
compiler but couldn't see why it was quicker.

Finally I took gcc's asm output and assembled it. It ran as fast as
the version produced directly by the compiler which verified the test
was valid. Then I realised that the gcc code does not save ecx and
edx. (Part of the calling convention, I believe.) I had been
concentrating on the body of the code. To my surprise, adding a save
of both or either register brought the gcc code to about the same
speed as the asm.

So is it possible that this is heavily influenced by calling overhead
or is this a code alignment issue or is there some other cause? I
don't know.

I wanted to spend some time on this in part to get familiar with
calling between asm and gcc (for which, if anyone else is interested
I've copied below a useful link that I found) but the rest will have
to remain a mystery for now. The bottom line, for me, is that, at
least for this test case, the code generated by gcc -O3 is very good
indeed. Looking at its asm output I can see both a number of standard
compiler optimisations and that it has recognised a number of
potential issues and dealt with them very well.

At least I now have two-way calling working between Nasm and C - and a
new respect for gcc!

  http://www.cs.lmu.edu/~ray/notes/nasmexamples/

James

[toc] | [prev] | [next] | [standalone]

Page 2 of 6 — ← Prev page 1 [2] 3 4 5 6  Next page →

Back to top | Article view | comp.lang.c

csiph-web