Isso-W commented on code in PR #2542:
URL: https://github.com/apache/systemds/pull/2542#discussion_r3769731911
##########
src/main/java/org/apache/sysds/runtime/matrix/data/LibMatrixSketch.java:
##########
@@ -19,89 +19,807 @@
package org.apache.sysds.runtime.matrix.data;
-import org.apache.sysds.common.Types;
-
+import java.util.ArrayList;
import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.concurrent.Callable;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Future;
+
+import org.apache.sysds.common.Types;
+import org.apache.sysds.runtime.DMLRuntimeException;
+import org.apache.sysds.runtime.util.CommonThreadPool;
+import org.apache.sysds.runtime.util.UtilFunctions;
+import org.apache.sysds.utils.stats.InfrastructureAnalyzer;
public class LibMatrixSketch {
+ private static final long PAR_UNIQUE_NUMCELL_THRESHOLD = 1024 * 16;
+ private static final long PAR_UNIQUE_MAX_LOCAL_BYTES_FRACTION = 4;
+ /**
+ * Conservative footprint of one value retained in a
HashSet<Double>: the boxed Double plus amortized hash-map
+ * node and backing-array overhead.
+ */
+ private static final long PAR_UNIQUE_BYTES_PER_CELL = Double.BYTES * 8;
+ /**
+ * Computes unique values with the original single-threaded behavior.
The overload with a parallelism argument keeps
+ * this path as the k=1 baseline.
+ *
+ * @param blkIn input matrix block
+ * @param dir unique direction
+ * @return matrix block containing unique values
+ */
public static MatrixBlock getUniqueValues(MatrixBlock blkIn,
Types.Direction dir) {
- //similar to R's unique, this operation takes a matrix and
computes the
- //unique values (or rows in case of multiple column inputs)
-
+ return getUniqueValues(blkIn, dir, 1);
+ }
+
+ /**
+ * Computes unique values. For sufficiently large inputs and k > 1,
this uses parallel local deduplication or its
+ * batched variant.
+ *
+ * @param blkIn input matrix block
+ * @param dir unique direction
+ * @param k requested degree of parallelism
+ * @return matrix block containing unique values
+ */
+ public static MatrixBlock getUniqueValues(MatrixBlock blkIn,
Types.Direction dir, int k) {
+ return getUniqueValues(blkIn, dir, k,
getDefaultLocalBytesBudget());
+ }
+
+ /**
+ * Computes unique values with an explicit budget for the transient
deduplication structures. The budget decides
+ * between the full parallel path, its batched variant, and the
sequential fallback. This overload exists so tests
+ * can inject a small budget and deterministically exercise the batched
path, which the heap-derived default would
+ * not trigger.
+ *
+ * @param blkIn input matrix block
+ * @param dir unique direction
+ * @param k requested degree of parallelism
+ * @param maxLocalBytes budget in bytes for transient deduplication
structures
+ * @return matrix block containing unique values
+ */
+ public static MatrixBlock getUniqueValues(MatrixBlock blkIn,
Types.Direction dir, int k, long maxLocalBytes) {
+ // Similar to R's unique, this operation computes unique values
according
+ // to the requested direction.
+ if(!satisfiesMultiThreadingConstraints(blkIn, dir, k))
+ return getUniqueValuesSequential(blkIn, dir);
+
+ boolean localDedupMemorySafe =
isLocalDedupMemoryBudgetSafe(blkIn, dir, k, maxLocalBytes);
+ switch(dir) {
+ case RowCol:
Review Comment:
Before answering the two questions, a correction. `UniquePerf` warmed up
each configuration individually but not the whole run.
The benchmark now warms up all three directions before measuring anything.
Corrected results below.
RowCol
Size | Input | Unique Share | Unique Values | k=1 (ms) | k=4 (ms) | Speedup
-- | -- | -- | -- | -- | -- | --
small | 100000x1 | 1% | 1000 | 1.966 | 3.402 | 0.58
small | 100000x1 | 10% | 10000 | 1.713 | 5.572 | 0.31
small | 100000x1 | 50% | 50000 | 2.258 | 5.867 | 0.38
small | 100000x1 | 100% | 100000 | 3.349 | 6.589 | 0.51
large | 2000000x1 | 1% | 20000 | 34.466 | 30.974 | 1.11
large | 2000000x1 | 10% | 200000 | 38.477 | 94.247 | 0.41
large | 2000000x1 | 50% | 1000000 | 203.514 | 296.856 | 0.69
large | 2000000x1 | 100% | 2000000 | 252.824 | 370.762 | 0.68
Row
Size | Input | Unique Share | Unique Values per Row | k=1 (ms) | k=4 (ms) |
Speedup
-- | -- | -- | -- | -- | -- | --
small | 10000x64 | 1% | 1 | 45.488 | 10.565 | 4.31
small | 10000x64 | 10% | 6 | 50.046 | 13.272 | 3.77
small | 10000x64 | 50% | 32 | 60.186 | 29.949 | 2.01
small | 10000x64 | 100% | 64 | 96.148 | 56.697 | 1.70
large | 200000x64 | 1% | 1 | 905.786 | 215.934 | 4.19
large | 200000x64 | 10% | 6 | 975.045 | 250.145 | 3.90
large | 200000x64 | 50% | 32 | 1274.481 | 637.637 | 2.00
large | 200000x64 | 100% | 64 | 1910.039 | 1166.702 | 1.64
Col
Size | Input | Unique Share | Unique Values per Column | k=1 (ms) | k=4 (ms)
| Speedup
-- | -- | -- | -- | -- | -- | --
small | 64x10000 | 1% | 1 | 48.583 | 12.632 | 3.85
small | 64x10000 | 10% | 6 | 56.231 | 14.099 | 3.99
small | 64x10000 | 50% | 32 | 71.206 | 30.036 | 2.37
small | 64x10000 | 100% | 64 | 108.219 | 51.479 | 2.10
large | 64x200000 | 1% | 1 | 1105.272 | 254.552 | 4.34
large | 64x200000 | 10% | 6 | 1169.894 | 306.159 | 3.82
large | 64x200000 | 50% | 32 | 1563.054 | 627.662 | 2.49
large | 64x200000 | 100% | 64 | 2206.368 | 1147.500 | 1.92
While for smaller inputs, it doesn't work well.
| Input | Cells | 1% | 10% | 50% | 100% |
| --------- | ----- | ---- | ---- | ---- | ---- |
| 4096x1 | 4K | 0.10 | 0.06 | 0.13 | 0.25 |
| 16384x1 | 16K | 0.36 | 0.42 | 0.48 | 0.54 |
| 65536x1 | 64K | 1.30 | 0.72 | 0.95 | 0.82 |
But there are some interesting findings, The row-wise and column-wise
sequential implementation runs two passes, one to determine the output width
and one to fill it, and both hash every value.
cells | input | distinct per row | 2-pass (current) | 1-pass | 1-pass +
dense read
-- | -- | -- | -- | -- | --
1048576 | 8 MB | 4 | 22.9 ms | 12.4 ms (1.85x) | 10.1 ms (2.27x)
16777216 | 128 MB | 4 | 1041.4 ms | 539.8 ms (1.93x) | 482.0 ms (2.16x)
1048576 | 8 MB | 64 | 94.9 ms | 58.1 ms (1.63x) | 52.7 ms (1.80x)
16777216 | 128 MB | 64 | 1535.2 ms | 963.6 ms (1.59x) | 851.9 ms (1.80x)
The gain does not decay with scale, since what is saved is one hash per cell
rather than a fixed cost. The buffer is at most as large as the input, reached
only when every value in a row is distinct.
Is this still in the scope of this PR? We are glad to follow or starting
with an new issue. @gaturchenko
--
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]
