Opened 2 years ago

Closed 9 months 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 2 years ago by bburlacu

  • Description modified (diff)

comment:2 Changed 2 years ago by bburlacu

  • Status changed from new to accepted

comment:3 Changed 2 years ago by bburlacu

  • Owner changed from bburlacu to gkronber
  • Status changed from accepted to reviewing

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.

comment:4 Changed 2 years ago by bburlacu

  • Owner changed from gkronber to bburlacu

comment:5 Changed 2 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 23 months ago by bburlacu

r15934: Update project (include TriangularMatrix.cs)

comment:7 Changed 9 months ago by abeham

  • Owner changed from swagner to abeham

comment:8 Changed 9 months 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 9 months ago by abeham

  • Status changed from reviewing to readytorelease

comment:10 Changed 9 months ago by abeham

  • Keywords merged added

r17070: merged to stable

comment:11 Changed 9 months ago by abeham

  • Resolution set to done
  • Status changed from readytorelease to closed
Note: See TracTickets for help on using tickets.