Opened 6 years ago
Closed 5 years ago
#2919 closed enhancement (done)
Packed storage matrix type
| Reported by: | bburlacu | Owned by: | abeham |
|---|---|---|---|
| Priority: | medium | Milestone: | HeuristicLab 3.3.16 |
| Component: | Data | Version: | trunk |
| Keywords: | merged | Cc: |
Description (last modified by bburlacu)
Dense, fixed-size, symmetric matrices are pretty common. In HeuristicLab they are used for for storing similarities where for example we have code like this:
if (IsCommutative) {
Parallel.For(0, individuals.Count, parallelOptions, i => {
for (int j = i; j < individuals.Count; j++) {
similarityMatrix[i][j] = similarityMatrix[j][i] = CalculateSolutionSimilarity(individuals[i], individuals[j]);
}
});
}
This data could be more compactly stored by using a packed storage scheme (https://en.wikipedia.org/wiki/Packed_storage_matrix) leading to significant savings when storing experiments where each run contains similarity matrices (genotype, phenotype).
Advantages:
- compact storage
- more efficient parallelization along the length of the storage array (as opposed to the snipped above where each thread does a different amount of work)
Disadvantages:
- packed storage prevents vectorization in case of indexed access, which might lead to worse performance (compared to a regular matrix)
- would require refactoring of the SolutionSimilarityCalculator & friends
Change History (11)
comment:1 Changed 6 years ago by bburlacu
- Description modified (diff)
comment:2 Changed 6 years ago by bburlacu
- Status changed from new to accepted
comment:3 Changed 6 years ago by bburlacu
- Owner changed from bburlacu to gkronber
- Status changed from accepted to reviewing
comment:4 Changed 6 years ago by bburlacu
- Owner changed from gkronber to bburlacu
comment:5 Changed 6 years ago by bburlacu
- Owner changed from bburlacu to swagner
r15932: Decide to enforce symmetry by returning values mirrored across the main diagonal.
comment:6 Changed 6 years ago by bburlacu
r15934: Update project (include TriangularMatrix.cs)
comment:7 Changed 5 years ago by abeham
- Owner changed from swagner to abeham
comment:8 Changed 5 years ago by abeham
- Milestone changed from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.16
Reviewed r15931:15932, r15934:
- TriangularMatrix is implemented as generic type, but is limited to numeric values (cf. TryParse). We'll get bad behavior when e.g. TriangularMatrix<DateTime> is created. It would be better to use the same pattern as ValueTypeMatrix<T>, make the type abstract and then derive concrete types (IntTriangularMatrix, DoubleTriangularMatrix, etc.)
- This type is not used anywhere in the trunk
comment:9 Changed 5 years ago by abeham
- Status changed from reviewing to readytorelease
comment:11 Changed 5 years ago by abeham
- Resolution set to done
- Status changed from readytorelease to closed
Note: See
TracTickets for help on using
tickets.
r15931: Implement TriangularMatrix deriving from ValueTypeMatrix. This choice was made to support multiple data types without having separate TriangularIntMatrix, TriangularDoubleMatrix, etc. Validation becomes more difficult but it is a compromise for a more generic matrix type.