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

vsb>В общем сделал через synchronized, мне такой скорости за глаза. Почему-то думал, что будет на порядок медленней.
Я тоже сделал тесты. У меня для вас плохие новости. Все гораздо сложнее, чем кажется на первый взгляд. Давайте по-порядку.

Тесты на JMH (я хотел его освоить для других проектов, вы дали хороший повод) доступны здесь. Извините, sbt. Я его знаю лучше. А еще он у меня есть! (А вот gradle, maven и прочего — нет). Весь код на Java, находится в src. Параметры запуска и результаты — в random.txt/urandom.txt, еще небольшое описание в README.txt (можно не читать, там примерно то же, что в этом сообщении).

Собственно, я экспериментировал с различными разположениями synchronized а также с вариантами атомиков. На коротких тестах (я проверял, что алгоритмы вообще работают) Synchronized везде оказался в 1.5 раза лучше. При этом перемещение SecureRandom вверх давало небольшой прирост скорости (uid2RndFirst). Я еще игрался с nanoTime — оно может иметь разрешение лучше, чем currentTimeMillis(). И само по себе вроде бы быстрее в Linux, но скорость компенсируется необходимостью делать дополнительную математику. Отладил я тесты, запустил jmh с настройками по-умолчанию и отправился по своим делам. Вернулся, посмотрел на процесс и ужаснулся. Отдельные запуски провалились по скорости в 5 раз (с двух миллионов до четырехсот тысяч). При этом "отдельные запуски" — это вычисление в течение 10 секунд. На таком разбросе считать "среднюю прозиводительность" как-то не очень правильно. На машине ничего тяжелого запущено не было, списать на это не получится. И тут-то я понял, что мы измеряем что-то не то.

Фактически вы в ваших тестах (и я при запуске тестов по умолчанию) измеряем не скорость вашего алгоритма. Мы измеряем быстродействие (throughput) у SecureRandom. По-умолчанию он ходит в /dev/random, который может блокироватсья при недостатке энтропии. Поэтому-то и проваливалось быстродействие, когда я был не за компьютером — нет энтропии (нажатия клавиш, движения мышки). И вот здесь оказывается на руку тот факт, что synchronized — тяжелый. Что такое атомик? В сущности, это просто чтение/запись в память специальными инструкциями процессора. Synchrnoized делает гораздо больше. Да, в простом случае там тоже spin-lock, но потом он переделывается в мютекс операционной системы, планировщик ОС уведомляется о том, что поток в ожидании и т.д. В общем, движуха. А движуха — это энтропия, которой нам так не хватает! Решение synchronized побеждает не потому, что оно лучше. Нет! Оно побеждает как раз потому, что оно гораздо хуже!

Если переконфигурировать JVM на использование неблокирующего шума (/dev/urandom), ситуация в корне меняется. Атомики и некоторые (они короткие по коду, скорее всего разруливаются спинлоком без вызовов OS) варианты синхронизации приближаются к теоретическому максимуму в четыре миллиона. Ну и начинают есть 100% CPU (предыдущие итерации — нет, они блокируются на random и загрузка CPU где-то в районе 20-40% всего). И в целом атомики выигрывают у synchronized аж в 8 раз! И казалось бы, справедливость восторжествовала! Но и здесь не все так гладко...

У нас ведь раньше synchronized давал 3/4 теоретической пропускной способности. Так как мы его аж в 8 раз обогнали? Так вот, оказывается, synchronized-решения (которые с "большой" синхронизацией) теперь стали работать в 6 раз медленне . Т.е. мы вроде-бы заменили вызовы в SecureRandom на более быстрые, и все у нас замедлилось. Этот эффект я объяснять не умею. Может быть, какие-то эффекты, связанные с планировщиком ОС. Т.е. когда у нас SecureRandom блокируется, добавление потока в список ожидания (wait list) на мьютексе дает энтропию, разблокирует другой поток и все получается более-менее по-порядку. А когда там synchronized, все получается быстро и слишком много потоков встают в ожидание. В общем, я . Если кто-то знает — поделитесь соображениями.

Выводов не будет. Я бы по результам данных экспериментов добавил сбор метрик вокруг всего метода и SecureRandom. Кто его знает, что там у вас с энтропией будет на реальных серверах. А еще я бы поймал админа или девопса и спросил, что у них вообще происходит. В некоторых компаниях образы docker для Java уже содержат настройки по использованию /dev/urandom в качестве источника случайных чисел. В этом случае нужно брать атомики или "малую" синхронизацию. А вот если ничего нет — нужно собирать данные и думать дальше.

vsb>Наверное можно ещё сделать через ThreadLocal переменные и не заморачиваться тем, что в разных потоках будут получаться одинаковые (timeMillis, counter), попробую ради интереса этот вариант, сравнить скорость.
Гипотеза. Будет порядка двух миллионов. Может быть меньше. Вряд ли больше. Все из-за недостаточной энтропии для SecureRandom.

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

