Как стать автором
Обновить

Строковые коллекции только для чтения: экономим на спичках

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

Мы не будем касаться возможности чтения данных из базы по частям: это тема для отдельного разговора. Кроме того, чтение по частям вполне можно сочетать с описанными здесь подходами, добиваясь дополнительной экономии памяти. Также не будем использовать, например, опцию виртуальной машины -XX:+UseCompressedStrings: она экономит память не только в нашем случае и тоже может сочетаться с нашими методами.

Перед тем как что-то оптимизировать, надо это что-то измерить. В нашем случае речь об объёме памяти, занимаемой списком. Причём, разумеется, нас интересует не shallow size (размер самого объекта ArrayList), а retained size (размер ArrayList и всех объектов, на которые он ссылается прямо или косвенно). Замер произведём с помощью Eclipse Memory Analyzer. Найдём нужный объект в куче (например, по имени класса) и воспользуемся опцией Show retained set. Получим такую картину:



Как и предполагалось, сам ArrayList весит совсем немного — 24 байта. Прилично весит массив Object[] ссылок на строки, определённый внутри ArrayList, но всё же больше 90% места съедают сами объекты строк и связанные с ними массивы char[].

Небольшого улучшения можно добиться, если урезать массив Object[] до реального количества элементов. Как известно, ArrayList выделяет место с запасом, чтобы не выделять заново каждый раз, когда добавляется элемент. Раз мы знаем, что элементов больше не добавится, нам этот запас ни к чему. Просто и эффективно это сделать можно так:

List<String> genes = readGenes();
genes = Arrays.asList(genes.toArray(new String[genes.size()]));


Здесь результат уже не ArrayList (точнее ArrayList, но другой). Мы сперва создаём копию массива нужной длины, а затем над копией делаем обёртку. Теперь retained set выглядит так:



Массив стал немного меньше, а в итоге мы сэкономили 0.44% места. Ну ничего, мы только разминаемся.

Посмотрим на эти массивы char[]. Они содержат идентификаторы генов типа «ENSG00000121410» (15 символов — 30 байт), ещё по 8 байт системной информации об объекте да по 4 байта длины. И эти 42 байта выравниваются по 8, то есть ещё добавляется 6 неиспользуемых байт. Таким образом из 48 байт только 30 несут полезную информацию (с +UseCompressedStrings их можно убавить до 15, тогда доля «лишней» информации ещё увеличится). Что с этим можно сделать?

Вспомним, как работает String.substring. Строка, которая получается в результате, делит общий буфер char[] с родительской строкой: в дочерней строке устанавливаются соответствующим образом значения offset и count. При этом дочерняя строка с точки зрения пользователя ничем не отличается от обычной, но если родительская была удалена, то полный буфер всё равно хранится, даже если вы от мегабайтной строки отрезали один символ. Иногда это напрягает, приходится выискивать такие места в коде и подписывать new String, но нам сейчас, наоборот, поможет. Мы посадим все строки массива на один буфер char[]. Для этого напишем вспомогательный метод в каком-нибудь утилитном классе:

public static List<String> compactify(Collection<String> list) {
    StringBuilder sb = new StringBuilder();
    for( String item : list ) sb.append(item);
    String data = sb.toString();
    List<String> result = new ArrayList<String>(list.size());
    int index = 0;
    for( String item : list ) {
        result.add(data.substring(index, index + item.length()));
        index += item.length();
    }
    return result;
}


Метод сперва склеивает все строки исходной коллекции в одну длинную строку, а потом нарезает её на подстроки с помощью substring. Прогоним наш список genes через эту, казалось бы, бесполезную операцию и посмотрим на retained set:



Ага, уже существенно. Сэкономили практически все те лишние байты, о которых говорилось выше, в сумме выиграв 24% от исходного размера. Если строки в вашем массиве короче 15 символов, то экономия будет ещё больше. Заметьте, кстати, что при создании ArrayList мы явно указали его длину, поэтому Object[] не содержит лишних элементов, то есть первую оптимизацию мы не потеряли.

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

Всё же 24% мало. Глаз режут объекты String, которые по сути не несут никакой пользы (сами данные-то в char[]). Может, можно их не хранить, а нарезать строку по требованию? Для этого нам придётся написать свою реализацию List и хранить смещения начал строк:

public class CompactStringList extends AbstractList<String> implements RandomAccess {
    private String data;
    private int[] offsets;
    
    public CompactStringList(Collection<String> list) {
        StringBuilder sb = new StringBuilder();
        offsets = new int[list.size()];
        int offset = 0, i = 0;
        for( String item : list ) {
            sb.append(item);
            offsets[i++] = offset;
            offset+=item.length();
        }
        data = sb.toString();
    }

    public String get(int index) {
        return index == offsets.length - 1 ? data.substring(offsets[index]) : 
            data.substring(offsets[index], offsets[index + 1]);
    }

    public int size() {
        return offsets.length;
    }
}


В конструкторе мы снова склеили все входные строчки в одну, запоминая смещения начал строк в массив. При получении элемента (для простоты я не проверяю корректность параметра) мы отрезаем нужный кусок от строки. При этом создаётся только новый объект String, а сами данные не копируются. Взглянем на retained set такого объекта:



Теперь мы сэкономили 55.5% по сравнению с исходным вариантом, тут уже можно пускаться в пляс.

Конечно же, последняя оптимизация самая спорная и зависит от дальнейших сценариев использования. К примеру, если вы часто делаете get одного и того же элемента и полученные строки сохраняете в других коллекциях, у вас расплодятся объекты String. Хоть они и указывают на общий буфер, но по 40 байт на строку (в 32-битной HotSpot) вы потеряете. Не увлекайтесь оптимизациями ради оптимизаций: может получиться только хуже. Тем не менее, во многих приложениях этот метод может оказаться полезным. Ну или в крайнем случае расширит понимание возможностей Java некоторым читателям.
Теги:
Хабы:
+24
Комментарии 19
Комментарии Комментарии 19

Публикации

Истории

Работа

Java разработчик
356 вакансий

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн