Смесь: Неочевидное + Оптимизация

[Жека]

Всем привет!

Я сейчас занимаюсь оптимизацией приложения: j2me-клиент для мобильной соц. сети Galaxy.
(можете загуглить, не буду рекламировать)

Решил создать эту тему, чтобы делиться наблюдениями, слушать советы и всё такое прочее.

Зачем вообще всё это:
В обычных мобильниках (не смартфонах) для джава-проги доступно около 2 мб оперативной памяти.
Как раз-таки памяти мне и не хватает для юзерского комфорта.

При старте приложения - главный экран - съедается порядка 1 мб.
Остаётся ещё 1 до ошибки "Out of memory".

Что есть в приложении:
* непрерывный коннект к чат-серверу по сокету
* самодельный браузер, псевдо-хтмл, много картинок - грузятся по хттп.
* планета с персонажами (костюмы, одежда), объектами, фоном/интерьером
* чатик


Масштабы проекта:
* 25 packages
* 177 классов и интерфейсов суммарно
Например, в пакете browser 50 классов/интерфейсов.

Что заметно жрёт оперативку:
* создание новых объектов, в частности строк (парсинг страниц, получение команд из сокета)
* картинки (браузер и планета)

Я юзаю ручной вызов GC (сборщик мусора), и по возможности стараюсь перехватить переполнение памяти через
catch(OutOfMemoryError out) {}
но не всегда срабатывает, прога крэшится и закрывается.

Т.к. j2me - это младшая, но родная, сестра "обычной" java, то тема может быть полезна широкому кругу читателей.

Далее отдельными постами рассказ.

[Жека]

0. Для справки

Внутренние объекты java при дефолтном создании:

* Vector - элементы хранятся в массиве.
v = new Vector() - выделяется память под 10 элементов, при выходе за границы внутренний массив вектора пересоздаётся, расширяясь вдвое (могу наврать тут, может и не в 2)

* Hashtable
h = new Hashtable() - размерность таблицы равна 11, хз почему так

* StringBuffer - данные хранятся во внутреннем массиве chars[]
sb = new StringBuffer() - размерность равна 16


1. Коннект и реконнект к чат-серверу

Раньше
при каждом подключении или переподключении создавался новый поток, в котором новый сокет.

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


2. Загрузка ресурсов по http

Раньше
а) на каждый запрос картинки создавался отдельный поток в лоадере
б) для каждой загрузки страницы создавался новый лоадер + поток в нём

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


3. LinkedList vs Vector

Стараюсь по возможности заменить использование Vector на LinkedList, чтобы не тратились ресурсы при расширении размерности вектора.
* LinkedList - мой самодельный двунаправленный список, ибо в комплекте j2me списков нет.
Vector хорош, когда нужен произвольный доступ к элементам по индексу в массиве.


4. Шрифты

Используются рисованные шрифты. При загрузке красятся в несколько цветов.
Для кнопочной версии приложения красим, подменяя цвета в палитре, для сенсорной версии переводим картинку в rgba[], красим через hsv преобразование, и далее создаём из полученных new_rgba[] новую картинку.

Раньше
для каждого шрифта грузились все данные, картинки + описательные структуры данных, массивы смещений символов и массивы ширин букв и прочее

Теперь
для одинаковых шрифтов, различающихся только цветом, грузим описательные структуры только 1 раз, остальным шрифтам присваиваем указатели на эти структуры.
В частности, в шрифте есть массивы
* private int arrWidth[];
* private int arrBlock[];
* private int arrOffset[];
Количество символов = 337. На 1 шрифт приходится 337*3*4 = 4044 байта. Умножим это на 5 крашенных вариантов и получим 20,2 кб. гуд!



5. Смайлы, ч1

Раньше мы использовали анимированные смайлы.
Пришлось для хранения смайла использовать класс View, который умеет проигрывать анимацию.
View содержит набор Pic
Pic содержит ImageObject
ImageObject содержит Image (это джавовская картинка)
* ImageObject - обёртка над стандартной картинкой, хранить ключ-url и саму картинку, и немного служебной инфы

Раньше
каждый смайл имел тип View

Теперь
каждый смайл имеет тип ImageObject
Это позволило съэконосить 70 кб памяти!
В любом случае, буду делать рефактор классов View и Pic.


6. Смайлы, ч2
В данный момент пытаюсь улучшить функцию разбивки текста на текст и смайлы.
RegExp'ов в j2me нет, да они и оперативы жрут скорее всего больше доступного.
Всего есть 76 текстовых вариантов смайлов.

Сейчас
1. проходим по всем смайлам, ищём их в строке, запоминаем самый ближний к началу строки
2. делим строку на текст до смайла (если есть), сам смайл (если есть) и остаток строки снова подаём на вход пункта 1.

