www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 9963] New: Absurdly Inefficient Codegen For Adding Boolean Predicates

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9963

           Summary: Absurdly Inefficient Codegen For Adding Boolean
                    Predicates
           Product: D
           Version: D1 & D2
          Platform: All
        OS/Version: All
            Status: NEW
          Keywords: performance
          Severity: normal
          Priority: P2
         Component: DMD
        AssignedTo: nobody puremagic.com
        ReportedBy: dsimcha yahoo.com



D source Code:

__gshared ulong n_less = 0, n_greater = 0;

void doConditional(ubyte thresh, ubyte[] arr) {
  ulong l, g;
  foreach(val; arr) {
    l += (thresh < val);
    g += !(thresh < val);
  }

  n_less += l;
  n_greater += g;
}

DMD-generated ASM code (foreach loop only, from obj2asm, when compiled with -O
-inline -release):

L33:        mov    RDX,-018h[RBP]
        mov    CL,[RDX][R8]
        cmp    CL,R9B
        mov    EAX,1
        ja    L47
        xor    EAX,EAX
L47:        cdqe
        add    R11,RAX
        cmp    R9B,CL
        sbb    EAX,EAX
        inc    EAX
        cdqe
        add    RBX,RAX
        inc    R8
        cmp    R8,-010h[RBP]
        jb    L33

Why use sbb + neg + two cmp instructions instead of just using setb and setae? 
This executes in about 0.495 seconds for an array of 100 million elements.

GCC's codegen for the same function:

L20:        movzx    ECX,[RAX][RDX]
        xor    R10D,R10D
        cmp    ECX,EDI
        setnle    R10B
        add    R9,R10
        cmp    ECX,EDI
        setle    CL
        add    RAX,1
        movzx    ECX,CL
        add    R8,RCX
        cmp    RAX,RSI
        jne    L20

This executes in about 0.095 seconds for an array of 100 million elements.

My hand-compilation for this loop:

   LStart:
    cmp DL, byte ptr [RAX];
    setae R9B;
    adc R10, 0;
    inc RAX;
    add R11, R9;
    cmp RAX, RBX;
    jb LStart;

This executes in about 0.071 seconds for an array of 100 million elements.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Apr 19 2013
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9963


Walter Bright <bugzilla digitalmars.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bugzilla digitalmars.com



02:35:53 PDT ---
A partial fix:

https://github.com/D-Programming-Language/dmd/pull/1917

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Apr 21 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9963




16:05:32 PDT ---
https://github.com/D-Programming-Language/dmd/pull/1921

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Apr 22 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9963




02:58:24 PDT ---
And this should finish it:

https://github.com/D-Programming-Language/dmd/pull/1924

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Apr 23 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9963




03:03:07 PDT ---
Which brings the inner loop to:

L2C:            mov     RBX,-8[RBP]
                mov     CL,[RBX][R8]
                cmp     CL,R9B
                setnbe  DIL
                movzx   EDI,DIL
                add     R11,RDI
                cmp     R9B,CL
                sbb     RSI,0FFFFFFFFh
                inc     R8
                cmp     R8,-010h[RBP]
                jb      L2C

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Apr 23 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9963




00:08:26 PDT ---
https://github.com/D-Programming-Language/dmd/pull/1928

brings the code generated to:

L2B:            mov     RBX,-8[RBP]
                mov     CL,[RBX][R8]
                cmp     R9B,CL
                adc     R11,0
                cmp     R9B,CL
                sbb     RSI,0FFFFFFFFh
                inc     R8
                cmp     R8,-010h[RBP]
                jb      L2B

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Apr 24 2013
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9963


Walter Bright <bugzilla digitalmars.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED
           Severity|normal                      |enhancement


-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Apr 26 2013