Пост «Кое-что о весе страницы» вызвал у меня желание написать маленькое дополнение. Многие замечают, что оптимизация размера веб-страниц становится менее актуальной в связи с увеличением пропускных способностей каналов. Рано или поздно все будут сидеть на гигабите, и будет совершенно неважно, весит ваша страница 100Кб или 250. Возможно, так оно и будет. Однако помимо скорости канала есть и другой параметр — задержка или латентность. И если пропускная способность каналов с развитием технологий может вырасти ещё очень сильно, то у латентности существует физический предел: это скорость света в оптоволокне — около 200 тысяч километров в секунду.

Хотя эта скорость очень велика, но всё же недостаточно, чтобы о ней забывать, ведь и планета у нас немаленькая. Wolfram Alpha не зря выдаёт на запросы по расстоянию время прохождения этого расстояния светом в волокне. Пусть у вас стоит сервер в Токио, а клиент пришёл из Рио-де-Жанейро. Если даже эти два города соединить оптоволокном по кратчайшей траектории на поверхности Земли, свет будет идти 86.7 мс.

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

Многие в общих чертах представляют, как работает обратная лучевая трассировка: через каждый пиксель окна вывода алгоритм пропускает луч и вычисляет, с какими объектами сцены он пересекается и как в результате данный пиксель должен быть освещён. Алгоритм по сути требует, чтобы у нас была функция, которая для каждой позиции возвращает цвет точки. Разумеется, тот же подход можно применять не только для трёхмерной графики: любое изображение можно растеризовать таким образом, если у нас есть подходящая функция. Рассмотрим для примера, как с помощью такого подхода решить задачу визуализации диаграмм разложения на простые множители, о которой написал helarqjsc.

Моя реализация здесь. На картинке изображено 10! = 3628800, хотя всех деталей, разумеется, не видно.

Как известно, в Java существуют примитивные типы для чисел (byte, short, int, long, float, double) и объектные обёртки над ними (Byte, Short, Integer, Long, Float, Double). В различных статьях можно встретить диаметрально противоположные рекомендации о том, чем пользоваться. С одной стороны объектные обёртки универсальны: их можно использовать со стандартными коллекциями, которые удобны, инкапсулированы и вообще прекрасны. Но боксинг убивает производительность и ест кучу памяти. Примитивные типы быстры и компактны, но их можно поместить только в массивы, которые и от записи не защитишь, и абстракция на нуле. Если же вам нужно что-то типа Map, для отображения чего-нибудь на числа, то придётся либо мириться с потерей производительности и памяти, либо использовать сторонние библиотеки, реализующие нестандартный интерфейс. Однако в некоторых случаях вам помогут изменяемые (mutable) числа.

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

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

List<String> getElements(String key);

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

public interface MyCollection {
    List<String> getElements(String key);
    String getElement(String key, int index);
    List<String> getElementsRange(String key, int fromIndex, int toIndex);
    int getElementsCount(String key);
}

Я собрал здесь некоторые не очень очевидные факты о заглавных и строчных буквах, с которыми может столкнуться программист в работе. Многие из вас переводили строки во «все заглавные» (uppercase), «все строчные» (lowercase), «первую заглавную, а остальные строчные» (titlecase). Ещё более популярна операция сравнения без учёта регистра. В мировом масштабе такие операции могут быть весьма нетривиальны. Пост построен в виде «сборника заблуждений» с контрпримерами.

1. Если я переведу строку в uppercase или lowercase, число Unicode-символов не изменится.

Нет. В тексте могут попасться строчные лигатуры, которым не соответствует один символ в верхнем регистре. Например, при переводе в uppercase: fi (U+FB00) -> FI (U+0046, U+0049)

2. Лигатуры — изврат, ими никто не пользуется. Если их не учитывать, то я прав.

Нет. Некоторым буквам с диакритикой нет точного соответствия в другом регистре, поэтому приходится использовать комбинированный символ. Скажем, в языке африкаанс есть буква ʼn (U+0149). В верхнем регистре ей соответствует комбинация из двух символов: (U+02BC, U+004E). Если вам попадётся транслитерация арабского текста, вы можете столкнуться с (U+1E96), которой в верхнем регистре также нет односимвольного соответствия, поэтому придётся заменять на (U+0048, U+0331). В ваханском языке есть буква (U+01F0) с аналогичной проблемой. Вы можете возразить, что это экзотика, однако на африкаанс в википедии 23000 статей.

3. Ну хорошо, но давайте считать комбинированный символ (с участием modifying или combining code points) одним символом. Тогда длина всё же сохранится.

Нет. Есть, например, в немецком языке буква «эсцет» ß (U+00DF). При переводе в верхний регистр, она превращается в два символа SS (U+0053, U+0053).

Недавняя статья на Slashdot о программировании игр на ассемблере для Атари (Donkey Kong и я) напомнила об ассемблерных приложениях, которые я писал по молодости, и о компьютерах, которые у нас тогда были.

