Pull to refresh

Comments 85

К сожалению в Яве не существует встроенных механизмов, чтобы напрямую сократить потребление памяти при работе со строками

Существуют. Вы можете работать с массивом байт вместо класса String. Как, например, это делают в проекте Netty (смотреть класс AsciiString). Так же в Java 9 на подходе JEP 254.
Не согласен.

1) Массив байт даёт выигрыш в 1 байт на символ (из пяти!). Просто по той причине, что если вы хотите использовать .hashCode и .equals, вам придётся положить массив в объект-контейнер, который будет отвечать за хэширование и сравнение.
2) Это ни разу не встроенный механизм, а свой велосипед.
3) JEP 254 — это хотя бы намёк на то, что разработчики знают о существовании проблемы. Но это опять же экономия в 1 байт для строк с латиницей. Для национальных языков выигрыш отсутствует.

Основной расход памяти здесь не на сами символы (в тесте их просто нет), а на дорогущие обвязки объектов и неспособность Java хранить объектные поля рядом с самим экземпляром. Есть подстольные решения для последнего, но это ещё более велосипед.
UFO just landed and posted this here
Я исключительно имею ввиду, что если использовать свою реализацию строк, то придётся обернуть её в контейнер для использования в любой структуре данных в качестве ключа. И выигрыш сводится к более компактному хранению массива символов, а это несущественная экономия.

Если использовать решение со складыванием содержимого всех строк в один большой массив — там уже начинаются варианты. Но это государство в государстве, по сути своя модель управления памятью.
UFO just landed and posted this here
Предложение описано в секции «Как бороться», пункт 2. Не использовать java.lang.String, по крайней мере в лоб, и искать алгоритмически более оптимальные варианты решения исходной задачи.

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

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

Не согласны с тем что вместо класса String можно использовать массив байт? Ну ок…

Массив байт даёт выигрыш в 1 байт на символ (из пяти!).

Это лишь одна из возможных оптимизаций. Можно банально все в один массив сложить, или в коллекцию. Тут уже можно сэкономить в 2-3 раза. Совсем не обазательно массив байт оборачивать в класс. А если у вас все строки уникальны, то Вам даже и строки хранить не надо, тут уже от задачи зависит.

2) Это ни разу не встроенный механизм, а свой велосипед.

Масисив байтов не встроенный механизм? Ну ок…

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

Спс, кэп.
Единственное, чем String лучше char[] так это то, что у первого осмыслено работают методы .equals и .hashCode. Поэтому строковые объекты можно использовать в качестве ключей коллекций, а массивы символов, без предварительного интернирования, нет. За хэш мы платим 24 байта на строку. И хоть вы и сделаете свой ByteString, столкнётесь с той же дилеммой.

Все оптимизации в данном случае — это в той или иной степени свой механизм управления памятью. Работает? Конечно! Удобно? Ни разу.
Подозреваю, что в такой ситуации проще написать (или модифицировать существующий) контейнер, который будет по-особому выполнять equals и hashCode для массивов символов. Что-то вроде IdentityHashMap.
Была идея хранить строку в национальной кодировке как массив байт и первые четыре ячейки использовать под хэш. Если дописать свои структуры данных, то вариант выглядел как рабочий. До реализации не дошло — проще выкрутились.
Я конечно понимаю, что в тегах только Java, но первая мысль какая пришла мне в голову это сравнить с .Net-том. Итого стандартное консольное приложение созданое при помощи студии с copy-past-fix_syntax_errors кодом занимает 528 МБ, что в свою очередь ~5 раз меньше. Как-то уж больно большой оверхед получается для тех кому нужны базы данных, где строки на входе и на выходе.
Было бы очень интересно посмотреть на похожий тест в .NET, Python и Rust. Просто я не так хорошо разбираюсь во внутренних механизмах этих платформ, чтобы провести его максимально честно.

