Сразу хочу сказать, что никого оскорблять не хочу и меня интересует только техническая сторона вопроса. Выкладываю в паблик текст задания после того как мне отказались ответить на мои уточняющие вопросы по поводу того, что именно не так.

Задачу стояла так:

авторОчередь заданий с относительным порядком

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


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

Пример: подход, при котором очередь выполняет все задания последовательно в единственном потоке, удовлетворяет условию на порядок выполнения заданий с одинаковым значением ключа.


Примерный интерфейс задания:
interface Task implements Runnable {
String getKey();
}

Примерный интерфейс очереди:
interface TaskExecutor {
void submit(Task task);
}



Решение должно использовать только стандартную библиотеку Java 8, плюс тестовые фреймвоки на выбор.

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

Не требуется делать решение, покрывающее все возможные варианты, учтённые или не учтённые в описании выше.

Мы ожидаем, что решение займет несколько часов.
Если есть сомнения, делайте как проще и задокументируйте, какие упрощения или предположения вы сделали.

Давайте тесты обсуждать не будем, только экзекутор.

я решил задачу двумя способами. Первый - очень очевидно и просто, но с неточностью(не учёл, что hashCode может быть отрицательным), но не достаточно производительно.

Хотел бы обсудить второй способ. Лично мне он очень понравился и я был удовлетворён, что смог решить.

вот код:




а вот комментарий от проверяющего(Кстати спасибо ему большое, что он его выдал - всё таки я потратил время, выполнял задачу, услышать фидбэк очень интересно):

автор## Второй вариант решения

Преимущество этого подхода в том, что задачи с разными ключами будут занимать все доступные потоки.

Проблема предложенной реализации в том, что при использовании метода ConcurrentMap.compute функция ремапинга может быть вызвана несколько раз.
Если несколько потоков одновременно добавляют новые задания с одним и тем же ключом, некоторые из заданий будут многократно добавлены в цепочку CompletableFuture.

Простейший пример - какое-то задание T0 с ключом Х находится в обработке, то есть в мапе присутствует CompletableFuture F0.
Два разных потока одновременно добавляют новые задания T1 и Т2 с тем же ключом Х. В обоих потоках вычисляется taskMap.compute от F0, внутри функции ремапинга оба потока добавляют свои задания в цепочку на F0, но только одному потоку удаётся завершить taskMap.compute, например первому потоку, который создаст CompletableFuture F1. Второй поток вычисляет ремапинг ещё раз, на этот раз от F1, и добавляет своё задание в цепочку поверх F1.

В итоге, если в poolExecutor достаточно свободных потоков, после завершения T0 оба задания T1 и Т2 начнут выполняться одновременно, а после завершения Т1 запуститься ещё один экземпляр Т2.

Дальше я задал следующий вопрос:

По первому решению я согласен с комментариями, а вот что касается второго - хотелось бы уточнений.

авторВ jdk ConcurrentHashMap compute не может исполняться Параллельно для ключей из одного бакета. То есть потоки с задачами T1 и T2 выстроятся в очередь и не будет описанных выше проблем.
/**
* Attempts to compute a mapping for the specified key and its
* current mapped value (or {@code null} if there is no current
* mapping). The entire method invocation is performed atomically.
* Some attempted update operations on this map by other threads
* may be blocked while computation is in progress, so the
* computation should be short and simple, and must not attempt to
* update any other mappings of this Map.
*/
Это довольно легко проверить если сделать Thread.sleep внутри compute и сделать из разных потоков put с одинаковыми ключами.
Я полагаю, что проблема в том, что я использовал ConcurrentHashMap через интерфейс ConcurrentMap, документацию которого я не прочитал. ConcurrentMap интерфейс действительно разрешает несколько раз выполнять compute(видимо для CAS алгоритмов)
/*The default implementation may retry these steps when multiple
* threads attempt updates including potentially calling the remapping
* function multiple times.
*/
И тогда я понимаю как может произойти описанная ситуация.

Мои мысли правильны?

