Реализация и ограничения ConcurrentHashMap

Question

У меня довольно большой проект, и я захожу в тупик. Я хотел посмотреть, есть ли у великого сообщества какие-либо предложения.

У меня большой набор данных, и я пытаюсь построить социальный график. Данные содержат более 9,5 миллионов отображений координат в значение Short. Для значений ключа в ConcurrentHashMap я использую строку, то есть координаты, объединенные с ',' между ними.

По сути, я нахожу общее количество групп между пользователями. У меня есть начальная хэш-карта, которая создается довольно легко, которая сопоставляет GroupID с вектором AvatarID. Эта часть работает нормально. Затем у меня есть 12 потоков, которые отвечают за собственный набор GroupID и обработку (добавление + 1 к количеству пользователей в каждом groupID), причем весь доступ осуществляется из ConcurrentHashMap.

После обработки около 8000 групп возникает проблема с доступом. Только один поток за раз кажется активным, и я не уверен, что это из-за огромного размера или другого фактора. Это проблема, поскольку у меня есть 300 000 групп, которые должны быть обработаны в общей сложности (и своевременно).

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

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

Спасибо за ваше время, -mojavestorm

Дальнейшее объяснение:

Две реализации и их ограничения:

1) У меня есть предварительная карта HashMap (Integer, Vector (Integer)), которая содержит GroupID в качестве ключа и вектор userID. Потоки разделяют групповые идентификаторы между собой и, используя каждый возвращенный вектор (целое число), каждый поток сохраняет короткое значение в соответствии с координатой (говоря, что UserID x и UserID y принадлежат (коротким) n группам вместе) в TLongShortHashMap threadMap и каждый поток имеет свой собственный ThreadMap. Координаты отображаются в длинные значения. После завершения каждого потока значения соответствующих ключей в каждой из нитокMap добавляются к одному и тому же ключу в комбинированной карте, которая покажет, как много групп UserID x и UserID y принадлежат друг другу во всей системе.

Проблема с этой реализацией состоит в том, что между потоками существует сильное перекрытие, поэтому создаются чрезмерные короткие значения. Например, Пользователь 1 и Пользователь 2 принадлежат к различным группам вместе. Поток A и Поток B отвечают за свой собственный диапазон групп, включая принадлежащие Пользователю 1 и Пользователю 2, поэтому как Поток A, так и Поток B сохраняют в своей копии threadMap длинное значение для координаты (1, 2) и короткое значение. Если происходит чрезмерное перекрытие, тогда требования к памяти могут быть невыполненными. В моем случае все 46 ГБ ОЗУ, которые я выделяю для Java, израсходованы, и тоже довольно быстро.

2) Используя тот же preMap в этой реализации, каждому потоку присваивается диапазон пользовательских координат, за которые он отвечает. Каждый поток выполняется и получает каждую имеющуюся у него координату и выполняет итерацию по preMap, проверяя каждый groupID и проверяя, принадлежат ли UserID x и UserID y к вектору, возвращенному из preMap. Эта реализация устраняет наложение, которое произойдет между threadMaps.

Проблема с этим - время. Прямо сейчас программа работает с потрясающей скоростью 1400 лет, чтобы закончить. Объем используемой памяти колеблется от 4 до 15 ГБ, но, похоже, остается «низким». Не совсем уверен, что он будет оставаться в рамках, однако, я думаю, что это будет. Для меня нет очевидных улучшений.

Надеюсь, эти описания понятны и помогут понять мою проблему. Спасибо.

Answer 1

Я хотел бы, чтобы каждый поток обрабатывал свою собственную карту. Это означает, что каждый поток может работать взаимозависимо. После завершения потоков вы можете объединить все результаты. (Или, возможно, объединить результаты по мере их завершения, но это может добавить сложности с небольшим преимуществом)

Если вы используете короткое, я бы использовал в коллекции, как TObjectIntHashMap , которая более эффективна для обработки примитивов.

---

В простом случае у вас есть short координаты public static void main (String ... args) выдает IOException { длина int = 10 *1000* 1000; int [] x = new int [length]; int [] y = new int [length];

  Random rand = new Random();
  for (int i = 0; i < length; i++) {
    x[i] = rand.nextInt(10000) - rand.nextInt(10000);
    y[i] = rand.nextInt(10000) - rand.nextInt(10000);
  }

  countPointsWithLongIntMap(x, y);
  countPointsWithMap(x, y);

}

private static Map<String, Short> countPointsWithMap(int[] x, int[] y) {
  long start = System.nanoTime();
  Map<String, Short> counts = new LinkedHashMap<String, Short>();
  for (int i = 0; i < x.length; i++) {
    String key = x[i] + "," + y[i];
    Short s = counts.get(key);
    if (s == null)
      counts.put(key, (short) 1);
    else
      counts.put(key, (short) (s + 1));
  }
  long time = System.nanoTime() - start;
  System.out.printf("Took %.3f seconds to use Map<String, Short>%n", time/1e9);

  return counts;
}

private static TIntIntHashMap countPointsWithLongIntMap(int[] x, int[] y) {
  long start = System.nanoTime();
  TIntIntHashMap counts = new TIntIntHashMap();
  for (int i = 0; i < x.length; i++) {
    int key =  (x[i] << 16) | (y[i] & 0xFFFF);
    counts.adjustOrPutValue(key, 1, 1);
  }
  long time = System.nanoTime() - start;
  System.out.printf("Took %.3f seconds to use TIntIntHashMap%n", time/1e9);
  return counts;
}

печать

Took 1.592 seconds to use TIntIntHashMap
Took 4.889 seconds to use Map<String, Short>

---

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

public static void main(String... args) throws IOException {
  int length = 10 * 1000 * 1000;
  double[] x = new double[length];
  double[] y = new double[length];

  Random rand = new Random();
  for (int i = 0; i < length; i++) {
    x[i] = (rand.nextInt(10000) - rand.nextInt(10000)) / 1e4;
    y[i] = (rand.nextInt(10000) - rand.nextInt(10000)) / 1e4;
  }

  countPointsWithLongIntMap(x, y);
  countPointsWithMap(x, y);

}

private static Map<String, Short> countPointsWithMap(double[] x, double[] y) {
  long start = System.nanoTime();
  Map<String, Short> counts = new LinkedHashMap<String, Short>();
  for (int i = 0; i < x.length; i++) {
    String key = x[i] + "," + y[i];
    Short s = counts.get(key);
    if (s == null)
      counts.put(key, (short) 1);
    else
      counts.put(key, (short) (s + 1));
  }
  long time = System.nanoTime() - start;
  System.out.printf("Took %.3f seconds to use Map<String, Short>%n", time / 1e9);

  return counts;
}

private static TDoubleObjectHashMap<TDoubleIntHashMap> countPointsWithLongIntMap(double[] x, double[] y) {
  long start = System.nanoTime();
  TDoubleObjectHashMap<TDoubleIntHashMap> counts = new TDoubleObjectHashMap<TDoubleIntHashMap>();
  for (int i = 0; i < x.length; i++) {
    TDoubleIntHashMap map = counts.get(x[i]);
    if (map == null)
      counts.put(x[i], map = new TDoubleIntHashMap());
    map.adjustOrPutValue(y[i], 1, 1);
  }
  long time = System.nanoTime() - start;
  System.out.printf("Took %.3f seconds to use TDoubleObjectHashMap<TDoubleIntHashMap>%n", time / 1e9);
  return counts;
}

печать

Took 3.023 seconds to use TDoubleObjectHashMap<TDoubleIntHashMap>
Took 7.970 seconds to use Map<String, Short>