Крылья, ноги... Хвост!

java: cache padding

noreply@blogger.com (Vladimir Dolzhenko) — Mon, 09 Jan 2012 17:11:00 +0000

Думаю, что многие уже наслышаны о магии cache padding в disruptor'е.

Однако, куда более интересный факт - наличие cache padding'а уже в самом jdk 1.5 java.util.concurrent.Exchanger:

    /**
     * A Slot is an AtomicReference with heuristic padding to lessen
     * cache effects of this heavily CAS'ed location.  While the
     * padding adds noticeable space, all slots are created only on
     * demand, and there will be more than one of them only when it
     * would improve throughput more than enough to outweigh using
     * extra space.
     */
    private static final class Slot extends AtomicReference<Object> {
        // Improve likelihood of isolation on <= 64 byte cache lines
        long q0, q1, q2, q3, q4, q5, q6, q7, q8, q9, qa, qb, qc, qd, qe;
    }

добавлено: Спасибо вопросу Артёма и последующей дискуссии Рустана - в продолжении темы Руслан задал этот вопрос в concurrency interest, где участвовал и Doug Lea.

Внимательно читайте исходники и да прибудет с вами просветление.

Задачка: Сортировка по частоте

noreply@blogger.com (Vladimir Dolzhenko) — Sun, 18 Dec 2011 09:19:00 +0000

Дан (очень) большой массив целых чисел, необходимо отсортировать по частоте появления элемента в массиве.
Ограничения: постоянная память, сложность O(N log(N)).

Пример:
[ 1 3 1 ] -> [ 3 1 1 ] т.к. частота(3) = 1; частота(1) = 2
[ 7 1 1 0 ] -> [ 7 0 1 1 ]
[ 9 1 0 1 3 1 3 3 ] -> [ 9 0 1 1 3 3 3 ]

java: autoboxing и ==

noreply@blogger.com (Vladimir Dolzhenko) — Sat, 19 Nov 2011 19:37:00 +0000

С появлением java 5 появилась и такая вещь как auto boxing, на мой взгляд штука скорее вредная, чем полезная, но не суть.

Наверняка многие java программисты сходу могут ответить на вопрос «какой будет результат ?»

        Integer a = 100;
        Integer b = 100;
        Integer c = 300;
        Integer d = 300;
        
        System.out.println(a == b);
        System.out.println(c == d);

Тем более, что многие книги, как то Java Puzzlers, упоминают об этом.

Всё бы ничего, да только вот многие не знают, что cache можно расширить, точнее его вернюю границу:

-Djava.lang.Integer.IntegerCache.high=300

и результат выше приведённого примера в обоих случаях будет true.

p.s. чем равно -Integer.MIN_VALUE ?

Spring Boostrap

noreply@blogger.com (Vladimir Dolzhenko) — Fri, 28 Oct 2011 11:14:00 +0000

We uses spring framework within each our project. I would like to share some small and useful tricks we use in our Bootstrap class.

To load any xml spring context you have to run smth like


try {
    final ClassPathXmlApplicationContext ctx = 
        new ClassPathXmlApplicationContext(
            new String[] {"application-context.xml"});
} catch ( final Throwable th) {
    log.error("Unable to start the context : " + th.getMessage(), th);
}

It's enough in the most cases.

For sure - it should be one main class in the whole project or several.

As well it would be better to add some more functionality there :

ctx.registerShutdownHook() - close context & releasing all resources on jvm shutdown
log4j (or what do you prefer to use?) initialization - just org.apache.log4j.BasicConfigurator.configure() call.
set the default java.lang.Thread.UncaughtExceptionHandler - it helps if some thread dies occasionally - at least you have a chance to log the exception for further investigation of the root cause - otherwise, thread will die peacefully and silent.
addBeanPostProcessor instance at createBeanFactory method. It handles bean initialization phase:
- just before bean start
  - to be sure where is the bean's class source location - just from properly packed jar-file or some hot-fix bypass.
  - start timeout watchdog - if some start time of bean exceeding the reasonable threshold (e.g. 1 minute) and initialization hasn't been finished yet - put a warning message to have an earlier issue detection - probably the bean depends on some external system (as database) that unavailable at the moment of start.
- after initialization - put a log message how long bean started

Два презерватива на необитаемом острове

noreply@blogger.com (Vladimir Dolzhenko) — Mon, 15 Aug 2011 19:52:00 +0000

Волею судьбы на необитаемом острове оказалось четверо: двое мужчин и еще две прелестные дамы.

Через какое-то время природа взяла свое и было решено «заняться любовью», однако выяснилось, что все четверо болеют венерическими заболеваниями, причем все - разными.

Поскольку никто не желал добавлять себе еще одно, то после некоторых поисков было найдено два презерватива.

Как провести все четыре возможные встречи между разнополыми партнерами?

внимание! комментарии содержат ответ.

Задачка: 12 монет и 3 взвешивания

noreply@blogger.com (Vladimir Dolzhenko) — Wed, 13 Jul 2011 06:54:00 +0000

Есть 12 монет и аптекарские весы с двумя чашами, которые могут показывать больше, меньше и равно.

Известно, что одна из монет фальшивая - отличается только по весу, причём не известно - тяжелее ли она настоящей или легче.

Как при помощи только трёх взвешиваний определить какая монета фальшивая и тяжелее ли она или легче настоящей ?

Android: HTC MyTouch 4G

noreply@blogger.com (Vladimir Dolzhenko) — Wed, 08 Jun 2011 11:54:00 +0000

Вот уже почти месяц как я счастливый обладатель g-phone от HTC - MyTouch 4G, он же HTC Glacier. Изначально бюджет был определён как 10т.руб за новый Android с cpu класса 1GHz и ram не менее 512Mb - в итоге поторговавшись на ebay был получен данный аппарат. В бюджет самого телефона уложился и ещё ~$40 пришлось отдать за пересылку из Америки в Россию. После моего старого кирпича от SonyEricsson 6летней давности радовало всё: cpu ARMv7 1Ghz, 768Mb ram; как выяснилось уже после покупки - это и gpu на чипе Adreno 205, что делает работу с видео и графикой очень плавной и приятной; яркий и чёткий wvga (480 x 800) экран; две камеры - передняя и задняя (5Mpix); зарядка micro usb - он же и просто канал подключения к компу; wifi; gps; синхронизация с google account (адресная книга, почта, google reader, picasa); стандарный minijack; акселлерометр - он же g-sensor; pattern lock screen и куча софта на android market. Словом, value for money - я считаю, что платить 20круб за телефон подобного класса, но у которого чуть лучше экран - это перебор.

