Является ли неинициализированная локальная переменная самым быстрым генератором случайных чисел?

Я знаю, что неинициализированная локальная переменная - это неопределенное поведение ( UB ), а также у значения могут быть представления ловушек, которые могут повлиять на дальнейшие операции, но иногда я хочу использовать случайное число только для визуального представления и больше не буду использовать их в другой части Программа, например, установить что-то со случайным цветом в визуальном эффекте, например:

void updateEffect(){
    for(int i=0;i<1000;i++){
        int r;
        int g;
        int b;
        star[i].setColor(r%255,g%255,b%255);
        bool isVisible;
        star[i].setVisible(isVisible);
    }
}

это быстрее, чем

void updateEffect(){
    for(int i=0;i<1000;i++){
        star[i].setColor(rand()%255,rand()%255,rand()%255);
        star[i].setVisible(rand()%2==0?true:false);
    }
}

а также быстрее, чем другой генератор случайных чисел?

Как уже отмечали другие, это неопределенное поведение (UB).

На практике это будет (вероятно) фактически (отчасти) работать. Чтение из неинициализированного регистра в архитектурах x86 [-64] действительно приведет к ошибочным результатам и, вероятно, не принесет ничего плохого (в отличие, например, от Itanium, где регистры могут быть помечены как недопустимые , что приводит к распространению ошибок, таких как NaN).

Есть две основные проблемы:

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

2. Это плохая практика (заглавная 'B') - позволять подобным вещам проникать в ваш код. Технически компилятор может вставлять reformat_hdd();каждый раз, когда вы читаете неопределенную переменную. Это не будет , но вы все равно не должны этого делать. Не делай небезопасных вещей. Чем меньше исключений вы делаете, тем безопаснее вы от случайных ошибок все время.

Более насущная проблема с UB заключается в том, что он делает поведение всей вашей программы неопределенным. Современные компиляторы могут использовать это, чтобы исключить огромные участки вашего кода или даже вернуться в прошлое . Игра с UB похожа на викторианского инженера, демонтирующего живой ядерный реактор. Есть миллионы вещей, которые могут пойти не так, и вы, вероятно, не будете знать половину базовых принципов или внедренных технологий. Это может быть хорошо, но вы все равно не должны позволить этому случиться. Посмотрите на другие хорошие ответы для деталей.

Кроме того, я бы уволил тебя.

Позвольте мне сказать это ясно: мы не вызываем неопределенное поведение в наших программах . Это никогда не хорошая идея, точка. Есть редкие исключения из этого правила; например, если вы являетесь разработчиком библиотеки, реализующей offsetof . Если ваше дело подпадает под такое исключение, вы, вероятно, уже знаете это. В этом случае мы знаем, что использование неинициализированных автоматических переменных является неопределенным поведением .

Компиляторы стали очень агрессивными с оптимизацией вокруг неопределенного поведения, и мы можем найти много случаев, когда неопределенное поведение приводило к недостаткам безопасности. Наиболее печально известным случаем, вероятно, является удаление проверки нулевого указателя ядра Linux, о которой я упоминал в своем ответе на ошибку компиляции C ++? где оптимизация компилятора вокруг неопределенного поведения превратила конечный цикл в бесконечный.

Мы можем прочитать « Опасные оптимизации CERT и Потеря причинности» ( видео ), в которых, среди прочего, сказано:

Авторы компиляторов все чаще используют неопределяемое поведение в языках программирования C и C ++ для улучшения оптимизации.

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

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

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

Я не знаю ни одного примера, где это происходит, но на данный момент мы не можем это исключить.

Реальные примеры, а не ожидаемый результат

Вы вряд ли получите случайные значения. Компилятор может оптимизировать весь цикл. Например, в этом упрощенном случае:

void updateEffect(int  arr[20]){
    for(int i=0;i<20;i++){
        int r ;    
        arr[i] = r ;
    }
}

clang оптимизирует его ( смотрите вживую ):

updateEffect(int*):                     # @updateEffect(int*)
    retq

или, возможно, получить все нули, как в этом модифицированном случае:

void updateEffect(int  arr[20]){
    for(int i=0;i<20;i++){
        int r ;    
        arr[i] = r%255 ;
    }
}

увидеть его вживую :

updateEffect(int*):                     # @updateEffect(int*)
    xorps   %xmm0, %xmm0
    movups  %xmm0, 64(%rdi)
    movups  %xmm0, 48(%rdi)
    movups  %xmm0, 32(%rdi)
    movups  %xmm0, 16(%rdi)
    movups  %xmm0, (%rdi)
    retq

