Есть ли эффективная замена памяти java.lang.String?

Question

После прочтения этой старой статьи измерения потребления памяти несколькими типами объектов я был поражен, увидев, сколько памяти String s используется в Java:

length: 0, {class java.lang.String} size = 40 bytes
length: 7, {class java.lang.String} size = 56 bytes

Хотя в статье есть несколько советов по минимизации этого, я не нашел их полностью удовлетворительными. Кажется, расточительно использовать char[] для хранения данных. Очевидным улучшением для большинства западных языков стало бы использование byte[] и кодировки, такой как UTF-8, поскольку вам требуется только один байт для хранения наиболее часто встречающихся символов, а не два байта.

Конечно, можно использовать String.getBytes("UTF-8") и new String(bytes, "UTF-8"). Даже накладные расходы самого экземпляра String исчезли бы. Но тогда вы теряете очень удобные методы, такие как equals(), hashCode(), length(), ...

Насколько я могу судить, у Sun есть патент на byte[] представление строк.

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

Но мне не удалось найти API для этого патента.

Почему меня это волнует?
В большинстве случаев нет. Но я работал над приложениями с огромными кешами, содержащими множество строк, которые выиграли бы от более эффективного использования памяти.

Кто-нибудь знает такой API? Или есть другой способ сохранить небольшой объем памяти для строк, даже за счет производительности процессора или более уродливого API?

Пожалуйста, не повторяйте предложения из вышеприведенной статьи:

• собственный вариант String.intern() (возможно с SoftReferences)
• хранение одного char[] и использование текущей реализации String.subString(.), чтобы избежать копирования данных (неприятно)

Обновление

Я запустил код из статьи о текущей JVM от Sun (1.6.0_10). Он дал те же результаты, что и в 2002 году.

Answer 1

С небольшой помощью от JVM ...

ПРЕДУПРЕЖДЕНИЕ: Это решение устарело в новых версиях Java SE. См. Другие специальные решения ниже.

Если вы используете JSM HotSpot, начиная с Java 6, обновление 21, вы можете использовать эту опцию командной строки:

-XX:+UseCompressedStrings

Страница параметров JVM гласит:

Используйте байт [] для строк, которые могут быть представлены как чистый ASCII. (Введен в Java 6, обновление 21, выпуск Performance)

ОБНОВЛЕНИЕ : эта функция была нарушена в более поздней версии и должна была быть исправлена ​​снова в Java SE 6u25, как указано в примечаниях к выпуску 6u25 b03 (однако мы этого не делаем см. это в примечаниях к финальному выпуску 6u25 ). отчет об ошибке 7016213 не виден из соображений безопасности. Таким образом, используйте с осторожностью и проверьте в первую очередь. Как и любая опция -XX, она считается экспериментальной и может быть изменена без особого уведомления, поэтому, вероятно, не всегда лучше не использовать ее в скрипте запуска производственного сервера.

ОБНОВЛЕНИЕ 2013-03 (благодаря комментарию Алексей Максимус ) : см. Этот связанный вопрос и его принят ответ . Вариант теперь кажется умершим. Это дополнительно подтверждается в отчете об ошибке 7129417 .

Конец оправдывает средства

Предупреждение: (некрасиво) Решения для конкретных нужд

Это немного из коробки и ниже уровня, но так как вы спросили ... не бейте мессенджера!

Ваше собственное представление строки зажигалки

Если ASCII подходит для ваших нужд, то почему бы вам просто не развернуть собственную реализацию?

Как вы упомянули, вы можете byte[] вместо char[] внутри. Но это еще не все.

Чтобы сделать его еще более легким, вместо того, чтобы оборачивать свои байтовые массивы в класс, почему бы просто не использовать вспомогательный класс, содержащий в основном статические методы, работающие с этими байтовыми массивами, которые вы передаете? Конечно, он будет чувствовать себя довольно C-ish, но он будет работать и сэкономит вам огромные накладные расходы, которые идут с String объектами.

И конечно, он потерял бы некоторые приятные функциональные возможности ... если бы вы не реализовали их заново. Если они вам действительно нужны, то выбора не так много. Благодаря OpenJDK и множеству других хороших проектов, вы вполне можете развернуть свой собственный класс LiteStrings, который работает только с параметрами byte[]. Вам нужно будет принимать душ каждый раз, когда вам нужно вызвать функцию, но вы сэкономите кучу памяти.

Я бы порекомендовал сделать его похожим на контракт класса String и предоставить значимые адаптеры и компоновщики для преобразования из и в String, и вы можете также захотеть иметь адаптеры для и из StringBuffer и StringBuilder, а также некоторые зеркальные реализации других вещей, которые могут вам понадобиться. Определенно какая-то часть работы, но, возможно, она того стоит (см. Чуть ниже раздела «Подсчитайте!»).

Сжатие / декомпрессия на лету

Вы можете очень хорошо сжать свои строки в памяти и распаковать их на лету, когда они вам понадобятся. В конце концов, вам нужно только читать их, когда вы к ним обращаетесь, верно?