Прошивка. Примерно через пару неделю меня стали утомлять постоянно запущенные сервисы yahoo! mail, yahoo! messanger и ещё с десяток левых приложений, которые оживают самостоятельно даже после того, как их убиваешь. Всё это идёт в стандартной прошивке от htc. Выход - CyanogenMod - альтернативная прошивка, там же на wiki был найдена инструкция по root'ованию и перепрошивке TMobile myTouch 4G. С первого раза прошивка меня не устроила - была потеряна интеграция с сервисами google и прочее - было решено вернутся. Затем попробовал прошивку Royal Ginger, основанная на CyanogenMod прошивка - и надо сказать, что она мне очень даже понравилась: много новых и вкусных мелочей и значительно экономней кушает батарейку. Pattern Lock screen При помощи такого нехитрого механизма можно блокировать экран от случайных прикосновений и доступа. Очевидно, чем больше точек в графе, тем сложнее его подобрать.

Swype Данный способ ввода позволяет печатать слова, не отрывая палец от экрана. Cоздателем технологии является Клифф Кушлер (Cliff Kushler), автор предиктивного ввода T9. Swype позволяет пользователю вводить слово, скользя пальцем от буквы к букве, поднимая палец только в промежутке между словами. Для угадывания слова Swype использует алгоритм исправления ошибок и лингвистическую модель языка. Безусловно, поддерживается как английский, так и русский ввод. Не является уникальной особенностью android'а, но очень приятная функциональность.

Приложения. Много всякого и интересного каждый может найти себе на Android Market, для себя отметил:

LauncherPro
ColorDict - offline словарь, ведёт историю поиска слов, понимает словари в формате stardict - можно найти и словари lingvo в данном формате, и очень полезный Oxford English-English Dictionary
Locus Pro - карты и навигация, поддерживает карты OpenSteetMap, google, yandex и много других, кеширует в формате sqlite, после чего доступно offline. Интерграция с gps и прочие плюшки типа треков и т.п.
Google apps - это и GMail, Google Reader и Picasa
VuDroid - читалка и pdf, и djvu с запоминанием страницу, где остановился.
FancyWidget - можно было бы сказать, что стандарный widget часов и погоды, просто красивый и удобный.
Skype как он есть
Labyrinth - детская забава по катанию металлического шарика по лабиринту.
Hybrid StopWatch - красивый и фунциональный секундомер с таймером
cluBalance - widget, позволяющий следить за балансом: сколько потрачено за день, месяц; автоматическое обновление после каждого звонка, sms, internet подключения
ConnectBot - ssh client
MoboPlayer - медиа-плеер с плюшками - выбор звуковой дорожки, субтитров, вшитых в mkv, mov, mpv - кушает целую кучу медиа форматов и т.п
RocketDial Pro - звонилка с поддержкой поиска имени по T9, организация контактов по группам и т.п
SpringPad - заметки, задачи и т.п, сервис интегрируется как с mozilla firefox, так и chrome
AlarmClock Plus - будильник, похож на стандартный, но можно настроить большую кнопку snooze и маленькую dismiss, отключение будильника по решению небольшого математического выражения

Добавлено: Результаты Quadrant benchmark

java: деградация пула строк

noreply@blogger.com (Vladimir Dolzhenko) — Wed, 25 May 2011 09:32:00 +0000

Наверняка многие java программисты знают о существовании пула строк, который хранится в PermGen.

Кроме всего прочего каждая строка, которая была получена через

new String(data);

можно привести к каноническому представлению посредством вызова метода intern().

Однако, доступ к полу строк может деградировать из-за большого кол-ва строк в пуле.

В своей статье вы уверены, что знаете про строки все? автор упоминает, что сложность intern() есть O(N), где N - размер пула строк.

Надо сказать меня сильно удивило - т.к. ещё в стародавние времена, когда стали доступны исходники sun hotspot jvm 1.4 (кстати, именно из них собирался blackdown-jdk) помню, что на уровне c++ пул строк сделан как Hashtable, у которого, как известно, сложность поиска O(1) - т.е константа.

Артём предоставил небольшой benchmark, который таки показывает линейность:

public class StringPoolTest {

static final int N = 1000000;
static int k;

static String TEST_STRING = "0123456789";


public static void main(String[] args) throws Exception{
final StringPoolTest stringPoolTest = new StringPoolTest();
stringPoolTest.m();
}

private void m() throws Exception {
for(final int i : new int[]{100, 1000, 
10 * 1000,
20 * 1000,
25 * 1000,
100 * 1000, 
500 * 1000, 
1000 * 1000
}){
cleanAndPopulate(i);
tripleCount(N);
}
}

private void tripleCount(int n) {
count(n);
count(n);
count(n);
}

private void cleanAndPopulate(int n) throws Exception{
clean();
populate(n);
}

private void gc() throws InterruptedException {
System.out.println(" gc begin");
Runtime.getRuntime().gc();
Runtime.getRuntime().gc();
Runtime.getRuntime().gc();
System.out.println(" gc finished.");
}

private void count(int n) {
int i, j;
long t = System.nanoTime();
for (i = 0; i < n; i++) {
i++;
}
long t1 = System.nanoTime();
for (j = 0; j < n; j++) {
access();
j++;
}
long t2 = System.nanoTime();
k = i - j;//prevent JIT from clashing loop
System.out.println(size() + ": " + (((t2 - t1) - (t1 - t)) / n / 1e3) + " us." );
}

private String[] a;// = new String[N];

protected void access() {
TEST_STRING.intern();
}

protected void populate(int n) {
a = new String[n];
for (int i = 0; i < n; i++) {
a[i] = Integer.toString(i).intern();
}
}

protected void clean() throws InterruptedException {
a = null;
gc();
}

protected int size() {
return a.length;
}
}