Но на это сообщение мне ответили, что коллеги не имеют достаточно свободного времени, чтобы мне отвечать.

Я полагаю, что неправильное решение значит решение не такое какое они считают наиболее правильным.

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

авторПо первому решению я согласен с комментариями, а вот что касается второго - хотелось бы уточнений.

это часть письма была, конечно.

irbis_alquestioner,

Я в толк не возьму,а Вы тестировали...или просто сделали...Когда речь идёт о многопоточном,то там надо эмулировать ситуации...
В Вашем случае должна быть эмуляция и быть бы лог эмуляции
Типа
Начинает исполнятся задача такая-то(с ключом)
Исполняется задача такая-то
Исполнилась задача такая-то
Начинает исполнятся задача такая-то(с ключом)
Исполняется задача такая-то
Начинает исполнятся задача такая-то(с ключом)
Исполнилась задача такая-то
Исполняется задача такая-то
Начинает исполнятся задача такая-то(с ключом) Опаньки...а уже этот ключ не закончил выполнение
поэтому wait

В частности в эмуляцию подаём все с одинаковыми ключами и я в логе должен видеть однозначно последовательное выполнение.

Для себя на этапе разработки делал, но потом написал тест, который делает это "более умно". Но это совсем другая история. Предлагаю в данном топике тесты не обсуждать.

irbis_al,

Безусловно, такие тесты есть, у меня тоже вызвало вопросы, что тест не валился, а они говорят, что такое может быть. Но это ж конечно многопоточка, если ты не получил ни разу - не значит, что все верно

irbis_alquestionerirbis_al,

Безусловно, такие тесты есть, у меня тоже вызвало вопросы, что тест не валился, а они говорят, что такое может быть. Но это ж конечно многопоточка, если ты не получил ни разу - не значит, что все верно

В том то и дело ,что задание на многопоточность это айсберг...Вершина видная это код ,что Вы написали,а остальное инфраструктура(тесты и логи) где Вы доказываете,что Вы не верблюд и конфликтной ситуации произойти не может.
Я обычно эмулирую с семафорным захватом.Если произошло поточное конфликтное столкновение то эти потоки висят(сцепились как два терьера)...ждут когда кто-то семафоры отпустит.
От Вас наверное именно этого (Невидимой части айсберга) и ожидали.
А раз Вы не серьёзно отнеслись к этой подводной части с Вами никто и разговаривать не захотел.(несмотря на то,что возможно у Вас всё работает верно,-Во всяком случае написано довольно изящно)

Раз уж зашёл разговор про тесты...я в начале таски пробовал добавлять в сет(потокобезопасный) ключ, в конце - удалял. Если в начале не получалось добавлять - значит случилось что-то, что не должно было случиться и я этот факт регистрировал, в конце теста смотрел сколько инцидентов случилось. Тест сабмитил 100_000 тасков по 10 ключам, то есть по 10_000 на каждый ключ. Внутри каждой таски Thread.sleep длительностью от 5 до 30 мс. случайно.

А про семафор я чего-то не понял. Кто с кем сцепиться должен был и по какой причине? семафор же позволяет n потокам войти в критическую секцию.

Но дело явно не в тестах - они ведь явно написали, что код не потоко безопасный, содержит race condition-ы

scf,

Ну мы же все понимаем, что "может" случается для конкурентной модификации в рамках бакета.

vimbaquestioner,

Я детально не вчитывался, но напервый взгляд нигде не сказано, что удалять из мапы нельзя находясь внутри compute, однако по факту это так, по крайней мере для openjdk 1.8.111. Вот этот кода кусок намертво виснет, ровно по той же причине по которой у меня повис и ваш экзекьютор:



В вашем коде действительно как и сказали проверяющие, есть ещё и возможность паралельного выполнения тасок по одному и тому же ключу, только причины другие, не те которые Вам отписали. Но прежде чем я вам их назову, сначала исключите зависание, вызванное тем что whenComplete может вызваться внутри compute, из-за того что фьюча уже закомплечена. Именно расстановка слипов вас и сгубила при тестировании.