Конечно, насилие будет означать:

• более сложный (и, следовательно, менее поддерживаемый) код,
• больше вычислительной мощности,
• Требуются относительно длинные строки, чтобы сжатие было релевантным (или чтобы объединить несколько строк в одну, внедрив собственную систему хранения, чтобы сделать сжатие более эффективным).

Обе

Для полной головной боли, конечно, вы можете сделать все это:

• C-ish класс помощника,
• байтовые массивы,
• сжатый магазин на лету.

Обязательно сделайте это с открытым исходным кодом. :)

Сделай это графом!

Кстати, посмотрите эту великолепную презентацию о Построении Java-приложений с эффективным использованием памяти , написанных Н. Митчеллом и Г. Севицким: [ 2008 версия ], [ Версия 2009 ].

Из этой презентации мы видим, что 8-символьная строка пожирает 64 байта в 32-битной системе (96 для 64-битной системы !!), и большая часть из-за JVM накладные расходы. И из этой статьи мы видим, что 8-байтовый массив будет "съедать" только 24 байта : 12 байтов заголовка, 8 x 1 байт + 4 байта выравнивания).

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

Answer 2

В Terracotta у нас есть несколько случаев, когда мы сжимаем большие строки, когда они отправляются по сети, и фактически оставляем их сжатыми до тех пор, пока не потребуется декомпрессия. Мы делаем это, конвертируя char [] в byte [], сжимая byte [], затем кодируя этот byte [] обратно в исходный char []. Для некоторых операций, таких как хэш и длина, мы можем ответить на эти вопросы без декодирования сжатой строки. Для таких данных, как большие строки XML, вы можете получить существенное сжатие таким образом.

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

Все это делается с помощью инструментария байт-кода на java.lang. Строка, которую мы обнаружили, очень деликатна из-за того, как рано String используется при запуске, но стабильна, если вы следуете некоторым рекомендациям.

Answer 3

В статье указываются две вещи:

1. Увеличение массивов символов на 8 байтов.
2. Существует большая разница в размере между объектами char [] и String.

Накладные расходы связаны с включением ссылки на объект char [] и трех целых чисел: смещения, длины и пространства для хранения хеш-кода String, а также стандартных накладных расходов, связанных с простым использованием объекта.

Немного отличается от String.intern (), или массив символов, используемый String.substring (), использует один символ [] для всех строк, это означает, что вам не нужно хранить ссылку на объект в вашей оболочке String- как объект Вам все еще потребуется смещение, и вы вводите (большое) ограничение на количество символов, которое вы можете иметь в общей сложности.

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

Пространственно-временный компромисс между хранением хеша может помочь вам, если он вам не нужен часто.

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

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

Мои объекты состояли из смещения int (предел подходит для моей ситуации), длины int и хеш-кода int.

java.lang.String был знакомым молотком для того, что я хотел сделать, но не лучшим инструментом для работы.

Answer 4

Внутренняя кодировка UTF-8 имеет свои преимущества (например, меньший объем памяти, который вы указали), но она также имеет недостатки.

Например, определение длины символа (а не длины байта) строки в кодировке UTF-8 является операцией O (n). В Java-строке стоимость определения длины символа равна O (1), а при генерации представления UTF-8 - O (n).

Это все о приоритетах.

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

• Класс String должен поддерживать все возможные символы Юникода.

• Хотя unicode определяет 1-байтовые, 2-байтовые и 4-байтовые варианты, 4-байтовые символы (на практике) довольно редки, поэтому можно представлять их как суррогатные пары. Вот почему java использует 2-байтовый символьный примитив.

• Когда люди вызывают методы length (), indexOf () и charAt (), их интересует позиция символа, а не позиция байта. Для создания быстрых реализаций этих методов необходимо избегать внутренней кодировки UTF-8.

• Такие языки, как C ++, усложняют жизнь программиста, определяя три различных типа символов и заставляя программиста выбирать между ними. Большинство программистов начинают с использования простых строк ASCII, но когда им в конечном итоге требуется поддержка международных символов, процесс модификации кода для использования многобайтовых символов является чрезвычайно болезненным. Я думаю, что дизайнеры Java сделали отличный компромиссный выбор, сказав, что все строки состоят из 2-байтовых символов.

Answer 5

Я думаю, что вы должны быть очень осторожны, основывая любые идеи и / или предположения на статье javaworld.com 2002 года. С тех пор было много, много изменений в компиляторе и JVM. По крайней мере, сначала проверьте свою гипотезу и решение в сравнении с современной JVM, чтобы убедиться, что решение того стоит.

Answer 6

