18 марта 2010 г.

Чем плохо synchronized(this)?

Несколько лет назад, бродя по исходникам JDK я задался вопросом -- почему там так часто встречается организация блокировки через
private final Object lock = new Object();
....

synchronized(lock){
...
}

хотя для этих целей легко можно использовать synchronized(this)? Я еще понимаю, если нужно несколько мониторов для разных наборов атомарных изменений (хотя, на мой взгляд, это часто первый звоночек что объекту нужна декомпозиция), но я часто видел такой код и когда монитор только один. Какое-то время это было для меня загадкой, пока у кого-то из гуру я не встретил ответа -- использование this как монитора синхронизации может нарушать инкапсуляцию вашего объекта. Монитор синхронизации -- это штука с состоянием: у него есть владелец (owner) который может меняться. Давая возможность клиентам работать с вашим объектом вы не можете запретить им работать с его монитором -- а это может менять его состояние, и нарушать те инварианты, на которые вы рассчитывали, проектируя класс.

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

Но вот вчера у меня, наконец, сложился явный и четкий пример. Итак, код:
public class Runner {

private Thread owner = null;

public synchronized void run( final Callable task ) throws Exception {
    owner = Thread.currentThread();
    try {
        task.call();
    } finally {
        owner = null;
    }
}

public synchronized void check() {
    final boolean invariant = ( owner == null ) || ( owner == Thread.currentThread() );
    if ( !invariant ) {
       //can this code be executed?
       throw new AssertionError( "Lock is broken: " + owner + " is owner, but " + Thread.currentThread() + " is here!" );
    }
}

}

на первый взгляд кажется, что код в строках 17-18 никогда не может быть выполнен. Оба метода синхронизированы, никакой посторонний поток не может влезть, пока текущий поток внутри run(Callable). Однако, сломать этот объект крайне просто:
final Runner runner = new Runner();

final Callable task = new Callable() {
    public Object call() throws Exception {
        runner.wait( 2000 );
        return null;
    }
};

final Thread thread = new Thread( "runner" ) {
    public void run() {
        try {
            runner.run( task );
        } catch ( Exception e ) {
            throw new RuntimeException( e );
        }
    }
};

thread.start();

//ensure thread started
Thread.yield();
Thread.sleep( 100 );
//check the invariant
runner.check();

object.wait() должен вызываться внутри synchronized(object), и, на время ожидания он отпускает монитор. То есть пока поток thread ждет 2 секунды на мониторе runner этот монитор свободен, несмотря на то, что выше по стеку есть synchronized(runner). И в эти 2 секунды любой другой поток может захватить этот монитор -- что мы и делаем, демонстрируя нарушение инварианта класса.

Какой отсюда вывод? Вывод такой: если вы используете callback интерфейсы -- т.е. если ваш код выполняет внутри себя какой-то другой код, пришедший "со стороны" -- вы должны делать это либо вне синхронизации, либо использовать монитор синхронизации, до которого клиентский код не сможет добраться, вроде private final Object lock = new Object()

На данный момент я не вижу других способов (кроме callback), как "открытая" синхронизация с помощью synchronized(this) может нарушить инкапсуляцию. Если класс колбэки не использует -- можно использовать синхронизированные методы спокойно.

17 марта 2010 г.

Чем отличается synchronized метод от synchronized(this) блока?

Аттрибут synchronized -- это флаг на методе. Компилятор не будет вставлять на выходе и выходе из метода инструкции захвата и освобождения монитора, как в случае с synchronized(this) блоком; вместо этого уже JVM, на стадии выполнения кода фиксирует наличие этого флага, и автоматически выполняет требуемый захват и освобождение монитора. То есть все различие -- флаг в описании метода вместо двух байт-кодов в его теле. Возникает вопрос: стоит ли беспокоиться из-за двух инструкций (инструкций байт-кода, не процессора!) Чаще всего -- нет. Но представьте себе, например, что JIT-компилятор использует количество байт-кодов в теле метода как одну из метрик для принятия решения о его инлайнировании? Что, кстати, почти наверняка так и есть...

Вольный перевод отсюда (сноска в конце страницы)

