Почему HashSet <Point> намного медленнее, чем HashSet <string>?

Я хотел хранить некоторые пиксельные местоположения, не допуская дубликатов, поэтому первое, что приходит в голову, - это HashSet<Point> или подобные классы. Однако это кажется очень медленным по сравнению с чем-то вроде HashSet<string>.

Например, этот код:

HashSet<Point> points = new HashSet<Point>();
using (Bitmap img = new Bitmap(1000, 1000))
{
    for (int x = 0; x < img.Width; x++)
    {
        for (int y = 0; y < img.Height; y++)
        {
            points.Add(new Point(x, y));
        }
    }
}

занимает около 22,5 секунд.

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

HashSet<string> points = new HashSet<string>();
using (Bitmap img = new Bitmap(1000, 1000))
{
    for (int x = 0; x < img.Width; x++)
    {
        for (int y = 0; y < img.Height; y++)
        {
            points.Add(x + "," + y);
        }
    }
}

Итак, мои вопросы:

  • Есть ли причина для этого? Я проверил этот ответ, но 22,5 сек - это больше, чем числа, показанные в этом ответе.
  • Есть ли лучший способ хранить точки без дубликатов?

Ответы

Ответ 1

Существуют две перфомансы, вызванные структурой Point. Что-то, что вы можете увидеть, добавив Console.WriteLine(GC.CollectionCount(0)); к тестовому коду. Вы увидите, что для теста Point требуется ~ 3720 коллекций, но для тестирования строки требуется ~ 18 коллекций. Не бесплатно. Когда вы видите тип значения, вызываете так много коллекций, тогда вам нужно заключить "uh-oh, слишком много бокса".

Проблема заключается в том, что для HashSet<T> требуется IEqualityComparer<T> выполнить свою работу. Так как вы его не предоставили, он должен вернуться к возврату EqualityComparer.Default<T>(). Этот метод может хорошо работать для строки, он реализует IEquatable. Но не для Point, это тип, который вызывается из .NET 1.0 и никогда не получал дженериков. Все, что он может сделать, это использовать методы Object.

Другая проблема заключается в том, что Point.GetHashCode() не выполняет звездную работу в этом тесте, слишком много коллизий, поэтому он сильно ударяет Object.Equals(). String имеет отличную реализацию GetHashCode.

Вы можете решить обе проблемы, предоставив HashSet хороший компаратор. Как этот:

class PointComparer : IEqualityComparer<Point> {
    public bool Equals(Point x, Point y) {
        return x.X == y.X && x.Y == y.Y;
    }

    public int GetHashCode(Point obj) {
        // Perfect hash for practical bitmaps, their width/height is never >= 65536
        return (obj.Y << 16) ^ obj.X;
    }
}

И используйте его:

HashSet<Point> list = new HashSet<Point>(new PointComparer());

И это примерно в 150 раз быстрее, легко избивая строковый тест.

Ответ 2

Основной причиной падения производительности является весь бокс (как уже объяснялось в ответе Hans Passant).

Кроме того, алгоритм хеш-кода усугубляет проблему, потому что он вызывает больше вызовов Equals(object obj), увеличивая при этом количество конверсий бокса.

Также обратите внимание, что хэш-код Point вычисляется x ^ y. Это дает очень мало дисперсии в вашем диапазоне данных, и поэтому ведра HashSet перенаселены — что не происходит с string, где дисперсия хэшей намного больше.

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

(x << 16) ^ y

Для некоторых хороших советов, когда дело доходит до хэш-кодов, прочитайте сообщение в блоге Эрика Липперта по теме.