Как стать автором
Поиск
Написать публикацию
Обновить

Комментарии 34

Судя по ответам на гитхабе, цепочка вызовов на Windows просто быстрее, чем рассмотренное нами выше чтение из /dev/urandom на Linux

Не так давно random был переработан, интересно, насколько сильно это отразится на сабже.

Всего голосов 1: ↑1 и ↓0+1

А почему TreadStatic дорогой?

Всего голосов 1: ↑1 и ↓0+1

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

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

В общем, там внутри вполне понятный код, который надо исполнить. И он дорог относительно той работы, что мы бенчмаркали, чтобы стало осмысленно его минимизировать. Я бы порекомендовал ознакомиться с устройством этого атрибута в исходниках на гитхабе, забенчмаркать доступ к TreadStatic полям. Это будет увлекательно!

Всего голосов 7: ↑7 и ↓0+7

Ага, 'приключение на 20 минут' :)

Всего голосов 1: ↑1 и ↓0+1

в теории он должен быть супер дешевым на большинстве платформе где есть спец регистры указывающие на текущий поток, просто пока это не сделано в дотнете - я файлил ишью https://github.com/dotnet/runtime/issues/63619

Всего голосов 7: ↑7 и ↓0+7

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

Всего голосов 4: ↑3 и ↓1+2

Мне интересно, насколько криптостоек /dev/urandom, чтобы имело смысл даже в обычной реализации NewGuid() для линукса "крутить Мерсенна" вместо лазанья в системное устройство в целях повышения производительности. Вроде как предсказывать следующий GUID в таких задачах банально незачем.
А ещё, вроде как /dev/urandom довольно медленный источник байт, помнится, когда я попытался сделать dd if=/dev/urandom ..., у меня производительность была около 10 МБ/с всего лишь. Я не удивлюсь, если и в случае ситуации автора они банально уперлись в своем бенчмарке в скорость генерации случайных чисел устройством, вместо того, чтобы нарваться на излишний системный оверхэд. Один гуид 16 байт, получаем около 1.0 мкс ~= 16 МБ/с, немногим быстрее моего значения (и я мог приврать до одного двоичного порядка вверх, т.е. 10-20 МБ/с, помню, что 1х было в скорости).

Комментарий пока не оценивали0
помнится, когда я попытался сделать dd if=/dev/urandom ..., у меня производительность была около 10 МБ/с всего лишь

с тех пор его достаточно неплохо ускорили, я на своей машине сейчас вижу ≈235 МБ/с на 512-байтных блоках и ≈295 МБ/с на мегабайтных.

Комментарий пока не оценивали0

Любопытно, у меня разница гораздо ощутимее получилась. 187 MB/s на bs=512 count=1048576 и 451 MB/s на bs=1048576 count=512 (i7-8750H CPU @ 2.20GHz)

Комментарий пока не оценивали0

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

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

Всего голосов 1: ↑1 и ↓0+1

Есть ли причины, почему в итоговом примере со Span<byte>() используется unsafe-код, а не перегрузка конструктора, принимающая Span?

Всего голосов 2: ↑2 и ↓0+2

Никаких причин нет. Такой (действительно, менее красивый) код остался от старого варианта, когда такого конструктора ещё не существовало.

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

Всего голосов 3: ↑3 и ↓0+3

Была ещё библиотека от Додо, думаю вам будет интересно посмотреть https://github.com/dodopizza/primitives

Комментарий пока не оценивали0
Библиотечка очень интересная, но внутри генератора всё вызывается Guid.NewGuid() от которого они хотели избавиться, так что она не подойдёт.
Spoiler header 
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*) &currentTicks;
            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. Да и решают авторы статьи и библиотеки разные задачи
Комментарий пока не оценивали0
Даже не будем выставлять нужные битики, как того требует RFC, кому они нужны

ради экономии нескольких строчек кода? мне не нравится )

Комментарий пока не оценивали0

Если вам в принципе не нужна безопасность или случайность, а лишь уникальность — то зачем вообще все эти игры с 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();
    }
Всего голосов 3: ↑3 и ↓0+3

Если я всё сделал правильно, то мой вариант оказался чуть-чуть эффективнее ;)

|                          Method |     Mean | Allocated |
|-------------------------------- |---------:|----------:|
|    GenerateNotCryptoQualityGuid | 17.84 ns |         - |
| SequentialGuidGenerator.NewGuid | 21.36 ns |         - |

Но и ваш вариант очень хорош и действительно не обращается к (P)RNG.

Комментарий пока не оценивали0

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

Комментарий пока не оценивали0

Допустим, у нас N инстансов генерируют серии по M гуидов.