Ну так и в java коде синхронизированный метод выглядит заметно компактнее, чем метод, все тело которого обернуто в синхронизированный блок. Может, разработчики языка тем самым хотели на что-то намекнуть?

Синхронизация

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

В ближайшее время постараюсь уложить все у себя в голове в единую картинку, и написать сюда пару статей. Особенно хочется разобраться с volatile и Thread.interrupt(). Заодно, может быть, пока буду готовить статьи -- и сам, наконец, запомню :)

12 марта 2010 г.

Serialization libraries

Наткнулся на интересный "проект" по сравнению производительности различных способов/библиотек сериализации/десериализации в джава. Comparing varius aspects of Serialization libraries on the JVM platform Мало того, что лишний раз подивился на разницу в скорости стандартной сериализации с Externalizable, так еще и узнал о куче интересных библиотек. Например, Kryo выглядит вполне подходящей заменой стандартному механизму -- быстрее, нагляднее, архитектурно изящнее (механизмы сериализации настраиваются отдельно от сериализуемых объектов -- в отличие от стандартного метода, где объект в любом случае сам задает свой метод сериализации, и он может быть только один). А JSON Marshaller я собираюсь рассмотреть на место XStream в DataGuard -- все равно XStream-ский json даже после тщательной доработки напильником периодически генерирует ересь. Более того, в json marshaller есть и замена для org.json.* -- по их словам она более быстрая и более удобная.

11 марта 2010 г.

Со-процедуры (coroutines)

Не знаю русского эквивалента термина coroutines. Собственно, сам английский термин я узнал только сегодня -- хотя отдельные варианты сопроцедур -- генераторы и продолжения (continuations) -- встречал и раньше.

Так вот, сопроцедуры. Это такая штука, когда, наряду с обычным return вводится дополнительный способ завершения функции/процедуры -- обычно, его называют yield. В результате yield выполнение функции не завершается, а приостанавливается. Сохраняется состояние стека, локальные переменные. И в следующий раз, при вызове этой функции выполнение просто продолжится с того же самого места, где в прошлый раз был вызван yield.

Зачем это нужно? Ну во многих случаях это сильно упрощает программу. Например, я знаю веб-фреймворк для джавы , построенный на продолжениях (сontinuations, частный случай), где весь цикл взаимодействия с браузером может быть реализован в прямом смысле циклом -- for/while -- внутри одного метода (точнее, фреймворк написан на джаве, но код веб-приложения под него пишется на javascript/rhino). Когда нужно отправить данные пользователю ваш код просто вызывает что-то вроде var userResponse = postToUser(htmlPage); -- выполнение вашего кода приостанавливается на вызове postToUser, страница отправляется пользователю, он с ней что-то делает, результат отправляется на сервер -- и ваш код его получает в переменную userResponse, продолжая выполнение дальше. Очень изящно, гораздо проще, чем сервлеты.

Другой вариант -- всем известные генераторы, как замена итераторам.

В общем, штука удобная и интересная. К тому же, если верить автору, еще и достаточно быстрая. Если она в самом деле будет включена в jdk1.7 -- будет приятно.


Источник: http://classparser.blogspot.com/ via Levin Matveev blog

Syntax highlighter

Нашел себе подсветку синтаксиса для скриптов в блоге.

В теле поста пишем
<pre class="brush: java">
public static void main( final String[] args){
final int count = args.length;
System.out.println("count: "+count);
}
</pre>




и в результате получаем:
public static void main( final String[] args){
    final int count = args.length;
    System.out.println("count: "+count);
}


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

Подробности здесь: Awesome syntax highlighting

Numbers everyone should know

Numbers everyone (developer) should know (от разработчиков google)

* L1 cache reference 0.5 ns
* Branch mispredict 5 ns
* L2 cache reference 7 ns
* Mutex lock/unlock 100 ns
* Main memory reference 100 ns
* Compress 1K bytes with Zippy 10,000 ns
* Send 2K bytes over 1 Gbps network 20,000 ns
* Read 1 MB sequentially from memory 250,000 ns
* Round trip within same datacenter 500,000 ns
* Disk seek 10,000,000 ns
* Read 1 MB sequentially from network 10,000,000 ns
* Read 1 MB sequentially from disk 30,000,000 ns
* Send packet CA->Netherlands->CA 150,000,000 ns

