GCC 13 compilation error for parallel LSD radix sort

[gtkramer]

I am using GCC 13.2 with oneTBB 2021.11.0 on Linux to build this code, which looks like it meets the requirements of having a C++ 20-compliant compiler and a current version of oneTBB. When I do this, however, I'm getting the following compilation error:

In file included from /ParallelAlgorithms/ParallelMergeSort.h:29,
                 from /ParallelAlgorithms/RadixSortLSD.h:11,
                 from /ParallelAlgorithms/RadixSortLsdBenchmark.cpp:11:
/ParallelAlgorithms/RadixSortLsdParallel.h: In instantiation of ‘void ParallelAlgorithms::_RadixSortLSD_StableUnsigned_PowerOf2RadixParallel_TwoPhase_DeRandomize(unsigned int*, unsigned int*, size_t, unsigned int, unsigned int, bool) [with long unsigned int PowerOfTwoRadix = 256; long unsigned int Log2ofPowerOfTwoRadix = 8; long int Threshold = 100; size_t = long unsigned int]’:
/ParallelAlgorithms/RadixSortLsdParallel.h:500:128:   required from here
/ParallelAlgorithms/RadixSortLsdParallel.h:469:153: error: ‘_RadixSortLSD_StableUnsigned_PowerOf2Radix_PermuteDerandomized’ was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation
  469 |                         _RadixSortLSD_StableUnsigned_PowerOf2Radix_PermuteDerandomized< PowerOfTwoRadix, Log2ofPowerOfTwoRadix, Threshold, bufferDepth >(
      |                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
  470 |                                 _input_array, _output_array, 0, last, bitMask, shiftRightAmount, endOfBin, bufferIndex, bufferDerandomize);
      |                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~               
/ParallelAlgorithms/RadixSortLSD.h:135:13: note: ‘template<long unsigned int PowerOfTwoRadix, long unsigned int Log2ofPowerOfTwoRadix, long int Threshold, long unsigned int BufferDepth> void _RadixSortLSD_StableUnsigned_PowerOf2Radix_PermuteDerandomized(unsigned int*, unsigned int*, size_t, size_t, unsigned int, long unsigned int, size_t*, size_t*, unsigned int (*)[BufferDepth])’ declared here, later in the translation unit
  135 | inline void _RadixSortLSD_StableUnsigned_PowerOf2Radix_PermuteDerandomized(unsigned* input_array, unsigned* output_array, size_t startIndex, size_t endIndex, unsigned bitMask, unsigned long shiftRightAmount,
      |             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

This looks like an error related to the order of declaration and the point of instantiation for _RadixSortLSD_StableUnsigned_PowerOf2Radix_PermuteDerandomized. However, I can't quite put my finger on this one as to what the issue is because the RadixSortLSD.h header is already included in RadixSortLsdParallel.h.

I wonder if it has something to do with RadixSortLsdBenchmark.cpp needing RadixSortLSD.h needing ParallelMergeSort.h needing RadixSortLsdParallel.h needing the RadixSortLSD.h header again.

[DragonSpit]

I'm not sure how to duplicate this build issue. The latest commit from today (37ca936877a19d49d1e986fa8c98c71dad5be118) builds on WSL (Ubuntu 22.04.4 LTS) with:

• g++ (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
• libtbb-dev:amd64/jammy 2021.5.0-7ubuntu2 These are displayed from:
• g++ --version
• apt-show-versions libtbb-dev

[gtkramer]

Thanks for testing this. I tried using an older toolchain that has GCC 11.3 and TBB 2020.3 for building. It worked just fine.

I guess that means this code doesn't build with new GCC versions. I don't know about GCC 12 since I don't have access to that version of the compiler, but GCC 13 doesn't work.

[DragonSpit]

Sadly, only g++ for Linux, and VisualStudio 2022 (Microsoft and Intel) compilers for Windows, have been tested so far. Could you provide gcc command line that you're using to compile with gcc? Is using g++ or Intel compiler an option for Linux?

[DragonSpit]

Examining the call and definition of the problem function, the shiftRightAmount argument has a type mismatch, which some compilers may not care about, but maybe certain gcc versions do. I changed them to match. Pull the latest and give it a try 🤞

[gtkramer]

I guess I should be more specific here, I'm actually using g++ to build the code. We've actually moved away from using the Intel compiler and have standardized our software infrastructure on gcc/g++ just like a Linux distro would. Pros and cons I guess.

Thank you for the fix here! Unfortunately, that doesn't help. The same issue occurs. I tried replacing all of the header guards with #pragma once, but that didn't help either.

I'm building the code with the following rudimentary CMakeLists.txt:

cmake_minimum_required(VERSION 3.26)

project(ParallelAlgorithms
    VERSION 1.0.0
    LANGUAGES CXX
)

set(CMAKE_CXX_STANDARD 20)
set(CMAKE_CXX_STANDARD_REQUIRED True)
set(CMAKE_CXX_EXTENSIONS OFF)

find_package(TBB CONFIG REQUIRED)

add_executable(ParallelAlgorithms
    ParallelAlgorithms.cpp
    ParallelStdCppExample.cpp
    RadixSortLsdBenchmark.cpp
    MemoryUsage.cpp
    CountingSortParallelBenchmark.cpp
    SumBenchmark.cpp
    RadixSortMsdBenchmark.cpp
    ParallelMergeSortBenchmark.cpp
)

target_include_directories(ParallelAlgorithms PRIVATE ${CMAKE_CURRENT_SOURCE_DIR})

target_link_libraries(ParallelAlgorithms PRIVATE TBB::tbb)

In my $PATH, I have g++ 13.2.0. I exported $CMAKE_PREFIX_PATH to be the path where I have oneTBB 2021.11.0 installed, which is /opt/pkgs/tbb/2021.11.0. The same error as initially reported occurs.

If I configure CMake with -DCMAKE_VERBOSE_MAKEFILE=ON to get the specific compile line that's failing, this is what I get once I build:

c++ -I /home/gtkramer/projects/cpp/ParallelAlgorithms -isystem /opt/pkgs/tbb/2021.11.0/include -std=c++20 -MD -MT CMakeFiles/ParallelAlgorithms.dir/RadixSortLsdBenchmark.cpp.o -MF CMakeFiles/ParallelAlgorithms.dir/RadixSortLsdBenchmark.cpp.o.d -o CMakeFiles/ParallelAlgorithms.dir/RadixSortLsdBenchmark.cpp.o -c /home/gtkramer/projects/cpp/ParallelAlgorithms/RadixSortLsdBenchmark.cpp

For my g++ install, c++ is hardlinked to g++.

[alantudyk]

Another compilation problem:

# Not OK:

$ g++ ParallelAlgorithms.cpp ParallelStdCppExample.cpp RadixSortLsdBenchmark.cpp MemoryUsage.cpp CountingSortParallelBenchmark.cpp SumBenchmark.cpp RadixSortMsdBenchmark.cpp ParallelMergeSortBenchmark.cpp -ltbb -std=c++20 -O3 -o ParallelAlgorithms
/usr/bin/ld: /tmp/cclJzmwA.o: in function `main':
ParallelAlgorithms.cpp:(.text.startup+0x19c): undefined reference to `bundling_small_work_items_benchmark(unsigned long, unsigned long, unsigned long)'
collect2: error: ld returned 1 exit status

# OK:

$ g++ *.cpp -ltbb -std=c++20 -O3 -o ParallelAlgorithms

# Compiler:

$ g++ --version
g++ (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0