www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 10675] New: [Optimizer] optimize x >= a && x <= b and such to one comparison

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

           Summary: [Optimizer] optimize x >= a && x <= b and such to one
                    comparison
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: DMD
        AssignedTo: nobody puremagic.com
        ReportedBy: dmitry.olsh gmail.com


--- Comment #0 from Dmitry Olshansky <dmitry.olsh gmail.com> 2013-07-19
13:20:16 PDT ---
Currently DMD doesn't optimize interval-style conditions unlike GDC & LDC:

x >= a && x <= b

--->

//val size has to be big enough for the entire range of [0, b]
unsigned val =  x - a; 
val <= b - a

The are multitude of alternatives of the above including if/else if chains
and/or seuqnce of ifs with early return like:
if(x < a)
   return false;
if(x <= b
   return true;
return false;
See current (soon to be replaced) std.uni:
https://github.com/D-Programming-Language/phobos/blob/master/std/uni.d#L563

Typical use-case are ASCII isAlpha/isDigit etc. functions heavily used in
various lexers/scanners.

See little "benchmark". Timings are dominated by loop overhead and memory
access but a significant difference is observable non the less.

import std.file;
import std.stdio, std.datetime;

//let compiler optimize if/else
size_t process1(void[] buf)
{
    size_t cnt = 0;
    foreach(i; 0..100)
    foreach(c; cast(ubyte[])buf)
    {
        if(c < 0xAA)
        {
            if(c < 'A')
            {

            }
            else if(c <= 'Z')
                cnt++;
            else if(c < 'a')
            {

            }
            else if(c <= 'z')
                cnt++;            
        }
    } 
    return cnt;   
}

//do our job by hand
size_t process2(void[] buf)
{
    size_t cnt = 0;
    foreach(i; 0..100)
    foreach(c; cast(ubyte[])buf)
    {
        if(c < 0xAA)
        {
            //these x and y should be the smallest unsigned type to fit the
range
            size_t x = c - 'A'; 
            if(x <= 'Z'-'A')
                cnt++;
            else{
                size_t y = c - 'a';
                if(y <= 'z' - 'a')
                    cnt++;
            }
        }
    } 
    return cnt;   
}

void main(string argv[])
{
    foreach(v; argv[1..$]){
        StopWatch sw;
        sw.start();
        version(compiler){
            auto count = process1(read(v));
        }
        else version(manual)
            auto count = process2(read(v));
        else
            static assert(0);
        sw.stop();        
        writefln("%s %s ASCII alphabetic. [%d us]", v, count, sw.peek().usecs);
    }
}

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



--- Comment #1 from Dmitry Olshansky <dmitry.olsh gmail.com> 2013-07-19
13:22:00 PDT ---
Created an attachment (id=1236)
Disassembly of test case

Disassembly of 2 critical if-chainy functions.

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



--- Comment #2 from Dmitry Olshansky <dmitry.olsh gmail.com> 2013-07-19
13:23:23 PDT ---
Aye, and compiler flags used.

First version:
dmd -release -O -inline -noboundscheck -version=compiler if_else_opt.d

Optimized by hand version:
dmd -release -O -inline -noboundscheck -version=manual if_else_opt.d

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