запускается на Sun JDK 1.6.0.25 / OpenJDK 1.6.0.22 всё с опциями

-verbose:gc 
-XX:+PrintGCTimeStamps 
-XX:+PrintGCDetails 
-XX:+PrintGCApplicationStoppedTime 
-XX:NewSize=144m 
-XX:MaxNewSize=144m 
-XX:PermSize=128m 
-XX:MaxPermSize=128m 
-XX:+UseParNewGC 
-XX:ParallelGCThreads=2 
-XX:MaxTenuringThreshold=1 
-XX:SurvivorRatio=8 
-XX:+UseConcMarkSweepGC 
-XX:+CMSParallelRemarkEnabled 
-XX:+CMSClassUnloadingEnabled 
-XX:+CMSPermGenSweepingEnabled 
-XX:CMSInitiatingOccupancyFraction=60 
-XX:+UseCMSInitiatingOccupancyOnly

и вот результаты, вызвавшие недоумение:

100: 0.101 us.
1000: 0.102 us.
10000: 0.117 us.
20000: 0.127 us.
25000: 0.136 us.
100000: 0.37 us.
500000: 2.96 us.
1000000: 7.725 us.

Легко заметить, что время отклика на участке до 25000 есть константа, после начинается рост.

Взглянем более детально на исходный код openjdk jvm:
openjdk/hotspot/src/share/vm/classfile/symbolTable.hpp:

class StringTable : public Hashtable {
friend class VMStructs;

private:
// The string table
static StringTable* _the_table;

static oop intern(Handle string_or_null, jchar* chars, int length, TRAPS);
oop basic_add(int index, Handle string_or_null, jchar* name, int len,
unsigned int hashValue, TRAPS);

// Table size
enum {
string_table_size = 1009
};

oop lookup(int index, jchar* chars, int length, unsigned int hashValue);

StringTable() : Hashtable(string_table_size, sizeof (HashtableEntry)) {}

StringTable(HashtableBucket* t, int number_of_entries)
: Hashtable(string_table_size, sizeof (HashtableEntry), t,
number_of_entries) {}

public:
// The string table
static StringTable* the_table() { return _the_table; }

static void create_table() {
assert(_the_table == NULL, "One string table allowed.");
_the_table = new StringTable();
}

static void create_table(HashtableBucket* t, int length,
int number_of_entries) {
assert(_the_table == NULL, "One string table allowed.");
assert(length == string_table_size * sizeof(HashtableBucket),
"bad shared string size.");
_the_table = new StringTable(t, number_of_entries);
}

///// cut 
};

openjdk/hotspot/src/share/vm/classfile/symbolTable.cpp:

oop StringTable::intern(Handle string_or_null, jchar* name,
int len, TRAPS) {
unsigned int hashValue = hash_string(name, len);
int index = the_table()->hash_to_index(hashValue);
oop string = the_table()->lookup(index, name, len, hashValue);

// Found
if (string != NULL) return string;

// Otherwise, add to symbol to table
return the_table()->basic_add(index, string_or_null, name, len,
hashValue, CHECK_NULL);
}

Всё выглядит вполне hash table, если бы не один момент:

symbolOop SymbolTable::basic_add(int index, u1 *name, int len,
unsigned int hashValue, TRAPS) {
assert(!Universe::heap()->is_in_reserved(name) || GC_locker::is_active(),
"proposed name of symbol must be stable");

// We assume that lookup() has been called already, that it failed,
// and symbol was not found.  We create the symbol here.
symbolKlass* sk  = (symbolKlass*) Universe::symbolKlassObj()->klass_part();
symbolOop s_oop = sk->allocate_symbol(name, len, CHECK_NULL);
symbolHandle sym (THREAD, s_oop);

// Allocation must be done before grapping the SymbolTable_lock lock
MutexLocker ml(SymbolTable_lock, THREAD);

assert(sym->equals((char*)name, len), "symbol must be properly initialized");

// Since look-up was done lock-free, we need to check if another
// thread beat us in the race to insert the symbol.

symbolOop test = lookup(index, (char*)name, len, hashValue);
if (test != NULL) {
// A race occurred and another thread introduced the symbol, this one
// will be dropped and collected.
return test;
}

HashtableEntry* entry = new_entry(hashValue, sym());
add_entry(index, entry);
return sym();
}

openjdk/hotspot/src/share/vm/utilities/hashtable.inline.hpp

inline void BasicHashtable::add_entry(int index, BasicHashtableEntry* entry) {
entry->set_next(bucket(index));
_buckets[index].set_entry(entry);
++_number_of_entries;
}

Кратко: при добавлении нового элемента не происходит масштабирование таблицы, таблица создана изначально с 1009 bucket'ов.

При значительном увеличении пула строк данная таблица вырождается - как следствие увеличивается число коллизий по hash коду, что мы и наблюдаем на benchmark'е.

Добавлено:
После было решено опробовать gcj 4.4.5:

$  gcj --version
gcj (Gentoo 4.4.5 p1.0, pie-0.4.5) 4.4.5
$ gcj --main=StringPoolTest StringPoolTest.java -o StringPoolTest && ./StringPoolTest

результат стабильный на всём рассматриваемом отрезке и составляет ~0.13us.

По скольку на руках есть исходный код OpenJDK 1.6.0.22 не составило труда изменить размер пула строк
openjdk/hotspot/src/share/vm/classfile/symbolTable.hpp:

  // Table size
enum {
string_table_size = 20011
};

И выполнить опять тот же тест

100: 0.145 us.
1000: 0.153 us.
10000: 0.154 us.
20000: 0.154 us.
25000: 0.153 us.
100000: 0.155 us.
500000: 0.197 us.
1000000: 0.238 us.

Т.о. было найдено верное место в исходном коде jvm и результат изменений практически устранил деградации поиска строки в пуле.

Задачка: Честный стражник и лжец

noreply@blogger.com (Vladimir Dolzhenko) — Tue, 08 Mar 2011 16:38:00 +0000

Перед вами две двери:
одна из них ведет на волю, другая - прямая дорога к смерти.