Java выбрала UTF-16 для компромисса скорости и размера хранилища. Обработка данных UTF-8 - это гораздо больше PITA, чем обработка данных UTF-16 (например, при попытке найти позицию символа X в байтовом массиве, как вы собираетесь сделать это быстро, если каждый символ может иметь один, два, три или даже до шести байтов? Вы когда-нибудь думали об этом? Перебирать строку за байтом не очень быстро, понимаете?). Конечно, UTF-32 будет проще обрабатывать, но тратить вдвое больше места для хранения. Вещи изменились с первых дней Unicode. Теперь определенным символам требуется 4 байта, даже когда используется UTF-16. Правильное обращение с ними делает UTF-16 почти таким же плохим, как UTF-8.

В любом случае, будьте уверены, что если вы реализуете класс String с внутренним хранилищем, использующим UTF-8, вы можете выиграть немного памяти, но вы потеряете скорость обработки для многих строковых методов. Также ваш аргумент - слишком ограниченная точка зрения. Ваш аргумент не будет верен для кого-то в Японии, так как японские символы не будут меньше в UTF-8, чем в UTF-16 (на самом деле они будут занимать 3 байта в UTF-8, тогда как в UTF-16 они будут только двумя байтами) , Я не понимаю, почему программисты в таком глобальном мире, как сегодня, с вездесущим Интернетом, по-прежнему говорят о «западных языках», как будто это все, что имело бы значение, как будто бы только в западном мире есть компьютеры, а остальная часть живет в пещеры. Рано или поздно любое приложение укушается из-за того, что оно не может эффективно обрабатывать незападные символы.

Answer 7

Просто сожмите их все с помощью gzip. :) Шучу ... но я видел странные вещи, и это дало бы вам гораздо меньше данных при значительных затратах на процессор.

Единственные другие реализации String, о которых я знаю, - это классы Javolution. Я не думаю, что они более эффективны при использовании памяти:

http://www.javolution.com/api/javolution/text/Text.html
http://www.javolution.com/api/javolution/text/TextBuilder.html

Answer 8

Опция компилятора UseCompressedStrings кажется самым простым путем. Если вы используете строки только для хранения и не выполняете никаких операций equals / substring / split, то может работать что-то вроде этого класса CompactCharSequence:

http://www.javamex.com/tutorials/memory/ascii_charsequence.shtml

Answer 9

Сегодня (2010) каждый ГБ, добавляемый на сервер, стоит около 80 фунтов стерлингов или 120 долларов. Прежде чем приступить к реорганизации String, вы должны спросить себя, действительно ли оно того стоит.

Если вы собираетесь сэкономить ГБ памяти, возможно. Десять ГБ, определенно. Если вы хотите сэкономить 10 с МБ, скорее всего, вы потратите больше времени, чем оно того стоит.

То, как вы сжимаете строки, зависит от модели использования. Много ли повторяющихся строк? (используйте пул объектов) Много ли длинных строк? (используйте сжатие / кодирование)

Другая причина, по которой вам могут потребоваться строки меньшего размера, - это уменьшение использования кэша. Даже самые большие процессоры имеют около 8 МБ - 12 МБ кэш-памяти. Это может быть более ценным ресурсом, и его нелегко увеличить. В этом случае я предлагаю вам взглянуть на альтернативы строкам, но вы должны иметь в виду, как сильно это изменится в фунтах или долларах по сравнению со временем, которое требуется.

Answer 10

В настоящее время я реализую метод сжатия следующим образом (я работаю над приложением, которому нужно хранить очень большое количество документов в памяти, чтобы мы могли выполнять вычисления между документами):

• Разбейте строку на 4-символьные «слова» (если вам нужен весь Юникод) и сохраните эти байты в long, используя маскировку / сдвиг битов. Если вам не нужен полный набор Unicode и только 255 символов ASCII, вы можете поместить 8 символов в каждый long. Добавляйте (char) 0 в конец строки, пока длина не разделится равномерно на 4 (или 8).
• Переопределите реализацию хэш-набора (например, TLongHashSet Троува) и добавьте каждое «слово» к этому набору, скомпилировав массив внутренних индексов, где long заканчивается в наборе (убедитесь, что вы также обновили свой индекс, когда набор перефразируется)
• Используйте двумерный массив int для хранения этих индексов (таким образом, первое измерение - это каждая сжатая строка, а второе измерение - это каждый индекс «слова» в хэш-наборе), и возвращает единственный индекс int в этот массив обратно к вызывающей стороне (вы должны владеть массивами слов, чтобы вы могли глобально обновить индекс при перефразировке, как упомянуто выше)

Преимущества:

• Постоянное время сжатия / распаковки
• Строка длины n представляется в виде массива int длины n / 4, с дополнительными издержками набора слов long, который асимптотически увеличивается по мере уменьшения числа уникальных "слова" встречаются
• Пользователю возвращают единственную int строку «ID», которая удобна и мала для хранения в своих объектах

Distadvantages:

• Несколько хакерский, поскольку включает в себя сдвиг битов, связывание с внутренностями хэш-набора и т. Д. ( Билл К не одобрит)
• Хорошо работает, если вы не ожидаете много повторяющихся строк. Проверить, существует ли уже строка в библиотеке, очень дорого.