9 марта 2010 г.

Smack XMPP

На выходных игрался с XMPP. Недавно на хабре был анонс простенькой текстовой игры через jabber: snow@talk2play.ru Мне поднадоело играть в нее самому, захотелось это дело автоматизировать. В итоге, после 3-х дней отладки мой бот более-менее устойчиво набирает очки. Нет ничего приятнее, чем смотреть, как кто-то делает твою работу...

Джабберовский XMPP протокол (и его реализация в Smack) произвел хорошее впечатление. Простой и расширяемый. В будущих проектах собираюсь попробовать предоставлять network interface через него -- на пару к обычному HTTP.

5 марта 2010 г.

Запуск внешних программ

Недавно в DataGuard пришлось разбираться с запуском внешних программ из java. Некоторые вещи оказались довольно нетривиальны, так что я решил поделиться.

На первый взгляд, все достаточно просто -- для простых случаев есть Runtime.exec(), если нужно настроить параметры среды для запуска -- есть ProcessBuilder. В любом случае получаем объект Process, у которого вызываем Process.waitFor(), чтобы дождаться завершения -- и, вроде бы, все?

К сожалению, ничего подобного. Несмотря на то, что API выглядит просто и очевидно, корректное его использование совсем не просто, и не очевидно. Какие конкретно подводные камни нас ждут?

Главный из них -- потоки ввода-вывода (IO streams). У порождаемого процесса нет терминала, к которому он привязан, его stdin, stdout, stderr выдаются порождающему процессу -- то есть, нам. Причем обрабатывать их -- наша обязанность. Потоки, созданные ОС имеют ограниченный размер буфера. Если, к примеру, буфер stdout для запущенного процесса заполнен, со стороны java никто его не читает (==не освобождает) а процесс настойчиво хочет что-то вывести -- то процесс просто окажется заблокирован на IO, и будет ждать, пока stdout кто-нибудь освободит. Если мы не предусмотрели в java код, читающий process.getInputStream() -- получается стандартный дедлок: мы ждем завершения процесса, процесс ждет нас.

Самый опасный момент здесь в том, что размер буфера заранее не определен. Поэтому приложение может в одном случае работать как часы, а в другом -- непонятно зависать.

Конкретный пример: в обычном, штатном режиме работы внешний процесс выдает одну-единственную строчку "Ок" и завершается. Строчка вполне влезает в буфер, поэтому код

final Process p = Runtime.getRuntime().exec( "my-script.bat" );  
final int retCode = p.waitFor();  

работает корректно. Но наступает день Х, когда звезды складываются неудачно. И процесс завершается с ошибкой. И, как и положено уважающей себя программе, старается эту ошибку максимально подробно описать. И пытается вывести в stdout простыню текста, превышающую размер буфера. Вуаля -- процесс ждет на выводе, java-программа -- на process.waitFor()

На мой взгляд -- это пример плохо спроектированного API. Простая вещь -- запустить внешний процесс не заморачиваясь с его выводом -- делается весьма нетривиально. Более того, из самого API это никак не следует. Да, в документации к Process это прописано, но я считаю, что хороший API это такой, использование которого, по крайней мере для простых задач, очевидно без документации. Можно было бы дополнить контракт, например, так: "если клиент не запросил process.getInputStream()/process.getErrorStream() до вызова process.waitFor() -- stdout/stderr внешнего процесса автоматически перенаправляются вникуда".

Но наши друзья из Sun этого не сделали, так что приходится отдуваться самим: ProcessRunner

Что делает: берет сконфигурированный ProcessBuilder, создает внешний процесс, запускает асинхронно "помпы", прокачивающие его потоки ввода-вывода либо в пустоту (если пользователь ничего не задал) либо из/в заранее заданные потоки. Метод ProcessRunner.execute() блокируется пока либо процесс не завершится, либо пока не будет вызван ProcessRunner.interrupt(). Пример использования:
final ProcessBuilder pb = new ProcessBuilder("my-script.bat");  
final ExecutorService pool = Executors.newFixedThreadPool(3); // нужно минимум 3 свободных потока в пуле 
final ProcessRunner pwd = new ProcessRunner( "run", pb,  pool );  