Оба эти случая являются совершенно приемлемыми формами неопределенного поведения.

Обратите внимание: если мы находимся на Itanium, мы можем получить значение ловушки :

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

Другие важные заметки

Интересно отметить разницу между gcc и clang, отмеченную в проекте UB Canaries, относительно того, насколько они готовы использовать неопределенное поведение в отношении неинициализированной памяти. В статье отмечается ( выделение мое ):

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

Как отмечает Матье М., то, что должен знать каждый программист на Си о неопределенном поведении № 2/3, также имеет отношение к этому вопросу. Это говорит среди прочего ( выделение мое ):

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

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

Для полноты картины я, вероятно, должен упомянуть, что реализации могут выбрать, чтобы неопределенное поведение было четко определено, например, gcc позволяет пробивать типы через объединения, тогда как в C ++ это выглядит как неопределенное поведение . В этом случае реализация должна документировать это, и это обычно не будет переносимым.

Нет, это ужасно

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

Если вы хотите «быстрый и грязный» генератор случайных чисел, то rand()это ваш лучший выбор. В своей реализации все, что он делает, это умножение, сложение и модуль.

Самый быстрый из известных мне генераторов требует, чтобы вы использовали в uint32_tкачестве типа псевдослучайной переменной Iи использовали

I = 1664525 * I + 1013904223

генерировать последовательные значения. Вы можете выбрать любое начальное значение I(называемое семенем ), которое вам нравится. Очевидно, что вы можете кодировать это в строке. Модуль со стандартным гарантированным циклом без знака действует как модуль. (Числовые константы подобраны этим замечательным научным программистом Дональдом Кнутом.)

Хороший вопрос!

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

1. Всегда одно и то же.
2. Будьте одним из небольшого набора ценностей.
3. Получить значения в одном или нескольких небольших диапазонах.
4. Просмотреть множество значений, делимых на 2/4/8 из указателей в 16/32/64-битной системе
5. ...

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

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

Читайте о случайности . Как вы увидите, случайность очень специфична и ее трудно получить. Распространенная ошибка - думать, что если вы просто возьмете что-то, что трудно отследить (например, ваше предложение), вы получите случайное значение.

Много хороших ответов, но позвольте мне добавить еще один и подчеркнуть, что в детерминированном компьютере нет ничего случайного. Это верно как для чисел, создаваемых псевдо-RNG, так и для «случайных» чисел, обнаруженных в областях памяти, зарезервированных для локальных переменных C / C ++ в стеке.

НО ... есть принципиальная разница.

Числа, сгенерированные хорошим псевдослучайным генератором, обладают свойствами, которые делают их статистически похожими на действительно случайные ничьи. Например, распределение является равномерным. Длина цикла велика: вы можете получить миллионы случайных чисел, прежде чем цикл повторится. Последовательность не имеет автокорреляции: например, вы не увидите, как появляются странные шаблоны, если вы берете каждый 2-й, 3-й или 27-й номер или если вы смотрите на определенные цифры в сгенерированных числах.

Напротив, «случайные» числа, оставленные в стеке, не имеют ни одного из этих свойств. Их значения и их кажущаяся случайность полностью зависят от того, как построена программа, как она компилируется и как она оптимизируется компилятором. В качестве примера, вот вариант вашей идеи как отдельной программы:

#include <stdio.h>

notrandom()
{
        int r, g, b;

        printf("R=%d, G=%d, B=%d", r&255, g&255, b&255);
}

int main(int argc, char *argv[])
{
        int i;
        for (i = 0; i < 10; i++)
        {
                notrandom();
                printf("\n");
        }

        return 0;
}

Когда я компилирую этот код с помощью GCC на компьютере с Linux и запускаю его, он оказывается довольно неприятно детерминированным:

R=0, G=19, B=0
R=130, G=16, B=255
R=130, G=16, B=255
R=130, G=16, B=255
R=130, G=16, B=255
R=130, G=16, B=255
R=130, G=16, B=255
R=130, G=16, B=255
R=130, G=16, B=255
R=130, G=16, B=255