Пока что сделал предварительную проверку по 4 символам, которые уникальны для смайлов - : ; % ) и др.
Для строк без смайлов это даёт прирост скорости раз в 7. Со смайлами - замедляет, но не сильно, т.к. джавовский string.IndexOf() работает очень шустро.


Сложение строк

На днях я обнаружил опасность.
При сложении строк компилятор подставляет туда StringBuffer.
s = s+"1024"; превратится в
s = new StringBuffer().append(s).append(1024).toString();

Bроде всё круто, но при этом StringBuffer будет пересоздавать/расширять внутренний массив, и мы получаем в оперативке массив, почти вдвое больший чем сумма наших исходных строк!

В джаве строки - это структуры со ссылкой на массив chars[] и переменными start и len.

Если текст жирный, например 10+ кб, как браузерная страница, то прибавлением к строке любого символа расширит строку до двукратного размера.

Можно обрезать лишние символы в оперативке через
s = new String(s)
если на них больше никто не ссылается, но они всё равно будут живы до очередного вызова сборщика мусора.


Продолжение следует.

[Жека]

Улучшение поиска смайлов в тексте. Завершил.

Фишки новой функции:
* предварительный поиск смайловых символов (даёт ускорение только если в тексте нет смайлов)
* поиск сразу всех смайлов, сортировка по позиции смайла в тексте делается сразу

Т.к. текстовые варианты некоторых смайлов являются подстрокой других, например "0 : )" или "{ : )" включают в себя ": )", то пришлось делать проверку - не попадает ли очередной найденный смайл в позицию уже найденных.
Проверка - это цикл по найденным смайлам. Раз уж никуда не деться от этого цикла, то в нём делаю проверку соотнесения позиции текущего найденного смайла с найденными ранее, тем самым определяю позицию для вставки, т.е. не нужно потом сортировать все смайлы по позиции.

Зачем нужна сортировка? Чтобы можно было указывать лимит смайлов, свыше которого всё считается обычным текстом.

Победа:
* время поиска сократилось в 2 раза
* объём потребляемой памяти сократился в 3 раза

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

Тестирование:
Для теста взял некий текст (под спойлером) длиной 639 символов, содержащий в середине 4 смайла.

"Женщины - как яблоки . Самые вкусные висят на самой макушке дерева. Многие Мужчины не хотят лезть на дерево за вкусными яблоками, потому что они боятся упасть и удариться. Вместо этого они собирают упавшие яблоки с земли, которые не так хороши, но зато доступны. Поэтому яблоки на макушке думают, что с ними, что-то не так, хотя на самом деле - ОНИ ВЕЛИКОЛЕПНЫ! Женщины - как яблоки :-.. Самые вкусные висят на самой макушке дерева. Им просто нужно дождаться того человека, который не побоится залезть на макушку дерева. Отправь это сообщение Женщинам, которых ты ЛЮБИШЬ! Милая, красивая, нежная! ЛЮБИ И БУДЬ ЛЮБИМА! Счастья тебе! "

Поиск производился в цикле, 500 итераций.

Результаты теста:

* новая функция, тест №1:
использовано памяти перед тестом: 943 кб
время выполнения: 1836 мс
память после теста: 1254 кб

* старая функция, тест №2:
использовано памяти перед тестом: 943 кб
время выполнения: 4361 мс
память после теста: 1896 кб

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

Спасибо за внимание!

[Жека]

Загрузка текста из файла

Джава хорошо дружит с кодировкой UTF-8.
В ней на один символ приходится от 1 до 2 байтов.

Когда-то давно я пробовал загрузить текст из файла, и возникли проблемы.
В итоге я извратился, сделав свой формат строки, в котором символ представлен по типу джавовского:
size|byte1[byte2]

Так и жил с этим.
А недавно, делая проект на андроид, и пытаясь там грузить УТФ-текст из файла, я обнаружил, что в начале строки вылазит какой-то непонятный символ, но остальная часть строки нормальная.
Сделал самое простое: t = t.substring(1)
Но так как этот символ есть не всегда, то пришлось в начало добавлять спец. символ, типа #, и далее
i = t.indexOf('#');
t = t.substring(i);

Как-то это стрёмно, вставлять символ, выцеплять подстроку.

А потом обнаружил в Notepad++ кодировку "UTF-8 without BOM", решил сохранить в неё, и вуаля - всё чётко, только мой текст!

Ещё:

* в Qt строки в utf-8 сохраняются без BOM.
* в php чтение из файла - тоже лучше использовать без BOM, иначе левый символ в начале
* ответ на стековерфлоу: What's different between utf-8 and utf-8 without BOM?

