shieru1214 opened a new pull request, #2542: URL: https://github.com/apache/systemds/pull/2542
### Summary This PR adds a multi-threaded path for `unique` in `LibMatrixSketch`. The existing single-threaded implementation is kept and is still used as the baseline/fallback. I added a new overload: `getUniqueValues(MatrixBlock blkIn, Types.Direction dir, int k)`, where `k` controls the requested number of threads. The implementation now covers: - `RowCol`: unique values for single-column inputs - `Row`: unique rows - `Col`: unique columns ### Implementation For `k > 1` and sufficiently large inputs, the code uses thread-local deduplication followed by a global merge. Each worker builds its own local set/map first, so the worker phase does not rely on one shared synchronized structure. There are two parallel paths: - regular parallel deduplication, used when the estimated local memory usage is safe - batched parallel deduplication, used when full thread-local maps may be too large The batched path processes a limited number of ranges at a time, merges the local results, clears them, and then continues with the next batch. If the input is small, `k <= 1`, or batching is not useful, the code falls back to the original single-threaded path. For row and column deduplication, I added content-based key wrappers for copied row/column values. The global merge is ordered so that first occurrences are preserved. ### Testing I added a focused standalone check class: - `src/test/java/org/apache/sysds/runtime/matrix/data/LibMatrixSketchUniqueParallelTest.java` It checks `RowCol`, `Row`, and `Col`, and compares the multi-threaded result against the single-threaded baseline. I also ran the existing unique tests: - `mvn -Dtest=UniqueRow,UniqueRowCol test` I ran the focused check locally as well, including one run with a smaller JVM heap to exercise the memory-aware path. ### Runtime experiments I ran local runtime experiments with fixed `k=4`, comparing against `k=1`. The experiment varies: - direction: `RowCol`, `Row`, `Col` - input size: small and large - unique share: `1%`, `10%`, `50%`, `100%` - `Unique Count` is the number of distinct values, rows, or columns generated for that case. - Speedup is computed as `k=1 time / k=4 time`, so values above 1 mean that the multi-threaded path was faster. The results are mostly in line with the expected trade-off. The parallel path helps more for `Row` and `Col`, where each key represents a copied row or column and hashing/comparison is more expensive than in the scalar `RowCol` case. The benefit is clearer on larger inputs and with higher unique shares, because there is more work to distribute across threads. For small inputs, and for some simple `RowCol` cases, the overhead from task scheduling and merging local results can be larger than the saved work. The table below shows the local runtime results. These numbers are from local runs and are meant as an initial comparison, not as a full benchmark. | Direction | Size | Input | Unique Share | Unique Count | k=1 (ms) | k=4 (ms) | Speedup | |---|---|---|---:|---:|---:|---:|---:| | RowCol | small | 100000x1 | 1% | 1000 | 3.975 | 13.665 | 0.29 | | RowCol | small | 100000x1 | 10% | 10000 | 2.032 | 16.826 | 0.12 | | RowCol | small | 100000x1 | 50% | 50000 | 3.128 | 7.356 | 0.43 | | RowCol | small | 100000x1 | 100% | 100000 | 3.088 | 7.704 | 0.40 | | RowCol | large | 2000000x1 | 1% | 20000 | 24.340 | 22.364 | 1.09 | | RowCol | large | 2000000x1 | 10% | 200000 | 26.118 | 95.699 | 0.27 | | RowCol | large | 2000000x1 | 50% | 1000000 | 77.059 | 105.895 | 0.73 | | RowCol | large | 2000000x1 | 100% | 2000000 | 119.494 | 127.973 | 0.93 | | Row | small | 1000x16 | 1% | 10 | 0.369 | 0.295 | 1.25 | | Row | small | 1000x16 | 10% | 100 | 1.289 | 0.564 | 2.29 | | Row | small | 1000x16 | 50% | 500 | 1.175 | 1.075 | 1.09 | | Row | small | 1000x16 | 100% | 1000 | 1.241 | 1.237 | 1.00 | | Row | large | 5000x16 | 1% | 50 | 0.654 | 2.090 | 0.31 | | Row | large | 5000x16 | 10% | 500 | 4.254 | 1.608 | 2.65 | | Row | large | 5000x16 | 50% | 2500 | 16.327 | 1.599 | 10.21 | | Row | large | 5000x16 | 100% | 5000 | 21.106 | 2.020 | 10.45 | | Col | small | 16x5000 | 1% | 50 | 0.645 | 0.755 | 0.86 | | Col | small | 16x5000 | 10% | 500 | 0.543 | 1.525 | 0.36 | | Col | small | 16x5000 | 50% | 2500 | 0.639 | 1.448 | 0.44 | | Col | small | 16x5000 | 100% | 5000 | 0.881 | 2.091 | 0.42 | | Col | large | 16x50000 | 1% | 500 | 3.174 | 2.293 | 1.38 | | Col | large | 16x50000 | 10% | 5000 | 4.109 | 2.827 | 1.45 | | Col | large | 16x50000 | 50% | 25000 | 8.032 | 6.280 | 1.28 | | Col | large | 16x50000 | 100% | 50000 | 19.391 | 12.272 | 1.58 | -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
