понеділок, 28 лютого 2011 р.

Invocation of var-arg method via Reflection API

When trying to invoke the method accepting array or variable arguments, you should take few things into account.

The argument type to be matched is an array of variable argument type. So if you declare String... or String[] in your method's signature, you should match for String[].class in both cases.

// Test.java
package milkyway.Test;

public class Test {
    public static void main(String... args) {
        System.out.println("yo");
    }
}
 
// A long time later in a galaxy far far away
ClassLoader scl = ClassLoader.getSystemClassLoader();
Class c = scl.loadClass("milkyway.Test");
Method m = c.getMethod("main", String[].class);

Later, you may want to invoke the method, and you can be tempted to pass null, or an array to your method, but watch out. Neither of these will work

m.invoke(null);
m.invoke(null, null);
m.invoke(null, new String[0]);
m.invoke(null, new String[] { "one", "two", "three" });

All will result in java.lang.IllegalArgumentException with various reasons.

To make the invoke() happy, you should explicitly cast the argument to Object type:

m.invoke(null, (Object)null);
m.invoke(null, (Object)new String[0]);

If you want to pass no variable arguments in the case of var-arg method, pass null or empty array as we just did. This tells invoke() to call the method with empty list of variable arguments.

Quick merge of two arrays in Java

Given two arrays, the goal is to get a concatenation of two. You may go through lands of JCF if you want, but also you may be puzzled if this can be done without it. I did.

Here is the code:

public class Utils {
    @SuppressWarnings("unchecked")
    public static <T> T[] mergeArrays(T[] a, T[] b) {

        if (a == null || a.length == 0) return b;
        if (b == null || b.length == 0) return a;

        T[] m = (T[]) Array.newInstance(a.getClass().getComponentType(), a.length + b.length);

        System.arraycopy(a, 0, m, 0, a.length);
        System.arraycopy(b, 0, m, a.length, b.length);

        return m;
    }
}

The first key point here, that we create new array instance with the help of Reflection API, using Array.newInstance() method.

The second key point is we obtain array element type at runtime with Class.getComponentType() method.

And final point is we use System.arraycopy() method to copy array contents, which is native call and is fastest you can get on JVM.

This doesn't work on arrays of primitive types, but version for primitives is as easy as search and replace T with required primitive type.

неділя, 27 лютого 2011 р.

Cертификат по Java!

Получил свой первый сертификат по Java! Тренироваться на тестах намного полезнее для сдачи чем чтение JLS. Будете читать JLS - станете хорошими читателями JLS, ну а я хочу хорошо сдать экзамен.

субота, 26 лютого 2011 р.

java.util.concurrent. Часть первая. Почему?

Часть первая, в которой множеством слов раскрывается смысл существования этого API
Эта статья, хоть и не является прямым переводом, основана на статье Брайана Гетца Concurrency in JDK 5.0



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

Однако потоки были реализованы современными операционными системами задолго до массового появления многоядерных процессоров. Зачем же нужны потоки на однопроцессорных системах?

Их несколько
  1. Отзывчивый графический интерфейс. Длительные операции могут быть выполнены в отдельном потоке, в то время как приложение способно обслуживать события от клавиатуры и мышки. 
  2. Возможность более эффективного использования ресурсов: процессора, памяти, жесткого диска и сети. В то время как один из потоков простаивает, ожидая завершения операции чтения файла, второй поток может в это время устанавливать сетевое соединение с клиентом, а третий - обрабатывать какой нибудь запрос. 
  3. Простота модели “поток-на-запрос” и идея фоновых системных процессов. Оставляя детали распределения ресурса процессора на совесть операционной системы, мы получаем возможность сконцентрировать программу на обработки самого запроса. Мы также можем выделить определённые задачи (например, сборку мусора или системный отладчик) в отдельные потоки, и таким образом “незаметно” добавить новые свойства программе. 
Первые два пункта в основном понятны, третий распишу более подробно.

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

Однако алгоритм не создается для одного запроса. Если требуется обрабатывать большое количество входных данных, то возникает желание либо уменьшить общее время их обработки, либо увеличить скорость их обработки (и таким образом увеличить пропускную способность обработчика). Самый простой способ в данном случае - поставить больше однопоточных алгоритмов и заставить их работать параллельно. Возможно, придется как-то согласовывать доступ к общим ресурсам и координировать их выполнение, но это обычно значительно проще чем разработка нового алгоритма, который за раз может обработать больше чем один набор данных (такой алгоритм нужно не только разработать, но еще и доказать). Это и понимается под простотой модели “поток-на-запрос”.

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

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

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

Поскольку в Java данные - это объекты, то к классам этих объектов, которые будут обрабатывать вызовы из нескольких потоков, предъявляется требование многопоточной безопасности (thread safety). Что это значит? Это. конечно же значит, что вызовы методов обьекта будут безопасными, что, конечно, правильно, но нисколько не помогает нам понять, что же такое потокобезопасность класса.

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

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

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


