Почему именно массивы.fill () не используется в HashMap.ясно () больше?

Я заметил что-то странное в реализации HashMap.clear(). Вот как это выглядело в OpenJDK 7u40:

public void clear() {
    modCount++;
    Arrays.fill(table, null);
    size = 0;
}

и вот как это выглядит с OpenJDK 8u40:

public void clear() {
    Node<K,V>[] tab;
    modCount++;
    if ((tab = table) != null && size > 0) {
        size = 0;
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null;
    }
}

Я понимаю, что сейчас table может быть null для пустой карты, поэтому требуется дополнительная проверка и кэширование в локальной переменной. Но почему было Arrays.fill() заменен на for-loop?

кажется, что изменение было введено в этот коммит. К сожалению, я не нашел объяснения, почему простой цикл for может быть лучше, чем Arrays.fill(). Это быстрее? Или безопаснее?

5 68
javascript arrays java-8 hashmap

5 ответов:

я постараюсь суммировать три более разумные версии, которые были предложены в комментариях.

@Holger говорит:

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

это самая простая вещь для тестирования. Скомпилируем такую программу:

public class HashMapTest {
    public static void main(String[] args) {
        new java.util.HashMap();
    }
}

С java -verbose:class HashMapTest. Эта воля распечатайте события загрузки класса по мере их возникновения. С JDK 1.8.0_60 я вижу более 400 загруженных классов:

