Почему рекурсия может вызвать разрывы во времени обработки? ⇐ JAVA

[Anonymous]

Я занимаюсь оптимизацией алгоритма Штрассена-Винограда для умножения матриц на Java. Я прочитал в Википедии об алгоритме Штрассена, что «если матрицы достаточно неквадратные, имеет смысл сократить начальную операцию до более квадратных произведений», поэтому я измерил время расчета для различных соотношений сторон матрицы, чтобы найти то, что я тоже считаю » unsquare», в зависимости от требуемого времени обработки. Однако при сборе данных выяснилось, что формула времен не является непрерывной. Соотношение сторон выше ~1,28 приводило к увеличению времени вычислений алгоритма примерно в 10 раз, как показано на следующем изображении:



Умножение выполнялось на матрицы размеров [A X B] * , где B является постоянным во время теста, Соотношение сторон 1 > — это A/B, а Соотношение сторон 2 — это C/B, где A и C различаются.
Я ожидал, что этот разрыв сместится при изменении B, но при значениях 50, 100 и 200 разрыв поверхности остался на том же месте.
Используя собственный таймер, который работает с рекурсивными функциями, я обнаружил, что единственным замедлением при пересечении этого порогового соотношения сторон являются рекурсивные части моей функции. Они выглядят так:

Manix u, v, w; // u = (A[2] - A[0]) X (B[1] - B[3]) u = A[2].sub(A[0], NumberType).fastDot(B[1].sub(B[3], NumberType), NumberType); // v = (A[2] + A[3]) X (B[1] - B[0]) v = A[2].add(A[3], NumberType).fastDot(B[1].sub(B[0], NumberType), NumberType); // w = A[0] X B[0] + (A[2] + A[3] - A[0]) X (B[0] + B[3] - B[1]) w = ABNaught.add(A[2].add(A[3].sub(A[0], NumberType), NumberType).fastDot(B[0].add(B[3], NumberType).sub( B[1], NumberType), NumberType), NumberType); /* Штрассен-Виноград: * * | A[0] X B[0] + A[1] X B[2] v + w + (A[0] + A[1] - A[2] - A[3]) X B[3] | * | | * | u + w + A[3] X (B[1] + B[2] – B[0] – B[3]) u + v + w | * * Обратите внимание, что A[0] X B[0] используется здесь и в w, то есть нам нужно вычислить только 7 умножений вместо 8. */ Маникс[] ProductLayer = { ABNaught.add(A[1].fastDot(B[2], NumberType), NumberType), v.add(w, NumberType).add(A[0].add(A[1], NumberType).sub(A[2], NumberType).sub(A[3], NumberType).fastDot(B[ 3], номертипа), номертипа), u.add(w, NumberType).add(A[3].fastDot(B[1].add(B[2], NumberType).sub(B[0], NumberType).sub(B[3], ТипНомера), ТипНомера), ТипНомера), u.add(v, NumberType).add(w, NumberType) }; Тестирование функций add и sub, используемых в этом разделе кода, не выявило никаких отклонений. Единственные функции, оставшиеся в разделе-нарушителе, — это рекурсивные вызовы fastDot.
При сборе данных я ожидал увидеть гладкую, а не прерывистую поверхность. Мое единственное объяснение состоит в том, что это связано с накладными расходами Java на вызовы функций, но ничего конкретного. Может быть, кто-нибудь, обладающий большими знаниями о компиляторе Java, попытается объяснить этот феномен?