Перед каждой из дверей сидит стражник, причем один из них - лжец, а второй говорит правду и только правду; однако вы не знаете, кто из них кто.

Задав только один вопрос только одному из стражников, определить дорогу на свободу.

Каков вопрос стоит задать ?

внимание! комментарии содержат ответ.

Serialization graph

noreply@blogger.com (Vladimir Dolzhenko) — Tue, 08 Mar 2011 12:37:00 +0000

Стандартная сериализация в java обладает рядом недостатков (см. Effective Java 2nd edition, автор Josh Bloch стр. 289), среди которых: медленная сериалазиция (см. jvm-serializers benchmarks) и сохранение полного графа объектов.
Однако, идея сохранения графа имеет и положительный аспект.

Вкратце, процесс стандартной сериализации графа объекта выглядит так:

Заголовок пакета содержит только описания классов без их свойств (можно назвать «словарь объектов»).
При этом в сериализованном виде объекты представлены как ссылки (возможно, на не до конца проинициализированные объекты).
Процесс десериализации создаёт карту объектов на основе «словаря объектов» , которые в последствии заполняет свойствами-примитивами (boolean, int, long и т.п) и в т.ч. и ссылками на объекты из «словаря объектов».

Т.о. стандарная сериализация позволяет разрешать циклические зависимости, а так же избегать повторов сериализации объектов в потоке.

В противовес медленной сериализации, обратной совместимости, контролю сериализованного графа и т.п часто ставят «ручную» сериалализацию, например, используя java.io.Externalizable.

Часто при передаче, н-р массива объектов, встречаются повторяющиеся объекты (как правило строки, но не только), т.е

Введя понятие «словаря объектов» (или словаря строк) можно добиться уменьшения объёма пакета без существенных доп. нагрузок.

ps. на моём примере при сериализации около 200 объектов выигрыш составил ~ 50%.

Stuff: Powerball

noreply@blogger.com (Vladimir Dolzhenko) — Mon, 17 Jan 2011 11:03:00 +0000

Пару дней покрутив ручной тренажёр power ball коллеги - решил купить себе тоже :)

log2(1M)

noreply@blogger.com (Vladimir Dolzhenko) — Sun, 16 Jan 2011 08:18:00 +0000

Многие задачки, которые задают на собеседованиях появляются рано или поздно на ресурсах типа braingames.ru, что в общем-то и не удивительно.

Так например, fp-сообществу понравилась эта задачка, придуманная в нашем отделе.

По мотивам Top 25 Oddball Interview Questions Of 2010 и особенно вопроса, задаваемого в UBS

sqrt(2000) = ?

вспомнилась классическая задача, задаваемая у нас:

log₂(1000000) = ?

Не предполагается, что ответ будет с точностью до какого знака после запятой (точки) - достаточно оценить с точностью до единицы.

Lock Coarsening, Biased Locking, Escape Analysis and others

noreply@blogger.com (Vladimir Dolzhenko) — Fri, 31 Dec 2010 21:20:00 +0000

Оптимизационные трюки, используемые при динамической компиляции jit'ом в java 6. В java 6 была существенно изменена (по сравнению с java 5) работа блокировок, существенно облегчив их, в java6u14 появился escape-анализ, который работает по-умолчанию, а так же много других интересных подходов.

Lock coarsening, Eliminate locks - укрупнение блокировок

-XX:+EliminateLocks

Данная опция, относящаяся к оптимизации многопоточных приложений, не удаляет блокировки в целом - имеет место устранение излишних блокировок в результате их объединения, и в некотором смысле их загрубление.
Несколько смежных блоков, которые выполняются под одним и тем же монитором могут быть объединены в блок с одним захватом монитора.
Тем самым происходит устранение излишних разблокирований и повторных захватов мониторов.
Если между двумя захватами одного и того же монитора находится блок не под монитором, дабы уменьшить число захватов он тоже окажется под монитором - это и есть загрубление блокировок (lock coarsening).

-XX:+EliminateLocks
Устранение лишних блокировок - Lock coarsening

На примере показано как устраняется overhead на захват монитора.
Biased Locking - Смещение блокировок

-XX:+UseBiasedLocking

Обновлено.. Краткий пересказ Biased locking в рабочих заметках

Механизм biased locking основывается на свойстве, что большинство объектов захватывают монитор на очень малое время, так, что даже при большом количестве потоков contention оказывается весьма мал.

-XX:-UseBiasedLocking
Иллюстрация работы с отключённым biased locking.

Для этого в JVM были реализованы spin-locks (thin locks), используется ownerThreadId, и, пытаясь захватить монитор, CAS(-1, threadId). Если CAS удался — захватили монитор, иначе делаеться еще несколько попыток в цикле (вдруг нынешний владелец отпустит монитор буквально через пару тактов). Количество итераций это предмет тонкого тюнинга, возможно даже адаптивного, на базе профиля предыдущих попыток. Если даже со спиннингом мы не захватили монитор — откатываемся к OS-specific locks (fat-locks).

-XX:+UseBiasedLocking
Escape analysis - Анализ локальности

-XX:+DoEscapeAnalysis

Цель escape-анализа - определить локализован ли указатель создаваемого объекта внутри блока объекта или он выходит (escape) за рамки данного блока (в другую нить (thread), может быть возвращен из блока, а также, когда указатель помещён в глобальную переменную).

Исследование данной проблемы длится не один год, одна из подробных статей Escape analysis for Java была представлена в 1999 году.

В java каждая нить (thread) имеет свой собственный кусок памяти - стек (stack), который хранит фреймы (историю вызовов методов), частичные результаты операций, локальные переменные (примитивы, в т.ч. и указатели/ссылки на объекты). В этом смысле java стек очень похож на стек C++, за исключением того, что в java стеком нельзя напрямую оперировать и создавать на нём объекты, как в C++.

Куча (heap), общая для всех нитей область памяти, используется для хранения всех создаваемых объектов.

-XX:-DoEscapeAnalysis
Объекты создаются на общей куче

Благодаря escape-анализу объекты могут быть созданы прямо на стеке или размещены в регистрах (используя register allocator). Не смотря на то , что создание объекта на кучи всё достаточно дешёвая операция - есть обратная сторона - Garbage Collector. Для высоконагруженных приложений даже вызов minor gc это существенные затраты. Объект, созданный на стеке, будет уничтожен, когда он покинет stack frame, в котором он был создан, как следствие - отсутствие нагрузки на (minor) GC.