Это будет бесценный материал для принятия взвешенного решения, какую платформу использовать в похожих сценариях (если есть такой выбор).
Rust 1.12 Linux 4.7.5 x86_64
extern crate heapsize;
use heapsize::heap_size_of;
use std::os::raw::c_void;
use std::mem::size_of_val;

fn main() {
    let n = 100_000_000;
    let mut vec: Vec<String> = Vec::with_capacity(n);
    for _ in 0..n {
        vec.push(String::from(""));
    }

    let self_size = unsafe { heap_size_of(vec.as_ptr() as *const c_void) };

    let string = String::from("");
    let string_size = size_of_val::<String>(&string);

    print!("Heap size: one string: {}B, vec: {}B\n", string_size, self_size);
}


Heap size: one string: 24B, vec: 2684354560B

Итого размер строки по умолчанию 24 байта. + 271МБ(~10%) рискну предположить что пропало в недрах jemalloc. Независимо от количества элементов эти 10% остаются десятью процентами.
А 24 байта — указатель, длина и максимальный размер(capacity).
Я тут еще немного подумал и понял, что это никак не связано со строками. Подобная проблема будет во всем где есть куча, ссылки и т.д., то есть везде.
Наверное так и есть. Другое дело, сколько занимают обвязки объектов и ссылки на других платформах? Этого я не знаю.
node.js 4.6.0, linux kernel 4.7.2 x86_64

const util = require('util');
const process = require('process');

var A=new Array();

for (var i=0; i<10000000; i++)
	A.push(new String("/u0000"));


console.log(util.inspect(process.memoryUsage()));


~$ nodejs x.js
{ rss: 496259072, heapTotal: 474601056, heapUsed: 470572400 }


До кучи:
...
for (var i=0; i<10000000; i++)
	A.push(new String((10000000+i).toString())); // Длинна строки всегда 8 символов
...


{ rss: 821313536, heapTotal: 794501216, heapUsed: 790837096 }
Слеш не тот :)

...
for (var i=0; i<10000000; i++)
	A.push(new String("\u0000"));
...


{ rss: 496185344, heapTotal: 474601056, heapUsed: 470573552 }


Принципиально картинка не поменялась. И да, тут 10 млн строк.
Спасибо за тест. В JavaScript под капотом тот же UTF-16, судя по всему и остальные вещи похожим образом сделаны.
Для большого количества дублирующихся строк можно использовать интернирование (string interning). Суть механизма такая: поскольку строки в Яве неизменяемые, то можно хранить их в отдельном пуле и при повторе ссылаться на существующий объект вместо создания новой строки. Такой подход не бесплатен — он стоит и памяти и процессорного времени для хранения структуры пула и поиска в нём.

Но строки в джаве и так хранятся в отдельном пуле и, если такая строка существует в пуле, то будет ссылаться на нее
Это вы про константные строки говорите (которые в кавычках в самом java файле). Если создавать строку именно как new String() — то никакого пула не будет, пока не вызовем метод .intern() у строки.
Здесь стоит быть аккуратнее. Java сама складывает в пул только строковые литералы. Т.е. те строки, которые были в вашем исходном коде к моменту компиляции программы.

Остальные строки можно сложить в пул (интернировать) применив к ним метод .intern(). Попробуйте запустить следующий код:

package ru.habrahabr.experiment;

public class StringEqualityExperiment {
    public static void main(String[] args) {
        String x = "abc";
        String y = "abc";

        System.out.println(x == y);

        x = new String("abc");
        y = new String("abc");

        System.out.println(x == y);

        x = new String("abc").intern();
        y = new String("abc").intern();

        System.out.println(x == y);

        x = new String("abc").intern();
        y = new String("abc");

        System.out.println(x == y);
    }
}

Он выдаст: true false true false.