Если вы посмотрите на скомпилированный код с дизассемблером, вы сможете подробно реконструировать происходящее. Первый вызов notrandom () использовал область стека, которая ранее не использовалась этой программой; кто знает что там было Но после этого вызова notrandom (), есть вызов printf () (который компилятор GCC фактически оптимизирует для вызова putchar (), но не говоря уже), который перезаписывает стек. Таким образом, в следующий и последующий раз, когда вызывается notrandom (), стек будет содержать устаревшие данные из выполнения putchar (), и поскольку putchar () всегда вызывается с одинаковыми аргументами, эти устаревшие данные всегда будут одинаковыми, слишком.

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

Действительно, как и другие, я бы также серьезно подумал об увольнении того, кто пытался выдать эту идею за «высокопроизводительный ГСЧ».

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

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

Это также означает, что часто контент будет «странным», но фиксированным или слегка случайным или переменным, но с явным очевидным паттерном (например, увеличение значений на каждой итерации).

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

Неопределенное поведение не определено. Это не значит, что вы получаете неопределенное значение, это означает, что программа может делать все что угодно и при этом соответствовать спецификации языка.

Хороший оптимизирующий компилятор должен занять

void updateEffect(){
    for(int i=0;i<1000;i++){
        int r;
        int g;
        int b;
        star[i].setColor(r%255,g%255,b%255);
        bool isVisible;
        star[i].setVisible(isVisible);
    }
}

и скомпилировать его в noop. Это, безусловно, быстрее, чем любая альтернатива. У него есть недостаток в том, что он ничего не будет делать, но это недостаток неопределенного поведения.

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

void updateEffect(){}

Что, безусловно, быстрее, чем ваш правильный цикл, и из-за UB, совершенно соответствует.

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

Ваш конкретный пример кода, вероятно, не будет делать то, что вы ожидаете. Хотя технически каждая итерация цикла заново создает локальные переменные для значений r, g и b, на практике это то же самое пространство памяти в стеке. Следовательно, он не будет повторно рандомизирован с каждой итерацией, и вы в конечном итоге назначите те же 3 значения для каждого из 1000 цветов, независимо от того, насколько случайными являются r, g и b индивидуально и изначально.

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

Как и большинство людей, здесь упоминается неопределенное поведение. Undefined также означает, что вы можете получить некоторое допустимое целочисленное значение (к счастью), и в этом случае это будет быстрее (так как вызов функции rand не выполняется). Но не используйте его практически. Я уверен, что это приведет к ужасным результатам, так как удача не с вами все время.

Действительно плохо! Плохая привычка, плохой результат. Рассматривать:

A_Function_that_use_a_lot_the_Stack();
updateEffect();

Если функция выполняет A_Function_that_use_a_lot_the_Stack()всегда одну и ту же инициализацию, она покидает стек с одинаковыми данными. Именно эти данные мы и называем updateEffect(): всегда одно и то же значение! ,

Я выполнил очень простой тест, и он не был случайным.

#include <stdio.h>

int main() {

    int a;
    printf("%d\n", a);
    return 0;
}

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

Вам нужно иметь определение того, что вы подразумеваете под «случайным». Разумное определение предполагает, что полученные значения должны иметь небольшую корреляцию. Это то, что вы можете измерить. Это также не тривиально, чтобы достичь контролируемым, воспроизводимым образом. Так что неопределенное поведение, конечно, не то, что вы ищете.

Существуют определенные ситуации, в которых неинициализированная память может быть безопасно прочитана с использованием типа "unsigned char *" [например, буфер, возвращаемый из malloc]. Код может читать такую ​​память, не беспокоясь о том, что компилятор выбрасывает причинно-следственные связи из окна, и бывают ситуации, когда может быть более эффективно подготовить код для чего-либо, что может содержать память, чем для того, чтобы гарантировать, что неинициализированные данные не будут прочитаны ( распространенным примером этого будет использование memcpyчастично инициализированного буфера, а не дискретное копирование всех элементов, которые содержат значимые данные).

Однако даже в таких случаях следует всегда предполагать, что если какая-либо комбинация байтов будет особенно неприятной, чтение ее всегда приведет к такой комбинации байтов (и если определенная схема будет неудобной при производстве, но не при разработке, такая шаблон не появится, пока код не будет в производстве).