-XX:+DoEscapeAnalysis

Более того - нет необходимости использовать блокировку для локализованных объектов - т.к. жизненный цикл объекта ограничен одним блоком и никакая другая нить не может его «увидеть» или использовать (прямое следствие из определения pointer escape) .

В качестве примера используем следующий microbenchmark:
```
import java.util.*;

public class Foo {
public static void main(String[] args){
final int warmup = 100 * 1000; 
final int run = 1000 * 1000; 
foo(warmup);
final long start = System.nanoTime();
foo(run);
final long end = System.nanoTime();
System.out.println((end - start) / 1000 / 1e3);
}

private static int foo(int count){
int s = 0; 
for(int i = 0; i < count; i++){
Collection c = new ArrayList();
s += c.size();
}
return s;
}
}
```
```
$ java -XX:-DoEscapeAnalysis -verbose:gc -XX:+PrintGCDetails Foo
[GC [PSYoungGen: 12160K->152K(14144K)] 12160K->152K(46528K), 0.0019620 secs] [Times: user=0.01 sys=0.00, real=0.01 secs]
[GC [PSYoungGen: 12312K->136K(26304K)] 12312K->136K(58688K), 0.0008050 secs] [Times: user=0.00 sys=0.00, real=0.00 secs]
[GC [PSYoungGen: 24456K->136K(26304K)] 24456K->136K(58688K), 0.0006690 secs] [Times: user=0.00 sys=0.00, real=0.00 secs]
[GC [PSYoungGen: 24456K->136K(50624K)] 24456K->136K(83008K), 0.0005730 secs] [Times: user=0.00 sys=0.00, real=0.00 secs]
65.78
Heap
PSYoungGen      total 50624K, used 14728K [0xa3e20000, 0xa7180000, 0xb3ac0000)
eden space 48640K, 30% used [0xa3e20000,0xa4c602a8,0xa6da0000)
from space 1984K, 6% used [0xa6f90000,0xa6fb2050,0xa7180000)
to   space 1984K, 0% used [0xa6da0000,0xa6da0000,0xa6f90000)
PSOldGen        total 32384K, used 0K [0x844c0000, 0x86460000, 0xa3e20000)
object space 32384K, 0% used [0x844c0000,0x844c0000,0x86460000)
PSPermGen       total 16384K, used 1900K [0x804c0000, 0x814c0000, 0x844c0000)
object space 16384K, 11% used [0x804c0000,0x8069b048,0x814c0000)
```
```
$ java -XX:+DoEscapeAnalysis -verbose:gc -XX:+PrintGCDetails Foo
0.747
Heap
PSYoungGen      total 14144K, used 4135K [0xa3ed0000, 0xa4e90000, 0xb3b70000)
eden space 12160K, 34% used [0xa3ed0000,0xa42d9d90,0xa4ab0000)
from space 1984K, 0% used [0xa4ca0000,0xa4ca0000,0xa4e90000)
to   space 1984K, 0% used [0xa4ab0000,0xa4ab0000,0xa4ca0000)
PSOldGen        total 32384K, used 0K [0x84570000, 0x86510000, 0xa3ed0000)
object space 32384K, 0% used [0x84570000,0x84570000,0x86510000)
PSPermGen       total 16384K, used 1893K [0x80570000, 0x81570000, 0x84570000)
object space 16384K, 11% used [0x80570000,0x807496f0,0x81570000)
```
и такой же тест, для java.util.Vector

ArrayList Vector

-EA +EA -EA +EA

время выполнения, ms: 65.78 0.747 115.805 0.83

срабатываний GC: 4 0 5 0

время работы GC, ms: 4 - 4.5 -

Как и ожидалось время выполнения значительно меньше, меньше вызовов GC, который удаляет объекты «как только так сразу» из young geneneration. Так же заметно ускорение работы thread-safe «версии» ArrayList'а - java.util.Vector.

Однако, не стоит надеяться, что благодаря escape-анализу производительность увеличится столь же стремительно как в данном синтетическом тесте. Определённо можно сказать, что нагрузка на GC будет значительно меньше для большинства типов приложений.

график нагрузки gc реального приложения
до использования java6u14 и после,
по вертикали - суммарное время проведённое в gc

Оптимизация конкатенации строк

-XX:+OptimizeStringConcat (java 6u20+).

Несколько типичных шаблонов по конкатенации можно оптимизировать, например, String использует тот же объект char[] (т.е та же ссылка/указатель) который хранит StringBuffer или StringBuilder:
The end result is the saving of an unnecessary char[] allocation and a subsequent call to arraycopy.

Рассмотрим в деталях, что происходит, при формировании, например, сообщения:
Более детально стоит обратить, что происходит в методе java.lang.StringBuilder.toString():
```
    public String toString() {
// Create a copy, don't share the array
return new String(value, 0, count);
}
```
и далее в конструкторе java.lang.String:
```
    public String(char value[], int offset, int count) {
if (offset < 0) {
throw new StringIndexOutOfBoundsException(offset);
}
if (count < 0) {
throw new StringIndexOutOfBoundsException(count);
}
// Note: offset or count might be near -1>>>1.
if (offset > value.length - count) {
throw new StringIndexOutOfBoundsException(offset + count);
}

this.offset = 0;
this.count = count;
this.value = v;
}
```

Использование byte[] вместо char[] для строки содержащей исключительно ASCII символы.

-XX:+UseCompressedStrings (java6u21)

java.lang.String по своей сути является обёрткой вокруг массива char[], делая его защищённым и не изменяемым. char занимает 2 байта. Если же строки используют исключительно ASCII символы, т.е ограничены диапазоном одного байта - используя данную оптимизацию немного сэкономить память.

Однако, не стоит ожидать, что объём используемой памяти сильно сократится.

Ссылки:

Applicative-order evaluation vs Normal-order evaluation

noreply@blogger.com (Vladimir Dolzhenko) — Sun, 31 Oct 2010 15:03:00 +0000

