14 августа 2009 г.

Решил перед уходом в отпуск протестировать "потолок" скорости расчета, на который можно рассчитывать в джаве. Для примера взял простейшую систему из N материальных точек (без столкновений, без вращений), в однородном поле тяжести. Все координаты развернул в линейные массивы double[], и реализовал стандартный Рунге-Кутты 4-го порядка. Итог: real-time (т.е. когда симуляционное время не отстает от реального) считается примерно 4500 объектов (jre1.6.0_14, -server -XX:+DoEscapeAnalysis, P4 3.2Ггц).

Для сравнения: когда у нас еще не было вращения и столкновений, в real-time обсчитывалось примерно 500 объектов. Т.е. я оцениваю так, что потенциал чисто низкоуровневых оптимизаций (развернуть структуры данных, улучшить cache-locality, b т.п.) у нас еще где-то на 300-500% прироста.

В качестве ориентировки переписал (матерясь -- забыл уже все) код на С++, запустил из под Visual Studio. Включил все оптимизации, которые нашел (__inline, глобальную оптимизацию, оптимизацию скорости, SSE2). Результат (примерный) -- процентов на 5-9% быстрее, чем в джаве
Вчера, наконец-то, вчерне закончил работу над вращением. Теперь у нас есть объекты с честными 3-мя вращательными степенями свободы, тензор момента инерции, и уравнения Эйлера для вращательной динамики. Но это еще только треть дела. У нас есть идеальные абсолютно упругие столкновения таких тел, в результате которых они могут приобретать момент импульса. Причем с точным (в пределах машинной точности) сохранением всех задействованных инвариантов -- энергии, импульса и момента импульса.

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

В планах неупругие столкновения и трение. А пока ухожу в отпуск

7 августа 2009 г.

тригонометрия

Тригонометрические функции в джаве довольно медленные. 1000 проходов по 100000 вычислений синусов на моей машине (P4, 3.2ГГц) выполняется за 8 секунд. Простейшая аппроксимация Тейлора с пятым порядком включительно выполняется в 10 раз быстрее, при этом дает 9-10 верных знаков на интервале (-0.1, 1). И, насколько я помню, аппроксимация Тейлора еще не лучшая для этой цели. Так что если вам нужна быстрая тригонометрия для небольших углов -- добро пожаловать назад в 80-90-е,

5 августа 2009 г.

JStackAlloc

Пока изучал JBullet наткнулся там на интересную вещь. Автор довольно прямолинейно портировал С-шный Bullet, и наткнулся на проблемы с производительностью из-за большого количества создаваемых объектов типа Vector3d, Matrix4d и тому подобных легковесных "value objects" -- в С++ они, понятно, создавались на стеке. В итоге он сделал финт ушами -- создал небольшую библиотечку JStackAlloc, которая эмулирует выделение объектов на стеке для джавы.

В коде мы пишем такую штуку:
public static Vector3f average(Vector3f v1, Vector3f v2, Vector3f out) {
     out.add(v1, v2);
     out.scale(0.5f);
     return out;
}

public static void test() {
     Vector3f v1 = Stack.alloc(Vector3f.class);
     v1.set(0f, 1f, 2f);

     Vector3f v2 = Stack.alloc(v1);
     v2.x = 10f;

     Vector3f avg = average(v1, v2, Stack.alloc(Vector3f.class));
}


* This source code was highlighted with Source Code Highlighter.


после чего над скомпилированным кодом выполняется небольшой ant-task, который, используя ASM модифицирует байт-код класса, превращая его в что-то вроде

public static void test() {
     $Stack stack = $Stack.get();
     stack.pushVector3f();
     try {
         Vector3f v1 = stack.getVector3f();
         v1.set(0f, 1f, 2f);

         Vector3f v2 = stack.getVector3f(v1);
         v2.x = 10f;

         Vector3f avg = average(v1, v2, stack.getVector3f());
     }
     finally {
         stack.popVector3f();
     }
}


* This source code was highlighted with Source Code Highlighter.


Внутри $Stack для каждого потока (ThreadLocal) заводится обычный стек для каждого типа объектов. В общем-то ничего особо нового, просто самые тупые ручные операции (не забыть на каждый alloc сделать push в начале метода, pop в конце, обернуть в finally), кроме того порядком загрязняющие код делаются в автоматическом режиме на стадии компиляции, и в исходном коде не заметны. По словам Джезека (автора) он таким образом сумел получить приемлемую производительность для своей библиотеки.

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

С другой стороны, в 1.6.0_14 появилась экспериментальная поддержка escape analysis, который должен разбираться как раз вот с такими вот случаями временных объектов в рамках одного метода. Так что, скорее всего, библиотечка немного запоздала. Ее бы во времена 1.5...