До версии 5.0 единственными средствами JDK для придания классам свойств потокобезопасности были синхронизация выполнения методов и блоков с помощью ключевого слова synchronized, а взаимодействие осуществлялось с помощью внутренних блокировок объектов и volatile-переменных. Этого оказалось недостаточно для миллионов современных программистов, поэтому наиболее инициативный из них, по имени Даг Ли написал книгу Concurrent Programming in Java. Многие описанные в книге идеи легли в основу JSR 166: Concurrency Utilities и в результате под общим зонтиком java.util.concurrent API, в JDK 5.0 было добавлено множество новых высокоуровневых средств для облегчения задач взаимодействия потоков: блокирующие структуры данных, различные средства синхронизации и много других интересных вещей, которые я рассмотрю в следующей части.

вівторок, 22 лютого 2011 р.

Кеши значений в Java

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

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

Собственно их мне известно три.

Кеш строк

Многие знают, а кто не знает - узнают, что в Java строковые константы часто оказываются равны. Это называется интернированием. Например

public class Nan {
    public static void main(String[] args) {
        CharSequence cs = "hello";
        String s = "hello";
        System.out.println(cs == s);
    }
}

--
true

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

С другой стороны, если вам все же нужно различать одинаковые строки, пользуйтесь оператором new.

public class Nan {
    public static void main(String[] args) {
        String s1 = new String("hello");
        String s2 = new String("hello");
        System.out.println(s1 == s2);
    }
}

-- 
false

Интернирование может быть сделано вручную с помощью метода intern().

public class Nan {
    static String concat(String x, String y) {
        return x + y;
    }
    static void showTruth(String x, String y) {
        System.out.println("ref: " + (x == y) + "\tintern: " + (x == y.intern()));
    }

    public static void main(String[] args) {
        String s = "Hello";
        showTruth(s, "Hello");
        showTruth(s, new String("Hello"));
        showTruth(s, concat("He", "llo"));
    }
}
--
ref: true intern: true
ref: false intern: true
ref: false intern: true


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

Кеши целочисленных оберток

В каждом из классов Long, Integer, Short и Byte присутствует внутренний кеш ссылок на значения от -128 до 127, причем в каждом из классов он реализован по-разному. Лучи ненависти в сторону Sun направляют противники копипасты под негодующие крики ненавистников Java. Что интересно, в Sun JVM присутствует возможность во время выполнения изменить верхний (и только!) предел кеша для Integer (и только!) на произвольное значение с помощью опции -XX:AutoBoxCacheMax или выставив системный параметр java.lang.Integer.IntegerCache.high в необходимое значение

В общем и кратко:

public class Nan {
    public static void main(String[] args) {
        Integer i1 = 10;
        Integer i2 = 10;
        System.out.println(i1 == i2);

        i1 = 128;
        i2 = 128;
        System.out.println(i1 == i2);
    }
}

--
true
false

-- с -Djava.lang.Integer.IntegerCache.high=128
true
true

Внутренний кеш используется при использовании метод valueOf у оберток, что видно в исходном коде, а автобоксинг проиcходит через вызов valueOf. Все значения кеша инициализируются в статическом блоке, что незначительно бьет по скорости первого использования Integer (только не это !).

Кеш логических значений

У обертки Boolean также присутствует кеширование. Его valueOf всегда возвращает ссылку на один из двух внутренних экземпляров: Boolean.TRUE или Boolean.FALSE. В отличии от String у Boolean нету метода intern() поэтому бездумное использование конструктора приведет к перерасходу памяти. Лучше всего всегда-всегда использовать valueOf.

Заключение (censored)

Кеши - вещь, полезная в хозяйстве для любителей поспорить на несколько сотен и блеснуть своей <*> перед коллективом. Как по-мне, целочисленные кеши бесполезны в большинстве задач, где обычно просто нужно забоксить пару значений, а вероятность попадания в кеш ничтожная. Если и есть какой-то выигрыш при итерациях, то для таких случаев можно было б придумать чтото поэлегантней, а не прикручивать <!> к <*>, который к тому же и память занимает в несколько килобайт. К интернированию строк и кешу булевых значений претензий не имею, вполне логично и правильно.

неділя, 6 лютого 2011 р.

2NF для детей

Начало лирического отступления


Довольно интересно повторять все эти нормальные формы, отношения, зависимости. Сразу вспоминается Гриша, как я его не то чтобы особо любил, как преподавателя, но уважал. И курс его мне нравился, один из немногих который я сознательно учил. Помню мы с Костиком и Серегой отсканировали книжку Ульмана, может быть один из последних экземпляров, который кто либо видел :). Вот этот скан меня и выручает.


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


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


Конец лирического отступления

Что же такое вторая нормальная форма или 2NF? Так чтоб трехлетний ребенок понял...

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

Цель нормализации к первой нормальной форме (1NF) - дать возможность построения высказываний о данных с помощью формул логики предикатов первого порядка. На практики это дает возможность построения запросов выборки по условиям, так как значения имеют одинаковую природу.

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

То есть первая НФ имеет дело, со структурой значений записей.

