В задачах поиска информации одной из важнейших задач является поиск точно заданной подстроки в строке. Примитивный алгоритм поиска подстроки в строке основан на переборе всех подстрок, длина которых равна длине шаблона поиска, и посимвольном сравнении таких подстрок с шаблоном поиска. По традиции шаблон поиска или образец принято обозначать как needle (англ. «иголка»), а строку, в которой ведётся поиск — как haystack (англ. «стог сена»). На языке Python примитивный алгоритм выглядит так:

index = -1
for i in xrange(len(haystack)-len(needle)+1):
    success = True
    for j in xrange(len(needle)):
        if needle[j]<>haystack[i+j]:
            success = False
            break
    if success:
        index = i
        break
print index

Обозначим n=|haystack|, m=|needle|. Простейший алгоритм поиска даже в лучшем случае проводит n–m+1 сравнений; если же есть много частичных совпадений, скорость снижается до O(n*m).

Рассматриваемый далее алгоритм хотя и имеет невысокую скорость на «хороших» данных, но это компенсируется отсутствием регрессии на «плохих». Алгоритм Кнута-Морриса-Пратта является одним из первых алгоритмов с линейной оценкой в худшем случае.

В октябре на хабре появилась замечательная статья про работу HashMap. Продолжая данную тему, я собираюсь рассказать о реализации java.util.concurrent.ConcurrentHashMap.
Итак, как же появился ConcurrentHashMap, какие у него есть преимущества и как он был реализован.

Эта статья рассказывает о времени выполнения и о расходе памяти большинства алгоритмов используемых в информатике. В прошлом, когда я готовился к прохождению собеседования я потратил много времени исследуя интернет для поиска информации о лучшем, среднем и худшем случае работы алгоритмов поиска и сортировки, чтобы заданный вопрос на собеседовании не поставил меня в тупик. За последние несколько лет я проходил интервью в нескольких стартапах из Силиконовой долины, а также в некоторых крупных компаниях таких как Yahoo, eBay, LinkedIn и Google и каждый раз, когда я готовился к интервью, я подумал: «Почему никто не создал хорошую шпаргалку по асимптотической сложности алгоритмов? ». Чтобы сохранить ваше время я создал такую шпаргалку. Наслаждайтесь!

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

Продолжая цикл статей об Hyperboria, в этой статье будут рассмотрены следующие аспекты:
1) Количество IP адресов в Hyperboria, как они генерируются.
2) Коллизии и как с ними бороться.
3) Почему используется служебный (приватный) диапазон IPv6 адресов.
4) Роутеры и Hyperboria.
5) Маршруты и DHT.
6) Защищенность сети.

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

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

Здравствуйте! В этой статье я вкратце расскажу вам о процессах, потоках, и об основах многопоточного программирования на языке Java.
Наиболее очевидная область применения многопоточности – это программирование интерфейсов. Многопоточность незаменима тогда, когда необходимо, чтобы графический интерфейс продолжал отзываться на действия пользователя во время выполнения некоторой обработки информации. Например, поток, отвечающий за интерфейс, может ждать завершения другого потока, загружающего файл из интернета, и в это время выводить некоторую анимацию или обновлять прогресс-бар. Кроме того он может остановить поток загружающий файл, если была нажата кнопка «отмена».

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

Давайте начнем. Сначала о процессах.

В статье описывается решение для мониторинга с использованием Cacti на примере задачи анализа и контроля потребления ресурсов большого Java-приложения.

Передо мной стояла задача – в краткие сроки предложить меры по стабилизации большого трехзвенного Java-приложения, имеющего проблемы с потреблением памяти и производительностью. Времени, как обычно, мало: 1-2 недели на все. На фирме отсутствовала подходящая инфраструктура мониторинга приложений, и в мою задачу не входило ее создавать. Вариант с использованием JConsole не подходил из-за необходимости анализировать потребление за продолжительное время и смотреть его после возможных внезапных перезагрузок приложений.

В одной из фирм, где я работал, было реализовано впечатляющее по удобству и простоте решение для мониторинга Java-приложений на основе RRD Tool. Состояло оно из несложной надстройки на perl-скриптах, обеспечивающих сбор и отображение данных через HTTP и ряда доработок-агентов сбора данных в самом приложении. Для меня это стало идеей решения, однако, времени на написание обвязки над RRD у меня не было.

После аккуратного поиска нашелся бесплатный инструмент, реализующий необходимую мне надстройку – Cacti. Cacti это приложение, написанное в инфраструктуре Apache-PHP-MySql, позволяющее настраивать сбор и отображение данных мониторинга на основе веб-интерфейса. Разобраться с ним оказалось несложно, пару дней для подъема инфраструктуры, затем настройка и дописывание агентов сбора данных и все.

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

Мне было интересно, какие коллекции сколько съедают дополнительной памяти при хранении объектов. Я провёл замеры накладных расходов для популярных коллекций, предполагающих хранение однотипных элементов (то есть списки и множества) и свёл результаты на общий график. Вот картинка для 64-битной Hotspot JVM (Java 1.6):

