You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@systemds.apache.org by "Biranavan-Parameswaran (via GitHub)" <gi...@apache.org> on 2025/12/08 21:07:50 UTC
[PR] Feature/systemds 3730 multithreaded roll operation [systemds]
Biranavan-Parameswaran opened a new pull request, #2376:
URL: https://github.com/apache/systemds/pull/2376
## RollOperation: Single vs Multithreaded Performance Summary
### **Test Matrix Sizes**
Two ranges of matrix sizes were evaluated:
1. **Small/Medium Matrices:**
Rows = 2017–2516, Cols = 1001–1500
(Defined as: `MIN_ROWS = 2017`, `MIN_COLS = 1001`, plus up to +500 random)
2. **Large Matrices:**
Rows ≈ 8000–8500, Cols ≈ 4000–4500
(Same generation logic but higher baseline)
These two ranges allow observing how workload size impacts single-threaded (**ST**) vs multithreaded (**MT**) performance.
---
### **Dense Matrices**
- Multithreaded (**MT**, 10 cores) execution consistently improves performance versus single-threaded (**ST**, 1 core).
- **Small/Medium matrices:** typically **2×–3.5× speedup**.
- **Large matrices:** typically **1.3×–4.7× speedup**, depending on layout and shift.
- Occasional slowdowns are visible, almost certainly due to **JVM warm-up effects** during early measurements.
---
### **Sparse Matrices (1% sparsity)**
- **Small/Medium sparse matrices:** MT is often **slower** than ST because the workload is too small; overhead dominates.
- Example: 0.5 ms (ST) → 2.0 ms (MT) → **0.25× slowdown**
- **Large sparse matrices:** MT becomes **consistently beneficial**, commonly achieving **3×–4.5× speedups**.
- Example: 7.0 ms (ST) → 1.8 ms (MT) → **3.9× speedup**
---
### **Key Point**
- **Dense:** MT provides strong speedups for all matrix sizes. Occasional outliers are due to **JVM warm-up**.
- **Sparse:** MT helps only when the matrix contains *enough actual stored values*. Highly sparse matrices should remain **single-threaded (ST)** to avoid overhead.
This shows that very sparse matrices should stay single-threaded, while denser workloads benefit from multithreading.
@janniklinde will review this PR.
--
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: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Feature/systemds 3730 multithreaded roll operation [systemds]
Posted by "janniklinde (via GitHub)" <gi...@apache.org>.
janniklinde commented on PR #2376:
URL: https://github.com/apache/systemds/pull/2376#issuecomment-3641594972
Thank you for the very good PR @Biranavan-Parameswaran and thanks for addressing the normalization issue for negative shifts in the roll operation. I particularly like that you added new correctness tests to increase test coverage and that you provide benchmarks to verify speedups for larger / dense matrices.
I suggest that `RollOperationThreadSafetyTest` is moved to `test.java.org.apache.sysds.performance.matrix` (and renamed to `MatrixRollPerf`). As you correctly mentioned, warmups can distort experimental results. Similarly, the overhead of `JUnit` is also not ideal for performance tests. I would consider doing a performance test in the style of `MatrixAggregate` to get more accurate results.
It would be interesting to see the performance of larger dense matrices with few numbers of columns (including column vectors). My guess is that performance drops in that scenario because you then do many array copies on small ranges. If the underlying row-major `DenseBlock` is `DenseBlockFP64`, I think we could benefit from replacing the row-by-row copy with one (or two in the overflow case) large arraycopy calls (similar to the `clen == 1` case in `copyDenseMtx(...)`).
--
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: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Feature/systemds 3730 multithreaded roll operation [systemds]
Posted by "Biranavan-Parameswaran (via GitHub)" <gi...@apache.org>.
Biranavan-Parameswaran commented on PR #2376:
URL: https://github.com/apache/systemds/pull/2376#issuecomment-3667644261
Thank you for the reminder @janniklinde . I have added the missing license.
--
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: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Feature/systemds 3730 multithreaded roll operation [systemds]
Posted by "mboehm7 (via GitHub)" <gi...@apache.org>.
mboehm7 closed pull request #2376: Feature/systemds 3730 multithreaded roll operation
URL: https://github.com/apache/systemds/pull/2376
--
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: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Feature/systemds 3730 multithreaded roll operation [systemds]
Posted by "codecov[bot] (via GitHub)" <gi...@apache.org>.
codecov[bot] commented on PR #2376:
URL: https://github.com/apache/systemds/pull/2376#issuecomment-3641779438
## [Codecov](https://app.codecov.io/gh/apache/systemds/pull/2376?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
:x: Patch coverage is `94.52055%` with `4 lines` in your changes missing coverage. Please review.
:white_check_mark: Project coverage is 72.30%. Comparing base ([`79122eb`](https://app.codecov.io/gh/apache/systemds/commit/79122eb1f3d6ea9d9b4457a8d1550e7b032a0707?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`1d41175`](https://app.codecov.io/gh/apache/systemds/commit/1d411755d7b1d8831ed04a78f8681f3add8b1568?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
:warning: Report is 6 commits behind head on main.
| [Files with missing lines](https://app.codecov.io/gh/apache/systemds/pull/2376?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
|---|---|---|
| [...ache/sysds/runtime/matrix/data/LibMatrixReorg.java](https://app.codecov.io/gh/apache/systemds/pull/2376?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Forg%2Fapache%2Fsysds%2Fruntime%2Fmatrix%2Fdata%2FLibMatrixReorg.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-c3JjL21haW4vamF2YS9vcmcvYXBhY2hlL3N5c2RzL3J1bnRpbWUvbWF0cml4L2RhdGEvTGliTWF0cml4UmVvcmcuamF2YQ==) | 95.52% | [2 Missing and 1 partial :warning: ](https://app.codecov.io/gh/apache/systemds/pull/2376?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [...ds/runtime/instructions/cp/ReorgCPInstruction.java](https://app.codecov.io/gh/apache/systemds/pull/2376?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Forg%2Fapache%2Fsysds%2Fruntime%2Finstructions%2Fcp%2FReorgCPInstruction.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-c3JjL21haW4vamF2YS9vcmcvYXBhY2hlL3N5c2RzL3J1bnRpbWUvaW5zdHJ1Y3Rpb25zL2NwL1Jlb3JnQ1BJbnN0cnVjdGlvbi5qYXZh) | 66.66% | [0 Missing and 1 partial :warning: ](https://app.codecov.io/gh/apache/systemds/pull/2376?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## main #2376 +/- ##
============================================
+ Coverage 72.29% 72.30% +0.01%
- Complexity 46937 46961 +24
============================================
Files 1513 1513
Lines 178421 178489 +68
Branches 35036 35049 +13
============================================
+ Hits 128993 129065 +72
+ Misses 39665 39658 -7
- Partials 9763 9766 +3
```
</details>
[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/apache/systemds/pull/2376?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
<details><summary> :rocket: New features to boost your workflow: </summary>
- :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
- :package: [JS Bundle Analysis](https://docs.codecov.com/docs/javascript-bundle-analysis): Save yourself from yourself by tracking and limiting bundle sizes in JS merges.
</details>
--
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: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Feature/systemds 3730 multithreaded roll operation [systemds]
Posted by "janniklinde (via GitHub)" <gi...@apache.org>.
janniklinde commented on code in PR #2376:
URL: https://github.com/apache/systemds/pull/2376#discussion_r2610333818
##########
src/main/java/org/apache/sysds/runtime/matrix/data/LibMatrixReorg.java:
##########
@@ -514,6 +516,119 @@ public static MatrixBlock roll(MatrixBlock in, MatrixBlock out, int shift) {
return out;
}
+ public static MatrixBlock roll(MatrixBlock input, MatrixBlock output, int shift, int numThreads) {
+
+ final int numRows = input.rlen;
+ final int numCols = input.clen;
+ final boolean isSparse = input.sparse;
+
+ // sparse-safe operation
+ if(input.isEmptyBlock(false))
+ return output;
+
+ // special case: row vector
+ if(numRows == 1) {
+ output.copy(input);
+ return output;
+ }
+
+ if(numThreads <= 1 || input.isEmptyBlock(false) || input.getLength() < PAR_NUMCELL_THRESHOLD) {
Review Comment:
`input.isEmptyBlock(false)` check is unnecessary (duplicate)
--
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: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Feature/systemds 3730 multithreaded roll operation [systemds]
Posted by "Biranavan-Parameswaran (via GitHub)" <gi...@apache.org>.
Biranavan-Parameswaran commented on PR #2376:
URL: https://github.com/apache/systemds/pull/2376#issuecomment-3662113175
This patch introduces multi threading support for the roll operation to improve performance across a wide range of matrix shapes and sizes. The new `MatrixRollPerf` benchmark was added to evaluate performance characteristics under different workloads, while the existing `RollOperationThreadSafetyTest` was intentionally kept to ensure correctness and equivalence between single threaded and multithreaded execution paths.
---
## RollOperation. Single vs Multithreaded Performance Summary
### Test Coverage and Motivation
Performance was evaluated across multiple matrix configurations to understand how matrix shape, density, and size affect multithreaded scaling. The goal was to validate expected speedups and identify edge cases where multithreading may not be beneficial.
---
## General Performance Observations
### Dense Matrices with Moderate Aspect Ratios
For dense matrices with moderate to large column counts, multithreaded execution consistently improves performance.
- Typical speedups range from **~1.3× to ~4×**, depending on matrix size and shape.
- Larger matrices benefit more from multithreading since overhead becomes less significant.
These results confirm that the multithreaded roll implementation behaves as expected for typical dense workloads.
---
### Sparse Matrices
Sparse matrices show more nuanced behavior.
- For small or moderately sized sparse matrices, multithreading can be slower due to scheduling and synchronization overhead.
- As matrix sizes grow, multithreading becomes beneficial, with observed speedups up to **~4×**.
This aligns with my expectations. Sparse workloads require sufficient actual work per thread to justify parallel execution.
---
## Matrices with Few Columns and Large Row Counts
Additional experiments were conducted for very tall matrices with few columns, including the extreme case of `clen == 1` (column vectors). These shapes were specifically tested following @janniklinde's feedback.
### Initial Behavior
For column vectors, the original multithreaded implementation performed significantly worse than the single threaded version. This was due to many small copy operations and excessive threading overhead.
### Attempted Optimization
An optimized multithreaded implementation was prototyped for the case where the underlying block is `clen == 1` (column vectors). This version replaced row by row copies with one or two large contiguous `System.arraycopy` calls, similar to the existing optimized path in `copyDenseMtx`.
This optimization significantly improved the multithreaded behavior compared to the previous implementation.
### Final Results
Despite the improvement, benchmarking shows that even with this optimization:
- For very large column vectors (100M–150M rows), **single threaded execution remains faster**.
- Example results:
- 100M × 1 dense. ~50 ms (ST) vs ~54 ms (MT)
- 150M × 1 dense. ~68 ms (ST) vs ~89 ms (MT)
This indicates that the operation is memory bandwidth bound and already near optimal when using one or two large `arraycopy` calls. The overhead of multithreading outweighs its benefits, even at large sizes.
Because the optimized multithreaded path for `clen == 1` does not provide a net performance benefit, this change was **not committed**, as it would increase complexity without improving performance.
---
## Conclusion and Proposed Direction
- Multithreading provides strong and consistent speedups for dense and sufficiently large sparse matrices.
- Sparse matrices and column vectors can suffer from threading overhead.
- Column vectors (`clen == 1`) are best handled by a **single threaded bulk copy**, as this already saturates memory bandwidth.
Based on these findings, a reasonable follow up improvement would be to explicitly force a **single threaded roll path for `clen == 1`**, while retaining multithreaded execution for wider matrices where it demonstrably improves performance.
If there is agreement on this approach, I can follow up with a targeted change implementing this specialization.
--
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: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Feature/systemds 3730 multithreaded roll operation [systemds]
Posted by "mboehm7 (via GitHub)" <gi...@apache.org>.
mboehm7 commented on PR #2376:
URL: https://github.com/apache/systemds/pull/2376#issuecomment-3698735914
LGTM as well. Thanks for the patch and experiments @Biranavan-Parameswaran, thanks for the review @janniklinde, and sorry for the delay. During the merge I just added a few TODOs (for ourself in the future) to experiment with multiple tasks per thread which usually improves load balance, and to call a common kernel from both single- and multi-threaded operations (i.e., single-threaded simply calls the multi-threaded kernel with start=0 and end=numRows). The special case for clen=1 is safe because our in-memory blocks only support numRows/numCols of max integer, which means the allocated dense block will always be contiguous.
--
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: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Feature/systemds 3730 multithreaded roll operation [systemds]
Posted by "janniklinde (via GitHub)" <gi...@apache.org>.
janniklinde commented on PR #2376:
URL: https://github.com/apache/systemds/pull/2376#issuecomment-3669261021
LGTM @mboehm7 - one possible concern I have both with the single-threaded and multi-threaded implementation is that `clen == 1` has to guarantee that `in.getDenseBlockValues()` does not throw an exception or returns only the first row. Because the single-threaded case already had that implementation, I am not sure if it is intentional or an issue.
Thank you again for your contribution, bugfixes, and detailed tests and benchmarks @Biranavan-Parameswaran.
It appears that `System.arraycopy` already saturates memory bandwidth (shown by your single column benchmarks). An optional improvement I could see for `DenseBlockFP64` is to always perform two large arraycopies instead of many small ones (currently this is only limited to `clen==1`). Due to the contiguous row-major layout of some dense block implementations, performing two large arraycopies should be possible.
--
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: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Feature/systemds 3730 multithreaded roll operation [systemds]
Posted by "janniklinde (via GitHub)" <gi...@apache.org>.
janniklinde commented on PR #2376:
URL: https://github.com/apache/systemds/pull/2376#issuecomment-3665328710
Thank you for the changes and the detailed performance analysis @Biranavan-Parameswaran. There is still a missing license that should be added.
--
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: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org