Нормальным порядком вычисления (normal-order evaluation), если кратко, можно назвать такой порядок вычисления, что сперва происходит «полная подстановка, затем редукция».

Аппликативный порядок вычисления (applicative-order evaluation), напротив, сперва происходит «вычисление аргументов, затем вызов процедуры».

В качестве наглядного примера - попробуем реализовать свою собственную функцию and для clojure.

(defn
  #^{:test (fn []
 (assert (true? (my-and true)))
 (assert (false? (my-and true false)))
 (assert (true? (my-and true true)))
 (assert (false? (my-and true true false)))
 (assert (true? (my-and true true true)))
)}
  my-and 
  ([x] x)
  ([x & more] (if (false? x) x (reduce my-and more)))
)

Отлично.

Почему же тогда автор clojure решил использовать макросы в реализации функции and ?

В группе языков lisp, как впрочем и во многих других языках, используется аппликативный порядок вычисления (в общем случае, если не используются мощности «синтаксического сахара»).

Разница между my-and и and в том, что my-and использует аппликативный порядок (т.е все аргументы будут вычислены до вызова функции), в то время как and использует несколько иной порядок.
И, поэтому, один из легальных способов изменить порядок вычисления - применение макросов.

В качестве примера используем функцию foo:

user=> (defn foo[x] (do (println "foo") x))
user=> (my-and (foo false) (foo false) (foo true))
foo
foo
foo
false
user=> (and (foo false) (foo false) (foo true))
foo
false

P.S. Строго говоря, and не использует нормальный порядок вычисления, а «псевдонормальный порядок» на один шаг.

Hazelcast

noreply@blogger.com (Vladimir Dolzhenko) — Sun, 26 Sep 2010 17:27:00 +0000

hazelcast
In-Memory Data Grid for Java
hazelcast project on Google Code; Hazelcast.com
hazelcast documentation

Краткая история:

Start-up, основан 2008
Open source бизнес модель. Получение прибыли на консалтинге и поддержке самого Hazelcast
Более 100 пользователей, в основном в США и в Европе

Характеристики:

Pure java 5, NIO
Apache 2.0 licence
Light-weight & simple
Распределённая реализация
- java.util.{Queue, Set, List, Map}
- java.util.concurrency.locks.Lock
- java.util.concurrent.ExecutorService
Распределённый MultiMap для взаимосвязи один-ко-многим
Поддержка шифрования на уровне socket
Распределённые Topic для публикации/подписки сообщений
Socket level encryption support for secure clusters
Синхронное (write-through) и асинхронное (write-behind) сохранение в БД
Мониторинг и управление кластером через JMX
Поддержка инфомации о состоянии кластера и его членов
Динамическое обранужение
Динамическое масштабирование
Динамическое перераспределние резервных копий данных
Динамический fail-over
и другое

Конкуренты:
Сами отцы Hazelcast'а называют своими конкурентами:

Oracle Coherence
IBM WebSphere eXtreme Scale / ObjectGrid
TerracoWa
Gigaspaces
Gemstone
JBossCache/JGroups/Infinispan

Поскольку мой опыт ограничен Oracle/Tangosol Coherence, то сравниваю всегда именно с ним. Однако в целом продукты по функциональности очень похожи друг на друга:

Quick start: один единственный jar, который нужно добавить в classpath
Простое конфигурирование:
- описание кластера - имя, пароль, шифрование, если необходимо
- описание сети узлов- multicast,unicast,tcp/ip
- декларация map и их свойств
Очень схожий API, как по функционалу, так и по названию - порой отличие только в наименовании package'ей
Производительность (latency) - разница не более 30% (как +, так и -)
Детально не исследовался вопрос:
- потребление cpu
- потребление памяти
- объём сетового траффика

Безусловно есть и различия.
Так, например, не касаясь вопросов лицензии и стоимости - не нашёл распределённый topic, queue, executor service

Bugs & Hazelcast:
Ошибки присутствуют, как и в любом проекте и продукте, большая часть не мешает его нормальному использованию - на критические ошибки реагируют (посте отправки issue в issue tracker) достаточно быстро - был случай, когда patch был создан в течении часа после отпраки issue.

Однако, было найденно несколько критических ошибок, которые не были исправлены (согласно svn и дате их "добавления") более полугода, что заставляет очень сильно задуматься/удивится/etc в свете заявления самих hazelcast'овцев о сотне пользователей в US/Europe.

Maven dependency:

<dependency>
    <groupId>com.hazelcast</groupId>
    <artifactId>hazelcast-all</artifactId>
    <version>1.9</version>
</dependency>

Ivy dependency:

<dependency org="com.hazelcast" name="hazelcast-all" rev="1.9"/>

P.S. Можно сказать, что Hazelcast - это реальная open source альтернатива Oracle Coherence под Apache license. Сообщество живое, реагируют быстро, новые идеи и функциональность приветствуется - проект растёт и вполне успешно.

P.P.S. С недавних пор я hazelcast committer.

Задача Льва Толстого

noreply@blogger.com (Vladimir Dolzhenko) — Wed, 16 Jun 2010 07:12:00 +0000

Продавец продаёт шапку. Стоит 10 р.

Подходит покупатель, меряет и согласен взять, но у него есть только банкнота 25 р. Продавец отсылает мальчика с этими 25 р. к соседке разменять.

Мальчик прибегает и отдаёт 10 + 10 + 5.

Продавец отдаёт шапку и сдачу 15 руб.

Через какое-то время приходит соседка и говорит, что 25 р. фальшивые, требует отдать ей деньги. Ну что делать. Продавец лезет в кассу и возвращает ей деньги.

На сколько обманули продавца ?

внимание! комментарии содержат ответ.

Задачка: Круглый стол

noreply@blogger.com (Vladimir Dolzhenko) — Fri, 30 Apr 2010 10:54:00 +0000

За круглым столом сидят два игрока.

Первый играет белыми круглыми фишками, второй - такими же, но чёрными.

Игрок должен положить на стол только одну фишку, после чего ход переходит к другому игроку.

Игрок проигрывает, если нет свободного места, чтобы положить фишку.

Как следует действовать игроку, начинающему игру, чтобы всегда выигрывать ?