Даёшь хранение текста в формате "UTF-8 without BOM"!

Моя функция загрузки текста:

public static String loadText(final String path) {
    try {
        final InputStream is = Utils.class.getResourceAsStream(path);
        final DataInputStream dis = new DataInputStream(is);
        int size = dis.available();
        byte b[] = new byte[size];
        int actual = dis.read(b);
        dis.close();
        is.close();
        String s = (new String(b, 0, actual, "UTF-8")).trim();
        return s;
    }
    catch(Exception e) {}
    return null;
} 


[impersonalis]

Сообщение от Жека

Джава хорошо дружит с кодировкой UTF-8.
В ней на один символ приходится от 1 до 2 байтов.

Но ведь в UTF-8 символ, в общем случае, может занимать от 1 до 6 байт. Или "в ней"="в джаве"? (хотя на вряд ли будут использоваться символы из не базовой плоскости)

[Жека]

imper, да я попутал, спасибо за уточнение!

[Жека]

Hashtable

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

Зато это избавит меня от пересоздания "внутренностей" хэш-таблицы при достижении maxCapacity.

Вот статья для углубленного изучения: java.util.Hashtable from inside (на русском).

[Igor]

Может, не перебором, а хотя бы бинарный? Отсортировать по ключам, если, конечно, нет частых вставок и удалений.
И ещё - для поиска смайликов можно всё-таки сделать конечный автомат. Не знаю как по памяти, но по скорости выполнения должен быть сильно лучше.

[Жека]

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

Igor, можешь дать ссылок или описать суть того, как конечный автомат применить к смайлам?

[Igor]

Во всяких парсерах для компиляторов активно используется.
моё видение того как оно работает:

есть текст и смайлики ": )", ": (" и "{ : )"
посимвольно читаем текст, есть несколько состояний, входной символ в переменной "с"
1) (начальное состояние)
(с == ":") -> 2
(c == "{") -> 3
иначе подаем на выход c и не меняем состояние
2)
(с== ")"), выдаём смайлик и переходим в 1
(с == "("), выдаём смайлик и переходим в 1
(с== "{") выводим ":" (это не кусок смайлика), переходим в 3
иначе выводим ":" + c и переходим в 1
3)
(с == ":") -> 4
иначе выводим "{" + c и переходим в 1
4)
(с == ")") выводим смайл "{", переходим в 1
(c == "("), выводим "{" + "", переходим в 1
иначе выводим "{:" + c и переходим в 1.

Если всё просто, можно захардкодить вручную, если сложно, то пишут штуку, которая это делает сама.

[Жека]

Понял суть, спасибо.
Хардкодить не наш метод, ибо 76 комбинаций, начиная от : ) и заканчивая :troll:
Всё же эти посимвольные проверки окажутся медленнее чем поиск подстроки всей текстовой комбинации смайла (инфа почти 100%).

Волшебный String.indexOf ()

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

Что за проверки? Зачем?

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

Для них и были проверки некие в цикле по тексту.

char c = text.charAt (k);
if (c >= '0' && c <= '9') {
    block = DIGITS;
    offset = k;
} 


И так для всех диапазонов (русские, англ, закорючки).

Однако! Это оказалось медленнее, чем

offset = ALL_FONT_CHARS.indexOf (text.charAt (k)); 


ALL_FONT_CHARS содержит все доступные для отрисовки символы шрифта.

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

Кстати, буквы ёЁ стоят особняком от остальных русских букв в таблице символов, что совсем нектати.

[impersonalis]

Сообщение от Жека

Кстати, буквы ёЁ стоят особняком от остальных русских букв в таблице символов

в CP-1251 (Windows-1251)

[Жека]

Копирование массивов, System.arrayCopy()

Чудесный и шустрый метод для копирования данных из одного массива в другой, как целиком, так и части.

У себя в коде использую

* при расширении массивов, создаём массив большего размера, копируем в него текущий массив (надо бы избавиться от этих expand'ов)

* при чтении байтов из сокета

Чтение из сокета:

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

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

for(int k = lastPos; k < size; ++k) {
    buf[k-lastPos] = buf[k];
}

//size = 2048 байт
//lastPos - позиция неполной команды

Сравнил скорость присвоения в цикле и arrayCopy, копирование побеждает.

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

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

Официальное описание функции arrayCopy() (english).

[Жека]

Сообщение от impersonalis

в CP-1251 (Windows-1251)

разве только там? вот например таблица utf http://unicode-table.com/ru/

[impersonalis]

Сообщение от Жека

разве только там? вот например таблица utf http://unicode-table.com/ru/

Не только, но и не везде. Если речь только о unicode - то ок