Пул, начиная с Java 7, можно использовать (до этого были серьёзные архитектурные проблемы). Но стоит подкручивать его под конкретный сценарий настроечкой -XX:StringTableSize и заранее оценивать, стоит ли в принципе овчинка выделки. В нашем случае, при работе с уникальными строками, использование пула начисто лишено всякого смысла.
Да, вы правы, но в статье сказано
К сожалению в Яве не существует встроенных механизмов, чтобы напрямую сократить потребление памяти при работе со строками.

и далее расказывается про пул строк и интернирование, поэтому я и уточнил данный момент
Справедливое замечание.
Пул, начиная с Java 7, можно использовать

Вот как вы можете ссылаться на презентацию Шипилёва и тут же говорить, что интернирование можно использовать? Шипилёв кучу раз со свойственной ему выразительностью говорил, что интернирование использовать нельзя. Вот в том самом видео, на которое вы ссылку вставили, с 32-й минуты про это же и говорит. Это низкоуровневая штука, нужная самой JVM и библиотекам, использующим JNI. Это не для пользователей. Если вам нужна дедупликация, напишите свой собственный пул, это 15 строчек кода. Не пользуйтесь String.intern(), если вы просто хотите снизить расход памяти! Он для других целей.

Остаётся молча согласиться и пойти поправить в статье. Спасибо, что обратили на это моё внимание.
Не очень понимаю один момент. Почему бы не сложить слова в один большой массив, а фразы представлять в виде двух индексов — первого и второго слова? Более того, можно брать не массив строк, а один большой массив символов, где слова разделены спецсимволов.
Тут, конечно, всё зависит от того, как вы потом эти фразы используете.
Мы ровно так и сделали! Просто любой велосипед стоит человеческих ресурсов и нужно уметь быстро оценить есть ли возможность решить задачу встроенными средствами, перед тем как начать прикручивать педали и руль к проекту.
О, я угадал :)
У меня почему-то эта мысль появилась в самом начале поста, ещё на формулировке задачи. Я бы, конечно, тоже проверил вариант со строками, но уже потом, типа «может и не стоило так усложнять?».
Использовать intern для дедупликации данных не стоит: чревато потерей производительности, причем проседать может в 10 раз на миллионах строк. Об этом рассказывал Алексей Шипилев в докладе «Катехизис java.lang.String». Вот часть про intern: https://youtu.be/SZFe3m1DV1A?t=1912
Спасибо за ссылку на доклад. Смотрел его когда-то, но замылилось в памяти. Доклад очень полезный, добавлю его в статью.

По теме — Алексей немного лукавит. Если использовать подстроечный параметр -XX:StringTableSize, то просадка по скорости не такая ужасающая получается. Но сам посыл очень грамотный: если используешь встроенную магию в приложениях чувствительных к производительности, будь добр разобраться как она работает.

Особенно это касается встроенного интернирования, с которым ещё в шестёрке были адовы проблемы с забиванием PermGen.
Спасибо за XX:StringTableSize, походу дела нашел еще интересную статью: http://java-performance.info/string-intern-in-java-6-7-8/. Там, например, сказано, что размер StringTableSize должен быть простым числом, чтобы увеличить производительность. Обсуждается это на http://stackoverflow.com/questions/1145217/why-should-hash-functions-use-a-prime-number-modulus.

Может быть, проверите на реальных данных, как влияет простота размера таблицы со строками на количество коллизий в HashMap-е?
В String, как и в любом другом объекте есть заголовок — system hash code, lock биты и т.п. Переход на ValueType позволит его несколько облегчить.

На данный момет, при таком масштабе — 100 млн строк — будет ещё просадка и от GC — обход такого графа не дешёвое удовольствие (и когда они в молодом поколении, и когда будут перенесены в старое). В общем-то схожие проблемы возникают при подобных масштабах при любых объектах — и пока один выход — уходить в offheap.

