Ставьте лайк и смотрите снова, формируйте привычку, ищите в WeChat【Третий принц Ао Бин】Следуйте за этим дураком, у которого, кажется, что-то есть
эта статьяGitHub github.com/JavaFamilyОн был включен, и есть полные тестовые сайты, материалы, шаблоны резюме и моя программа жизни для интервью с производителями первой линии.
предисловие
Генерация случайных чисел в коде — очень распространенная функция, и JDK предоставил готовый класс Random для ее реализации, а класс Random является потокобезопасным.
Ниже приведена реализация Random.next() для генерации случайного целого числа:
protected int next(int bits) {
long oldseed, nextseed;
AtomicLong seed = this.seed;
do {
oldseed = seed.get();
nextseed = (oldseed * multiplier + addend) & mask;
//CAS 有竞争是效率低下
} while (!seed.compareAndSet(oldseed, nextseed));
return (int)(nextseed >>> (48 - bits));
}
Нетрудно заметить, что операция CAS используется для обновления начального числа в приведенном выше методе.В сценарии с большим количеством конкурирующих потоков эта операция CAS, скорее всего, завершится ошибкой, и в случае сбоя она будет повторена, и эта повторная попытка потребует операций ЦП, что значительно повысит производительность.
Следовательно, хотя Random является потокобезопасным, он не является «высококонкурентным».
Чтобы решить эту проблему и повысить производительность генераторов случайных чисел в средах с высокой степенью параллелизма, существует ThreadLocalRandom, высокопроизводительный генератор случайных чисел с высокой степенью параллелизма.
ThreadLocalRandom наследуется от Random, согласно принципу подстановки Лискова это означает, что ThreadLocalRandom предоставляет ту же функцию генерации случайных чисел, что и Random, но алгоритм реализации немного отличается.
Переменные в потоке
Чтобы справиться с конкуренцией потоков, в Java существует класс ThreadLocal, который выделяет отдельное и не связанное пространство для хранения для каждого потока.
Реализация ThreadLocal зависит отThreadLocal.ThreadLocalMap threadLocalsполе участника.
Точно так же, чтобы разрешить генератору случайных чисел доступ только к данным локального потока и избежать конкуренции, в Thread добавляются еще три члена:
/** The current seed for a ThreadLocalRandom */
@sun.misc.Contended("tlr")
long threadLocalRandomSeed;
/** Probe hash value; nonzero if threadLocalRandomSeed initialized */
@sun.misc.Contended("tlr")
int threadLocalRandomProbe;
/** Secondary seed isolated from public ThreadLocalRandom sequence */
@sun.misc.Contended("tlr")
int threadLocalRandomSecondarySeed;
Как члены класса Thread, эти три поля естественным образом тесно связаны с каждым объектом Thread, поэтому они становятся настоящей переменной ThreadLocal, а генератор случайных чисел, реализованный этими переменными, становится ThreadLocalRandom.
Устранение ложного обмена
Я не знаю, заметили ли вы, что у этих переменных есть аннотация @sun.misc.Contended Для чего используется эта аннотация? Чтобы понять это, вы должны сначала узнать важную проблему параллельного программирования —ложный обмен:
Мы знаем, что ЦП не имеет прямого доступа к памяти, данные загружаются в регистр из кэша, а кэш имеет L1, L2, L3 и другие уровни. Здесь мы сначала упростим эти ответственные иерархии, предполагая, что существует только один уровень кэш-памяти и одна основная память.
Когда ЦП читает и обновляет кеш, это выполняется в единицах поведения, также называемых строкой кеша.Строка обычно составляет 64 байта, что составляет 8 длинных строк.
Поэтому возникает вопрос: строка кэша может содержать несколько переменных, что произойдет, если несколько потоков будут обращаться к разным переменным одновременно, и эти разные переменные окажутся в одной строке кэша?
Как показано на рисунке выше, X и Y — это две соседние переменные, расположенные в одной строке кэша, их загружают как CPU core1, так и core2, core1 обновляет X, и в то же время core2 обновляет Y, потому что чтение и обновление Данные основаны на Поведении кеша является единицей, что означает, что когда эти две вещи происходят одновременно, возникает конкуренция, в результате чего ядрам 1 и 2 может потребоваться обновить свои собственные данные (строка кеша обновляется другой стороной). ), что приводит к снижению производительности системы. Это проблема ложного обмена.
Как это улучшить? Как показано ниже:
На приведенном выше рисунке мы занимаем строку кэша только для X и строку кэша только для Y, так что каждое обновление и чтение не будут иметь никакого эффекта.
@sun.misc.Contended("tlr") в приведенном выше коде поможет нам сгенерировать некоторые отступы до и после переменной на уровне виртуальной машины, чтобы отмеченная переменная располагалась в той же строке кеша и не конфликтовала с другие переменные.
В объекте Thread переменные-члены threadLocalRandomSeed, threadLocalRandomProbe и threadLocalRandomSecondarySeed помечены как одна и та же группа tlr, поэтому эти три переменные помещаются в отдельную строку кэша, не конфликтуя с другими переменными, тем самым повышая скорость доступа в параллельной среде. .
Эффективная альтернатива отражению
Генерация случайных чисел требует доступа к таким членам, как threadLocalRandomSeed of Thread, но, учитывая инкапсуляцию класса, эти члены видны в пакете.
К сожалению, ThreadLocalRandom находится в пакете java.util.concurrent, а Thread — в пакете java.lang, поэтому ThreadLocalRandom не имеет доступа к threadLocalRandomSeed и другим переменным Thread.
В это время ветераны Явы могут выскочить и сказать: что это такое, посмотри на мое отражение Дафа, неважно, что ты можешь вытащить и посетить.
Это правда, что отражение — это метод, который может обойти инкапсуляцию и получить прямой доступ к внутренним данным объектов, однако производительность отражения не очень высока и не подходит в качестве высокопроизводительного решения.
Есть ли способ позволить ThreadLocalRandom получить доступ к внутренним членам Thread и в то же время иметь метод, выходящий далеко за рамки отражения и бесконечно близкий к прямому доступу к переменной? Ответ положительный, то есть использовать класс Unsafe.
Здесь я кратко представлю два используемых метода Unsafe:
public native long getLong(Object o, long offset);
public native void putLong(Object o, long offset, long x);
Метод getLong() будет считывать длинные данные по смещению байта объекта o; putLong() запишет x по смещению байта смещения объекта o.
Такой метод работы, аналогичный C, обеспечивает значительное повышение производительности.Что еще более важно, поскольку он избегает имен полей и использует смещения напрямую, вы можете легко обойти ограничения видимости членов.
Проблема с производительностью решена, следующая проблема заключается в том, как узнать позицию смещения члена threadLocalRandomSeed в потоке, что требует использования небезопасного метода objectFieldOffset(), см. следующий код:
Приведенный выше статический код при инициализации класса ThreadLocalRandom получает позиции переменных-членов Thread threadLocalRandomSeed, threadLocalRandomProbe и threadLocalRandomSecondarySeed в смещении объекта.
Поэтому всякий раз, когда ThreadLocalRandom необходимо использовать эти переменные, к ним можно получить доступ через небезопасные методы getLong() и putLong() (и, возможно, getInt() и putInt()).
Например, при генерации случайного числа:
protected int next(int bits) {
return (int)(mix64(nextSeed()) >>> (64 - bits));
}
final long nextSeed() {
Thread t; long r; // read and update per-thread seed
//在ThreadLocalRandom中，访问了Thread的threadLocalRandomSeed变量
UNSAFE.putLong(t = Thread.currentThread(), SEED,
r = UNSAFE.getLong(t, SEED) + GAMMA);
return r;
}
Как быстро этот небезопасный метод может упасть на землю, давайте посмотрим на это в качестве эксперимента:
Здесь мы сами пишем класс ThreadTest, используя методы отражения и небезопасные методы для постоянного чтения и записи переменных-членов threadLocalRandomSeed и сравнения их различий в производительности.Код выглядит следующим образом:
В приведенном выше коде метод отражения byReflection() и метод Unsafe byUnsafe() используются для чтения и записи переменной threadLocalRandomSeed 100 миллионов раз соответственно.Полученные результаты тестирования следующие:
byUnsafe spend :171ms
byReflection spend :645ms
Нетрудно заметить, что метод использования Unsafe намного превосходит метод отражения, что является одной из причин, по которой Unsafe широко используется в JDK для замены отражения.
начальное число случайных чисел
Мы знаем, что для генерации псевдослучайных чисел требуется начальное число, а начальными являются threadLocalRandomSeed и threadLocalRandomSecondarySeed. где threadLocalRandomSeed — это long, а threadLocalRandomSecondarySeed — это int.
threadLocalRandomSeed является наиболее широко используемым, и большое количество случайных чисел на самом деле основано на threadLocalRandomSeed. А threadLocalRandomSecondarySeed используется только в некоторых конкретных внутренних реализациях JDK и широко не используется.
Начальное семя по умолчанию использует системное время:
Приведенный выше код завершает инициализацию начального числа и сохраняет инициализированное начальное число в местоположении SEED (т. е. threadLocalRandomSeed) через UNSAFE.
Затем вы можете использовать метод nextInt() для получения случайного целого числа:
public int nextInt() {
return mix32(nextSeed());
}
final long nextSeed() {
Thread t; long r; // read and update per-thread seed
UNSAFE.putLong(t = Thread.currentThread(), SEED,
r = UNSAFE.getLong(t, SEED) + GAMMA);
return r;
}
Каждый вызов nextInt() обновляет threadLocalRandomSeed с помощью nextSeed(). Так как это переменная, уникальная для потока, то конкуренции вообще не будет, повторных попыток CAS не будет, а производительность значительно улучшится.
Роль зонда Зонд
В дополнение к начальному значению есть еще тестовая переменная threadLocalRandomProbe, для чего эта переменная используется?
Мы можем понимать threadLocalRandomProbe как значение хэша (не 0) для каждого потока, которое можно использовать в качестве характеристического значения потока, и на основе этого значения можно найти для потока конкретную позицию в массиве.
static final int getProbe() {
return UNSAFE.getInt(Thread.currentThread(), PROBE);
}
Взгляните на фрагмент кода:
CounterCell[] as; long b, s;
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
boolean uncontended = true;
if (as == null || (m = as.length - 1) < 0 ||
// 使用probe，为每个线程找到一个在数组as中的位置
// 由于每个线程的probe值不一样，因此大概率 每个线程对应的数组中的元素也是不一样的
// 每个线程对应了不同的元素，就可以没有冲突的进行完全的并发操作
// 因此探针probe在这里 就起到了防止冲突的作用
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
В конкретной реализации, если приведенный выше код конфликтует, вы также можете использоватьThreadLocalRandom.advanceProbe()метод для изменения контрольного значения потока, что может дополнительно избежать возможных конфликтов в будущем, тем самым снижая конкуренцию и улучшая производительность параллелизма.
static final int advanceProbe(int probe) {
//根据当前探针值，计算一个更新的探针值
probe ^= probe << 13; // xorshift
probe ^= probe >>> 17;
probe ^= probe << 5;
//更新探针值到线程对象中 即修改了threadLocalRandomProbe变量
UNSAFE.putInt(Thread.currentThread(), PROBE, probe);
return probe;
}
Суммировать
Сегодня мы представили объект ThreadLocalRandom, высокопроизводительный генератор случайных чисел в среде с высокой степенью параллелизма.
Мы не только представили функцию и внутренний принцип реализации ThreadLocalRandom, но также рассказали, как объект ThreadLocalRandom достигает высокой производительности (например, за счет псевдосовместного использования, Unsafe и т. д.) Мы надеемся, что вы сможете гибко применять эти технологии в своих собственных проектах.
Есть ли у маленьких дураков более глубокое понимание этой непопулярной категории? Если понял, можешь поднять волну в комментариях: стань сильнее
Я Ао Бин, чем больше ты знаешь, тем больше ты не знаешь, увидимся в следующий раз.
Статья постоянно обновляется, вы можете искать в WeChat "Третий принц Ао Бин"Прочтите это в первый раз, ответьте [материал] Подготовленные мной материалы интервью и шаблоны резюме крупных заводов первой линии, эта статьяGitHub github.com/JavaFamilyОн был включен, и есть полные тестовые сайты для интервью с крупными заводами.Добро пожаловать в Star.