SIMD: производительность нарезки матрицы ⇐ JAVA

[Anonymous]

Я хочу иметь возможность брать «срез» матрицы — относительно распространенную операцию в линейной алгебре.
На первый взгляд это похоже на тот алгоритм, который должен извлечь выгоду из SIMD — особенно потому, что наши индексы являются Int. Проходим цикл, вычисляем индекс, помещаем его в новый массив.

Код: Выделить всё

 extension (m : Matrix)
inline def slice2(rowRange: List[Int], colRange: List[Int]): Matrix =
val oldRows = range(rowRange, m.rows)
val oldCols = range(colRange, m.cols)
val numNewRows = oldRows.size
val numNewcols = oldCols.size

val newArr = NArray.ofSize[Double](oldCols.size * oldRows.size)
var idx = 0
while idx < newArr.size do
val i = idx / numNewRows
val colpos = oldCols(i)
val stride = colpos * m.rows
var j = idx % numNewRows
val rowPos = oldRows(j)
// println(s"i: $i || j: $j ${stride + rowPos} ")
newArr(idx) = m.raw(stride + rowPos)
idx += 1
end while
Matrix(newArr, (oldRows.size, oldCols.size))(using BoundsCheck.DoBoundsCheck.no)
end slice2

Вот реализация.

Код: Выделить всё

extension (m : Matrix)
inline def apply(rowRange: RangeExtender, colRange: RangeExtender): Matrix =
val oldRows: Array[Int] = range(rowRange, m.rows)
val oldCols: Array[Int] = range(colRange, m.cols)
val numNewRows = oldRows.size
val numNewcols = oldCols.size
val newArr = NArray.ofSize[Double](numNewcols * numNewRows)

val spd = DoubleVector.SPECIES_PREFERRED
val spi = spd.withLanes(java.lang.Integer.TYPE)
val l = spi.length()

val rowsArr = IntVector.broadcast(spi, numNewRows)
val oldRowsArr = IntVector.broadcast(spi, m.rows)

var idx = 0
while idx < spi.loopBound(newArr.size) do
val indexes = IntVector.broadcast(spi, idx).addIndex(1)
val iVec = indexes.div(rowsArr)
val j_vec = indexes.sub(iVec.mul(rowsArr))

val colStride = IntVector.fromArray(spi, oldCols, 0, iVec.toArray(), 0).mul(oldRowsArr)
val oldRow = IntVector.fromArray(spi, oldRows, 0, j_vec.toIntArray(), 0)
val toInsertIdx = colStride.add(oldRow)
DoubleVector
.fromArray(spd, m.raw, 0, toInsertIdx.toIntArray(), 0)
.intoArray(newArr, idx)

idx += l
end while

while idx < newArr.size do
val i = idx / numNewRows
val colpos = oldCols(i)
val stride = colpos * m.rows
var j = idx % numNewRows
val rowPos = oldRows(j)
// println(s"i: $i || j: $j ${stride + rowPos} ")
newArr(idx) = m._1(stride + rowPos)
idx += 1
end while
Matrix(newArr, (oldRows.size, oldCols.size))(using BoundsCheck.DoBoundsCheck.no)

end apply

Тесты проходит, но производительность... отвратительная.

Код: Выделить всё

Benchmark                     (len)   Mode  Cnt         Score          Error  Units
SlicingBenchmark.slice_loop2     10  thrpt    3  66054296.885 ± 11789323.861  ops/s
SlicingBenchmark.slice_vec       10  thrpt    3  11711099.686 ±  2576154.270  ops/s

Примерно в 6 раз медленнее, чем простой цикл while. Этот недостаток становится более острым по мере увеличения размера матрицы, что говорит мне о том, что дело не в стоимости установки. Похоже, что этот алгоритм значительно медленнее, векторизован.
Я начал разбирать его, пытаясь выяснить, где именно, и, к моему удивлению, это оказалась вот эта линия.
По моим оценкам, только это

Код: Выделить всё

      var idx = 0
while idx < spi.loopBound(newArr.size) do
val indexes = IntVector.broadcast(spi, idx).addIndex(1)
idx += l
end while

работает медленнее, чем вся зацикленная версия. Другими словами, генерировать индексы в векторизованной форме медленнее, чем выполнять весь алгоритм в цикле.
Можно ли этого ожидать? Я склоняюсь к тому, что это «ошибка», но я далек от своего понимания. Кто-нибудь еще получил подобные результаты? Кроме того, полоса ошибок огромна.

Код: Выделить всё

Benchmark                     (len)   Mode  Cnt       Score        Error  Units
SlicingBenchmark.slice_loop2     50  thrpt    3  707118.601 ± 204524.302  ops/s
SlicingBenchmark.slice_vec       50  thrpt    3  374814.713 ± 567035.529  ops/s

Хорошо, проблема в смене полосы движения. то есть это.

Код: Выделить всё

    val spd = DoubleVector.SPECIES_PREFERRED
val spi = spd.withLanes(java.lang.Integer.TYPE)

Я думал, что он просто обработает то же количество дорожек, что и Double Species. Я думаю, что да, но это сильно снижает производительность.

Подробнее здесь: https://stackoverflow.com/questions/790 ... erformance