ValueType давно уже напрашиваются и на различных конференциях по Яве регулярно всплывают подстольные реализации лёгких объектов. Но это в светлом будущем, а нам эффективный код сегодня писать :)
Вот мы у себя условно вчера решили через offheap, храним utf-8 — ибо в 98% наших случаев это именно latin1, offheap sort и прочие рутины.
Возможно, я сейчас глупость ляпну, но всё же: А почему при таких объёмах слов и словосочетаний не закодировать их в виде чисел? В тип int количество словосочетаний должно поместиться. К примеру: положительные -> слова, а отрицательные -> словосочетания. Тогда текст у нас будет представлен как
int[] textCodes;
.
Вот только надо подумать об устройстве достаточно осмысленной и при этом быстрой хэш-функции…
Ну закодировали вы строки числами, а дальше-то что? Как отсортировать все строки по алфавиту? Или, например, найти все биграммы, где первое слово одной является вторым словом другой? А распечатать их потом обратно в виде слов как?
UFO just landed and posted this here
Не, у нас не так. Есть три ресурса: память, процессор и инженерный ресурс. Последний — самый дорогой. Но используя его можно иногда экономить первые два одновременно.
UFO just landed and posted this here
Глупость ляпнуть вы никак не можете, мы же не на экзамене. А в самых безумных предложениях часто скрываются самые лучшие идеи, потому как всплывают они из подсознания и ещё не осознаны, а уже на языке.

Более того ваше направление мысли абсолютно верное. Именно так мы и поступили, но об этом отдельная статья.
UFO just landed and posted this here
Эксперимент в статье только для иллюстрации, как предельный случай задачи со строками. Данных-то 0, но 4 гигабайта из собственного кармана мы уже заплатили.
Как не грустно есть еще разработчики которые верят в System.gc() :sad:
А что не так с вызовом System.gc()? В боевом коде — это серьёзный косяк, но в расчётных задачах на конкретной версии виртуальной машины — отличная штука.

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

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

Можно использовать всё что угодно и как угодно, просто в этом случае вы берёте на себя ответственность за последствия.
P.S. Не зря в jvisualvm и прочих профайлерах есть кнопочка Force GC:


Которая дёргает тот же самый метод. И не зря есть подстроечный параметр -XX:+DisableExplicitGC, который защищает ваш боевой код от отчаянных разработчиков сторонних библиотек, которые вопреки всем советам дёргают рубильник.
В 8-й яве System.gc() никаких видимых изменений в куче не производит. По крайней мере в тех экспериментах, которые я сам проводил. Единственный надежный способ выполнить полную сборку мусора — это сделать дамп кучи только с живыми объектами.
Тесты, описанные выше, проводились на Java 8 и System.gc() там прекрасно работал. Чей и какую версию JDK используете?
Сейчас вот такую. Эксперименты ставил на более ранней версии восьмерки.

java version «1.8.0_102»
Java(TM) SE Runtime Environment (build 1.8.0_102-b14)
Java HotSpot(TM) 64-Bit Server VM (build 25.102-b14, mixed mode)
Не умею диагностировать по фото, но странно это. Флажочек -XX:+DisableExplicitGC не стоит нигде?

Поделитесь вашими экспериментами.

Очень простые. Я проверял, как работает мой метод finalize(). В 7-й яве он у меня вызывался после System.gc(). В 8-й яве уже не вызывался. Специальных настроек GC я не включал намеренно, потому что интересовало именно поведение JVM по умолчанию. Тогда я заменил System.gc() на сброс дампа, и finalize() отработал во всех версиях явы.

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

Вот, пожалуйста. Выгружаю JDBC-драйвер, загруженный из отдельного каталога. Пока он не выгружен, каталог в Windows не удаляется, так как файлы заняты. В семерке все удаляется сразу, а в восьмерке только после удара в бубен через JMX.

