[C++] diff.cc is extremely slow to compile

[asfimport]

This comes up especially when doing an optimized build. diff.cc is always enabled even if all components are disabled, and it takes multiple seconds to compile.

Reporter: Antoine Pitrou / @pitrou
Assignee: Wes McKinney / @wesm

Related issues:

• [C++] Reduce shared library / binary code size (umbrella issue) (is related to)

PRs and other links:

• GitHub Pull Request #7311

_{Note: This issue was originally created as ARROW-7784. Please see the migration documentation for further details.}

[asfimport]

Antoine Pitrou / @pitrou:
Using CLangBuildAnalyzer I get the following results:

**** Files that took longest to codegen (compiler backend):
 66372 ms: build-clang-profile/src/arrow/CMakeFiles/arrow_objlib.dir/sparse_tensor.cc.o
 16457 ms: build-clang-profile/src/arrow/CMakeFiles/arrow_objlib.dir/array/diff.cc.o
 6283 ms: build-clang-profile/src/arrow/CMakeFiles/arrow_objlib.dir/scalar.cc.o
 5284 ms: build-clang-profile/src/arrow/CMakeFiles/arrow_objlib.dir/builder.cc.o
 5090 ms: build-clang-profile/src/arrow/CMakeFiles/arrow_objlib.dir/array/dict_internal.cc.o

[asfimport]

Wes McKinney / @wesm:
"QuadraticSpaceMyersDiff" is being instantiated for every Arrow type. Given that this code is not performance sensitive, I would suggest refactoring this code to only instantiate a single implementation of the Diff algorithm (rather than 25+ instantiations) and where relevant introduce a virtual interface for interacting with values in different-type arrays.

[asfimport]

Ben Kietzman / @bkietz:
Issue resolved by pull request 7311
#7311