Java: как написать быструю программу?

>как писать быстрые программы на Java

[anshlag]Первым делом берешь С...[/anshlag]

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

k&r? :)

Про выделение памяти я знаю. Это у нас на C++ уже давно всё есть. Просто хочется подробней про производительность Java узнать, чтобы знать где и на чём что теряется, а где не теряется.

>быстрые программы

>Java

/0

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

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

Блин! Та реализация что у тебя на С++ быстрей работала, естественно будет быстрей работать и на яве.

>Учитывая выбор реализации я уже буду проектировать классы и программу в целом, и я уже понимаю, что классы будут заметно отличаться от того, что у нас есть на C++.

Особо ничего отличаться не будет, если ты конечно не слишком сильно углублялся в плюснутые извращения:)

Интерено, как оно не будет отличаться, если на плюсах я использую std::vector со всеми его достоинствами, а в Java его нету. Приходится использовать простые массивы, а это уже совсем другая песня с точки зрения проектирования классов базовых структур данных и операций с ними.

А так, конечно, for он и в Java for...

P.S. Я углублялся в плюснутые извращения. :-)

>std::vector
а чем для вашей задачи ArrayList плох?

boxing/unboxing?

Седжвик Роберт «Фундаментальные алгоритмы на JAVA. Части 1-4. Анализ. Структуры даных. Сортировка. Поиск» (пер. с англ.)
Издательство:ДиаСофт
Год издания: 2003 г.
Кол-во страниц: 688 стр.
Переплет: твердый

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

http://code.google.com/p/google-collections/
http://trove4j.sourceforge.net/
http://pcj.sourceforge.net/
?

>Интерено, как оно не будет отличаться, если на плюсах я использую std::vector со всеми его достоинствами, а в Java его нету.

А это что тогда - http://java.sun.com/j2se/1.4.2/docs/api/java/util/Vector.html ?

http://www.ozon.ru/context/detail/id/1829400/

У Блоха есть немного об оптимизации.

Принимаешь хорошо тормозящие вещества... Профит!

Алгоритмы от языка не зависят. Теоретически на жабке массивы быстрее, чем коллекции, но из-за отсутствия указателей нет возможности быстро по ним бегать. А в остальном - как в плюсах. Может, и правда лучше _критичные_ алгоритмы в виде небольшой нативной либки сделать?

>Может, и правда лучше _критичные_ алгоритмы в виде небольшой нативной либки сделать?

Слишком много гиморроя. Но простой гуглинг по "Java demoscene" показывает что не так уж все и плохо. OpenGL-биндинг там конечно не используется.

> Теоретически на жабке массивы быстрее, чем коллекции, но из-за отсутствия указателей нет возможности быстро по ним бегать

arr[i] уже "не быстро"?

>но из-за отсутствия указателей нет возможности быстро по ним бегать. А в остальном - как в плюсах.

Уверен? Я — нет.
http://www.kano.net/javabench/
— Java уделывает C++ на хэшах и коллекциях. А так же у неё высокая скорость вызова методов и инстанцирования объектов в 4...10 раз.

Cкорость вызова методов в 10 раз быстрее чем в сипипи? чтото сказками попахивает

int *pElem = arr;
for (int i=0;i<SIZE;i++) {
  *pElem++ = i;
}
В этом случае нет арифметики для вычисления вида "база + смещение * размер элемента". Что влияет на скорость.

а я вот не уверен, что это можно оказать критичное влияние на скорость... сделаем бенчмарк?

> "база + смещение * размер элемента"

Умножение можно заменить сдвигом индекса влево на два (для int[], float[] и Object[]) или три (long[] и double[]) бита.

Сделайте:) Для остроты - возьмите не int, а структурку с размером, не являющимся степенью двойки.

Да, сдвиг быстрее умножения (хотя для больших структур сдвиг не поможет). Но лучше-то вообще без арифметики.

>> Интерено, как оно не будет отличаться, если на плюсах я использую std::vector со всеми его достоинствами, а в Java его нету.

> А это что тогда - http://java.sun.com/j2se/1.4.2/docs/api/java/util/Vector.html ?

А это может хранить только Java объекты и по сравнению с std::vector<double> будет ощутимо тормозить из-за постоянного boxing/unboxing.

Интересно, а HotSpot разве не сможет заоптимизировать подобный код на java:

int[] array = ...;
for (int i = 0; i < array.length; ++i) {
 array[i] = i;
}

??

на границы можно не проверять, доступ к элементам идет последовательный

>Да, сдвиг быстрее умножения (хотя для больших структур сдвиг не поможет). Но лучше-то вообще без арифметики.