Вторая (и третья) НФ имеет дело уже с ключами и зависимостями в схеме. Перечислим ее цели с пояснениями.


  1. Главной целью приведения ко второй нормальной форме есть желание избавиться от избыточности хранения данных и как следствие избежать аномалий модификации этих данных (аномалий изменения, вставки и удаления)
  2. Второй по порядку, но не по значению, целью нормализации в 2NF есть максимально разбить модель данных на отдельные отношения, чтобы их можно было комбинировать и использовать в выражениях новыми, не предусмотренными изначально способами.
  3. Минимизировать усилия по изменению схемы в случае необходимости. Чем меньше зависимостей внутри схемы, меньше изменений в ней потребуется при изменении модели данных.
  4. Понятность схемы для пользователя. Чем держать все данные в одной большой таблице, проще представить данные как несколько связанных и логически разделенных отношений. Это проще читать, воспринимать, проектировать и поддерживать. В конце концов, любая модель данных начинается на доске или бумаге в виде кружочков, блоков и линий, которые так любят рисовать дети и программисты.


Например, у нас есть схема

R = { 'Идентификатор', 'Название СД-Диска', 'Название группы' },

где первичным ключом является ’Идентификатор’, а альтернативным ключом - ’Название СД-диска’. Эта схема находится во 2NF, поскольку неключевой атрибут ’Название группы’ зависит только от ключа и не зависит от подмножества атрибутов этого ключа (которых собственно нет, см. ниже).

Схема отношения имеет 2NF если любой неключевой атрибут зависит только от ключа, и не зависит от подмножества его атрибутов.

Вообще ставить вопрос о несоответствии 2NF можно только в случае если в схеме есть составные ключи. Схемы с простыми ключами как в примере всегда имеют 2NF. Указанная схема есть как раз пример такого случая, так как в ней оба ключа (а это ’Идентификатор’ и ’Название СД-диска’) простые, и подмножества атрибутов этих ключей пусты.

Несоответствие 2NF рассмотрим на схеме

R = { ’Название группы’, ’Название СД-диска’, ’Название песни’, 'Автор слов’, ’Композитор’ }

Одна и та же песня может входить в несколько дисков, также теоретически возможны одноименные альбомы с одноименными песнями у разных групп, например трибьюты. Поэтому ключом будет { ’Название группы’, ’Название СД-диска’, ’Название песни’ }. При этом атрибуты ’Автор слов’ и ’Композитор’ зависят от множества атрибутов { ’Название группы’, ’Название песни’ }. Это и есть нарушение 2NF.

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

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

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

Чтобы избежать подобных аномалий и убрать избыточность, нам нужно разбить схему, то есть провести декомпозицию, на две схемы:

R1 = { ’Название группы’, ’Название СД’, ’Название песни’ }
R2 = { ’Название группы’, ’Название песни’, ’Автор’, ’Композитор’ }

Обе схемы имеют 2NF, R1 - поскольку у нее нет неключевых атрибутов, а R2 - поскольку ’Автор’ и ’Композитор’ зависят от ключа { ’Название группы’, ’Название песни’ } и не зависят (функционально) от любого из атрибутов 'Название группы’ или ’Название песни’.

Проиллюстрируем на другом примере. У нас есть детали на складах. Все это представлено в таблице вида

----------------------------------------------
| ДЕТАЛЬ | СКЛАД | КОЛИЧЕСТВО | АДРЕС_СКЛАДА |
==================----------------------------

Ключом в данной схеме есть пара { ’Деталь’, ’Склад’ }, но ’Адрес_склада’ функционально зависит только от атрибута ’Склад’, то есть от подмножества атрибутов ключа. Поэтому требования 2NF несоблюдены. Чем плохо? Во-первых, адрес склада будет дублироваться для всех деталей на складе (избыточность) и если адрес изменится, нужно будет изменить все эти записи, чтобы сохранить целостность (могут возникнуть аномалии удаления). Во-вторых, если на складе еще нет деталей, то у нас нет возможности хранить адрес склада, так как схема такую ситуацию не предусматривает. Поэтому добаление нового склада невозможно (аномалия вставки), а вывоз деталей со склада означает, что мы потеряем информацию о его адресе (аномалия удаления).

Вот собственно и все.
Надеюсь было понятно, я же пошел разбираться с 3NF!

Що спільного між архітектурами UNIX та RDBMS?

Повторюю реляційну модель, реляційну алгебру та нормальні форми моделі даних.

Поняття нормальної форми 1NF, я думаю, є саме тим ключовим моментом, що дозволяє реляційним моделям домінувати ось уже 40 років. Ключовий момент 1NF - спрощення складених типів та ієрархічних моделей до плоских відношень зробило СУБД відносно простими системами, у тому плані що дані розбиті на атомарні значення, що мають прості типи. Це дозволяє за допомогою формальних мов (наприклад SQL) та функцій БД будувати запити, не передбачені на початку проектування БД і, таким чином сприяє довгому життєвому циклу реляційних баз даних.