[BUG] Hausdorff fails with OOM for > intmax num inputs

[cwharris]

Hausdorff fails for large number of inputs. The problem originates in Thrust, which is storing num_items as int, but fixing that uncovers an illegal memory access bug.

NVIDIA/cccl#766

[cwharris]

fix had to be rolled back due to performances regression in libcudf. Will have to tackle this problem by partitioning inputs, rather than accepting a single large input. partitions will have to begin/end at specific offsets to ensure inclusive_scan results are correct. these offsets are deterministic, according to cartesian_product_group_index begin/end pairs. The math for this is a forward-only packing problem, which is simple to compute in the CPU, but not as straightforward on the GPU. attempts to compute on the CPU resulting in slow performance, but this may have been expected due to the high number of inputs I was testing with at the time. further investigation is required.

[cwharris]

I reapplied the thrust scan_by_key patch locally to allow for 64 bit indices, ran all @rapidsai/cudf benchmarks, and found little to no performance difference. From there, I was able to get hausdorff working with 5000 spaces and 100 points. However, higher inputs resulted in an OOM from thrust temporary memory allocations:

(rapids) rapids@compose:~$ test-cuspatial-cpp HAUSDORFF_TEST

+ cd /home/charris/dev/rapids/cuspatial/cpp/build/release
[2/2] Linking CXX executable gtests/HAUSDORFF_TEST
+ ctest --force-new-ctest-process --output-on-failure -R HAUSDORFF_TEST
Test project /home/charris/dev/rapids/cuspatial/cpp/build/release
    Start 5: HAUSDORFF_TEST
1/1 Test NVIDIA/thrust#5: HAUSDORFF_TEST ...................***Exception: SegFault  1.27 sec
Running main() from ../googletest/src/gtest_main.cc
[==========] Running 2 tests from 2 test suites.
[----------] Global test environment set-up.
[----------] 1 test from HausdorffTest/0, where TypeParam = float
[ RUN      ] HausdorffTest/0.6000Spaces100Points
Thread,Time,Action,Pointer,Size,Stream
57027,01:13:22.531965,try allocate,_,4800000,0x0
57027,01:13:23.206586,did allocate,0x7f71fc000000,4800000,0x0
57027,01:13:23.208725,try allocate,_,4800000,0x0
57027,01:13:23.208874,did allocate,0x7f71fc600000,4800000,0x0
57027,01:13:23.209343,try allocate,_,24000,0x0
57027,01:13:23.209485,did allocate,0x7f71efe00000,24000,0x0
57027,01:13:23.303551,try allocate,_,288000000,0x0
57027,01:13:23.304031,did allocate,0x7f71c2000000,288000000,0x0
57027,01:13:23.348967,try allocate,_,288000000,0x0
57027,01:13:23.349418,did allocate,0x7f71b0000000,288000000,0x0
57027,01:13:23.349435,try allocate,_,1152000000,0x0
57027,01:13:23.350452,did allocate,0x7f716a000000,1152000000,0x0
57027,01:13:23.350481,try allocate,_,56953128704,0x0
57027,01:13:23.354702,free,0x7f716a000000,1152000000,0x0
57027,01:13:23.355787,free,0x7f71b0000000,288000000,0x0
57027,01:13:23.358178,free,0x7f71c2000000,288000000,0x0
57027,01:13:23.360274,free,0x7f71efe00000,24000,0x0
57027,01:13:23.361089,free,0x7f71fc600000,4800000,0x0
57027,01:13:23.362148,free,0x7f71fc000000,4800000,0x0
unknown file: Failure
C++ exception with description "std::bad_alloc: CUDA error at: /home/charris/dev/rapids/rmm/include/rmm/mr/device/cuda_memory_resource.hpp:69: cudaErrorMemoryAllocation out of memory" thrown in the test body.
[  FAILED  ] HausdorffTest/0.6000Spaces100Points, where TypeParam = float (874 ms)
[----------] 1 test from HausdorffTest/0 (874 ms total)

[----------] 1 test from HausdorffTest/1, where TypeParam = double
[ RUN      ] HausdorffTest/1.6000Spaces100Points
Thread,Time,Action,Pointer,Size,Stream
57027,01:13:23.363653,try allocate,_,4800000,0x0
57027,01:13:23.363661,did allocate,0x7f724bd62c90,4800000,0x0

I hypothesize that this is a legitimate OOM caused by the design of temporary memory usage in the single-pass scan algorithm within thrust/cub. However, It I believe it is unreasonable to attempt to reduce the temporary memory requirements for cub/thrust single-pass-scan implementation at this time (specifically, as part of this bug). Therefore, I will be looking for alternatives that do not require patching thrust.

edit:

for anyone coming across this comment wondering why inclusive_scan is being used, it's because the hausdorff implementation uses an associative (non-commutative) reduction operator, but thrust/cub does not provide an associative reduction algorithm. Instead, inclusive_scan is being used in conjunction with a proprietary "scatter output iterator" to compress the output at write time, only taking the last element of each scan. Essentially the thrust/cub scan algorithm was never designed to be used with this many inputs, and therefore makes a reasonably assumption about the maximum size of temporary storage. patching thrust to a 64 bit integer increased the maximum number of inputs, and therefore increased the maximum possibly temporary storage size, resulting in an an OOM for a large number of inputs. This could be alleviated by using a circular buffer for the single-pass scan algorithm, rather than retaining all intermediate results, but that's far out of scope for this bug.