В Жабе массивов структур нет, есть лищь массивы примитивов. BTW, я сейчас вспомнил что есть такая замечательная инструкция lea которая избавляет даже от необходимости делать сдвиг.

Жабка не может не проверять границы. Иначе обещание безопасности будет нарушено

>А это может хранить только Java объекты и по сравнению с std::vector<double> будет ощутимо тормозить из-за постоянного boxing/unboxing.

А в _твоей_ java есть не java объекты?

> Теоретически на жабке массивы быстрее, чем коллекции, но из-за отсутствия указателей нет возможности быстро по ним бегать.

Страуструп писал, что цикл через a[++i] и ++a должен в современных компиляторах исполняться с одинаковой скоростью.

Так что ява тормозит в других местах... интересно, кстати, в каких.

Ах да, я забыл - там же не "структуры" (в случае Object), а "массивы указателей на структуры". Значит, нужно время на разыменование.

Да, с lea должно быть быстро. Но вроде в нее не всякую арифметику запихать можно.

> Подскажите, пожалуйста, книгу, в которой написано, как писать быстрые программы на Java.

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

Но вопрос конечно интересный.

>Подозреваю, что могущие и желающие понять такую книгу давно освоили с++

И? То что они осилили с++ не значит что они на нём могут/хотят писать.

>Cкорость вызова методов в 10 раз быстрее чем в сипипи? чтото сказками попахивает

Скорость вызова _виртуальных_ методов за счёт run-time оптимизации, которая может инлайнить виртуальные функции. Плюсам такое на дано, потому джава может заруливать когда в прогремме сильная косвенность.

> А в _твоей_ java есть не java объекты?

http://java.sun.com/docs/books/tutorial/java/nutsandbolts/datatypes.html

>Страуструп писал, что цикл через a[++i] и ++a

По крайней мере VS compiler генерит одинаковый ассмблерный код.

>нтересно, а HotSpot разве не сможет заоптимизировать подобный код на java:

Учитывая то, что каждый доступ к оперативки ~150 тактов, к 16 следующим закешированным байтам по ~10 такутов, то сложение за 1-2 такта скорее всего не играет никакой роли.

> Скорость вызова _виртуальных_ методов за счёт run-time оптимизации, которая может инлайнить виртуальные функции. Плюсам такое на дано, потому джава может заруливать когда в прогремме сильная косвенность.

Реквестирую пример на обоих языках.

(Оптимизатор явы действительно может развиртуализировать методы, но в этом случае на плюсах нормальный человек *уже* написал невиртуальный метод.)

> Учитывая то, что каждый доступ к оперативки ~150 тактов, к 16 следующим закешированным байтам по ~10 такутов, то сложение за 1-2 такта скорее всего не играет никакой роли.

Не в какие ворота не лезет. Скорость прокачки памяти в районе 8 GB/s дает в районе 2 Гигаобращений в секунду.

>но в этом случае на плюсах нормальный человек *уже* написал невиртуальный метод.)

Если класс вообще кому-то полезен то его рано или поздно кото-то унаследует. А если нужный метод окажется невиртуальным, то будут искать аффтара с монтировкой.

>Не в какие ворота не лезет.

Это когда ЖД через DMA пишет. А когда проц обращается разово - то вот так. Можешь почитать спеки интеловские.

>Оптимизатор явы действительно может развиртуализировать методы, но в этом случае на плюсах нормальный человек *уже* написал невиртуальный метод

А вот нифига. Это действительно чувствуется в больших системах с высокой косвенностью - например на серверах с IoC и прочей плагинность.

Тут, конечно, можно выкрутиться, сказав, что двухядерник за время одного из таких обращений сделает 8 операций, но тратить два ядра на прокачку памяти? у них и другая работа найдется.

> А вот нифига. Это действительно чувствуется в больших системах с высокой косвенностью - например на серверах с IoC и прочей плагинность.

На серверах на яве? Ява успешно борется с теми трудностями, которых в плюсах нет.

Реквестирую еще раз примеры на обоих языках.

>Тут, конечно, можно выкрутиться, сказав

Про банальную высокую летентность

> Если класс вообще кому-то полезен то его рано или поздно кото-то унаследует.

Что ты отнаследуешь из класса DateTime? Или он никому не полезен?

>Реквестирую еще раз примеры на обоих языках.

На хелловорлдах это будет нагромождением. Посмотрите архитектуру Eclipse. На с++ такое не построить (да, чисто теоретически написать всё можно и на асме, но такие сферические предположения никому не интересны). И уж точно работать быстрее не будет.

Предложите код на плюсах, а мы попробуем портировать...

> На хелловорлдах это будет нагромождением.

Не боюсь.

> Посмотрите архитектуру Eclipse.

Она вполне могла быть заточена под яву.