Комментарии 34
Судя по ответам на гитхабе, цепочка вызовов на Windows просто быстрее, чем рассмотренное нами выше чтение из
/dev/urandom
на Linux
Не так давно random был переработан, интересно, насколько сильно это отразится на сабже.
А почему TreadStatic дорогой?
Это интересный вопрос, на который я не умею отвечать за пару предложений.
Если очень кратко и не совсем правда - это же не волшебный атрибут, и он как-то должен извлечь из какой-то коллекции нужный инстанс, чтобы предоставить его. А для этого он как-то должен вычислить "ключ" для обращения к этой коллекции, основанный, видимо, на "идентификаторе текущего потока".
В общем, там внутри вполне понятный код, который надо исполнить. И он дорог относительно той работы, что мы бенчмаркали, чтобы стало осмысленно его минимизировать. Я бы порекомендовал ознакомиться с устройством этого атрибута в исходниках на гитхабе, забенчмаркать доступ к TreadStatic полям. Это будет увлекательно!
в теории он должен быть супер дешевым на большинстве платформе где есть спец регистры указывающие на текущий поток, просто пока это не сделано в дотнете - я файлил ишью https://github.com/dotnet/runtime/issues/63619
Выглядит так, будто для ваших нужд вообще достаточно получить одно случайное (или даже не случайное) число, а дальше крутить свой генератор (вихрь Мерсена или ещё что) прямо в юзерспейсе. Хотя вряд ли есть необходимость настолько упираться в оптимизацию...
Мне интересно, насколько криптостоек /dev/urandom, чтобы имело смысл даже в обычной реализации NewGuid() для линукса "крутить Мерсенна" вместо лазанья в системное устройство в целях повышения производительности. Вроде как предсказывать следующий GUID в таких задачах банально незачем.
А ещё, вроде как /dev/urandom довольно медленный источник байт, помнится, когда я попытался сделать dd if=/dev/urandom ..., у меня производительность была около 10 МБ/с всего лишь. Я не удивлюсь, если и в случае ситуации автора они банально уперлись в своем бенчмарке в скорость генерации случайных чисел устройством, вместо того, чтобы нарваться на излишний системный оверхэд. Один гуид 16 байт, получаем около 1.0 мкс ~= 16 МБ/с, немногим быстрее моего значения (и я мог приврать до одного двоичного порядка вверх, т.е. 10-20 МБ/с, помню, что 1х было в скорости).
помнится, когда я попытался сделать dd if=/dev/urandom ..., у меня производительность была около 10 МБ/с всего лишь
с тех пор его достаточно неплохо ускорили, я на своей машине сейчас вижу ≈235 МБ/с на 512-байтных блоках и ≈295 МБ/с на мегабайтных.
Действительно, если поставить себе задачу "максимально эффективно генерировать уникальные идентификаторы в распределённом кластере", то наверняка нужно было бы идти каким-то таким путём, как вы предложили.
Но да, вы снова правы, настолько упираться в оптимизацию генерации эвентов телеметрии нет необходимости. Потому и статья - детективно-развлекательная. Разобраться, что там внутри. Задешево, просто и весело найти решение получше.
Есть ли причины, почему в итоговом примере со Span<byte>() используется unsafe-код, а не перегрузка конструктора, принимающая Span?
Была ещё библиотека от Додо, думаю вам будет интересно посмотреть https://github.com/dodopizza/primitives
public static Uuid NewTimeBased()
{
byte* resultPtr = stackalloc byte[16];
var resultAsGuidPtr = (Guid*) resultPtr;
var guid = Guid.NewGuid();
resultAsGuidPtr[0] = guid;
long currentTicks = DateTime.UtcNow.Ticks - ChristianCalendarGregorianReformTicksDate;
var ticksPtr = (byte*) ¤tTicks;
resultPtr[0] = ticksPtr[3];
resultPtr[1] = ticksPtr[2];
resultPtr[2] = ticksPtr[1];
resultPtr[3] = ticksPtr[0];
resultPtr[4] = ticksPtr[5];
resultPtr[5] = ticksPtr[4];
resultPtr[6] = (byte) ((ticksPtr[7] & ResetVersionMask) | Version1Flag);
resultPtr[7] = ticksPtr[6];
resultPtr[8] = (byte) ((resultPtr[8] & ResetReservedMask) | ReservedFlag);
return new Uuid(resultPtr);
}
p.s. Да и решают авторы статьи и библиотеки разные задачи
Даже не будем выставлять нужные битики, как того требует RFC, кому они нужны
ради экономии нескольких строчек кода? мне не нравится )
Если вам в принципе не нужна безопасность или случайность, а лишь уникальность — то зачем вообще все эти игры с Random?
Держите вариант, которому вообще не требуется обращение к ГСЧ кроме как при инициализации:
static class SequentialGuidGenerator
{
class ThreadState
{
private readonly byte[] buffer;
private ulong next;
public ThreadState(Guid seed)
{
buffer = seed.ToByteArray();
next = BitConverter.ToUInt64(buffer, 8);
}
public Guid NewGuid()
{
var span = buffer.AsSpan();
var r = BitConverter.TryWriteBytes(span[8..], unchecked(next++));
return new Guid(span);
}
}
static readonly ThreadLocal<ThreadState> state = new(() => new(Guid.NewGuid()));
public static Guid NewGuid() => state.Value.NewGuid();
}
Если я всё сделал правильно, то мой вариант оказался чуть-чуть эффективнее ;)
| Method | Mean | Allocated |
|-------------------------------- |---------:|----------:|
| GenerateNotCryptoQualityGuid | 17.84 ns | - |
| SequentialGuidGenerator.NewGuid | 21.36 ns | - |
Но и ваш вариант очень хорош и действительно не обращается к (P)RNG.
Кажется так веоятность коллизии существенно повышается если запускать этот код на разных машинах. Правда точных вычислений я не производил, было бы любопытно посмотреть на выкладки по шансу коллизий на, скажем, 100 машинах генерирующих гуид по такой схеме.
Допустим, у нас N инстансов генерируют серии по M гуидов.
Тогда для генератора независимых гуидов среднее число коллизий будет примерно (NM)2 2-128 (потому что вероятность коллизии пары гуидов 2-128, а пар (NM)2). И так как несколько коллизий ещё невероятнее чем одна — это число и будет вероятностью коллизии при малых N и M.
Для генератора последовательных гуидов среднее число коллизий определяется по той же самой формуле, но вероятности коллизии она уже не соответствует, поскольку коллизия в таком генераторе никогда не приходит одна. Вместо этого можно подсчитать среднее число пересёкшихся серий, и это будет 2N2M 2-128 (вероятность коллизии пары серий — 2M 2-128, а пар N2). Поскольку пересечение сразу трёх серий невероятнее пересечения двух — это и будет вероятностью коллизии.
Как видно, генератор последовательных гуидов на самом деле даёт коллизии реже, а вовсе не чаще. Что "компенсируется" куда большими проблемами если коллизия всё-таки случилась.
А можно пожалуйста для тупых пояснить?
Есть строчка кода:
return random ?? (random = new Random(Guid.NewGuid().GetHashCode()));
Тут вызывается Guid.NewGuid()
и берется от него HashCode
. Вопрос: почему в этом случае нет тормозов, ведь мы вызываем все тот же метод, из-за которого и начался весь сыр-бор?
Потому, что new Random(Guid.NewGuid().GetHashCode())
на самом деле исполнится всего один раз, в момент первого обращения. В дальнейшем оператор ??
будет возвращать сконструированный инстанс random
. Детали оператора ??
лучше посмотреть в документации.
https://man7.org/linux/man-pages/man2/getrandom.2.html же. И не надо лохматить бабушку. А если у вас старинный центос в котором нет данного сисколла - то ссзб.
return random ?? (random = new Random(Guid.NewGuid().GetHashCode()));
плохо соотносится с мыслью
Нам просто хочется, чтобы гуиды редко совпадали.
Сид в этом случае составляет 4 байта, и порядка 100k попыток создать генератор хватит, чтобы скорее всего хотя бы у двух генераторов совпали сиды. После этого они начнут генерировать одинаковые последовательности случайных байтов и одинаковые последовательности гуидов.
И если в одном процессе иметь 100k тредов может быть достаточно странно, то размазать их по сотням-тысячам процессов выглядит не очень сложной задачей.
Всё так, "парадокс дней рождений" :)
К счастью, .NET 6 становится всё более распространённым (у нас), где используется Random.Shared. А в нём сид уже достаточно большой.
Забавно, что Random.Shared имеет под капотам ThreadStatic-поле, то бишь нифига он не шарится между потоками.
https://man7.org/linux/man-pages/man2/getrandom.2.html же. И не надо лохматить бабушку. А если у вас старинный центос в котором нет данного сисколла - то ссзб.
Еще можно один раз сгенерировать Гуид, а потом его просто инкрементить.
я для таких задач использую псевдо-guid, потому что туда можно ещё полезную информацию засунуть, например дату время + какое-то случайное число чтобы исключить совпадение если вдруг в одно и то же время произойдёт событие, плюс какие-то IDшники можно туда засунуть, тогда и уникальный будет и в то же время не просто балласт, а там будут какие-то данные, да и сортировать удобно - получается как постоянно увеличивающийся ключ
Гляньте на Time-based UUID (RFC 4122) — подходит под ваше описание. А благодаря специальным маркерным битам, отвечающим за версию UUID, можно "дружить" с другими системами, использующими, к примеру, UUID v4, и не бояться коллизий.
Сказка про Guid.NewGuid()