Тогда для генератора независимых гуидов среднее число коллизий будет примерно (NM)2 2-128 (потому что вероятность коллизии пары гуидов 2-128, а пар (NM)2). И так как несколько коллизий ещё невероятнее чем одна — это число и будет вероятностью коллизии при малых N и M.


Для генератора последовательных гуидов среднее число коллизий определяется по той же самой формуле, но вероятности коллизии она уже не соответствует, поскольку коллизия в таком генераторе никогда не приходит одна. Вместо этого можно подсчитать среднее число пересёкшихся серий, и это будет 2N2M 2-128 (вероятность коллизии пары серий — 2M 2-128, а пар N2). Поскольку пересечение сразу трёх серий невероятнее пересечения двух — это и будет вероятностью коллизии.


Как видно, генератор последовательных гуидов на самом деле даёт коллизии реже, а вовсе не чаще. Что "компенсируется" куда большими проблемами если коллизия всё-таки случилась.

Комментарий пока не оценивали0

А можно пожалуйста для тупых пояснить?
Есть строчка кода:

 return random ?? (random = new Random(Guid.NewGuid().GetHashCode()));

Тут вызывается Guid.NewGuid() и берется от него HashCode. Вопрос: почему в этом случае нет тормозов, ведь мы вызываем все тот же метод, из-за которого и начался весь сыр-бор?

Комментарий пока не оценивали0

Потому, что new Random(Guid.NewGuid().GetHashCode()) на самом деле исполнится всего один раз, в момент первого обращения. В дальнейшем оператор ?? будет возвращать сконструированный инстанс random. Детали оператора ?? лучше посмотреть в документации.

Комментарий пока не оценивали0

что-то тупанул, спасибо)

Комментарий пока не оценивали0
Random ObtainRandom() => random ??= new Random(Guid.NewGuid().GetHashCode());

Можно вот так сделать...

Комментарий пока не оценивали0

https://man7.org/linux/man-pages/man2/getrandom.2.html же. И не надо лохматить бабушку. А если у вас старинный центос в котором нет данного сисколла - то ссзб.

Всего голосов 2: ↑1 и ↓10

У вас маниакальность какая-то, если вам нравится каждый день переходить на новый продукт, то вперед, не стоит всем навязываться, тем более без бюджетов для этого.

Комментарий пока не оценивали0
Мне кажется, или инициализация рандома
return random ?? (random = new Random(Guid.NewGuid().GetHashCode()));

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

Сид в этом случае составляет 4 байта, и порядка 100k попыток создать генератор хватит, чтобы скорее всего хотя бы у двух генераторов совпали сиды. После этого они начнут генерировать одинаковые последовательности случайных байтов и одинаковые последовательности гуидов.

И если в одном процессе иметь 100k тредов может быть достаточно странно, то размазать их по сотням-тысячам процессов выглядит не очень сложной задачей.
Всего голосов 4: ↑4 и ↓0+4

Всё так, "парадокс дней рождений" :)

К счастью, .NET 6 становится всё более распространённым (у нас), где используется Random.Shared. А в нём сид уже достаточно большой.

Комментарий пока не оценивали0
Может стоит выдать тем, кто ещё не на .net 6, и не может на него быстро перейти, какой-то другой рандом? Кажется, что такая схема генерации traceId может попортить много крови при попытке разбора конкретных ситуаций. Или сделать телеметрию практически бесполезной.
Всего голосов 1: ↑1 и ↓0+1

Забавно, что Random.Shared имеет под капотам ThreadStatic-поле, то бишь нифига он не шарится между потоками.

Всего голосов 1: ↑1 и ↓0+1

https://man7.org/linux/man-pages/man2/getrandom.2.html же. И не надо лохматить бабушку. А если у вас старинный центос в котором нет данного сисколла - то ссзб.

Всего голосов 2: ↑1 и ↓10

Еще можно один раз сгенерировать Гуид, а потом его просто инкрементить.

Комментарий пока не оценивали0

я для таких задач использую псевдо-guid, потому что туда можно ещё полезную информацию засунуть, например дату время + какое-то случайное число чтобы исключить совпадение если вдруг в одно и то же время произойдёт событие, плюс какие-то IDшники можно туда засунуть, тогда и уникальный будет и в то же время не просто балласт, а там будут какие-то данные, да и сортировать удобно - получается как постоянно увеличивающийся ключ

Комментарий пока не оценивали0

Гляньте на Time-based UUID (RFC 4122) — подходит под ваше описание. А благодаря специальным маркерным битам, отвечающим за версию UUID, можно "дружить" с другими системами, использующими, к примеру, UUID v4, и не бояться коллизий.

Комментарий пока не оценивали0

спасибо что подсказали! попробую

Комментарий пока не оценивали0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2024, Habr