pwd.execute();  

final int retCode = pwd.getReturnCode();  
...
pool.shutdown();


В этом примере ввод-вывод my-script.bat будет просто выброшен. Другой пример:
final ProcessBuilder pb = ...;  
final ProcessRunner pwd = new ProcessRunner( "run", pb, POOL );  

final ByteArrayOutputStream out = new ByteArrayOutputStream();  
final ByteArrayOutputStream err = new ByteArrayOutputStream();  
pwd.setOutputStream( out );  
pwd.setErrorStream( err );  

pwd.execute();  

assertEquals( 0, pwd.getReturnCode() );  
final byte[] output = out.toByteArray();  
final byte[] errors = err.toByteArray();  

Здесь stdout/stderr будут считаны в предоставленные нами потоки. Обратите внимание, что если флаг ProcessBuilder.redirectErrorStream() выставлен в true, то stderr будет слит с stdout, и errors будет пуст.

Больше примеров использования можно посмотреть в тестах ProcessRunnerTest

25 февраля 2010 г.

Data Oriented Programming вместо ООП

Пара интересных статей:

Musings on Data Oriented Design

Pitfalls of Object Oriented Programming (GCAP)

Суть вопроса, который поднимают авторы, такова -- за последние 30 лет развития IT скорость выполнения команд процессором выросла почти в 50000 раз, но время ответа памяти на запрос (memory latency) уменьшилось всего лишь раз в 10. В итоге мы получаем, что "стоимость" запроса к памяти (в циклах процессора) выросла примерно в 400 раз.

При этом современные компиляторы очень хорошо умеют работать с кодом -- фактически, машинный код, получаемый на выходе из компилятора может вообще не иметь ничего общего, с тем, что изначально было написано человеком -- кроме того, что делает то же самое. Но компиляторы очень мало что делают с данными -- размещение данных в памяти (data layout) генерируемое компилятором фактически очень мало отличается от того, что задекларировал программист в коде (разве что компилятор добавит туда от себя что-то -- vtable например, да выровняет по границам машинных слов). Хотя при современном состоянии дел с memory latency было бы гораздо выгоднее оптимизировать расположение данных под выполняемые задачи.

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

Вместо этого предлагается программисту (пока компиляторы не научились) продумывать размещение данных в памяти исходя из того, как они будут обрабатываться. В частности, в презентации (pdf) Том Албрехт показывает, как им удалось в 3-4 раза ускорить обновление-прорисовку дерева объектов сцены (scene tree) за счет изменения компоновки данных (там, правда, еще про предсказание ветвлений упомянуто)

15 февраля 2010 г.

JCaptcha

Разбирался на прошлой неделе с JCaptcha. Хорошая библиотека, но документация -- отвратная. Огромный разрыв между beginners guide и реальным использованием никак не покрыт. То есть начинаешь читать 5 minutes integration -- все вроде просто. Шаг чуть дальше -- нигде кроме как в исходниках инфы не найдешь.

Последний раз так с MFC мучался в дремучих 90-х. Думал уже, в мире джава таких проектов нет...

Вот, для примера, "переведенный" мною с языка spring-configuration на java код инициализации службы генерации капч:

private static final ImageCaptchaService instance;// = new DefaultManageableImageCaptchaService();

private static final int FONT_SIZE_MIN = 25;
private static final int FONT_SIZE_MAX = 29;

private static final int HEIGHT = 40;
private static final int WIDTH = 200;

static {
//Шрифт, которым будет написана капча. Размер не важен
final Font font = new Font( "Times New Roman", Font.PLAIN, 12 );

//разные буквы разными шрифтами разного размера
final FontGenerator fontGen = new RandomFontGenerator( FONT_SIZE_MIN, FONT_SIZE_MAX, new Font[]{ font } );
//...и разными цветами 
final ColorGenerator colorGen = new RandomListColorGenerator( new Color[]{ Color.RED, Color.GREEN, Color.BLUE, Color.BLACK } );
//однотонный белый фон-подложка. здесь, по-сути, задается размер капчи
final BackgroundGenerator bgGen = new UniColorBackgroundGenerator( WIDTH, HEIGHT, Color.WHITE );
//вырезаем слова от 6 до 9 букв
final TextPaster textPaster = new RandomTextPaster( 6, 9, colorGen );
//список слов можно задать 
final FileDictionary dict = new FileDictionary( "toddlist" );
final WordGenerator wordGen = new DictionaryWordGenerator( dict );
//final WordGenerator wordGen = new ComposeDictionaryWordGenerator( dict );

final ComposedWordToImage wordToImage = new ComposedWordToImage( fontGen, bgGen, textPaster );

final CaptchaFactory factory = new GimpyFactory( wordGen, wordToImage );

final GenericCaptchaEngine engine = new GenericCaptchaEngine( new CaptchaFactory[]{ factory } );

instance = new GenericManageableCaptchaService( engine, 300, 500000, 1 );
}

