Производительность неизменяемых реализаций набора в Scala

Недавно я нырял в Scala и (возможно, предсказуемо) потратил немало времени на изучение неизменяемого API-интерфейса коллекции в стандартной библиотеке Scala.

Я пишу приложение, которое обязательно выполняет много операций +/- на больших наборах. По этой причине я хочу убедиться, что выбранная реализация - это так называемая "постоянная" структура данных, чтобы я не делал copy-on-write. Я видел этот ответ от Мартина Одерского, но на самом деле это не совсем ясно для меня.

Я написал следующий тестовый код, чтобы сравнить производительность ListSet и HashSet для операций добавления:

import scala.collection.immutable._

object TestListSet extends App {
  var set = new ListSet[Int]
  for(i <- 0 to 100000) {
    set += i
  }
}

object TestHashSet extends App {
  var set = new HashSet[Int]
  for(i <- 0 to 100000) {
    set += i
  }
}

Ниже приведено приблизительное измерение времени выполнения HashSet:

$ time scala TestHashSet

real    0m0.955s
user    0m1.192s
sys     0m0.147s

И ListSet:

$ time scala TestListSet

real    0m30.516s
user    0m30.612s
sys     0m0.168s

Минусы в односвязном списке - это операция с постоянным временем, но эта производительность выглядит линейной или хуже. Является ли эта производительность удачной, связанной с необходимостью проверки каждого элемента набора для равенства объекта, чтобы он соответствовал инварианту без дубликатов Set? Если это так, я понимаю, что это не связано с "настойчивостью".

Что касается официальной документации, все, что я мог найти, это следующая страница, но она кажется неполной: Scala 2.8 API коллекций - характеристики производительности. Поскольку ListSet, по-видимому, первоначально является хорошим выбором для области памяти, возможно, в документах API должна быть информация о его производительности.

Ответ 1

Ключевая строка из источника ListSet - (в подклассе Node):

override def +(e: A): ListSet[A] = if (contains(e)) this else new Node(e)

где вы можете видеть, что элемент добавляется, только если он еще не содержится. Поэтому добавление в набор O(n). Обычно можно предположить, что XMap имеет схожие характеристики производительности с XSet, а ListMap отображается как линейное время. Вот почему, и именно так должен вести себя набор.

P.S. В случае TestHashSet вы измеряете время запуска. Это более чем в 30 раз быстрее.

Ответ 2

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

Коннор, в основном вы пытаетесь сделать microbenchmark. Это обычно не рекомендуется и чертовски сложно сделать правильно.

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

Таким образом, вы не можете ничего сделать о производительности двух коллекций с помощью вышеуказанного тестового кода. Например, то, что вы могли бы измерить, могло быть временем компиляции метода += HashSet и времени сбора мусора ListSet. Так что это сравнение между яблоками и грушами.

Чтобы выполнить микро-тест, вы должны:

Разогрейте JVM: загрузите все классы, убедитесь, что все коды кода в эталоне запущены, а горячие точки в коде скомпилированы (например, метод +=).
Запустите тест и убедитесь, что ни GC, ни компилятор не запускаются во время теста (используйте флаги JVM -XX:-PrintCompilation и -XX:-PrintGC). Если выполняется во время теста, отбросьте результат.
Повторите шаг 2 и образец 10-15 хороших измерений. Вычислить дисперсию и стандартное отклонение.
Оцените: если среднее значение каждого теста +/- 3 std не перекрывается, вы можете сделать вывод о том, что происходит быстрее. В противном случае это размытый результат (в зависимости от количества перекрытий).

Я могу порекомендовать прочитать рекомендации Oracle для выполнения микро-тестов и отличную статью о подводные камни Брайана Гетца.

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

Ответ 3

Поскольку набор должен иметь без дубликатов, перед добавлением элемента Set должен проверить, не содержит ли он уже этот элемент. Этот поиск в списке, который не гарантирует положение элемента, будет O (N) линейным временем. Эта же общая идея относится к операции удаления.

С помощью HashSet класс определяет функцию, которая выбирает местоположение для любого элемента в O (1), что значительно упрощает метод contains (element) за счет увеличения пространства для уменьшения вероятности элемента локальные столкновения.