Opened 10 months ago

Last modified 9 months ago

#226 new defect

Resolver is slow at finding constructors for 3+ dimensional arrays

Reported by: mlbrooks Owned by:
Priority: major Component: cfa-cc
Version: 1.0 Keywords:
Cc:

Description

This bug describes a simplification of a case that challenges new multidimensional array work, while doing bread-and-butter operations on short lists of dimensions.

#ifndef N
#define N 3
#endif

struct nil {};

forall( otype L | sized(L),
        otype R | sized(R) )
struct cons { L l; R r; };

#ifdef NOCTOR
#define XINIT @={}
#else
#define XINIT
#endif

int main() {
  #if   N==0
                                                                          nil           x XINIT;
  #elif N==1
                                                            cons( size_t, nil )         x XINIT;
  #elif N==2
                                              cons( size_t, cons( size_t, nil ) )       x XINIT;
  #elif N==3
                                cons( size_t, cons( size_t, cons( size_t, nil ) ) )     x XINIT;
  #elif N==4
                  cons( size_t, cons( size_t, cons( size_t, cons( size_t, nil ) ) ) )   x XINIT;
  #elif N==5
    cons( size_t, cons( size_t, cons( size_t, cons( size_t, cons( size_t, nil ) ) ) ) ) x XINIT;
  #else
    #error unsupported N
  #endif
}

Actual performance (seconds)

N   ctor   no-ctor
0     3.0  3.1
1     3.2  3.0
2     4.0  3.2
3    12    3.1
4   128    3.1
5   (err)  3.1

Target performance suggestion: under 10 sec for up to N=6

Change History (1)

comment:1 Changed 9 months ago by f37yu

Partially improved performance by reducing resolver environment size to O(N). Previously was O(4N).

Note 1: generated code size is also O(4N) due to thunk functions not being reused in otype assertions. This implies a heavy runtime penalty as too many local functions are created.
Currently generated code size is 2MB with N=5 and 8MB with N=6.
Caching is required to improve code generation.

Note 2: the exponential base of 4 comes from the "big 4" otype assertions (default ctor, copy ctor, dtor and assignment)

Last edited 9 months ago by f37yu (previous) (diff)
Note: See TracTickets for help on using tickets.