27 августа 2010 г.

Immutable vs Mutable объекты

Когда я узнал, что final поля "гарантированно видимы любому потоку" после завершения инициализации, я подумал, что ведь это чего-то да стоит. В том смысле, что создание immutable объекта с final полями должно быть дороже (как минимум, в многопоточном окружении, чтобы JIT не смог это оптимизировать). Т.е. как минимум нужен же мембар по завершении конструктора. Сегодня попытался это проверить -- объявил два идентичных класса, у одного из которых все поля final, и создавал их в 150 потоков параллельно. Черта с два -- одинаково. Даже наоборот, есть слабое преимущество у immutable класса, но я бы не назвал его статистически значимым -- где-то 0.5%, слишком мало, чтобы принимать во внимание в случае микробенчмарка.

P.S. Постфактум это становится довольно очевидным. Семантика final полей обеспечивается StoreStore барьером между инициализацией полей и публикацией ссылки на созданный объект:

localRef = alloc(...);
localRef.field1 = ...;
localRef.field2 = ...;
....
StoreStore;
globallyAvailableRef = localRef;

Но на x86, где я тестировал, StoreStore барьер не нужен -- тамошняя "железная" модель памяти (TSO -- total store order) достаточно строгая сама по себе.

Более того, по словам DL в его кулинарной книге StoreStore барьеры, даже если они и требуются на какой-то архитектуре, обычно одни из самых дешевых. Так что, с высокой степенью вероятности, их влияние на производительность даже там, где они есть (и требуются) будет теряться на фоне, например, затрат на выделение памяти

Производительность

Тестировал, ради интереса, пиковую производительность разных методов доступа к разделяемому состоянию в многопоточном окружении. Участники соревнования -- sunchronized, ReentrantLock, AtomicInteger, volatile+AtomicIntegerFieldUpdater.

Результаты, в целом, предсказуемы -- атомики в 2-3 раза быстрее блокировок. Две интересные вещи:


ReentrantLock опять обогнал synchronized! Заметно -- на четверть почти. Как-то я уже обнаруживал этот феномен. До сих пор не могу понять, в чем здесь цимус -- Сановцы забили на оптимизацию "старого" способа синхронизации? -- но на ус придется намотать :)


AtomicInteger немного обогнал volatile+AtomicIntegerFieldUpdater. Чуть-чуть -- процентов на 5 в среднем. Не то, чтобы неожиданно -- накладные расходы на reflection-based доступ -- но все же приятно видеть их вживую в цифрах. Разница есть, она измерима, но по величине явно не критична. Т.е. на AtomicIntegerFieldUpdater можно закладываться как на альтернативу AtomicInteger.

22 августа 2010 г.

Lock-free BufferedQueue

Дали тестовое задание перед собеседованием -- написать буфферизированную очередь. Т.е. на вход метода append(T item) из нескольких потоков сыплются некие объекты, и, раз в какой-то интервал времени, задаваемый при создании, накопившиеся объекты сбрасываются списком в заранее заданный callback. Причем, понятно, очередь должна иметь как можно большую пропускную способность, т.е. засинхронизировать метод append -- это не выход.

Первая моя версия использовала ReadWriteLock -- неэксклюзивным ReadLock-ом защищался append, эксклюзивным WriteLock-ом -- flush. Но потом я взмедитнул, и подумал, что блокировки там вообще лишние. И получилась у меня lock-free версия вот такой:
public class LockFreeBufferedQueue<ItemType> {

private final ICallback<Collection<ItemType>> callback;
private final long delay;
private final TimeUnit timeUnit;

private final ScheduledExecutorService executor;

private final CallableVoid> flushBufferTask = new Callable<Void>() {
public Void call() {
assert ( pending.get() > 0 ) : "Call without being scheduled";
flushBuffer();
return null;
}
};

private final AtomicInteger pending = new AtomicInteger( 0 );

/**
* volatile чтобы обойтись без блокировки в методе isClosed()
*/
private volatile boolean closed = false;

private volatile ScheduledFuture<Void> scheduledTask = null;

/**
* lock-free Queue implementation
*/
private final ConcurrentLinkedQueue<ItemType> queue = new ConcurrentLinkedQueue<ItemType>();

public LockFreeBufferedQueue( final ICallback<Collection<ItemType>> callback,
final long delay,
final TimeUnit timeUnit,
final ScheduledExecutorService executor ) {        
this.callback = callback;
this.delay = delay;
this.timeUnit = timeUnit;
this.executor = executor;
}

/**
* Не специфицированно, что должен делать метод close(), поэтому мы делаем так:
* 
* Уже добавленные задачи будут выполнены немедленно, в текущем потоке, добавление
* новых приведет к IllegalStateException в методе append().
*/
public void close() {
if ( !closed ) {
closed = true;
if ( scheduledTask != null ) {
if ( scheduledTask.cancel( false ) ) {
flushBuffer();
}
scheduledTask = null;
}
//todo but if executor is external?
executor.shutdown();
}
}

/**
* @throws IllegalStateException если очередь уже закрыта вызовом close()
* @throws NullPointerException  если item == null
*/
public void append( final ItemType item ) {
if ( closed ) {
throw new IllegalStateException( "Queue was closed" );
}

queue.add( item );

if ( pending.getAndIncrement() == 0 ) {
schedule();
}
}

private void flushBuffer() {
final int size = pending.get();

assert ( !queue.isEmpty() ) : "Call with empty queue";
assert ( size > 0 ) : "Call with 0 pending";

final Collection<ItemType> buffer = new ArrayList<ItemType>( size );

for ( int i = 0; i < size; i++ ) {
buffer.add( queue.poll() );
}

if ( pending.getAndAdd( -size ) > size ) {
schedule();
}

//todo что делать с исключениями?
callback.call( buffer );
}

private void schedule() {
scheduledTask = executor.schedule( flushBufferTask, delay, timeUnit );
}

public boolean isClosed() {
return closed;
}
}
//=============================
public interface ICallback<T> {
public void call( final T arg );
}


