Масштабируемый способ доступа к каждому элементу ConcurrentHashMap‹Element, Boolean› ровно один раз

Я мог бы попытаться наследоваться от ConcurrentHashMap, получить в свои руки экземпляры его внутреннего сегмента, попытаться сгруппировать их в 32 группы и работать с каждой группой отдельно. Хотя это звучит как хардкорный подход.

Хардкор действительно, но это единственное, что я видел, что будет работать. toArray() строит массив, выполняя перечисление, поэтому здесь нет выигрыша. Я не могу поверить, что синхронизированный HashSet будет лучше, если только соотношение visit() прогонов к другим операциям с картой не будет достаточно высоким.

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

У меня большой вопрос, нужно ли это? Профилировщик или временные прогоны показали вам, что это занимает слишком много времени для visit() каждого из ключей в одном потоке? Вы пытались создать пул потоков для каждого вызова visit() и иметь один поток, выполняющий перечисление, и потоки пула, выполняющие visit()?

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

Сказав, что вы можете использовать ConcurrentSkipListMap, в котором вы можете получить NavigableSet ключей. Затем вы можете удалить из него разделы, используя метод subSet. Однако ConcurrentHashMap будет иметь лучшую производительность для операций put, get (обратите внимание, что будет использоваться compareTo, а не hashCode). Ситуации, когда это лучше, кажутся маловероятными.

Решение, которое я в конечном итоге выберу, - это массив ConcurrentHashMaps вместо одного ConcurrentHashMap. Это специально, но, похоже, имеет отношение к моему варианту использования. Меня не волнует медленный второй шаг, поскольку он не влияет на производительность моего кода. Решение:

Создание объекта:

1. Create an array of size t of ConcurrentHashMaps, where t is a number of threads.
2. Create an array of Runnables, also of size t.

Население массива (однопоточный, не проблема):

1. Create the keys and apply pre-hash function, which will return an int in the range 0 ... t-1. In my case simply modulo t.
2. Put the key in the hashmap, by accessing appropriate entry in the array. E.g. if the pre-hash has resulted in index 4, then go for hashArray[4].put(key)

Итерация массива (хорошо многопоточная, прирост производительности):

1. Assign every thread from Runnables array a job of iterating over the hashmap with a corresponding index. This should give give a t times shorter iteration as opposed to single threaded.

Чтобы увидеть код проверки концепции (поскольку у него есть некоторые зависимости от проекта, который я не могу опубликовать здесь), перейдите по адресу мой проект на github

ИЗМЕНИТЬ

На самом деле, реализация приведенного выше доказательства концепции для моей системы оказалась трудоемкой, подверженной ошибкам и крайне разочаровывающей. Кроме того, я обнаружил, что упустил бы многие функции стандартной библиотеки ConcurrentHashMap. Недавно я исследовал решение, которое выглядит гораздо менее специфичным и гораздо более многообещающим, — это использование Scala, который создает байт-код, полностью совместимый с Java. Доказательство концепции основано на потрясающей библиотеке, описанной в этой статье и, насколько мне известно, в ней в настоящее время НЕВОЗМОЖНО достичь соответствующего решения в vanilla Java без написания тысяч строк кода, учитывая текущее состояние стандартной библиотеки и соответствующих сторонних библиотек.

import scala.collection.parallel.mutable.ParHashMap

class Node(value: Int, id: Int){
    var v = value
    var i = id
    override def toString(): String = v toString
}

object testParHashMap{
    def visit(entry: Tuple2[Int, Node]){
        entry._2.v += 1
    }
    def main(args: Array[String]){
        val hm = new ParHashMap[Int, Node]()
        for (i <- 1 to 10){
            var node = new Node(0, i)
            hm.put(node.i, node)
        }

        println("========== BEFORE ==========")
        hm.foreach{println}

        hm.foreach{visit}

        println("========== AFTER ==========")
        hm.foreach{println}

    }
}