vsb>В общем сделал через synchronized, мне такой скорости за глаза. Почему-то думал, что будет на порядок медленней.
Я тоже сделал тесты. У меня для вас плохие новости. Все гораздо сложнее, чем кажется на первый взгляд. Давайте по-порядку.

Тесты на JMH (я хотел его освоить для других проектов, вы дали хороший повод) доступны здесь. Извините, sbt. Я его знаю лучше. А еще он у меня есть! (А вот gradle, maven и прочего — нет). Весь код на Java, находится в src. Параметры запуска и результаты — в random.txt/urandom.txt, еще небольшое описание в README.txt (можно не читать, там примерно то же, что в этом сообщении).

Собственно, я экспериментировал с различными расположениями synchronized а также с вариантами атомиков. На коротких тестах (я проверял, что алгоритмы вообще работают) Synchronized везде оказался в 1.5 раза лучше. При этом перемещение SecureRandom вверх давало небольшой прирост скорости (uid2RndFirst). Я еще игрался с nanoTime — оно может иметь разрешение лучше, чем currentTimeMillis(). И само по себе вроде бы быстрее в Linux, но скорость компенсируется необходимостью делать дополнительную математику. Отладил я тесты, запустил jmh с настройками по-умолчанию и отправился по своим делам. Вернулся, посмотрел на процесс и ужаснулся. Отдельные запуски провалились по скорости в 5 раз (с двух миллионов до четырехсот тысяч). При этом "отдельные запуски" — это вычисление в течение 10 секунд. На таком разбросе считать "среднюю прозиводительность" как-то не очень правильно. На машине ничего тяжелого запущено не было, списать на это не получится. И тут-то я понял, что мы измеряем что-то не то.

Фактически вы в ваших тестах (и я при запуске тестов по умолчанию) измеряем не скорость вашего алгоритма. Мы измеряем быстродействие (throughput) у SecureRandom. По-умолчанию он ходит в /dev/random, который может блокироватсья при недостатке энтропии. Поэтому-то и проваливалось быстродействие, когда я был не за компьютером — нет энтропии (нажатия клавиш, движения мышки). И вот здесь оказывается на руку тот факт, что synchronized — тяжелый. Что такое атомик? В сущности, это просто чтение/запись в память специальными инструкциями процессора. Synchrnoized делает гораздо больше. Да, в простом случае там тоже spin-lock, но потом он переделывается в мютекс операционной системы, планировщик ОС уведомляется о том, что поток в ожидании и т.д. В общем, движуха. А движуха — это энтропия, которой нам так не хватает! Решение synchronized побеждает не потому, что оно лучше. Нет! Оно побеждает как раз потому, что оно гораздо хуже!

Если переконфигурировать JVM на использование неблокирующего шума (/dev/urandom), ситуация в корне меняется. Атомики и некоторые (они короткие по коду, скорее всего разруливаются спинлоком без вызовов OS) варианты синхронизации приближаются к теоретическому максимуму в четыре миллиона. Ну и начинают есть 100% CPU (предыдущие итерации — нет, они блокируются на random и загрузка CPU где-то в районе 20-40% всего). И в целом атомики выигрывают у synchronized аж в 8 раз! И казалось бы, справедливость восторжествовала! Но и здесь не все так гладко...

У нас ведь раньше synchronized давал 3/4 теоретической пропускной способности. Так как мы его аж в 8 раз обогнали? Так вот, оказывается, synchronized-решения (которые с "большой" синхронизацией) теперь стали работать в 6 раз медленне . Т.е. мы вроде-бы заменили вызовы в SecureRandom на более быстрые, и все у нас замедлилось. Этот эффект я объяснять не умею. Может быть, какие-то эффекты, связанные с планировщиком ОС. Т.е. когда у нас SecureRandom блокируется, добавление потока в список ожидания (wait list) на мьютексе дает энтропию, разблокирует другой поток и все получается более-менее по-порядку. А когда там synchronized, все получается быстро и слишком много потоков встают в ожидание. В общем, я . Если кто-то знает — поделитесь соображениями.

Выводов не будет. Я бы по результам данных экспериментов добавил сбор метрик вокруг всего метода и SecureRandom. Кто его знает, что там у вас с энтропией будет на реальных серверах. А еще я бы поймал админа или девопса и спросил, что у них вообще происходит. В некоторых компаниях образы docker для Java уже содержат настройки по использованию /dev/urandom в качестве источника случайных чисел. В этом случае нужно брать атомики или "малую" синхронизацию. А вот если ничего нет — нужно собирать данные и думать дальше.

vsb>Наверное можно ещё сделать через ThreadLocal переменные и не заморачиваться тем, что в разных потоках будут получаться одинаковые (timeMillis, counter), попробую ради интереса этот вариант, сравнить скорость.
Гипотеза. Будет порядка двух миллионов. Может быть меньше. Вряд ли больше. Все из-за недостаточной энтропии для SecureRandom.