Примитивный тип HashSet или HashMap в 10 раз быстрее, чем Object? - PullRequest
Новая
       89

Примитивный тип HashSet или HashMap в 10 раз быстрее, чем Object?

1 голос
/ 06 октября 2019

Обновление: Это следует считать ошибкой в ​​стабильном канале флаттера v1.9.1 + hotfix.4. При переключении на мастер канала это исправлено, значения int и Object Sets имеют одинаковый порядок величины.

При выполнении теста производительности HashSet<int> в среднем работает в 10 раз быстрее, чем HashSet<Object>. В чем причина такого поведения?

У меня было значительное падение производительности (более чем на порядок), когда я изменил внутренние компоненты библиотеки так, как я ожидал, чтобы быть более эффективным.

Проблема менялась с HashSet<int> на HashSet<MyClass>, что я подтвердил при запуске простого теста производительности в HashSet, который добавляет то же значение 1000 раз. В результате HashSet<int> работает в среднем в 10 раз быстрее, чем HashSet<Object>.

Есть предложения с точки зрения разработки кода? Код выглядит намного чище, если иметь HashSet<MyClass> вместо дополнительных структур данных, которые связывают экземпляры с int. Это падение производительности важно, так как это ядро ​​библиотеки. Единственный способ сохранить эффективность программы - манипулировать всем с помощью целого числа, идентифицирующего MyClass.

Здесь можно найти эталон: https://gist.github.com/icatalud/dc28bd3bdd7c13b39c308b7abb9a9d8c

Функция, которая добавляет кНабор следующий: 

plainAddSet<T>(T obj, [int n = 1000]) {
  var s = Set<T>();
  for (var i = 0; i < n; i++) {
    s.add(obj);
  }
}

Обновление: Запуск дополнительных тестов привел меня к основной причине снижения производительности. Получатель hashCode работает очень медленно. В следующем классе, если метод hashCode не переопределен, он занимает в 20 раз больше времени, даже медленнее, чем Object. В противном случае это займет немного больше, чем int Set. 

class Identifiable {
  static int lastId = 0;
  int id;
  Identifiable() : id = lastId++;

  // Not overriding this getter, causes the benchmark to take 20 times longer.
  int get hashCode => id;

  bool operator ==(other) =>
      other.runtimeType == runtimeType &&
      hashCode == other.hashCode;
}

Обновление 2: Тем не менее, было бы интересно понять, почему переопределение оператора == и доступ к hashCode из трехв несколько раз медленнее, чем выход из реализации объекта по умолчанию (что более чем в 10 раз медленнее, чем int). 

class Identifiable {
  bool operator ==(other) =>
      other.runtimeType == runtimeType &&
      other.hashCode == hashCode;
}

обновление 3: Существует открытая проблема оэто в хранилище дротик SDK. Он был там более 4 лет.

1 Ответ

0 голосов
/ 07 октября 2019

Я проверил с различными реализациями класса и вижу время ожидания для hashCode. Это имеет смысл, поскольку hashCode для целого числа - это то же самое целое число, что и его представление (имеет смысл, если вы об этом думаете).

hashCode для Object () более сложный и требует выполнения внешнего вызова внекоторый код, которого я не знаю.

Если я создам свой собственный класс и переопределю свойство hashCode с помощью что-то вроде «всегда возвращать 5», тогда я получу ту же скорость, что и целое число.

Так какhashCode (и ==) используются каждый раз, когда вы добавляете что-либо на карту или набор, важно, чтобы эти две функции были максимально эффективными.

Ответ на обновление 2

Причина, по которой свойство hashCode Object () медленнее, заключается в том, что оно работает намного больше, чем целочисленный hashCode. Я проверил исходный код, и он выполняет следующие шаги:

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

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

Обновление для «Предлагая обходной путь к этой проблеме»

Это происходит в стабильном канале флаттера v1.9.1 + hotfix.4, но исправлено в master. Это не должно быть необходимым для реализации в следующих выпусках Flutter.

Если вы не можете принять производительность стандартного метода hashCode прямо сейчас, я думаю, что единственный другой способ - это вручную кешировать его следующим образом: 

class ObjectWithCachedHash {
  int _hashCodeCache;

  @override
  int get hashCode => _hashCodeCache ??= super.hashCode;
}

Это следует делать, только если hashCode не зависит от каких-либо значений внутри объекта (например, стандартная реализация hashCode, основанная исключительно на экземплярах).

Обновлено с ссылкойвыдать

Проблема с медленным хэш-кодом является известной проблемой (спасибо Игнасио Каталану за указание на это):

https://github.com/dart-lang/sdk/issues/24206

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

https://github.com/dart-lang/sdk/issues/24206#issuecomment-539448012

Но исправление для этой регрессии устранит проблему только дляx64, так что 32-битные архитектуры (и, соответственно, все архитектуры ARM) будут по-прежнему зависеть от проблемы с производительностью (это еще одна проблема, котораяне связаны с регрессией).

Таким образом, для 32-битных пользователей и пользователей ARM рекомендуется локально кэшировать значение hashCode, если код зависит от Object.hashCode и будет проводить много сравнений (например, с использованиемКарты или Сеты с большим количеством объектов).

...