• d-bugmail puremagic.com (49/49) Apr 17 2012 http://d.puremagic.com/issues/show_bug.cgi?id=7934

d-bugmail puremagic.com writes:

http://d.puremagic.com/issues/show_bug.cgi?id=7934

           Summary: std.algorithm.sum and std.algorithm.reduce for fixed
                    size arrays too
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: bearophile_hugs eml.cc



This is a second part of Issue 4725


The D type system supports both dynamic arrays and fixed-sized arrays. Despite
Phobos regards fixed-sized arrays as second-class citizens of the language,
they are quite important and useful in high-performance code, because they
reduce the pressure on the garbage collector and allow for some extra
optimizations.

An example: their length is known at compile time, so if such length is small,
the compiler finds it simple to unroll loops. In scientific code loop unrolling
is very important. Sometimes the JavaHotSpot is able to beat C++ in Scientific
code on loops with bounds that aren't known at compile-time because the
Just-in-time compiler is able to see that an array length known only at
run-time is indeed constant for this run, so it's able to partially unroll the
loop. I have verified this beats all C++ compilers in some number-crunching
code.

A JIT is not needed with fixed-sized D arrays. Throwing away the length known
at compile-time to turn them into dynamic arrays to make them ranges, is a
waste of optimization opportunities.

If I see code:

int[5] a = foo();
auto s = sum(a);

I'd like that sum() to be replaced by an inlined unrolled loop, if the input
array length is known at compile-time, and it's small.

(I think it's not hard to do. The test on the length is easy to do with a
template constraint plus a compile-time function that essentially generates a
"a[0] + a[1] + a[2] + a[3] + a[4]" mixin).

I'd like a specialization of std.algorithm.reduce too for small fixed-sized
arrays.


Both sum and reduce call their normal dynamic array versions (slicing the input
with []) if the fixed size inout array is long enough (like more than 8 or 16
items), because a full loop unroll is not good in this case (still, even in
this case the back-end of the compiler will enjoy to know the array size at
compile-time).

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