Есть массив double-ов. Есть несколько потоков которые считают функцию качества и результат кладут в этот массив.
Каждый поток работает со своей частью массива и по индексам не пересекаются.
Можно ли работать с массивом без синхронизации?

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

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

Здравствуйте, kuaw26, Вы писали:

K>Есть массив double-ов. Есть несколько потоков которые считают функцию качества и результат кладут в этот массив.
K>Каждый поток работает со своей частью массива и по индексам не пересекаются.
K>Можно ли работать с массивом без синхронизации?
K>у меня пока не вышло. Почему-то в итоге некоторые элементы массива оказываются "пропущенными" и в итоге дальнейшая обработка
K>данных из этого массива происходит некорректно.

Странно. Нет никаких предпосылок для того чтоб запись в разные индексы массива была не потокобезопасной.
А чтение точно синхронизированно со всеми записями? Может оно происходит когда ещё не все потоки записали свои значения.

K>Есть массив double-ов. Есть несколько потоков которые считают функцию качества и результат кладут в этот массив.
K>Каждый поток работает со своей частью массива и по индексам не пересекаются.
K>Можно ли работать с массивом без синхронизации?

гарантии видимости(чтения) при записи в массив из разных потоков отсуствуют (
для лонгов и объектов в стандартной библиотеке есть AtomicLongArray и AtomicReferenceArray (всё lock-free), соответственно.
в качестве конструктива — можно адаптироваться к кому-то из них или написать своё на volatile/lock/synchronized.
вам нужна только видимость, т.что volatile-ов должно хватить.

Здравствуйте, abch-98-ru, Вы писали:
K>>Можно ли работать с массивом без синхронизации?
A9R>гарантии видимости(чтения) при записи в массив из разных потоков отсуствуют (
fix: если поток читающий != потоку записывающему

Здравствуйте, Blazkowicz, Вы писали:

B>Странно. Нет никаких предпосылок для того чтоб запись в разные индексы массива была не потокобезопасной.
Вообще, если копать очень глубоко, то предпосылки есть. Процессоры многоядерные, с отдельным кешем под каждое ядро. В одном потоке меняют, в другом не факт что видно (хоть я и далек от беталей работы процессоров, но здравый смысл подсказывает, что в целях оптимизации синхронизацию кешей при каждой записи могли не делать, или делать отложенно). Тут просто примитивы могут не быть видны без volatile, а с массивами то еще сложнее вроде ситуация.

elmal>Вообще, если копать очень глубоко, то предпосылки есть. Процессоры многоядерные, с отдельным кешем под каждое ядро. В одном потоке меняют, в другом не факт что видно (хоть я и далек от беталей работы процессоров, но здравый смысл подсказывает, что в целях оптимизации синхронизацию кешей при каждой записи могли не делать, или делать отложенно). Тут просто примитивы могут не быть видны без volatile, а с массивами то еще сложнее вроде ситуация.

Таки да тест делался на 4-х ядерном Core Quad 9500.
Основной поток пускал 4 рассчитывающих потока и ждал их окончания.
Использовал Fork/Join который обещают в 7-ой джаве добавить, но он уже и в 6-ке доступен.

abch-98-ru> гарантии видимости(чтения) при записи в массив из разных потоков отсуствуют (
для лонгов и объектов в стандартной библиотеке есть AtomicLongArray и AtomicReferenceArray (всё lock-free), соответственно.
в качестве конструктива — можно адаптироваться к кому-то из них или написать своё на volatile/lock/synchronized.
вам нужна только видимость, т.что volatile-ов должно хватить.

Это я уже то же нагуглил про AtomicXXXArray, но для double-ов нет готовой реализации.
Попробовать написать AtomicDoubleArray — ???
Нагуглил вот такую дискуссию:

> Is there a reason util.concurrent has no AtomicDoubleArray class?
Yes because there are no generally available atomic instructions for
operating on floating-point values. So basically your only option is
synchronization using locks.

> There is this throw-away line at the end of the package docs:
> "You can also hold floats using Float.floatToIntBits and
> Float.intBitstoFloat conversions, and doubles using
> Double.doubleToLongBits and Double.longBitsToDouble conversions."
> But that doesn't seem to help if you want to use the atomic add
> methods

Right, these techniques allow you to hold float bits and do atomic get/set
and CAS but not general arithmetic — because again there are no atomic
instructions for doing that.

> Is there another way to do atomic double array ops that doesn't
> involve using synchronize?

Nope — locking is really your only option.

Здравствуйте, kuaw26, Вы писали:

K>пока сделал так: каждый поток имеет свой приватный массив и пишет в него. После того как все потоки окончили работу, я через
K>System.arraycopy() перебрасываю данные в один большой массив.

Скажи, пожалуйста, почему ты считаешь что это плохо?
Мне наоборот кажется этот подход более правильным.
1. проще логика — каждый тред обработчик имеет свой стораж, и его вообще никак не волнует куда и как дальше будут записаны его результаты.
2. локальный массив если он не велик сможет скешироваться (тута я может брешу)
3. нет глобальной переменной YARRR :D

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

Здравствуйте, zubr, Вы писали:

Z>Скажи, пожалуйста, почему ты считаешь что это плохо?
Z>Мне наоборот кажется этот подход более правильным.
Z>1. проще логика — каждый тред обработчик имеет свой стораж, и его вообще никак не волнует куда и как дальше будут записаны его результаты.
Z>2. локальный массив если он не велик сможет скешироваться (тута я может брешу)
Z>3. нет глобальной переменной YARRR :D
Z>если какая то конвеерная обработка данных, и результатов одного треда хватает — упрощается логика и сам механизм.

Ну скажем так, в некоторых ситуациях — плохо.
Так как идет удвоенный расход памяти: большой массив в основном потоке и еще столько же, но пропорциональными кусками в потоках обработчиках.

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

ну и я просто хотел для себя выяснить, что же не так с массивом double-ов, так сказать, закрыть пробел в своих познаниях.

Нагуглил тут идею таки заюзать AtomicLongArray, просто предварительно преобразуя Double.doubleToLongBits(double) и потом обратно.

K>Но подумав хорошенько куда моя программа будет расти, а расти она будет в сторону запуска вчисляющих потоков на кластре,
K>то в итоге все равно бы пришлось каждому вычислителю выделять свой сторадж для локальных вычислений, а потом просчитанный кусок отдавать
K>главному процессу.
если мы уж про архитектуру... map/reduce не крутили для вашей задачи?

K>ну и я просто хотел для себя выяснить, что же не так с массивом double-ов, так сказать, закрыть пробел в своих познаниях.
вроде уже обсудили.

Здравствуйте, elmal, Вы писали:

B>>Странно. Нет никаких предпосылок для того чтоб запись в разные индексы массива была не потокобезопасной.
E>Вообще, если копать очень глубоко, то предпосылки есть. Процессоры многоядерные, с отдельным кешем под каждое ядро. В одном потоке меняют, в другом не факт что видно. Тут просто примитивы могут не быть видны без volatile, а с массивами то еще сложнее вроде ситуация.

А что там сложного? Массив инициализируется один раз и до запуска нитей-счетчиков, вся необходимая память выделяется сразу же. Взять недоинициализированный массив ни одна из нитей не может. Границы индексов у каждой нити свои и тоже рассчитываются до начала их работы. Основная нить начинает работу с массивом только после окончания работы всех нитей-счетчиков. То есть, все данные, касающиеся массива и его границ, известны до запуска нитей-счетчиков, так что никакого фейла из-за отсутствия volatile быть не может.
Не вижу ни одной причины, по которой может происходить ошибка из-за многопоточной среды.
Думаю, это скорее логическая ошибка в рассчетах или в распределении области для хранения данных.

Здравствуйте, kuaw26, Вы писали:

K>Нагуглил тут идею таки заюзать AtomicLongArray, просто предварительно преобразуя Double.doubleToLongBits(double) и потом обратно.

Если действительно "Основной поток пускал 4 рассчитывающих потока и ждал их окончания.", то не нужны никакие атомики. После окончания работы нить обязана скинуть все, что она закешировала (иначе смысла нет — результат работы уйдет вместе с кешом в GC).
Думаю, что проблема в логике разбиения массива на логические куски.
Можно код?

Здравствуйте, Donz, Вы писали:


D>А что там сложного? Массив инициализируется один раз и до запуска нитей-счетчиков, вся необходимая память выделяется сразу же. Взять недоинициализированный массив ни одна из нитей не может. Границы индексов у каждой нити свои и тоже рассчитываются до начала их работы. Основная нить начинает работу с массивом только после окончания работы всех нитей-счетчиков. То есть, все данные, касающиеся массива и его границ, известны до запуска нитей-счетчиков, так что никакого фейла из-за отсутствия volatile быть не может.
D>Не вижу ни одной причины, по которой может происходить ошибка из-за многопоточной среды.
D>Думаю, это скорее логическая ошибка в рассчетах или в распределении области для хранения данных.

В этом случае никто не гарантирует что результат записи потоков в этот массив будет виден в потоке, которые потом это дело читает. Вся запись поихайдет в локальном кэше процессора и без синхронизации кеша все может статься локально. Так что volatile таки нужен.

Здравствуйте, abch-98-ru, Вы писали:

K>>ну и я просто хотел для себя выяснить, что же не так с массивом double-ов, так сказать, закрыть пробел в своих познаниях.
A9R>вроде уже обсудили.
Нет, не обсудили.

Здравствуйте, kuaw26, Вы писали:

K>Здравствуйте, zubr, Вы писали:

Z>>Скажи, пожалуйста, почему ты считаешь что это плохо?
Z>>Мне наоборот кажется этот подход более правильным.
Z>>1. проще логика — каждый тред обработчик имеет свой стораж, и его вообще никак не волнует куда и как дальше будут записаны его результаты.
Z>>2. локальный массив если он не велик сможет скешироваться (тута я может брешу)
Z>>3. нет глобальной переменной YARRR :D
Z>>если какая то конвеерная обработка данных, и результатов одного треда хватает — упрощается логика и сам механизм.

K>Ну скажем так, в некоторых ситуациях — плохо.
K>Так как идет удвоенный расход памяти: большой массив в основном потоке и еще столько же, но пропорциональными кусками в потоках обработчиках.

А может есть возможность сихронизировать данные в большой массив последовательно. Ну тоесть локальные массивы сделать небольшими и сливать их по мере наполнения. В таком случае можно подобрать размер этих массивов так, что бы они были равны или кратны кэш линии процессора, что хорошо скажется на производительности. Правда это надо будет параметризовать в зависимости от железа.

Здравствуйте, kuaw26, Вы писали:

K>Есть массив double-ов. Есть несколько потоков которые считают функцию качества и результат кладут в этот массив.
K>Каждый поток работает со своей частью массива и по индексам не пересекаются.
K>Можно ли работать с массивом без синхронизации?

K>у меня пока не вышло. Почему-то в итоге некоторые элементы массива оказываются "пропущенными" и в итоге дальнейшая обработка
K>данных из этого массива происходит некорректно.

Насколько я понимаю, все должно быть в порядке без всяких синхронизаций.

Аргументация :

Если предположить иное (хоть из-за кешей, хоть из-за чего иного), то

Большой массив — это блок памяти. Тот факт, что он непрерывный — к делу не относится. Если бы он не был непрерывным, ничего бы не менялось в плане этой проблемы.
Тогда, получается, разные потоки могли бы писать в разные блоки памяти, и при этом возникали бы какие-то проблемы. Если бы они возникали, это подорвало бы вообще всю идею потоков — мало ли кто куда пишет.

Здравствуйте, Nicht, Вы писали:

N>В этом случае никто не гарантирует что результат записи потоков в этот массив будет виден в потоке, которые потом это дело читает. Вся запись поихайдет в локальном кэше процессора и без синхронизации кеша все может статься локально. Так что volatile таки нужен.
volatile будет действовать только на переменную, которая ссылается на весь массив. Даже если запись в массив кешировалась на потоке, это было бы важно только если бы происходило параллельное чтение. Чтение (по словам автора) происходит отдельным потоком после того как запись завершилась.

Здравствуйте, Blazkowicz, Вы писали:

B>Здравствуйте, Nicht, Вы писали:

N>>В этом случае никто не гарантирует что результат записи потоков в этот массив будет виден в потоке, которые потом это дело читает. Вся запись поихайдет в локальном кэше процессора и без синхронизации кеша все может статься локально. Так что volatile таки нужен.
B>volatile будет действовать только на переменную, которая ссылается на весь массив. Даже если запись в массив кешировалась на потоке, это было бы важно только если бы происходило параллельное чтение. Чтение (по словам автора) происходит отдельным потоком после того как запись завершилась.

Ну если гарантирован syncronized order между записью и чтение, то конечно все пучком. Этого можно добится несколькими способами, вызвать Thread.join() на пример. В спеке все это сказано. Однако если ты юзаешь ThreadPool то поток как бы и не завершится и будет alive, и там нужно делать синхроназед ордер вручную. Стандартный способ это свезка записи и чтения в другую volatile переменную, а между ними свое действие. Ну или вопользоваться FutureTask, там сделано тоже самое через AbstractQueuedSynchronizer.

Здравствуйте, Nicht, Вы писали:

N>В этом случае никто не гарантирует что результат записи потоков в этот массив будет виден в потоке, которые потом это дело читает. Вся запись поихайдет в локальном кэше процессора и без синхронизации кеша все может статься локально. Так что volatile таки нужен.

ТС ниже уточнил, что основная нить начинает обработку массива после окончания работы нитей-счетчиков. Кеши должны гарантировано сброситься.

Здравствуйте, Donz, Вы писали:

D>Здравствуйте, Nicht, Вы писали:

N>>В этом случае никто не гарантирует что результат записи потоков в этот массив будет виден в потоке, которые потом это дело читает. Вся запись поихайдет в локальном кэше процессора и без синхронизации кеша все может статься локально. Так что volatile таки нужен.

D>ТС ниже уточнил, что основная нить начинает обработку массива после окончания работы нитей-счетчиков. Кеши должны гарантировано сброситься.

Ну что значит после все равно не сильно понятно. Если стоит join() то да. Если же какая то другая магия, то не факт.

Про это сказано в спеке

The final action in a thread T1 synchronizes-with any action in another thread T2 that detects that T1 has terminated. T2 may accomplish this by calling T1.isAlive() or T1.join().

Тоесть если поток завершился и никто у него не спросил что он завершился, то и изменения могут и не увидеть.