Существует типичная проблема в большом классе задач, которая возникает при обработке потока сообщений:

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

При этом существуют некоторые ограничения на поток данных:

• поток не равномерный и состоит из событий разного типа
• количество типов событий заранее не известно, но некоторое конечное число
• каждый тип события имеет свою актуальность во времени
• все типы событий имеют равный приоритет

На диаграмме приведён пример разрешения проблемы: нагребатор(tm), работающий на нитке T₁, в то время как разгребатор(tm) работает на нитке T₂

• за время обработки события типа A успевают прийти новые события как типа B, так и A
• после обработки события типа B необходимо обработать наиболее актуальное событие типа A

Т.о. стоит задача о выполнении задач по ключу, так, что выполняется только самая актуальная из всех задач по данному ключу.

На суд публике представляется созданный нами ThrottlingExecutor.

Замечание терминологии: stream есть поток данных, тогда как thread есть нитка или нить выполнения. И не стоит путать потоки с нитками.

Замечание 1: проблема осложняется ещё тем, что может быть несколько нагребаторов(tm), при этом каждый нагребатор(tm) может порождать только события одного типа; с другой стороны есть потребность в нескольких (конечно же, для простоты можно выбрать N=1) разгребаторах(tm).

Замечание 2: мало того, что данный код должен работать в многопоточной (конкурентной) среде — т.е то самое множество нагребаторов(tm) — разгребаторов(tm), код должен работать с максимальной производительностью и низкими latency. Резонно к этим всем качествам добавить ещё и свойство garbage less.

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

С каждым днем слово java все больше и больше воспринимается уже не как язык, а как платформа благодаря небезызвестному invokeDynamic. Именно поэтому сегодня я бы хотел поговорить про виртуальную java машину, а именно — об так называемых Performance опциях в Oracle HotSpot JVM версии 1.6 и выше (server). Потому что сегодня почти не встретить людей, которые знают что-то больше чем -Xmx, -Xms и -Xss. В свое время, когда я начал углубляться в тему, то обнаружил огромное количество интересной информации, которой и хочу поделится. Отправной точкой, понятное дело, послужила официальная документация от Oracle. А дальше — гугл, эксперименты и общение:

-XX:+DoEscapeAnalysis

Начну, пожалуй, с самой интересной опции — DoEscapeAnalysis. Как многие из Вас знают, примитивы и ссылки на объекты создаются не в куче, а выделяются на стеке потока (256КБ по умолчанию для Hotspot). Вполне очевидно, что язык java не позволяет создавать объекты на стеке на прямую. Но это вполне себе может проделывать Ваша JVM 1.6 начиная с 14 апдейта.

Про то, как работает сам алгоритм можно прочитать тут (PDF). Если коротко, то:

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

Для реализации данного алгоритма строится и используется так называемый — граф связей (connection graph), по которому на этапе анализа (алгоритмов анализа — несколько) осуществляется проход для нахождения пересечений с другими потоками и методами.
Таким образом после прохода графа связей для любого объекта возможно одно из следующих следующих состояний:

• GlobalEscape — объект доступен из других потоков и из других методов, например статическое поле.
• ArgEscape — объект был передан как аргумент или на него есть ссылка из объекта аргумента, но сам он не выходит из области видимости потока в котором был создан.
• NoEscape — объект не покидает область видимости метода и его создание может быть вынесено на стек.

После этапа анализа, уже сама JVM проводит возможную оптимизацию: в случае если объект NoEscape, то он может быть создан на стеке; если объект NoEscape или ArgEscape, то операции синхронизации над ним могут быть удалены.

Следует уточнить, что на стеке создается не сам объект а его поля. Так как JVM заменяет цельный объект на совокупность его полей (спасибо Walrus за уточнение).

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

    for (int i = 0; i < 1000*1000*1000; i++) {
        Foo foo = new Foo();
    }

скорость выполнения может увеличится в 8-15 раз. Хотя, на казалось бы, очевидных случаях из практики о которых недавно писалось (тут и тут) EscapeAnalys не работает. Подозреваю, что это связано с размером стека.

Кстати, EscapeAnalysis как раз частично ответственен за известный спор про StringBuilder и StringBuffer. То есть, если Вы вдруг в методе использовали StringBuffer вместо StringBuilder, то EscapeAnalysis (в случае срабатывания) устранит блокировки для StringBuffer'а, после чего StringBuffer вполне превращается в StringBuilder.

Если вы словили OutOfMemoryError, то это вовсе не значит, что ваше приложение создает много объектов, которые не могут почиститься сборщиком мусора и заполняют всю память, выделенную вами с помощью параметра -Xmx. Я, как минимум, могу придумать два других случая, когда вы можете увидеть эту ошибку. Дело в том, что память java процесса не ограничивается областью -Xmx, где ваше приложение программно создает объекты.