Задачка: Мальчики

noreply@blogger.com (Vladimir Dolzhenko) — Wed, 28 Apr 2010 11:05:00 +0000

В семье два ребенка, причём один из них мальчик.

Какая вероятность что и другой тоже мальчик ?

Задачка: Сколько лет детям

noreply@blogger.com (Vladimir Dolzhenko) — Wed, 28 Apr 2010 11:03:00 +0000

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

Сколько лет детям?

внимание! комментарии содержат ответ.

Задачка: Таблетки

noreply@blogger.com (Vladimir Dolzhenko) — Tue, 20 Apr 2010 10:09:00 +0000

В джунглях тебя укусила ядовитая змея.

В аптечке есть 4 таблетки - две типа А две типа Б, причём выглядят абсолютно одинаково.

Противоядие - одна таблетка типа А и одна таблетка типа Б.
Во всех других случаях умираешь от змеиного яда (т.е если выпить две таблетки А, или две Б или выпить сразу 2 А и 2 Б)

Как стоит действовать?

java: How to get PrintAssembly

noreply@blogger.com (Vladimir Dolzhenko) — Sat, 17 Apr 2010 16:51:00 +0000

Thanks to Roman Yaroslavtsev who gave me a link to an article Memory Barriers and JVM Concurrency.

First of all this article is useful to gain a better understanding of Java Memory Model - another great thing that I discover is ability to look inside of assembly code generated by jit.

Refer to load-test-tool usage I going to use that simple example:

public class ArrayIterationTest {

  private final int[] data;

  public ArrayIterationTest(final int size) {
    this.data = new int[size];
  }

  public void doTest() {
    for ( int i = 0; i < data.length; i++ ){
  int j = data[i]; 
 }
  }

  public static final void main(String[] args){
   final long t0 = System.nanoTime(); 
   ArrayIterationTest t = new ArrayIterationTest(1000000);
   t.doTest();
   System.out.println((System.nanoTime() - t0) / 1000 / 1e3);
  }
}

Let's start it (user's jvm is sun jdk 1.6.0_20):

java -XX:+UnlockDiagnosticVMOptions
-XX:+PrintAssembly -XX:PrintAssemblyOptions=hsdis-print-bytes
-XX:CompileCommand=print,ArrayIterationTest
ArrayIterationTest

and have got

CompilerOracle: print ArrayIterationTest
Could not load hsdis-i386.so; library not loadable; PrintAssembly is disabled
14.029

So...

Dude, where's my hsdis-i386.so ?

There is no hsdis-i386.so in dev-java/sun-jdk-1.6.0.20, nor in dev-java/sun-jdk-1.7.0.0_alpha89 or in dev-java/icedtea6-bin-1.8.0

Let's fetch openjdk plugin implementation

hg clone http://hg.openjdk.java.net/jdk7/hotspot/hotspot/src/share/tools/hsdis/ openjdk-hotspot

and build it using hsdis's README

This version of the plugin requires the Gnu disassembler, which is available separately as part of the binutils project.

cd openjdk-hotspot/src/share/tools/hsdis/
mkdir build && cd build
wget http://ftp.gnu.org/gnu/binutils/binutils-2.20.1.tar.bz2 
tar jxf binutils-2.20.1.tar.bz2 && mv binutils-2.20.1 binutils && cd ..
make

and start again it now:

LD_LIBRARY_PATH=openjdk-hotspot/src/share/tools/hsdis/build/linux-i586/:$LD_LIBRARY_PATH
java -XX:+UnlockDiagnosticVMOptions
-XX:+PrintAssembly -XX:PrintAssemblyOptions=hsdis-print-bytes
-XX:CompileCommand=print,ArrayIterationTest
ArrayIterationTest

Note: use your own path to hsdis-arch.so in LD_LIBRARY_PATH .

And you've got something like this for your platform:

CompilerOracle: print ArrayIterationTest
Loaded disassembler from hsdis-i386.so
Decoding compiled method 0xb3bb5c48:
Code:
[Disassembling for mach='i386']
[Entry Point]
[Verified Entry Point]
  0xb3bb5d20: call   0xb7168b60         ;...e83b2e5b 03
                                        ;   {runtime_call}
  0xb3bb5d25: xchg   %ax,%ax            ;...666690
  ...

ps. for further information please refer to PrintAssembly at wikis.sun.com as well as for prebuild hsdis-i386.dll

FP-approach in Java via Goolge Collections

noreply@blogger.com (Vladimir Dolzhenko) — Sun, 28 Mar 2010 19:50:00 +0000

I'm going to demonstrate some elements of functional programming (fp) approach in java.

For this purpose I use Google Collections Library - provides new and elegant collection types as well as some fp elements and techniques.

A bit more about Google Collections Library:
Google Collections Library FAQ
What is the Google Collections Library?
Introduction to Google Collections by Benjamin Winterberg

For obvious cases I put examples in clojure and in java using fp-approach techniques.

Took short and nice example from "Programming clojure" book - StringUtils.isBlank() is the method (from the Apache Commons) checks to see whether a string is blank: either empty or consisting of only whitespace :

public static boolean isBlank(String str) {
  int strLen;
  if (str == null || (strLen = str.length()) == 0) {
    return true;
  }
  for (int i = 0; i < strLen; i++) {
    if ((Character.isWhitespace(str.charAt(i)) == false)) {
      return false;
    }
  }
  return true;
}

Here is a similar implementation in Clojure:

(defn blank? [s] (every? #(Character/isWhitespace %) s))

Java-fp-approach implementation of isBlank method powered by google collections, string is a sequence of chars - that's why I had introduce stringIterator:

import static ru.dolzhenko.lambda.iterators.StringIterator.*;

import static com.google.common.collect.Iterators.*;

public static boolean isBlank(String str) {
return all(stringIterator(str),
  new Predicate<Character>() {
    @Override
    public boolean apply(Character ch) {
      return Character.isWhitespace(ch);
    }
  });
}

map is function mapping, a classic primitive in functional programming - apply a function to all elements of a list, and return the resulting list.

e.g. parse string values to numbers:

(map #(Integer/valueOf %) ["1" "2" "3"])

on java:

Collections2.transform(
  ImmutableList.of("1", "2", "3"), 
  new Function<String, Integer>() {
    @Override
    public Integer apply(String from) {
      return Integer.valueOf(from);
    }
  });

Transform is also available for Iterables.transform(Iterable, Function), Iterators.transform(Iterator, Function) etc.

The reduce function is a little less obvious in its intent. This function reduces a list to a single value by combining elements via a supplied function.

The filter function returns elements of collection that satisfy predicate.

For instance, Let's solve ProjectEuler - Problem #1 - find the sum of all the multiples of 3 or 5 below 1000:

(reduce + (filter #(or (zero? (mod % 3)) (zero? (mod % 5))) (range 1000)))

... and the same on java:

// import static import static com.google.common.base.Predicates.*;
// import static com.google.common.collect.Iterators.*;

// import static ru.dolzhenko.lambda.iterators.LambdaIterators.*;
// import static ru.dolzhenko.lambda.functions.LambdaFunctions.*;
// import static ru.dolzhenko.lambda.functions.LambdaPredicates.*;

final BigDecimal value = reduce(sum(), filter(range(1000),
  or(
    zero(mod(new BigDecimal(3))),
    zero(mod(new BigDecimal(5)))
  )));

Yeah, there are no reduce and range functions in google collections too, so I had to ~~build my own theme park, with blackjack~~ make my own collection of functions LambdaIterators & Co. that supplement google collections with such useful functions as reduce, range, take, takeWhile, iterate, first, rest.

Definitely, Predicate is a function, so it can be described as

public interface Predicate<T> extends Function<T, Boolean>{ 
}

To avoid autoboxing overhead authors of google collections prefer to introduce new interface.

After that we able to construct expressions like

(take 5 (filter even? (iterate inc 1)))

on java:

take(5, filter(iterate(inc(), BigDecimal.ONE), even()))

as well as for finite collection as well as for infinite collection - functions
filter, transform, take, takeWhile, iterate, first, rest are lazy - in other words, elements are not calculated until they are needed.

btw. lambdaj is useful framework that provides pseudo fp approach in java.

Задачка: Груши

noreply@blogger.com (Vladimir Dolzhenko) — Wed, 10 Mar 2010 10:31:00 +0000

В ящике 4 x 4 лежат груши (16 шт.)

Какие 6 груш необходимо убрать, так, чтобы в каждой строке и каждом столбце было чётное число груш.

внимание! комментарии содержат ответ.

Source hosting

noreply@blogger.com (Vladimir Dolzhenko) — Mon, 01 Mar 2010 19:23:00 +0000

Задумался я завести учётную запись на каком-нибудь социальном source hosting'е.
Интересовали не только площадки для open source проектов, но и для личного закрытого использования.
И вот краткий обзор некоторых сервисов:

github
repository type: git
Free accounts: available
Paid accounts: available

	Giga	Medium	Small	Micro	Free
Disk space	60.0 GB	2.4 GB	1.2 GB	0.6 GB	0.3 GB
Private repositories	300	20	15	5	0
Private Collaborators	100	10	5	1	0
Public repositories	Unlimited	Unlimited	Unlimited	Unlimited	Unlimited
Wiki
Issue tracker
SSL
Fee / month	$200	$22	$12	$7	Free

К особенностям gitbuh'а стоит добавить сервис gist.github позволяющий писать небольшие куски кода (snipplet) прямо из web'а с совместным доступом и, конечно же, версионностью.

bitbucket.org
repository type: mercurial
Free accounts: available
Paid accounts: available
+ openId login

	Team	Large	Pro	Amateur	Free
Disk space	50.0 GB	26.0 GB	5.0 GB	2.5 GB	1.0 GB
Private repositories	150	25	15	5	1
Public repositories	Unlimited	Unlimited	Unlimited	Unlimited	Unlimited
HTTP push/pull
SSH push/pull
Wiki
Issue tracker
Fee / month	$100	$50	$12	$5	Free!

assembla.com
repository type: git, subversion
Free accounts: available
Paid accounts: available

unfuddle.com
repository type: git, subversion
Free accounts: available
Paid accounts: available

Open Source oriented hosting:

google code
repository type: subversion, mercurial
Disk space: 1Gb
Free accounts: available
Paid accounts: no

sourceforge.net
repository type: SVN, Git, Mercurial, Bazaar, CVS servers
Free accounts: available

berlios.de
На всех площадках приосходит автоматическое резервирование данных.

Дополнения приветствуются !

Задачка: A(4,3)

noreply@blogger.com (Vladimir Dolzhenko) — Fri, 26 Feb 2010 09:56:00 +0000

функция A(x,y) определена как
A(0,y) = 1, y ≥ 0
A(1,0) = 2
A(x,0) = x + 2, x ≥ 2
A(x + 1, y + 1) = A( A(x, y + 1), y), x ≥ 0, y ≥ 0

A(4,3) = ?

Данная функция есть функция Аккермана - простой пример вычислимой функции, которая не является примитивно рекурсивной.

F(z) = A(4, z)

Попытки вычислить A(4, 3) в лоб обречены на провал (код на clojure):

(defn A([x y]
 (cond 
  (zero? x) 1
  (and (= x 1) (zero? y)) 2
  (and (>= x 2) (zero? y)) (+ x 2)
  :else (recur (A (dec x) y) (dec y))
 )
))

Однако, на erlang прямо в лоб решается запросто:

-module(ack).
-export([a/2]).

a(0,_) -> 1;
a(1,0) -> 2; 
a(X,0) -> X+2;
a(X,Y) -> a( a(X-1,Y), Y-1).

запускаем...

$ erl
1> c(ack.erl).
{ok,ack}
2> ack:a(4,3).
ответ скрыт

Решить данную задачу на clojure вполне реально - дерзайте!

Level 1

ps. Я тем временем заработал Level 1 на Project Euler - на мой взгляд, отличный способ прокачать навыки в функциональном программировании.

	ArrayList		Vector
	-EA	+EA	-EA	+EA
время выполнения, ms:	65.78	0.747	115.805	0.83
срабатываний GC:	4	0	5	0
время работы GC, ms:	4	-	4.5	-