История одной оптимизации



    Аннотация


    Статья раскрывает особенности высокоуровневых оптимизаций вычислительных алгоритмов на Java на примере кубического алгоритма перемножения матриц.

    Шаг 0. Установи точку отсчета!


    Определимся с окружением:
    • Hardware: 1-socket/2-cores Intel Core 2 Duo T7300 2GHz, 2Gb ram;
    • Java: HotSpot(TM) Client VM (build 17.0-b17, mixed mode, sharing);


    Рассмотрим простейший кубический алгоритм перемножения матриц. Пожалуй, его знает любой студент или даже школьник. К тому-же, принцип работы алгоритма прекрасно иллюстрирует картинка из википедии в начале статьи, поэтому останавливаться на его особенностях не будем.

    for (int i = 0; i < A.rows(); i++) {
    	for (int j = 0; j < A.columns(); j++) {
    		double summand = 0.0;
    		for (int k = 0; k < B.columns(); k++) {
    			summand += A[i][k] * B[k][j];
    		}
    		C[i][j] = summand;
    	}
    }
    


    В качестве workload`а возьмем две плотных квадратных матрицы N x N двойной точности (double precision), где N = 1000.

    В таком случае, время работы простого кубического алгоритма: 18.921 s. Будем считать это число точкой отсчета (baseline) для последующих оптимизаций.

    Шаг 1. Знай правило 20/80!


    Известно, что 80% времени работает 20% кода. Задача разработчика — вычислить эти самые 20% из всего объема кода. В нашем случае все очевидно — искомые 20% сосредоточены во внутреннем вычислительном цикле. С точки зрения JVM, этот код — наиболее вероятный кандидат на just-in-time компиляцию. Проверить компилируется ли байт-код в нативный можно с помощью опций — XX:+PrintCompilation -XX:+CITime.

    $ java -XX:+PrintCompilation la4j.Demo
      1       java.lang.String::hashCode (64 bytes)
      2       java.lang.String::charAt (33 bytes)
      3       java.lang.String::indexOf (151 bytes)
      4       java.lang.String::indexOf (166 bytes)
      5       java.util.Random::next (47 bytes)
      6       java.util.concurrent.atomic.AtomicLong::get (5 bytes)
      7       java.util.concurrent.atomic.AtomicLong::compareAndSet (13 bytes)
      8       java.util.Random::nextDouble (24 bytes)
      9       la4j.matrix.DenseMatrix::set (10 bytes)
      1%      la4j.matrix.MatrixFactory::createRandomDenseMatrix @ 30 (68 bytes)
      10      la4j.matrix.MatrixFactory::createRandomDenseMatrix (68 bytes)
      2%      la4j.matrix.DenseMatrix::multiply @ 81 (152 bytes)
    


    Из листинга видно, что метод перемножения матриц (la4j.matrix.DenseMatrix::multiply) был успешно скомпилирован. Это дает нам определенный простор для дальнейших действий. Во-первых, поробуем воспользоваться преимуществами final переменных. Известно, что при компиляции в нативный код они транслируются непосредственно в значения. Теоретически, замена границ матриц на final значения сократит обращения к памяти на 1000x1000x1000 раз. Вместо этого, значения будут подставлены непосредственно. Проверим теорию.

    final int aColumns = A.columns();
    final int aRows = A.rows();
    final int bColumns = B.columns();
    final int bRows = B.rows();
    				
    for (int i = 0; i < aRows; i++) {
    	for (int j = 0; j < aColumns; j++) {
    		double summand = 0.0;
    		for (int k = 0; k < bColumns; k++) {
    			summand += A[i][k] * B[k][j];
    		}
    		C[i][j] = summand;
    	}
    }
    

    Время работы алгоритма: 16.996 s ;
    Прирост производительности: ~11%;

    Шаг 2. Помни о Кеше!


    На самом деле, такая реализация будет работать всегда медленно. Итерация по “k”, обращается к элементам матрицы B по столбцам. Такое чтение очень дорогое, потому что процессору приходится каждый раз подкачивать (prefetch) данные из памяти, вместо того, чтобы брать их готовыми из кеша.

    Примечательно, что Fortran не имеет такой проблемы. Многомерные массивы в нем хранятся по столбцам. Поэтому, кеш будет эксплуатироваться как следует и штатная реализация кубического алгоритма будет работать в разы быстрее.

    На рассматриваемой платформе размер кеш линии (cache line size) первого уровня (L1) — 64 байта — это самая дешевая память для процессора. В нашем случае, 64 байта почти бесплатной памяти дают потенциал для получения целых 8 ячеек матрицы (sizeof(double) = 8) в место одной сопровождаемой еще и оверхедом от префетчинга.

    Проблема алгоритма в том, что он практически не использует этой возможности. При этом, случайный доступ к памяти (по столбцам) приводит к сбросу кеш линии и инициализации процедуры обновления кеш линии при каждом обращении.

    Попробуем исправить это и реализовать последовательный доступ к элементам матриц, чтобы получить максимальную выгоду от кеша. Для этого просто транспонируем матрицу B и будем обращаться к ее элементам по строкам.
    final int aColumns = A.columns();
    final int aRows = A.rows();
    final int bColumns = B.columns();
    final int bRows = B.rows();
    
    double BT[][] = new double[bColumns][bRows];
    for (int i = 0; i < bRows; i++) {
    	for (int j = 0; j < bColumns; j++) {
    		BT[j][i] = B[i][j];
    	}
    }
    
    for (int i = 0; i < aRows; i++) {
    	for (int j = 0; j < aColumns; j++) {
    		double summand = 0.0;
    		for (int k = 0; k < bColumns; k++) {
    			summand += A[i][k] * BT[j][k];
    		}
    		C[i][j] = summand;
    	}
    }
    

    Время работы алгоритма: 7.334 s;
    Прирост производительности: ~232%;

    Шаг 3. Думай!


    Кода стало больше, однако время работы сократилось почти в 2.5 раза. Неплохо. Однако, при просмотре кода бросаются в глаза очевидные недостатки. Главный из которых — много циклов. Попробуем сократить объем кода и сделать его изящнее, объединив операции транспонирования и умножения в один вычислительный цикл. При этом, транспонирование будет осуществляться не для целой матрицы а по-столбцам, по мере их надобности.

    final int aColumns = A.columns();
    final int aRows = A.rows();
    final int bColumns = B.columns();
    final int bRows = B.rows();
    
    double thatColumn[] = new double[bRows];
    
    for (int j = 0; j < bColumns; j++) {
    	for (int k = 0; k < aColumns; k++) {
    		thatColumn[k] = B[k][j];
    	}
    
    	for (int i = 0; i < aRows; i++) {
    		double thisRow[] = A[i];
    		double summand = 0;
    		for (int k = 0; k < aColumns; k++) {
    			summand += thisRow[k] * thatColumn[k];
    		}
    		C[i][j] = summand;
    	}
    }
    

    Время работы алгоритма: 3.976 s;
    Прирост производительности: ~190%;

    Шаг 4. Выбрасывай!


    Воспользуемся еще одним преимуществом Java — исключениями. Попытаемся заменить проверку на выход за границы матрицы на блок try {} catch {}. Это сократит количество сравнений на 1000 в нашем случае. Действительно, зачем 1000 раз сравнивать то, что всегда будет возвращать false и на 1001 раз вернет true.

    С одной стороны — сокращаем количество сравнений, с другой — появляется дополнительные накладные расходы на обработку исключений. Так или иначе, такой подход дает некоторый прирост.

    final int aColumns = A.columns();
    final int aRows = A.rows();
    final int bColumns = B.columns();
    final int bRows = B.rows();
    
    double thatColumn[] = new double[bRows];
    
    try {
    	for (int j = 0; ; j++) {
    		for (int k = 0; k < aColumns; k++) {
    			thatColumn[k] = B[k][j];
    		}
    
    		for (int i = 0; i < aRows; i++) {
    			double thisRow[] = A[i];
    			double summand = 0;
    			for (int k = 0; k < aColumns; k++) {
    				summand += thisRow[k] * thatColumn[k];
    			}
    			C[i][j] = summand;
    		}
    	}
    } catch (IndexOutOfBoundsException ignored) { }
    

    Время работы алгоритма: 3.594 s;
    Прирост производительности: ~10%;

    Шаг 5. Не останавливайся!


    На этом этапе я пока остановился, потому что достиг желаемой цели. Моя цель была обогнать самую популярную сейчас библиотеку по работе с матрицами — JAMA (первая строчка в гугле по запросу “java matrix”). Сейчас моя реализация работает примерно на 30% быстрее чем JAMA. Кроме того, относительно небольшие оптимизации привели к приросту почти в 600%, относительно начальной версии.

    Вместо заключения (это не реклама)


    Рассмотренный код является частью open-source проекта laj4. Это библиотека для решения задач линейной алгебры на Java. Над проектом я начал работать на 4-ом курсе в процессе изучения курса вычислительной математики. Сейчас la4j показывает отличную производительность и работает в несколько раз быстрее чем аналоги на многих задачах.

    Если кто-то заинтересовался и хочет подобным образом проводить вечера — пишите в личку :)
    Поделиться публикацией

    Комментарии 84

    • НЛО прилетело и опубликовало эту надпись здесь
        +3
        Эм. Что вас тут смутило?
          0
          меня смутило слово «непосредственно», и чем отличаются локальные переменные с final и без final.
            –1
            Все просто. Если участок байт кода компилируется в нативный то c final перменными будет примерно следующие:

            Для простой перменной:
            int a;
            for (int i=0; i<a; i++) { }
            


            Для final:
            final int a = 10;
            for (int i=0; i<10; i++) { }
            


            Т.е. на машинных инструкциях x86 команды сравнения/переходов будут применены не к переменной а к значению.
              0
              Я не эксперт, но по-моему на машинных инструкциях x86 команды сравнения применяются к регистрам процессора в любом случае.

              К тому же у вас в статье сравниваются в первом случае — вызов метода объекта, куда может включаются кучка дополнительных проверок, во втором — фиксация значений в локальных переменных. Мне кажется, final тут не при чем. Попробуйте сравнить тоже самое, только без слова final, должно получиться тоже время.
                0
                Команда сравнения CMP может применяться и для пары регистр/значение — не только для памяти. (http://siyobik.info/index.php?module=x86&id=35)

                Вызов метода влюбом случае заинлайнится, т.к. методы columns() и rows() очеь короткие. Если мне не изменяет склероз инлайнтится все что меньшее 35 байткодов (это настраивается).

                Простые переменные я пробовал. Прирост дают именно final.
                0
                А теперь скомпилируйте .java исходник, в одном случае с final перед локальной переменной, в другом случае без final, и сравните побайтно получившиеся .class файлы.
                  –1
                  Мне удалось убедиться, что с final значения инлайнятся уже в байткоде. в то время как без final явная переменная «int a» тоже исчезла, и вместо неё появилось

                  byte byte0 = 10;
                  for(int i = 0; i < byte0; i++);

                  смотрел jad'ом

                  Однако, это само по себе ничего не доказывает. Надо смотреть что именно производит jit.
                    0
                    С числовыми константами все понятно. Не о них речь. Вы сравните
                        final int aColumns = A.columns(); и
                        int aColumns = A.columns();
                    Автор утверждал, что с final будет быстрее. Я же говорю, что такого быть не может, поскольку байткод получается абсолютно одинаковым!
                      0
                      Вопрос такой. Тогда в чем по-вашему разница между final и не-final c точки зрения генеринруемого кода?

                      С точки зреня этапа компиляции понятно. final перменные неизменяемые. Их модификация приводит в ошибки компиляции.
                        +2
                        В байткоде нигде не остается информации о том, была ли локальная переменная final или не final, поэтому JIT о final ничего не знает, и генерируемый код ничем не отличается. Тем не менее, JIT и сам умеет определять, что значение переменной не меняется, и применять соответствующие оптимизации (common subexpression elimination, loop invariant hoisting...)

                        Следует отличать эту ситуацию от двух других:
                        — когда final приписывается к полям класса, в этом случае в байткоде имеется информация об атрибуте final поля;
                        — когда final локальные переменные используются в замыканиях (анонимных классах внутри метода) — в этом случае значения этих переменных передаются в конструктор анонимного класса. Впрочем, на производительность это также не влияет.
                          0
                          Спс за ответ. Не понимаю, почему я был уверен в обратном :)
                            0
                            Исправьте пожалуйста статью, чтобы не путать людей. Прирост производительности получаеться не из за ключевого слова final, а за счет вынесениея выражения из цикла.
          0
          Я бы до 2 пункта не догадался наверное… Полезные советы, спасибо!
            +1
            Пожалуйста :)
            +9
            См. тж. пункт 2.6.2 «Как оптимизировать матричное умножение» книги Дж. Деммеля «Вычислительная линейная алгебра». В нем обсуждается блочная версия матричного умножения.

            И не совсем корректно говорить, «что Fortran не имеет такой проблемы». В приведенном примере медленным будет обращение уже к элементам матрицы A[i][k].

            Если хочется добиться еще большей производительности, стоит взглянуть в сторону эффективных реализаций BLAS'овской dgemm.

            Также, как оказывается, по запросу «BLAS java» можно много чего нагуглить.

            Успехов!
              +2
              Про блочный алгоритм я знал и про Штрассена знал. Я хотел добиться сравнимой скорости без использования быстрых алгоритмов.

              Спс за советы :)
                0
                Как можно добиться скорости без использования быстрых алгоритмов? :)
                  0
                  Примерно так как описано в посте :) Включая мозг.
                  +1
                  Выходит что это скорее академический интерес, чем практическая работа? ведь иначе причин не использовать «быстрые» алгоритмы я не вижу.

                  Действительно основная стоимость в анализе мелких трюков оптимизации на приемре этого алгоритма, чем реальная оптимизация алгоритма умножения матриц, которую можно было бы использовать.
                0
                Не подскажете, в каком месте библиотеки непосредственно находится этот код?
                Параметры A, B и C имеют тип Matrix?
                  0
                  Я немного перефразировал код, чтобы он бы понятнее. Вам нужно смотреть класс la4j.matrix.DenseMatrix. Метод multiply(Matrix matrix);
                    0
                    Не вижу такого класса
                      +2
                        0
                        Только с небольшим зачечанием. Грязный хак с исключениями еще не попал в trunk. С точки зрения перформанса это хорошее решение. А вот с точки зрения стабилити — не уверен.

                        Я привел его просто для примера в статье. Возможно, скокро его закомичу.
                          0
                          Странно, в архиве нет. Они на гугл-коде не автоматически обновляются?
                            0
                            все, понял
                              0
                              Нет конечно :) Используйте SVN. В архиве не совсем актуальная версия.
                              0
                              isTreangle() -> isTriangle()
                                0
                                Кто то мне писал об этом уже. Спс, я исправлю :)
                        +2
                        Станет ещё быстрее если использовать простой массив вместо массива массивов («двумерного» массива)
                          0
                          Это хороший вариант и я его уже протестировал.

                          1) Скорости особо не прибавилось
                          2) Стала тяжелее операции создания матрицы.
                          3) Пропадает совместимость (большинство существующих решений хранят как массив в массиве) с third-party библиотеками.

                          В итоге я от него отказался.
                            0
                            Довольно странно. Размер N, на котором вы тестеруете, случайно не степень двойки?
                              0
                              Те же матрицы 1000 на 1000.
                          0
                          Очень понравилось как изложен ход мыслей при решении задачи по оптимизации. Пишите еще.
                            0
                            Спасибо :) Постараюсь. Еще можно много чего наоптимизировать :)
                            +1
                            Помнится ещё в лохматом 2007 году Алексей Тутубалин перемножением матриц процессоры «щупал»:
                            blog.lexa.ru/2007/01/04/o_peremnozhenii_matric_i_prochix_arxitekturnix_zamorochkax.html
                            Правда он все это делал на C.
                              –1
                              Спс за ссылку!

                              Там в таблице для матрицы 1024x1024 время 2.58 (что почти сравнимо с моим). Учитывая что это а) 2007 год б) Си в) Старый добрый VS2005.
                                +3
                                г) скорее всего более слабая машина? ;)
                                  0
                                  2x Opteron 275 далеко не более слабая машина. Я б сказал, может даже немного более мощная.
                                0
                                Странно. Обычно «щупают» решением СЛАУ.
                                  0
                                  А он потом этими же матрицам «щупает» CUDA…
                                  Вроде параллелятся они не плохо…
                                    0
                                    Да, параллелятся хорошо. Извините, не могу вспомнить, где в вычислительной физике нужны быстрые перемножения матриц и где эта операция была бы «горлышком бутылки». В 3D графике понятно, все преобразования пространства — перемножения матриц.

                                    А вот решение СЛАУ — это то, к чему сводятся решения разностных задач в неявных схемах и всевозможные методы конечных элементов. И вот они уже решаются блочной LU декомпозицией.
                                +20
                                Очередная порция вредных советов, основанная на неправильных измерениях.
                                Пожалуй, единственная содержательная оптимизация из вышеперечисленных — Шаг 2.

                                Во-первых, забудьте про Client VM — она уже в прошлом. На многопроцессорном компьютере с >=2GB RAM (т.е. практически на любом современном ноутбуке) предпочтительней запускать Server VM. К счастью, в новых релизах JDK больше не будет разделения на client/server, останется одна Tiered VM.
                                Во-вторых, вспомните про правила бенчмаркинга, если вдруг вы измеряете не так.

                                Теперь по оптимизациям.
                                    Шаг 1: final int aColumns = A.columns() писать неплохо, но эта оптимизация в любом случае выполняется C2-компилятором автоматически.
                                    Шаг 3: В случае Server VM на 64-битной системе применение этой «оптимизации» ухудшило результат на 3%. C2-компилятор лучше справляется с простой вложенностью циклов.
                                    Шаг 4: Вообще зло. Мало того, что использование исключений при нормальном поведении — крайне плохой стиль, так еще бросание Exception — самая дорогая операция в Java VM, исчисляемая десятками, а то и сотнями тысяч простых арифметических операций. При бросании исключения происходит деоптимизация фреймов (т.е. возврат из скомпилированного кода в интерпретируемый), проход по стеку с заполнением stack trace, поиск exception handler'а. Конечно, 1000 операций это слишком мало, чтоб заметить разницу, попробуйте вставить ловлю исключения во внутренний цикл. Кроме того, C2-компилятор умет сам избавляться от лишних проверок на выход за пределы массива (array bounds check elimination).

                                Вообще, пример с матрицами очень хорош для совсем другого рода высокоуровневых оптимизаций: распараллеливания вычислений и преобразования многомерных массивов в одномерные, но вы про них даже словом не обмолвились.
                                  –4
                                  О каком С2 вы говорите?

                                  1 ) Это библиотека для простых пользователей, которые даже не знают что Hotspot есть клиентский а есть серверный.
                                  2) Это не бенчмарка, где все еречисленные вещи (распараллеливание) были бы интерестными;
                                  3) Это библиотека. Еще раз повторю. Распараллеливание ее считается чуть ли не дурным тоном. Привидите мне хоти один пример (кроме MKL)? Считается априори, что пользователь если ему надо — сам напишет map-reduce код используя рутины библиотеки для парралельного исполнения.
                                    +5
                                    С1 и С2 — это условные названия JIT-компиляторов в Client VM и Server VM соответственно.
                                    Пользователям про них и не надо знать, тем более, что уже через год, думаю, Client VM почти нигде не останется.
                                    Я считаю, что не стоит делать из красивого и логичного кода некрасивый и нелогичный, называя это оптимизацией, только потому, что на устаревающей VM он работает чуточку быстрее.
                                      0
                                      Нет java, кроме сан, и оракл пророк ее :)
                                      0
                                      Похоже, что для Вас подобные задачи так и остались чисто алгоритмическо-математическими.

                                      Есть сотня кодов, где подобные задачи приходится распараллеливать:
                                      1) Enzo гидродинамический код с МГД и AMR (http://lca.ucsd.edu/portal/software/enzo)
                                      2) ZEUS: lca.ucsd.edu/portal/software/zeus-mp2

                                      Разве для Java нет BLAS/LAPACK?
                                      • НЛО прилетело и опубликовало эту надпись здесь
                                        0
                                        да что там сервер, похоже что автор без прогрева мерил, даже в клиенте были бы совсем другие результаты
                                          0
                                          Конечно без разогрева. Я пытался вопросизвести сценарий использования обычного пользователя. Как вы себе это представляете.

                                          «Пожалуйста, сначала умножте эти две матрицы 500 раз просто так, только потом умножайте на результат».
                                          • НЛО прилетело и опубликовало эту надпись здесь
                                              0
                                              Этим я и занимаюсь сейчас :) Потом обязательно напишу отчет с графиками и циферками, в котором будут почти все современные Java библиотеки для работы с матрицами.
                                          0
                                          А есть где-нибудь поподробнее про механизм выкидывания exceptions в Java? Для меня вот было откровением, что при этом происходит деоптимизация. Проход по стек трейсу и поиск хендлера не выглядит как тяжелая операция, я бы предположил, что вот потом разворачивание стека до этого хендлера будет заметно тяжелее, чем собственно поиск и анализ. Впрочем, это мои догадки, было бы любопытно поглубже узнать этот вопрос.
                                            0
                                            Не знаю, я по исходникам изучал :)
                                            Деоптимизация происходит не всегда (в частности, не требуется, когда exception handler есть в том же методе), а, вот, как раз для корректного разворачивания она нужна (т.к. один фрейм скомпилированного кода может соответствовать нескольким фреймам интерпретатора), для отпускания мониторов и т.п.
                                              0
                                              Крут, завидую белой завистью. А не помнишь где конкретно эти исходники брать, а то тоже очень интересно. И приблизительно куда глядеть. Ну если не сложно, если сложно не надо, мне просто любопытно.

                                              И еще, я вот не удивлюсь, что там какие-то оптимизации таки есть под это дело. Ну, надеюсь, что есть. А то деоптимизация на каждый эксепшен звучит устрошающе.
                                                +3
                                                hg clone http://hg.openjdk.java.net/jdk7/hotspot/hotspot
                                                

                                                src/cpu/x86/vm/sharedRuntime_x86_64.cpp
                                                OptoRuntime::generate_exception_blob — генерация прослойки на ASM, вызываемой из скомпилированного кода;

                                                src/share/vm/opto/runtime.cpp
                                                OptoRuntime::handle_exception_C_helper — обработка Exception в контексте VM;

                                                src/share/vm/runtime/sharedRuntime.cpp
                                                SharedRuntime::compute_compiled_exc_handler — поиск Exception Handler.
                                          +1
                                          А где параметры запуска? Где описание того как мерили время?
                                            0
                                            Запускал так: java MainClass
                                            Таймеры: t1 = System.currentTimeMillis(); routine(); t2 = System.currentTimeMillis(); t3 = t2 — t1;

                                            :) Что конкретно вы хотите тут увидеть?
                                              +2
                                              Сколько прогонов было сделано, прежде чем были получены циферки выше? Среднеарифметическое считали?
                                                –2
                                                Брал лучшее (меньшее) время из пяти запусков.
                                                  +1
                                                  По-хорошему, надо среднее время и среднеквадратичное отклонение указывать.

                                                  Ваша статья мне напомнила статью автора Varnish [1], сейчас вообще популярна тематика оптимизации под кеши и архитектуру процессора.

                                                  [1] queue.acm.org/detail.cfm?id=1814327
                                                    +1
                                                    Редко встретишь хорошую статью, где бенчмарки указаны со среднеквадратичным отклонением. Не любят «программисты» статистику.
                                            –1
                                            прикрутили бы еще какой-то метод с передачей произвольного количества матриц внутрь и реализацией такого вот:
                                            ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%B5_%D0%BF%D0%B5%D1%80%D0%B5%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86

                                              +2
                                              Насчет фортрана что-то не понял. В одной матрице идет по строкам, в другой — по столбцам. На фортране была бы абсолютно такая же ситуация, но для первой матрицы, нет?
                                              0
                                              >>Примечательно, что Fortran не имеет такой проблемы. Многомерные массивы в
                                              >> нем хранятся по столбцам. Поэтому, кеш будет эксплуатироваться как следует
                                              >> и штатная реализация кубического алгоритма будет работать в разы быстрее.

                                              Не будет там транспонирование в разы быстрее, а если будет то не по этой причине.
                                              Есть два варинта:
                                              а) Читать по строкам, писать по столбцам;
                                              б) Читать по столбцам, писать по строкам.

                                              Так вот, читать по строкам будет быстре, за счет того что вы вычитываете целый кэшлайн и чаще всего с хардварным префетчем. Запись застрянет в кэше и вполне возможно что «склеится» на следущих итерациях.
                                              Когда вы делаете блокинг (шаг 2) вы реализуете «софтварный» префетч, но тут надо подумать о ширине блока. После первого блока «миссов» начала следущих блоков будут у вас уже в кэше.

                                              В отличие от Java на С можно поиграться еще и с явными префетчами, сделанными чаще всего на интринсиках:
                                              msdn.microsoft.com/en-us/library/84szxsww%28v=vs.80%29.aspx
                                                +1
                                                Во-первых, blocking используется для обеспечения так называемой temporal locality of reference, во-вторых, во 2-м шаге используется не blocking, а техника обеспечивающая spatial locality of reference.
                                                0
                                                Проведите, пожалуйста, тесты приведённых реализаций с размером 1024*1024 и 1025*1025. Должны получится забавные цифры.
                                                  +2
                                                  С месяц пишу такой же топик о c++ :)
                                                    0
                                                    А как эти цифры соотностся с сишными библиотеками? Например с IPP? Интересно было бы увидеть сколько ещё можно выжать.
                                                      0
                                                      Сравниваться с Сишными думаю бесполезно. Сам писал одну реалзизацию (блочный алгоритм + openmp), работающую за 0.5 секунд на матрица 1000 на 1000 (на той же самой машине, что и java).

                                                      С MKL вообще все плохо. Врятли в мире быстрее нее что-то сможет перемножить матрицы.
                                                        0
                                                        Вот поэтому и интересно — хочется знать теоретический придел :)) Т.е. понятно, что в джаве некоторые оптимизации принципиально не сделать без поддержки JVM, но хочется знать как далеко до идеала :)
                                                          0
                                                          GOTO BLAS library вроде всегда уделывала MKL
                                                        +1
                                                        Использовать исключения в логике весьма неудачная идея
                                                          0
                                                          Согласен, поэтому данный ког не попал в библиотеку. Он рассматривался лишь в исселдовательских целях.
                                                          0
                                                          Шаг 4 у вас два раза
                                                            0
                                                            Спс, исправил :)
                                                            0
                                                            Всегда плюсую подобные статьи. Когда дочитав до конца приходишь к однозначному выводу, что текст понятен и ошибочен, то обсуждение/комментарии обещают быть информативными и полезными, а значит и достойны повисеть на главной…
                                                              –1
                                                              Ну чо?

                                                              Как уже говорилось, надо было измерять на HotSpot.
                                                              Во-вторых, да, тут много примеров как делать не надо.

                                                              Например — исключения для управления. На практике, это очень тормозная операция. По опыту могу сказать, что отказ от такого рода управления в пользу традиционного может дать прирост в несколько раз(если исключения кидались особенно интенсивно).

                                                              Еще полезно посмотреть доклад «Performance Anxiety» Joshua Bloch.

                                                              Опять же, кто мешает использовать blas? Или написать обертку для нативных библиотек?
                                                                0
                                                                Ну ничо!

                                                                А на чем по вашему я измерял, если не на HotSpot (читайте про окружение)?

                                                                За ссылку на доклад спс.

                                                                Идея заключается в реализации «pure java library» безо всяких стронних штучек. Практика показывает, что разработчики на Java стараются избегать подобных нативных вещей и все более склоняются в сторону чистых Java решений.

                                                                  –1
                                                                  Хм. да, я хотел написать HotSpot Server VM.
                                                                +3
                                                                Шаг 4 — это такой бред. Никогда не стройте так логику на исключениях.
                                                                  0
                                                                  Рассмотрим простейший кубический алгоритм перемножения матриц. Пожалуй, его знает любой студент или даже школьник.

                                                                  Видимо не все так просто. У вас там ошибка. Я понимаю, что статья не про это, но странно видеть одну и ту же элементарную ошибку в каждом листинге статьи.

                                                                  Поправьте пожалуйста, а то копипастят же!

                                                                  При перемножении матрицы A размерностью mxn и матрицы B размерностью nxk, должна получаться матрица C размерностью mxk. Ваш алгоритм будет работать корректно только для квадратных матриц.

                                                                  Детали тут

                                                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                  Самое читаемое