12 февраля 2010 г.

JavaMail + SSL

Продолжение разбирательств. Краткий итог: итак, самый простой и надежный метод работы с SSL -- использовать
System.setProperty("mail.smtp.ssl.enable","true");

Все остальные настройки как в обычном smtp (только порт обычно 465 вместо 25). Работает с gmail -- проверено

Подробное описание:

Вариант с
System.setProperty("mail.transport.protocol", "smtps")

не работает. Точнее, не совсем работает -- не так, как ожидается. Раскопки в исходниках JavaMail (благо, они доступны) показывают, что свойство mail.transport.protocol используется только методом Session.getTransport() (который без аргументов). Но самой библиотекой этот метод не используется -- предполагается, что его вызывает клиентский код явно. Если вы отправляете почту через явно создаваемый транспорт, и получаете его через session.getTransport() -- свойство mail.transport.protocol будем иметь эффект. Если же вы, как я, отправляете почту через статический метод Transport.send(), то внутри него библиотека ищет подходящий транспорт через вызовом getTransport(Address), что отсылает нас к свойству mail.transport.protocol.rfc822 (rfc822 -- такой "тип адреса" у адреса электронной почты). Если хочется переопределить транспорт для такого типа адресов на smpts -- надо писать
System.setProperty("mail.transport.protocol.rfc822", "smtps");
, либо использовать session.setProtocolForAddress("rfc822", "smpts"). Если просто написать mail.transport.protocol = smtps, то Transport.send() это указание проигнорирует.

В числе прочего это означает, что если вы вместе с mail.transport.protocol = smtps укажете, как описано в документации, свойства типа mail.smpts.host -- они будут проигнорированы (использоваться будут свойства типа mail.smtp.host) и JavaMail будет ломиться на localhost (который используется в качестве адреса smtp сервера по-умолчанию).

JavaMail + SSL

Намучался искать нормальный (авторитетный) источник информации по отправке secure mail с помощью JavaMail. Secure -- это который через SSL и порт 465 (обычно).

В итоге нашел описание на самом java.sun.com (ссылка в заголовке).

Если я их правильно понял, есть 3 основных варианта (для самой свежей версии JavaMail -- 1.4.3)

Первый вариант просто указать системное свойство mail.smtp.ssl.enable=true. Провайдер вроде как должен сам понять, если имеет дело с секьюрным сервером.

Второй вариант -- последней версии можно использовать имя протокола smtps (pops, imaps) -- и, соответственно, все свойства задавать в виде mail.smtps.host, mail.smtps.port, etc.


Последний, самый старый вариант -- инсталлировать SSLSocketFactory через системное свойство mail.smtp.ssl.socketFactory.class

И еще гмайл и похожие сервера требуют установки свойства mail.smtp.starttls.enable=true.

В общем, JavaMail как обычно напоминает шаманские пляски.

5 февраля 2010 г.

String.trim()

Удивительно, но String.trim() не отбрасывает символ неразрываемого пробела 0x00A0. Я был просто поражен -- и нет даже никакой опции, как это убрать.

Более того, \s в регулярках тоже не считает 0x00A0 пробельным символом! Пришлось извращаться в духе [\s\u00A0]

3 февраля 2010 г.

Gallery of Processor Cache Effects

Блог разработчика из Микрософт Игоря Островского. Влияние кэша процессора на производительность

20 декабря 2009 г.

FBDataGuard в открытом бета-тестировании