Чтение неинициализированной памяти может быть полезно как часть стратегии генерации случайных чисел во встроенной системе, в которой можно быть уверенным, что память никогда не была записана с практически неслучайным контентом с момента последнего включения системы, а также в случае производства Процесс, используемый для памяти, приводит к тому, что его состояние при включении изменяется полуслучайным образом. Код должен работать, даже если все устройства всегда выдают одинаковые данные, но в тех случаях, когда, например, группе узлов, каждый должен выбрать произвольные уникальные идентификаторы как можно быстрее, имея генератор «не очень случайный», который дает половине узлов одинаковые начальные значения. Идентификация может быть лучше, чем отсутствие какого-либо начального источника случайности.

Как уже говорили другие, это будет быстро, но не случайно.

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

В этом случае значение, которое вы получите, будет зависеть от того, что было ранее в стеке - если вы вызываете функцию до этой, которая имеет сто локальных переменных типа char, все установлены в «Q», а затем вызываете свою функцию после что возвращает, то вы, вероятно, обнаружите, что ваши «случайные» значения ведут себя так, как будто вы все memset()их в «Q».

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

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

В общем: плохая идея, не делай этого. (как много "умных" оптимизаций уровня кода действительно ...)

Как уже упоминали другие, это неопределенное поведение ( UB ), но оно может «работать».

Кроме проблем, уже упомянутых другими, я вижу еще одну проблему (недостаток) - она ​​не будет работать ни на одном языке, кроме C и C ++. Я знаю, что этот вопрос касается C ++, но если вы можете написать код, который будет хорошим кодом C ++ и Java, и это не проблема, то почему бы и нет? Возможно, когда-нибудь кому-то придется перенести его на другой язык, и поиск ошибок, вызванных «магическими уловками» UB, вроде этого, безусловно, станет кошмаром (особенно для неопытного разработчика C / C ++).

Здесь возникает вопрос о другом подобном UB. Просто представьте, что вы пытаетесь найти ошибку, не зная об этом UB. Если вы хотите узнать больше о таких странных вещах в C / C ++, прочитайте ответы на вопрос по ссылке и посмотрите это БОЛЬШОЕ слайд-шоу. Это поможет вам понять, что находится под капотом и как оно работает; это не просто очередное слайд-шоу, полное «волшебства». Я совершенно уверен, что даже большинство опытных программистов на C / c ++ могут многому научиться на этом.

Не очень хорошая идея полагаться на нашу логику на неопределенное поведение языка. В дополнение к тому, что упомянуто / обсуждено в этом посте, я хотел бы отметить, что с современным подходом / стилем C ++ такая программа может не компилироваться.

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

https://stackoverflow.com/a/26170069/2724703

Таким образом, если мы изменим приведенный выше код и заменим фактические типы на auto , программа даже не скомпилируется.

void updateEffect(){
    for(int i=0;i<1000;i++){
        auto r;
        auto g;
        auto b;
        star[i].setColor(r%255,g%255,b%255);
        auto isVisible;
        star[i].setVisible(isVisible);
    }
}

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

Это должно дать вам очень тревожное ощущение, что вы используете такую ​​«случайность», как ваша бизнес-логика. Я не буду этого делать.

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

1. это определенное поведение

2. гарантированно не всегда будет 0

3. это главное

4. скорее всего, он будет статистически случайным, как неинтуализованные переменные

5. скорее всего он будет быстрее неинициализированных переменных, так как его значение известно во время компиляции

Есть еще одна возможность рассмотреть.

Современные компиляторы (ahem g ++) настолько умны, что просматривают ваш код, чтобы увидеть, какие инструкции влияют на состояние, а какие нет, и если инструкция гарантированно НЕ повлияет на состояние, g ++ просто удалит эту инструкцию.

Итак, вот что будет. g ++ определенно увидит, что вы читаете, выполняете арифметику, сохраняете то, что по сути является значением мусора, которое производит больше мусора. Поскольку нет никакой гарантии, что новый мусор будет более полезным, чем старый, он просто покончит с вашей петлей. Bloop!

Этот метод полезен, но вот что я хотел бы сделать. Объедините UB (неопределенное поведение) со скоростью rand ().

Конечно, rand()нужно уменьшить число s, но смешать их так, чтобы компилятор не делал ничего, чего бы вы не хотели.

И я не буду тебя увольнять.

Использование неинициализированных данных для случайности не обязательно плохо, если все сделано правильно. Фактически, OpenSSL делает именно это, чтобы заполнить свой PRNG.

Очевидно, это использование не было хорошо документировано, однако, потому что кто-то заметил, что Valgrind жаловался на использование неинициализированных данных и «исправил» их, что привело к ошибке в PRNG .

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