... 155 lines skipped ...
[Loaded java.util.Set from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.AbstractSet from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.Collections$EmptySet from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.Collections$EmptyList from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.Collections$EmptyMap from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.Collections$UnmodifiableCollection from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.Collections$UnmodifiableList from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.Collections$UnmodifiableRandomAccessList from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded sun.reflect.Reflection from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
**[Loaded java.util.HashMap from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.HashMap$Node from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.Class from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.Class$ReflectionData from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.Class$Atomic from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded sun.reflect.generics.repository.AbstractRepository from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded sun.reflect.generics.repository.GenericDeclRepository from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded sun.reflect.generics.repository.ClassRepository from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.Class$AnnotationData from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded sun.reflect.annotation.AnnotationType from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.WeakHashMap from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.ClassValue$ClassValueMap from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.reflect.Modifier from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded sun.reflect.LangReflectAccess from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.reflect.ReflectAccess from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
**[Loaded java.util.Arrays from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
...

Как видите, HashMap загружается задолго до кода приложения и Arrays загружается только 14 классов после HashMap. Элемент HashMap нагрузка вызвана sun.reflect.Reflection инициализация как есть HashMap статические поля. Элемент Arrays нагрузка, вероятно, будет вызвана WeakHashMap загрузки, который на самом деле имеет Arrays.fill на clear() метод. Элемент WeakHashMap загрузка запускается java.lang.ClassValue$ClassValueMap которая расширяет WeakHashMap. Элемент ClassValueMap присутствует в каждом java.lang.Class экземпляра. Так мне кажется, что без Arrays класс JDK не может быть инициализирован вообще. Кроме того,Arrays статический инициализатор очень короткий, он только инициализирует механизм утверждений. Этот механизм используется во многих других классах (включая, например,java.lang.Throwable который загружается очень рано). Никакие другие статические шаги инициализации не выполняются в java.util.Arrays. Таким образом, версия @Holger кажется неправильной мне.

здесь мы тоже нашли очень интересную вещь. Элемент WeakHashMap.clear() использует Arrays.fill. Это интересно, когда он появился там, но, к сожалению, это идет к доисторические времена (он уже был там в самом первом публичном репозитории OpenJDK).

Далее, @MarcoTopolnik говорит:

безопаснее, конечно, нет, но это может быть быстрее, когда fill вызов не встроен и tab коротко. На HotSpot как цикл, так и явный fill вызов приведет к быстрому встроенному компилятору (в сценарии Счастливого дня).

это было действительно удивительно для меня, что Arrays.fill не является непосредственно интринсифицированным (см. список характеристической создается с помощью @apangin). Кажется, что такой цикл может быть распознан и векторизован JVM без явной внутренней обработки. Так что это правда, что дополнительный вызов может быть не встроен в очень конкретных случаях (например, если MaxInlineLevel лимит исчерпан). С другой стороны, это очень редкая ситуация, и это только один вызов, это не вызов внутри цикла, и это статический, а не виртуальный/интерфейсный вызов, поэтому повышение производительности может быть только незначительным и только в некоторых конкретных сценариях. Не то, что обычно заботит разработчиков JVM.

также следует отметить, что даже компилятор C1' client ' (уровень 1-3) способен встроить Arrays.fill, например, в WeakHashMap.clear(), как встраивание журнала (-XX:+UnlockDiagnosticVMOptions -XX:+PrintCompilation -XX:+PrintInlining) говорит:

36       3  java.util.WeakHashMap::clear (50 bytes)
     !m        @ 4   java.lang.ref.ReferenceQueue::poll (28 bytes)
                 @ 17   java.lang.ref.ReferenceQueue::reallyPoll (66 bytes)   callee is too large
               @ 28   java.util.Arrays::fill (21 bytes)
     !m        @ 40   java.lang.ref.ReferenceQueue::poll (28 bytes)
                 @ 17   java.lang.ref.ReferenceQueue::reallyPoll (66 bytes)   callee is too large
               @ 1   java.util.AbstractMap::<init> (5 bytes)   inline (hot)
                 @ 1   java.lang.Object::<init> (1 bytes)   inline (hot)
               @ 9   java.lang.ref.ReferenceQueue::<init> (27 bytes)   inline (hot)
                 @ 1   java.lang.Object::<init> (1 bytes)   inline (hot)
                 @ 10   java.lang.ref.ReferenceQueue$Lock::<init> (5 bytes)   unloaded signature classes
               @ 62   java.lang.Float::isNaN (12 bytes)   inline (hot)
               @ 112   java.util.WeakHashMap::newTable (8 bytes)   inline (hot)

конечно, он также легко встроен умным и мощным компилятором C2 'server'. Поэтому я не вижу здесь никаких проблем. Кажется, что версия @Marco также неверна.

наконец-то у нас есть пара комментарии от @StuartMarks (который является разработчиком JDK, таким образом, какой-то официальный голос):

интересные. Я подозреваю, что это ошибка. Поток обзора для этого набора изменений -здесь и он ссылается на ранее что это Продолжение ТУТ. Начальное сообщение в этом более раннем потоке указывает на прототип HashMap.java в репозитории CVS Дуга ли. Я не знаю, откуда это взялось. Это, кажется, не соответствует ничему в истории OpenJDK.

... В любом случае, это мог быть какой-то старый снимок; for-loop был в методе clear() в течение многих лет. матрица.вызов fill() был представлен этот набор изменений, так оно и было на дереве всего несколько месяцев. Отметим также, что из вычислений, основанных на целое число.highestOneBit() представлен этот набор изменений также исчез в то же время, хотя это было отмечено, но отклонено во время обзора. Хммм.

действительно HashMap.clear() содержал петлю много лет, был заменить С Arrays.fill 10 апреля 2013 года и остался менее чем на полгода до 4 сентября, когда обсуждалось commit был введенный. Обсуждаемая фиксация была фактически серьезной переписью HashMap внутренности, чтобы исправить JDK-8023463 вопрос. Это была длинная история о возможности отравить HashMap С ключами, имеющими дублирующие хэш-коды, уменьшающие HashMap скорость поиска до линейной делает его уязвимым для DoS-атак. Попытки решить эту проблему были выполнены в JDK-7, включая некоторую рандомизацию строкового хэш-кода. Так кажется, что HashMap реализация была разветвлена от более ранней фиксации, разработанной независимо, затем слились в главную ветвь перезаписи несколько изменений, внесенных между ними.

мы можем поддержать эту гипотезу выполнения сравнения. Возьмите версия здесь Arrays.fill удалена (2013-09-04) и сравнить его с предыдущие версии (2013-07-30). Элемент diff -U0 выход имеет 4341 линии. Теперь давайте различать против версия до одного, когда Arrays.fill добавлено (2013-04-01). Сейчас diff -U0 содержит только 2680 русло. Таким образом, более новая версия на самом деле больше похожа на старшую, чем на непосредственного родителя.

вывод

в заключение я бы согласился со Стюартом Марксом. Не было никаких конкретных причин, чтобы удалить Arrays.fill, это просто потому, что промежуточное изменение было перезаписано по ошибке. Используя Arrays.fill отлично подходит как в коде JDK, так и в пользовательских приложениях и используется, например, в WeakHashMap. Элемент Arrays Class загружается в любом случае довольно рано во время инициализация JDK, имеет очень простой статический инициализатор и Arrays.fill метод может быть легко встроен даже клиентским компилятором, поэтому не следует отмечать недостаток производительности.

27

потому что это много быстрее!

Я провел несколько тщательных тестов бенчмаркинга на сокращенных версиях двух методов:

void jdk7clear() {
    Arrays.fill(table, null);
}

void jdk8clear() {
    Object[] tab;
    if ((tab = table) != null) {
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null;
    }
}

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

Map size |  JDK 7 (sd)|  JDK 8 (sd)| JDK 8 vs 7
       16|   2267 (36)|   1521 (22)| 67%
       64|   3781 (63)|   1434 ( 8)| 38%
      256|   3092 (72)|   1620 (24)| 52%
     1024|   4009 (38)|   2182 (19)| 54%
     4096|   8622 (11)|   4732 (26)| 55%
    16384|  27478 ( 7)|  12186 ( 8)| 44%
    65536| 104587 ( 9)|  46158 ( 6)| 44%
   262144| 445302 ( 7)| 183970 ( 8)| 41%

и вот результаты при работе над массивом, заполненным нулями (поэтому проблемы сборки мусора устраняются):

Map size |  JDK 7 (sd)|  JDK 8 (sd)| JDK 8 vs 7
       16|     75 (15)|     65 (10)|  87%
       64|    116 (34)|     90 (15)|  78%
      256|    246 (36)|    191 (20)|  78%
     1024|    751 (40)|    562 (20)|  75%
     4096|   2857 (44)|   2105 (21)|  74%
    16384|  13086 (51)|   8837 (19)|  68%
    65536|  52940 (53)|  36080 (16)|  68%
   262144| 225727 (48)| 155981 (12)|  69%

цифры в наносекундах, (sd) - это 1 стандартный отклонение, выраженное в процентах от результата (fyi," нормально распределенная " популяция имеет SD 68),vs это время JDK 8 относительно JDK 7.

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

тесты были запущены на jdk 1.8.0_45 в течение большого (миллионов) раз на массивах, заполненных случайный Integer объекты. Чтобы удалить лежащие числа, на каждом наборе результатов были отброшены самые быстрые и самые медленные 3% таймингов. Была запрошена сборка мусора, и поток уступил и спал непосредственно перед запуском каждого вызова метода. Разминка JVM была сделана на первых 20% работы, и эти результаты были отброшены.

3

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

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

потенциальные преимущества производительности не столь незначительны, если вы считаете все, что связано:

  1. не будет никакой потребности для JVM разрешить Arrays класс, плюс загрузка и инициализация его при необходимости. Это нетривиальный процесс, в котором JVM выполняет несколько шагов. Во-первых, он проверяет загрузчик классов, чтобы увидеть, если класс уже загружен, и это происходит каждый раз, когда вызывается метод; здесь, конечно, есть оптимизации, но это все еще требует некоторых усилий. Если класс не загружен, JVM необходимо будет пройдите дорогостоящий процесс его загрузки, проверки байт-кода, разрешения других необходимых зависимостей и, наконец, выполнения статической инициализации класса (что может быть сколь угодно дорогим). Учитывая, что HashMap Это такой основной класс, и что Arrays Это такой огромный класс (3600+ строк), избегая этих затрат может добавить до заметной экономии.

  2. так как нет Arrays.fill(...) вызов метода, JVM не придется решать, следует ли / когда встроить метод в тело звонившего. Так как HashMap#clear() имеет тенденцию называться много, JVM в конечном итоге выполнит встраивание, что требует перекомпиляции JIT clear метод. Без вызова метода,clear всегда будет работать на максимальной скорости (один раз изначально JITed).

еще одно преимущество больше не вызывает методы в Arrays заключается в том, что она упрощает диаграмму зависимостей внутри java.util пакета, так как одна зависимость удаляется.

1

Я буду стрелять в темноте здесь...

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

если вы посмотрите на состояние специализации документ,языковые ограничения раздел, он говорит следующее:

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

  • не удается преобразовать null в переменную, тип которой T
  • невозможно сравнить T с null
  • не удается преобразовать T в Объект
  • не удается преобразовать T[] в Object[]
  • ...

(выделено мной).

и впереди в Специализатор преобразований он говорит:

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

  • ...
  • подстановка типа переменной и искажение имени выполняется на сигнатурах всех методов
  • ...

позже, ближе к концу документа, в дополнительное расследование он говорит:

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

теперь, что касается изменения...

если Arrays.fill(Object[] array, Object value) метод будет специализированным, тогда его подпись должна измениться на Arrays.fill(T[] array, T value). Однако этот случай специально указан в (уже упомянутом) языковые ограничения раздел (это нарушило бы подчеркнутые пункты). Так что может быть кто-то решил, что было бы лучше не использовать его из HashMap.clear() метод, особенно если value - это null.

1

нет никакой фактической разницы в функциональности между циклом 2 версии. Arrays.fill делает то же самое.

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

есть 2 отдельные проблемы для каждого подхода:

  • С помощью Arrays.fill делает код менее подробным и более читаемым.
  • зацикливание прямо в HashMap кода (версия 8) производительность мудрый, это действительно лучший вариант. В то время как накладные расходы, вставка Arrays класс незначителен он может стать меньше, когда речь заходит о чем-то столь распространенном, как HashMap где каждый бит повышения производительности имеет большой эффект (представьте себе крошечный след уменьшить HashMap в fullblown webapp). Примите во внимание тот факт, что класс Arrays использовался только для этого одного цикла. Изменение достаточно мало, что это не так сделать четкий способ менее читабельным.

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

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

0