FBDataGuard -- это агент мониторинга "здоровья" серверов баз данных под СУБД Firebird. Firebird -- одна из двух (вторая -- PostgreSQL) достаточно известных и широко используемых, и при этом полностью открытых и бесплатных СУБД на рынке.

Основной ее недостаток, как и у большинства open source продуктов -- низкий, по сравнению с коммерческими аналогами, уровень дружелюбности к пользователю. FBDataGuard -- продукт, который пытается как-то справиться с этим недостатком. Это агент, запускаемый в фоновом режиме на том же сервере, что и СУБД, и занимающийся непрерывным мониторингом ряда важных параметров БД, сервера СУБД, и самого хост-компьютера. Начиная от свободного места на дисковых разделах, количества временных файлов, состояния индексов БД, количества активных пользователей, параметров транзакций... Ну и многое другое -- всего списка я сам не помню. Плюс к тому, агент выполняет по расписанию револьверные бэкапы, собирает статистику использования БД (для анализа на предмет оптимизации), хранит актуальную версию метаданных (это в разы облегчает починку БД в случае ее повреждения) и еще всякое-разное. И если что-то ломается, или параметры выходят за заданные границы -- начинает спамить админа письмами с угрозами. Кроме того у агента есть http-based RESTfull API, для получения актуальной информации о текущем состоянии. И -- в качестве примера его использования -- ajax-based веб-страничка мониторинга и управления агентом (веб-консоль). Такая вот красотищща.


В общем, штука незаменимая, непонятно, как люди до сих пор без нее жили. Точнее, в общем-то, понятно -- каждый писал собственные скрипты для всех этих задач. Ну вот мы и решили, что это некошерно, в 21-ом то веке, когда космические корабли...

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

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

7 декабря 2009 г.

apache wicket

Обнаружил замечательнейший web framework -- apache wicket. Бросил безнадежное дело с написанием нашего проекта на PHP, за выходные переписал все на джаве под wicket, заодно изучая Wicket In Action.

В чем фишка wicket:
1. Шаблоны страниц -- чистый html, только аттрибуты типа wicket:id указывают, где будет привязка к динамическом содержимому. Т.е. шаблон можно верстать в любом редакторе html и просматривать в любом браузере.
2. Динамика для шаблонов -- чистая джава. view+controller вместе, как в swing. Вообще само программирование очень сильно напоминает свинг -- настолько, что поначалу даже непривычно. Постоянно ищешь где же здесь запрятан цикл request-response.
3. Шаблоны можно наследовать и агрегировать. Т.е. можно создавать повторно используемые компоненты, и включать их в другие шаблоны, и можно расширять существующие шаблоны/компоненты. Просто чудо.

Среди прочего, за выходные узнал, что по скорости java servlet container в разы превосходят php. Правда, хотят больше памяти. Так что мои опасения, что джава для фронтенда высоконагруженного веб-приложения не подойдет были не обоснованными.

30 ноября 2009 г.

нужен профайлер

"Преждевременная оптимизация -- корень всех зол". Ну если не всех, то как минимум половины. Вопрос в чем -- что нужно, чтобы эту самую преждевременную оптимизацию не делать?

Заметил -- по мере того, как растет опыт в области оптимизации, как обрастаешь всякими фишками и фишечками на тему "как тут и там немного выиграть в скорости и памяти" начинает возникать все большее искушение вставлять эти фишечки где только можно. В итоге джава, которую я люблю именно за то, что провоцирует писать понятно, превращается в С.

Спросил себя -- что нужно, чтобы искушение оптимизировать все и вся не возникало? Да все просто -- нужна уверенность, что когда проблемы с производительностью возникнут, можно будет четко сказать где. Другими словами -- если я знаю, что у меня есть инструментарий, позволяющий быстро и точно локализовать узкие места -- я буду писать красивый и понятный код. Если я знаю, что профайлер мы уже 3 года как не можем купить -- я оптимизирую все, что можно, на всякий случай.

28 октября 2009 г.

Очередные сложности со столкновениями тел. Краткое содержание предыдущих серий:

Сначала мы столкновения реализовывали упругими силами, расталкивающими тела. Недостатки -- силы должны быть большими, чтобы не допускать глубокого проникновения тел друг в друга, а это приводит к жесткости задачи и довольно большим погрешностям интегрирования. Как правило, даже в не очень сложных задачах энергия флуктуировала на уровне 10-5 что довольно много.