Это первый мой опыт в самостоятельном написании lock-free алгоритмов на CAS-примитивах, поэтому написал я этот код часа за два, а медитировал над ним дня 3. Но косяков так и не нашел -- все должно работать как задумано. Увлекательное это занятие -- обдумывать корректность таких алгоритмов, мозг работает явно на повышенных оборотах

18 августа 2010 г.

Clipboard

Несколько дней уже разбираюсь с задачей экспорта картинки из Матконструктора в офисный пакет. Хочется картинку выдавать векторную, чтобы в, скажем, Word можно было ее потом масштабировать и редактировать как удобно. Собственно, экспортировать картинку в какой-нибудь векторный формат не проблема -- библиотека FreeHEP дает сразу полдюжины вариантов, от SVG до родного виндового EMF. Вопрос в том, как объяснить буферу обмена, что тот набор, казалось бы, случайных байт, что в нем лежит -- это не данные датчика случайных чисел, а-таки EMF.

Оказывается, сделать это все-таки можно. Похоже, первыми на решение набрели разработчики JFreeChart (во всяком случае, остальные источники ссылаются на них как на оригинал). Внимание, сейчас будет фокус:

//на самом деле mime-type здесь не важен, 
//можно использовать image/emf, application/emf, image/x-mgx-emf, etc
public static final DataFlavor EMF_FLAVOR= new DataFlavor("image/x-emf", "Enhanced Meta File");

static {
    // EMF graphics clipboard format
    try {
        final SystemFlavorMap sfm = (SystemFlavorMap)SystemFlavorMap.getDefaultFlavorMap();
        sfm.addUnencodedNativeForFlavor(EMF_FLAVOR, "ENHMETAFILE");//seems to be a key command!!
    } catch(Exception e) {
        e.printStackTrace();
    }
}

(источник)
Если я все правильно понял, волшебное заклинание sfm.addUnencodedNativeForFlavor(EMF_FLAVOR, "ENHMETAFILE"); объясняет джаве, что данные, маркированные как EMF_FLAVOR при передаче в системный буфер обмена никак не надо обрабатывать, надо отдать их туда как есть (массивом байт), и снабдить описанием типа "ENHMETAFILE". Интересно, какие еще типы можно так передавать? Пока я нашел только вариант, где удалось передать MathML.

Второй способ придумал автор Java Vector Cut and Paste Library. Финт ушами -- формат rtf поддерживается джавой из коробки, в том числе его передача через Clipboard. А rtf может служить контейнером для таких форматов как MACPICT, EMF и WMF. Через одно место, но уже неплохо -- в частности, MACPICT по его словам понимается как на Windows так и на Mac OS X. Но rtf не воспринимается, например, PowerPoint-ом -- в отличие от первого способа.

4 августа 2010 г.

MAC-адрес в java

Периодически обнаруживаю в JDK функциональность, которую я там не ожидал. Например, сегодня узнал, что можно получить MAC-адрес сетевой карты вызовом NetworkInterface.getHardwareAddress(). Причем судя по документации, метод еще с 1.4 тянется. А я почему-то был уверен, что хрен там, а не MAC из java. Приятная неожиданность.