array_constructor is slow

[mbasmanova]

Description

array_constructor is very slow: #5958 (comment)

array_constructor uses BaseVector::copyRanges, but this is very slow for flat vectors:

  void copyRanges(
      const BaseVector* source,
      const folly::Range<const BaseVector::CopyRange*>& ranges) override {
    for (auto& range : ranges) {
      copy(source, range.targetIndex, range.sourceIndex, range.count);
    }
  }

FlatVector::copy(source, rows, toSourceRow) is faster.

Switching from copyRanges to copy speeds up array_constructor for primitive types and structs significantly. Yet, this change makes arrays and maps slower.

The slowness is due to ArrayVector and MapVector not having implementation for copy(source, rows, toSourceRow). They rely on BaseVector::copy to translate rows + toSourceRow to ranges. This extra processing causes perf regression.

Questions:

• Should we optimize FlatVector::copyRanges by implementing a version of copyValuesAndNulls for ranges?
• Should we optimize Array/MapVector::copy(source, rows, toSourceRow)
• Should we do both?
• Any other solution?

Before:

array_constructor_ARRAY_nullfree##1                        16.80ms     59.53
array_constructor_ARRAY_nullfree##2                        27.02ms     37.01
array_constructor_ARRAY_nullfree##3                        38.03ms     26.30
array_constructor_ARRAY_nullfree##2_null                   52.86ms     18.92
array_constructor_ARRAY_nullfree##2_const                  54.97ms     18.19
array_constructor_ARRAY_nulls##1                           30.61ms     32.66
array_constructor_ARRAY_nulls##2                           55.01ms     18.18
array_constructor_ARRAY_nulls##3                           80.69ms     12.39
array_constructor_ARRAY_nulls##2_null                      69.10ms     14.47
array_constructor_ARRAY_nulls##2_const                    103.85ms      9.63


After:

array_constructor_ARRAY_nullfree##1                        18.06ms     55.37
array_constructor_ARRAY_nullfree##2                        40.40ms     24.75
array_constructor_ARRAY_nullfree##3                        58.71ms     17.03
array_constructor_ARRAY_nullfree##2_null                   77.86ms     12.84
array_constructor_ARRAY_nullfree##2_const                  70.42ms     14.20
array_constructor_ARRAY_nulls##1                           31.06ms     32.20
array_constructor_ARRAY_nulls##2                           62.26ms     16.06
array_constructor_ARRAY_nulls##3                           98.91ms     10.11
array_constructor_ARRAY_nulls##2_null                      84.37ms     11.85
array_constructor_ARRAY_nulls##2_const                    114.17ms      8.76

Before:

array_constructor_INTEGER_nullfree##1                      19.72ms     50.71
array_constructor_INTEGER_nullfree##2                      34.51ms     28.97
array_constructor_INTEGER_nullfree##3                      47.95ms     20.86
array_constructor_INTEGER_nullfree##2_null                 58.68ms     17.04
array_constructor_INTEGER_nullfree##2_const                45.15ms     22.15
array_constructor_INTEGER_nulls##1                         29.99ms     33.34
array_constructor_INTEGER_nulls##2                         55.32ms     18.08
array_constructor_INTEGER_nulls##3                         78.53ms     12.73
array_constructor_INTEGER_nulls##2_null                    72.24ms     13.84
array_constructor_INTEGER_nulls##2_const                   71.13ms     14.06


After:

array_constructor_INTEGER_nullfree##1                       3.41ms    293.37
array_constructor_INTEGER_nullfree##2                       7.27ms    137.61
array_constructor_INTEGER_nullfree##3                      11.73ms     85.29
array_constructor_INTEGER_nullfree##2_null                 11.72ms     85.36
array_constructor_INTEGER_nullfree##2_const                10.51ms     95.15
array_constructor_INTEGER_nulls##1                          4.72ms    211.65
array_constructor_INTEGER_nulls##2                         10.10ms     98.97
array_constructor_INTEGER_nulls##3                         15.00ms     66.68
array_constructor_INTEGER_nulls##2_null                    12.27ms     81.51
array_constructor_INTEGER_nulls##2_const                   12.72ms     78.64


Before:

array_constructor_MAP_nullfree##1                          17.34ms     57.65
array_constructor_MAP_nullfree##2                          29.84ms     33.51
array_constructor_MAP_nullfree##3                          41.51ms     24.09
array_constructor_MAP_nullfree##2_null                     56.57ms     17.68
array_constructor_MAP_nullfree##2_const                    71.68ms     13.95
array_constructor_MAP_nulls##1                             36.22ms     27.61
array_constructor_MAP_nulls##2                             68.18ms     14.67
array_constructor_MAP_nulls##3                             95.12ms     10.51
array_constructor_MAP_nulls##2_null                        86.42ms     11.57
array_constructor_MAP_nulls##2_const                      120.10ms      8.33


After:

array_constructor_MAP_nullfree##1                          19.37ms     51.64
array_constructor_MAP_nullfree##2                          37.79ms     26.46
array_constructor_MAP_nullfree##3                          60.15ms     16.62
array_constructor_MAP_nullfree##2_null                     78.50ms     12.74
array_constructor_MAP_nullfree##2_const                    86.56ms     11.55
array_constructor_MAP_nulls##1                             33.94ms     29.47
array_constructor_MAP_nulls##2                             70.08ms     14.27
array_constructor_MAP_nulls##3                            119.40ms      8.38
array_constructor_MAP_nulls##2_null                       100.92ms      9.91
array_constructor_MAP_nulls##2_const                      135.55ms      7.38


Before:

array_constructor_ROW_nullfree##1                          33.88ms     29.52
array_constructor_ROW_nullfree##2                          62.00ms     16.13
array_constructor_ROW_nullfree##3                          89.54ms     11.17
array_constructor_ROW_nullfree##2_null                     78.46ms     12.75
array_constructor_ROW_nullfree##2_const                    95.53ms     10.47
array_constructor_ROW_nulls##1                             44.11ms     22.67
array_constructor_ROW_nulls##2                            115.43ms      8.66
array_constructor_ROW_nulls##3                            173.61ms      5.76
array_constructor_ROW_nulls##2_null                       130.40ms      7.67
array_constructor_ROW_nulls##2_const                      169.97ms      5.88

After:

array_constructor_ROW_nullfree##1                           5.51ms    181.40
array_constructor_ROW_nullfree##2                          12.17ms     82.20
array_constructor_ROW_nullfree##3                          18.68ms     53.53
array_constructor_ROW_nullfree##2_null                     19.27ms     51.91
array_constructor_ROW_nullfree##2_const                    17.85ms     56.03
array_constructor_ROW_nulls##1                             11.42ms     87.53
array_constructor_ROW_nulls##2                             18.72ms     53.43
array_constructor_ROW_nulls##3                             29.59ms     33.79
array_constructor_ROW_nulls##2_null                        24.04ms     41.59
array_constructor_ROW_nulls##2_const                       23.98ms     41.70

CC: @laithsakka @bikramSingh91 @Yuhta @kevinwilfong

[mbasmanova]

Benchmark: #6566

[mbasmanova]

CC: @JkSelf

[mbasmanova]

PR #6568 adds a benchmark and optimizes array_constructor to use copy(source, rows, toSourceRow) for primitive types and struct of these and copyRanges for everything else. This change speeds up array_constructor of primitive types and structs of these by about 5x.

[mbasmanova]

PR #6566 also optimizes FlatVector::copyRanges and that speeds up array_constructor for arrays and maps.