Потом мы реализовали идеальные столкновения. Столкновение 2-х идеальных (недеформируемых) твердых тел даже с учетом вращения можно аналитически точно рассчитать используя только законы сохранения энергии/импульса/момента импульса. На выходе -- идеальный биллиард практически без артефактов -- точность соблюдения законов сохранения достигала 15 знаков после запятой -- фактически, точность машинной арифметики.

Схема отлично работала пока мы не начали ее тестировать в гравитационных полях. Оказывается, если "положить" неупругий шарик на "пол" --плоскость (в поле тяжести), то он начинает (медленно но неуклонно) в нее просачиваться. Причина простая -- на каждом шаге интегрирования шарик приобретает небольшую скорость вертикально вниз, и чуть-чуть смещается тоже вниз. Т.е. к концу шага он оказывается чуть внутри плоскости. Движок collision detection фиксирует взаимопроникновение, движок столкновений отрабатывает физику столкновения, и "отражает" скорость шарика -- теперь он летит вверх. Если столкновение абсолютно упругое, этой скорости точь-в-точь хватает, чтобы к концу следующего шага оказаться там же, где он был в начале предыдущего -- у поверхности пола -- и все начнется с начала. Т.е. шарик будет просто колебаться с периодом 2*dt. Но если столкновение неупругое, то после отражения у шарика будет меньшая скорость, и он потеряет ее в гравитационном поле раньше, чем "выскочит" из взаимопроникновения с плоскостью. И следующий шаг (микропадение-отражение-микроподскок) начнет уже с точки чуть-чуть под поверхностью. Это чуть-чуть будет каждый раз увеличиваться, постепенно шарик будет просачиваться в пол.

Решение было довольно очевидным -- нужно делать коррекцию положения (position correction -- штука, хорошо известная в игровых движках, хоть там и несколько другая физика). Т.е. вместе с модификацией импульсов/моментов тел в ходе столкновения нужно "откатить время" назад, ровно чтобы оказаться в моменте, где объекты еще только-только соприкоснулись. Строго говоря, откатить, конечно, нужно всю систему, но для упрощения жизни мы начали откатывать только пару сталкивающихся тел. Тела перестали проваливаться.

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

И вот, очередной раунд. Создаем стакан (стенки+пол), поле тяжести, +20 шариков, столкновения неупругие. Через несколько секунд шарики скапливаются на дне стакана. И начинают довольно быстро просачиваться друг в друга и в пол.

Почему? Кратные столкновения. Наше приближение -- при коррекции положения откатывать надо всю систему, но мы откатываем только текущую пару тел -- работает удовлетворительно только если в системе достаточно "свободно", если столкновения только парные, если отматывая время для одной пары тел и убирая их взаимопроникновение мы, тем самым, не создаем взаимопроникновение другой пары тел. В случае стакана с шариками на дне это не так. Каждый шарик в контакте с 2-3-4 другими, а то еще и с полом или стенками. Получается, что для данного шарика коррекция положения будет суперпозицией коррекций для всех его столкновений с соседями. По факту, более-менее правильно пройдет только последняя коррекция, остальные превратятся черт знает во что. Вот это "черт знает" и видно на экране :)

Что будет следующей итерацией пока не знаю. Надо думать. Честно рассчитывать кратные столкновения нереально -- во-первых, только из законов сохранения более чем парное столкновение не рассчитать, во-вторых под это дело придется сильно корежить движок collision detection, в третьих сам алгоритм position correction для этого случая неочевиден.

В раздумьях

16 октября 2009 г.

Зарегистрировал домен и развернул сайт Матконструктора

Поскольку 1С в маркетинге не силен, а завоевывать мир нашему как-то надо, мы (команда, работавшая над его созданием) решили сделать независимый сайт, где и будет происходить все непотребство. А именно, встречайте -- mathkit.ru

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

P.S. ...и не думайте, что можно зайти втихоря, и никто не заметит. Я высоко сижу счетчик повесил, всех вас запишут. Приеду -- все узнаю, всех увижу. Вам будет стыдно.