unload()
public void unload() {
    try {
        if (driverManager != null) {
            DriverManagerProxy dmp = driverManager;
            this.driverManager = null;
            dmp.deregisterDriver(driver);
        } else {
            DriverManager.deregisterDriver(driver);
        }
    } catch (SQLException e) {
        e.printStackTrace();
    }
    this.driver = null;
    if (classLoader != null) {
        ResourceBundle.clearCache(classLoader);
        try {
            cleanupThreadLocals(this.classLoader);
        } catch (ReflectiveOperationException e1) {
            e1.printStackTrace();
        }
        try {
            this.classLoader.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
        this.classLoader = null;
        System.gc();
        System.runFinalization();
        System.gc();
        System.runFinalization();
    }
    if (!delete(dir, false)) {
        dumpHeap();
        delete(dir, false);
    }
}

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

Принципиально сборки, вызванные через System.gc и через дамп хипа, не отличаются. Почему по-разному работает в Java 7 и Java 8 — не знаю. Может быть сотня причин; приведённого кода недостаточно, чтобы сказать, что именно. Могу сказать лишь одно — полагаться на вызов finalize точно не стоит. Очевидно, вы хотите закрыть ресурсы сразу при вызове unload — так и закройте их напрямую; может, даже явным вызовом finalize(), если другого способа нет.
Расскажите, пожалуйста, как напрямую выгрузить dll, которая была загружена через System.loadLibrary().
Да, это проблема. Через Reflection можно даже это сделать, но будет всё равно ужасно. Лучше, наверное, вообще избегать необходимости удаления каталога с загруженной dll.

Впрочем, речь была о другом: при настройках по умолчанию System.gc точно запускает сборку; проблема в чём-то ином. Есть ещё несколько способов вызвать GC: через DiagnosticCommandMBean или через JVMTI. Но дамп хипа — это имхо перебор.
Я декомпилировал классы, чтобы разобраться, что делается через MBean. Выяснилось, что там такой же вызов Runtime.getRuntime().gc(), как и в System.gc(). Поэтому вполне достаточно использовать System.gc().

Что у меня получилось в итоге:

Библиотека выгружается вместе с класслоадером.
Класслоадер выгружается после полной сборки мусора, если нет ни одного живого объекта из загруженных им классов.
После первой полной сборки мусора все объекты очищаются, но пустой класслоадер с библиотекой остается. Поэтому приходится 2 раза подряд вызывать System.gc().
Сам класслоадер удаляется после 2-го System.gc() в Java 7 и не удаляется в Java 8.
А вот dumpHeap делает то, что требуется, и объекты подчищает, и класслоадер, и библиотеку выгружает, и файл освобождает. Поскольку это дорого, то к этому лекарству я прибегаю только тогда, когда больше ничего не помогло.

Здесь он никак не мешает (и не помогает), потому что Eclipse MemoryAnalyzer практически во всех вьюшках показывает только достижимые объекты. То есть если в куче есть недостижимый, то неважно, собрал ли его GC или нет — в MemoryAnalyzer'е увидим одно и то же. А насчёт верят — ну разработчики JDK вон тоже верят. Тоже дураки?

Что-то у вас каша в голове. В OpenJDK ровно тот же самый хотспот, что и у автора поста. И хотспот — это JVM, а не JDK.

Чисто для перестраховки, чтобы не снимать лишней информации из кучи и не анализировать её в МАТе. Можно было поставить флажочек -dump:live джимапу и он бы сам полную сборку вызвал.
Ещё интересно увидеть — так ради прикола — результаты с -XX:+UseG1GC -XX:+UseStringDeduplication
А в восьмерке разве не G1 по умолчанию?
нет. он будет по-умолчанию в 9ке
$ java -XX:+UnlockDiagnosticVMOptions -XX:+PrintFlagsFinal -version | egrep "UseStringDe|UseG1GC"
bool UseG1GC                             = false                               {product}
bool UseStringDeduplication              = false                               {product}

java version "1.8.0_74"
Java(TM) SE Runtime Environment (build 1.8.0_74-b02)
Java HotSpot(TM) 64-Bit Server VM (build 25.74-b02, mixed mode)
И правда. Оказывается в Eclipse, с которым я работаю, в конфиге прописаны параметры

-XX:+UseG1GC
-XX:+UseStringDeduplication
Там в начале статьи идут параметры VM и специально включен CMS.
Действительно. Не обратил внимания.
Судя по всему меньше (около 2500mb), т.к. на /usr/lib/jvm/java-9-oracle/bin/java -Xmx3g -Xms3g у меня успешно выполнился приведенный выше код.

С включенной дедупликацией интересно прогнать если строки уникализировать (положить туда число и добить нулями слева до длины в 15 символом). Иначе они схлопываются и получается вырожденный случай.

На восьмёрке у меня -XX:+UseG1GC -XX:-UseStringDeduplication отвратительно себя ведёт — зажирает процессор и в целом в реальных приложениях проседает производительность. Но я не разбирался с ним досконально, просто ушёл обратно на CMS.
Весь оверхед связан с необходимостью автоматической сборки мусора. Если ваши алгоритмы предполагают наличие 100 млн объектов с возможностью произвольного доступа, то имеет смысл задуматься о самостоятельном управлении памятью, которую они занимают. Все эти объекты должны существовать вместе и уничтожаться будут тоже все разом, поэтому нет необходимости гонять сборщик мусора над ними. Поэтому заведите большой массив с данными и обертку, которая их вынимает по различным запросам.
Так и сделали. Но тут проблема не с производительностью, а именно с памятью.
Оверхед по памяти в данном случае — вообще ни разу не про сборку мусора. Оверхед у строк — это:
  • заголовок объекта
  • ссылка на массив char-ов
  • hashcode (кэшируется)
  • дырки (паддинги) для выравнивания полей


Это все можно было и без подобного теста узнать
Даже не подумаю верить теории, не увидев своими глазами в инспекторе снимка кучи. Теория — это хорошо для объяснения результатов эксперимента. Но не для принятия решений.
А почему вы думаете, что heap dump покажет вам реальное занимаемое место? Это же не дамп физической памяти, а очередной абстрактный формат, который разные тулы могут трактовать по-разному. Если уж и мерить размеры объектов, то с помощью правильных инструментов, см. JOL.
Спасибо за ссылки на альтернативные инструменты и альтернативные подходы. В общем и целом, есть конечно линейка, а есть и штангенциркуль. Всё от задачи зависит. В данном конкретном случае анализ снимка кучи даёт вполне наглядное и сходящееся с практикой знание.
Посмотрите, сколько в хипдампе занимают объекты java.lang.Class по мнению MAT.
40 байт вместо реальных 96! Или ещё: java.lang.invoke.MemberName якобы занимает 32 байта, хотя на самом деле 56. И это пример не с потолка: я сталкивался с реальными утечками, связанными с MemberName: JDK-8152271.

А статья без какого-либо анализа основывается исключительно на инструменте, который в некоторых случаях врёт в 2 раза!

Ну ладно уж тебе :-) Для строк MAT обычно не врёт, ему эвристик хватает, чтобы разобраться. Хотя, конечно, если вопрос стоит не "куда у меня десять гигабайт кучи делось", а "сколько точно байт занимает X", то, конечно, JOL использовать логичнее.

Моя претензия вовсе не к использованию MAT, а к тому, что в статье напрочь отсутствует какой-либо анализ, а выводы основываются только на цифрах конкретного эксперимента. Это из той же серии, что написать самодельный бенчмарк, и на его основе утверждать, что Java в 500 раз медленнее C++.
Ну вроде как понятное дело что и пустые строки будут занимать не хилое количество места в памяти. Они же объекты в джаве. Зато это упрощает работу с этими самыми стрингами. Но опять же было бы интересно сравнить с другими платформами, тогда можно какие то выводы делать.
Sign up to leave a comment.

Articles