А вас не смущает, что я тесты запускал и они проходили? Как это связано со слипами не понятно
Если Вы внимательно посмотрите, что remove выполняется не в compute треде

авторвас и сгубила при тестировании

Зачем пытаться, что-то придумывать если люди явно текстом написали, что их смущает?

забыл никquestionerМы ожидаем, что решение займет несколько часов.


сли останется время, большим плюсом будет написание своей ОС, компилятора Java и аналога Варкрафта.

Да, я в эти оценки тоже не верю. Год наверное назад был в одной конторе на собеседовании, поотвечал на вопросы, потом меня начинают спрашивать готов ли я сделать тестовое задание. А тогда у меня свободного времени особо не было и я скептически начал спрашивать что примерно за задание, какой объём. Мне говорят мол задачка небольшая часа на 3(на дом, естественно). В итоге я сказал, что мне лень её делать(текста я не получал). Потом спрашиваю знакомого из этой фирмы что за задание они дают и на сколько большое. В итоге выяснилось, что тот человек, который меня собеседовал с опытом 15+ лет буквально за полгода до моего собеседования пришёл в компанию и решал эту задачу. У него ушло 3 дня!

Alexey TominquestionerА вас не смущает, что я тесты запускал и они проходили? Как это связано со слипами не понятно

То, что тесты проходят, не гарантирует правильность кода. Особенно если это многопоточность.
Самая плохая бага- которая случается в одном случае из миллиона- на тестах не поймать, в проде- пожалуйста, будет приходить.
Непонимание этого- уже достаточная причина отказать.
А ваша агрессия- причина не объяснять отказ.

20765509

Судя по сообщению человека с ником Vimba у него виснет некий код. Судя по всему всегда. Имхо он либо виснет либо нет.

vimbaнапервый взгляд нигде не сказано, что удалять из мапы нельзя находясь внутри compute

автор /**
* Attempts to compute a mapping for the specified key and its
* current mapped value (or {@code null} if there is no current
* mapping). The entire method invocation is performed atomically.
* Some attempted update operations on this map by other threads
* may be blocked while computation is in progress, so the
* computation should be short and simple, and must not attempt to
* update any other mappings of this Map.
*
* @param key key with which the specified value is to be associated
* @param remappingFunction the function to compute a value
* @return the new value associated with the specified key, or null if none
* @throws NullPointerException if the specified key or remappingFunction
* is null
* @throws IllegalStateException if the computation detectably
* attempts a recursive update to this map that would
* otherwise never complete
* @throws RuntimeException or Error if the remappingFunction does so,
* in which case the mapping is unchanged
*/

vimba сначала исключите зависание, вызванное тем что whenComplete может вызваться внутри compute, из-за того что фьюча уже закомплечена.

Поясните что это и зачем, как вы решили, что это неправильно.

questionervimba сначала исключите зависание, вызванное тем что whenComplete может вызваться внутри compute, из-за того что фьюча уже закомплечена.

Поясните что это и зачем, как вы решили, что это неправильно.

Ок, действительно такое имеет место быть.




авторMain thread:1
Before sleep thread:11
After sleep
whenCompleted thread:1


Только они этого не нашли)

Надо подумать как это решить... из спортивного интереса

Alexey TominВаше решение- по сути своей хак.
Такой код нельзя пускать в production. Он чрезвычайно неочевиден.
Можно терпеть медленный код, но нельзя непонятный.
Тут дискутировать нечего- это вопрос вкуса. Работает или нет- уже вторично, на самом деле.

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

Да и заказчику зачастую на%?#ть понятно написано или нет - лишь бы работало. Как объясните заказчику, что есть рабочий непонятный код, который быстро работает, а есть медленный, но понятный. Думаю заказчик выберет быстрый вариант, если для него это критично. Но я опять же не агитирую писать непонятную ахинею. Я вообще не очень согласен, что код совсем уж непонятный. не простой - да, но и задача не самая очевидная не очень то делится на подзадачи.

Alexey Tominquestioner


На самом деле имя "queue" для этого параметра- уже смертный приговор.

Почему?