Поначалу я набирался опыта на DEC PDP-8, но самый кайф начался, когда появилась CP/M. CP/M изначально была «операционной системой для бизнеса», но ещё это была система, которую можно было позволить себе иметь дома, — серьёзная вещь для молодого подающего надежды гика.

Нередко случается, что какие-то данные программа загружает в память и оставляет их там надолго (а то и до конца работы) в неизменном виде. При этом используются структуры данных, оптимизированные как для чтения, так и для записи. Например, вы вычитываете из базы Ensembl список идентификаторов всех генов человека (включая всякие микроРНК и т. д. — всего чуть больше 50000). Если их прочитать в стандартный ArrayList, то на 32-битной HotSpot вы потратите чуть больше 4 мегабайт. Можно ли сэкономить память, зная, что коллекция больше не будет меняться?

Сегодня немного поэкспериментируем с методом finalize() и уничтожением объектов. Хотя даже начинающие Java-программисты примерно представляют, что finalize() вызывается, когда сборщик мусора решит уничтожить ваш объект, некоторые вещи могут всё-таки оказаться неожиданными. К примеру, зададимся вопросом: что случится с вашим приложением, если метод finalize() работает очень долго?

Размеры объектов в Java уже обсуждались на Хабре, например, здесь или здесь. Мне бы хотелось подробнее остановиться на размерах многомерных массивов — простая вещь, которая для меня стала неожиданной.

Оптимизируя вычислительный алгоритм по памяти, я наткнулся на то, что при определённых (вполне разумных) входных параметрах создаётся массив float[500][14761][2]. Сколько он может занимать в памяти (на HotSpot 1.6.0_26 32bit, если кому интересно)? Я примерно прикинул, что 500*14 761*2*sizeof(float) = 500*14 761*2*4 = 59 044 000 байт плюс какой-то оверхед. Решив проверить, как на самом деле, я воспользовался Eclipse Memory Analyzer (невероятно волшебная вещь, рекомендую!) и обнаружил, что «Retained Heap» для этого массива составляет 206 662 016 байт! Неплохой оверхед — 350%. Посмотрим, почему так получилось.

Вчера в багзилле mozilla.org с резолюцией WONTFIX закрыли баг №641509 «onbeforeunload event does not display site-supplied text, only standard message», судя по комментариям, окончательно и бесповоротно. В связи с этим захотелось написать немного об истории вопроса.

Просматривая различный код по выводу на экран какой-нибудь даже примитивной графики, я заметил чрезмерную любовь некоторых программистов к тригонометрии. Часто код пестрит синусами, косинусами и арктангенсами там, где без них можно обойтись. Этим грешат даже хорошие программисты, которые способны спроектировать сложную систему, но почему-то не освоили вектора в объёме школьной программы. Буквально азов векторной алгебры хватает для решения многих насущных проблем. В этом топике я хочу провести краткий ликбез, напомнить основные действия с векторами на плоскости и в качестве примера решить две задачи без тригонометрии: поиск отражённого луча по падающему лучу и произвольно расположенному зеркалу, а также рисование наконечника стрелки. Если вы можете представить в голове рисование произвольно направленной стрелки без синусов и косинусов, смело пропускайте этот топик. Для остальных постараюсь объяснять попроще.

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

Основное различие, разумеется, в том, что Integer — это полнофункциональный объект, который занимает место в куче, а в коде вы пользуетесь ссылками на него, которые неявно преобразуются в значения:

int a = 1000; // a - число
Integer b = 1000; // b - ссылка на объект

При присваивании значения переменной типа Integer обычно выделяется память в куче под новый объект, как будто вы написали new Integer(1000) (так называемый autoboxing). Однако иногда переиспользуются старые объекты. Это иллюстрирует следующий код (JDK 1.6):

Integer a1 = 50;
Integer a2 = 50;
Integer b1 = 500;
Integer b2 = 500;
System.out.println(a1==a2);
System.out.println(b1==b2);

Результатом выполнения будет:

true
false

Возможно, многие из читателей задавались вопросом, как людям удаётся собирать кубик Рубика 3×3 за 7 секунд. Если даже предположить, что рекордсмену сильно повезло, то таблица мирового рейтинга по среднему из пяти результатов уже не оставляет сомнений: если больше 80 человек в среднем укладываются в 12 секунд, очевидно они что-то знают. В этом кратком обзоре я постараюсь приоткрыть секреты скоростной сборки. Сразу оговорюсь, что после прочтения этой статьи вы не станете чемпионами: здесь приведены только основные моменты и ссылки на более подробную информацию. Кроме того, даже после изучения метода полностью вам потребуются долгие тренировки для достижения хороших результатов. Зато вы получите неплохое представление о том, как это делается, и при желании будете знать, куда двигаться дальше. Я думаю, при достаточной усидчивости после нескольких месяцев тренировок многие смогут достичь среднего результата в районе 30 секунд.

Недавние посты об алгоритме сборки кубика 5×5 сподвигли меня написать эмулятор кубика на канвас. Автором статей про сборку предлагался свой кубик на OpenGL, но он мне многим не понравился. Надеюсь, с моим кому-нибудь удастся освоить алгоритм быстрее. Некоторые особенности и преимущества:

• Кроссплатформенность, кроссбраузерность (IE за браузер не считаем), ненужность инсталлятора и прочие преимущества веб-приложения.
• Поддержка кубиков от 2×2 и до бесконечности (пока грани не станут сильно маленькими и рендеринг не начнёт жестоко тормозить). В интерфейс вынесено до 11×11, но в библиотеке ограничений нет.
• Псевдообъёмные грани для красоты.
• Бесконечный undo-буфер.
• Возможность замеса кубика (shuffle).
• Слои вращаются легко и интуитивно, быстро привыкаешь. Крутить весь кубик (мышкой с зажатым шифтом или правой кнопкой) не так легко, но тоже можно привыкнуть.
• Вся библиотека компактная, размещается в одном js-файле и не имеет никаких внешних зависимостей.
• Лицензия MIT, а также открытые и не очень страшные исходники позволяют вставить кубик на ваш сайт и доработать по вкусу.

Осторожно: этот топик полон старческого брюзжания.

В то время как рынок гаджетов всё больше эволюционирует в сторону сенсорных экранов, а интерфейсы упрощаются до невозможности, я продолжаю с ностальгией вспоминать старые добрые кнопочки. Особенно меня убивают интерфейсы mp3-плееров, в том числе совмещённых с сотовыми. Современные устройства будто направлены на то, чтобы для простой операции вроде переключения трека я должен неспеша достать гаджет из кармана, провести рукой по его плавным линиям, полюбоваться внешним видом и нежно потыкать в сенсорный экран, наслаждаясь каждым кликом. Управление плеерами свелось до пяти кнопок: трек назад, воспроизведение/пауза, трек вперёд, громкость вверх, громкость вниз. Сейчас уже считаешь за счастье, если хотя бы эти операции можно сделать, на секунду сунув руку в карман. Не у всех устройств даже эти кнопки легко находятся на ощупь, либо постоянно нажимаются непроизвольно, из-за чего приходится всегда включать/выключать режим Hold, который иногда тоже замучаешься снимать. Что-то чуть менее тривиальное требует манипуляций с менюшками и сенсорным экраном, которые могут занять до 10 секунд. Особенно весело этим заниматься в переполненном автобусе.

Upd: описанный ниже эффект проявляется только в MySQL ниже 5.1.25 — спасибо pharod.

Случайно обнаружился интересный эффект, приводивший к багу в приложении:

mysql> create table test(a int,b int);
Query OK, 0 rows affected (0.11 sec)

mysql> prepare ps from "select * from test";
Query OK, 0 rows affected (0.00 sec)
Statement prepared

mysql> alter table test drop column b;
Query OK, 0 rows affected (0.27 sec)
Records: 0 Duplicates: 0 Warnings: 0

mysql> execute ps;
ERROR 1054 (42S22): Unknown column 'testdb.test.b' in 'field list'

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

В реальной жизни проблема обнаружилась так: класс, отвечающий за общение с базой, кэширует prepared statements. Закэшированные statements поломались, когда потребовалось во время выполнения менять схему базы (не спрашивайте, зачем потребовалось: не всё в жизни делается так, как нам хочется). Будьте осторожнее!

Пост babarun про 3d-движок на js вызвал творческий порыв добавить тонирование Гуро для пущей реалистичности. Вот, что получилось (а сейчас ещё и с зеркальностью). По сравнению с обычным (flat) тонированием нормали требуется иметь не для граней, а для вершин (то есть для треугольной грани три нормали). По готовым нормалям граней нормали вершин вычисляются просто усреднением нормалей всех граней, включающих данную вершину; это делается один раз перед рендерингом. Освещённость вершин высчитывается в начале каждого кадра с учётом изменения положения камеры.

Основная сложность заключалась в том, как залить треугольник градиентом.

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

• Модерация веб-форума: массовый перенос, блокировка, удаление тем.
• Почтовый клиент: отметить выделенные письма как (не)прочитанные, добавить метку, перенести в спам.
• Система обработки научных данных: выделить интересующие строки в подмножество, пометить цветом, как заслуживающие внимания.

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

Я придумал простую штуку, которая позволяет решить все эти эти задачи. Она внедрена в одном коммерческом веб-приложении и хорошо себя зарекомендовала. Не видел более удобного решения, поэтому представляю на суд общественности.

Внезапно встретил такой JS-код:
var a = ~~b;
Сразу вспомнил, что ~ — это битовое дополнение, показалось, что написано просто
var a = b;
Однако битовые операции применимы только к целым числам, поэтому тут ещё неявное приведение типа. Самый короткий способ написать var a = Math.floor(b);?

Но не ведитесь на короткую крутую запись: Math.floor() работает вдвое быстрее (проверил в FF3.6).

~~$x для округления работает и в Перле, причём по времени столько же, сколько int($x). Интересно, что в других языках? В Питоне, наверно, тоже сработает? Upd: не сработало.