Java + ассемблер

Сначала думал написать тут короткую заметку про то, как подружить Java и ассемблер, но потом решил написать об этом пост на Хабре, и не зря — получил инвайт.
Статья: http://habrahabr.ru/post/145804/

В общем, этим я занимался вчера, а сегодня я успел сделать еще кое-что, на еще один пост на Хабре не тянет, так что напишу здесь. Для понимания того, что я делаю, рекомендуется прочесть эту статью.

Читать далее…


ТЫРПРАЙЗНО

Писал я, значит, лабораторную работу по дискретной математике и решал задачу о поиске минимального остовного дерева в полном геометрическом графе, который был задан расположением своих вершин на плоскости. Мое решение получало Time Limit Exceeded на девятом тесте, который, если верить интуиции, должен быть не очень крупным. Я несколько раз тщательно сверил свой код с разными источниками и не нашел в нем ничего слишком медлительного. По крайней мере, асимптотика была верной.

Убедившись, что проблема не в алгоритме, я решил посмотреть подробнее, что же настолько тормозит мою программу. Первый вариант работал на максимальном (порядка 5000 вершин) тесте примерно 21 секунду. Я не буду описывать здесь все мои попытки оптимизации, так как это не имеет значения, скажу только, что расстояние между двумя точками я считал как Math.hypot(x[i] — x[j], y[i] — y[j]), и улучшить время работы до чего-то меньшего, чем 3 секунды, мне не удалось. На каком-то этапе у меня появилась мысль: может, надо быть проще и написать, как в старые добрые времена, квадратный корень из суммы квадратов? Конечно же, это никак не должно повлиять на производительность, ведь адекватные люди именно так и реализовали бы hypot(), подумал я, но все же попробовал. Результат был удивителен: время работы программы теперь составляло 332 миллисекунды!

Что, что можно делать в этом методе настолько долго? Проверять особые случаи по 100 раз? Вычислять результат десятью разными способами? Линчевать негров? Строить планы захвата галактики? К сожалению, добраться до определения метода hypot() мне не удалось, он native’ный. Надо бы все же найти его где-нибудь и посмотреть, что же там такое происходит.

P.S.: До этого дня я думал, что самая смешная sqrt/hypot-функция была в одной из версий Borland Delphi. Реализация содержала около 30 строчек delphi-кода сомнительного качества, который затем был закомментирован. Вместо него были написаны другой(тоже закомментированный, но уже хороший) код и ассемблерная вставка.

P.P.S: а вот и разгадка.