железо должно уметь занулить мегабайт памяти за один такт?

за один такт тебе забьют одно машинное слово. например 8 байт в 64 битной архитектуре, и то если оно выровнено на границу 8 байт.

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

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

Действительно ли данная операция является O(n) под капотом?

Действительно.

Да. Нет. Ширина шины данных 64 бита. Но вообще слишком абстрактный вопрос. Есть видимокарты с hbm2 памятью шириной шины 2048 бит

Действительно ли данная операция является O(n) под капотом? Железо не умеет влепить во всю выделенную память сразу одно значение?

Железо не умеет, а вот дальше уже зависит от аллокатора и механизма выделения памяти.

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

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

Делаешь массив памяти на rs-триггерах и зануляешь за один такт, главное чтоб цепи питания не погорели во время переключения всего массива

на все нужные

А можно за раз адресовать вот так вот все нужные и не трогать ненужные?

там в озу вообще конденсаторы, а не транзисторы. транзисторы это для озу - жырнота.

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

Ну с какой-то гранулярностью думаю можно было бы сделать, если такой задачей озаботиться. Наверное не с точностью до байта, но, к примеру, на каждую степень 256 сделать отдельный проводник. Надо - килобайт занулил, надо - мегабайт, надо - гигабайт. Может и не O(1) получится, а что-то вроде O(logN).

а, кмк, там пара транзистор + конденсатор?

надо просто вытащить планку озу, она вся и занулится. и обратно вставить.

Тред посетила полиция вычислительной сложности алгоритмов.

Сегодня, без вычислительного штрафа. Ваша операция выполнится за O(n).

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

А, в таком случае нет пути

Возможен ли компьютер, для которого не нужны циклы и рекурсии?

Возможен ли компьютер, для которого не нужны циклы и рекурсии?

компьютеру вообще ничего не нужно. он себя лучше чувствует когда обесточен.

он себя лучше чувствует когда

Откуда ты знаешь?

он никогда не утверждал обратного.

Чувствуется, что пятница.

Что-то там про машину Тьюринга вспоминается.

Железо не умеет, а вот дальше уже зависит от аллокатора и механизма выделения памяти.

Заряди же DMA и отдыхай. Только оно память-память делает. Ну можно занулить 256 байт, потом через DMA 256 в 256 байт, потом эти 512 в следующие 512. Скоко там на DDR4, вроде до 3,5ГБ/сек?

Быстрее, чем memset. Видел его M$ реализацию на асме, там да, выравнивается до границы слова и потом movsq или типа того (stosq? забываю асм) цепочечная инструкция со счетчиком в ecx и es:edi.

Действительно ли данная операция является O(n) под капотом? Железо не умеет влепить во всю выделенную память сразу одно значение?

https://git.musl-libc.org/cgit/musl/tree/src/string/x86_64/memset.s?id=v1.2.1

Пока да. Но когда нибудь костромской школьник пролезший в самсунг, доиграется и будет нам «процессор в памяти», а в центральном процессоре специальная ассемблерная инструкция для заполнения от сих до сих одним значением

А с чего ты взял, что твой массив вообще окажется в оперативной памяти? Или что он будет там лежать одним большим куском?

p.s. https://travisdowns.github.io/blog/2020/01/20/zero.html

В железе есть SSE/AVX, может быть еще решение через язык, вот за мгновение создается массив нулей на 40960 ГБ и даже вытаскиваются из него значения

#include <iostream>
#include <ranges>

int main() {
  auto array = std::views::repeat(0) | std::views::take(1024lu * 1024 * 1024 * 1024 * 10);
  std::cout << array[100] << ", " << array[1024lu * 1024 * 1024 * 25] << std::endl;
}

Теория: алгоритмически это O(n).

Практика:

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

2. Выделение памяти может быть отложенным. У тебя есть область на несколько страниц памяти, которая забита нулями, и ты делаешь ее копию, система, в зависимости, от ее настроек, может не выделять новые страницы памяти, а подождать, пока копия начнет отличаться, то оригинала и тогда вот выделить новую страницу (там где есть отличие). В таком случае скорость заполнения нулями тут на первом O(1), потому как почти ничего не делается.

Чатгпт завафлил твой код

В этой строке кода создается бесконечный поток значений "0". std::views::repeat(0) создает бесконечный поток, состоящий только из значений "0". Затем std::views::take(1024lu * 1024 * 1024 * 1024 * 10) берет первые 10 триллионов (10^13) значений из этого потока. Однако, это действие не будет выполняться, так как std::views::repeat(0) создает бесконечный поток, и std::views::take не остановит его.

После этого, код пытается обратиться к элементам массива, используя слишком большие индексы:
...
Но так как массив бесконечный и попытки обратиться к элементам с такими большими индексами бессмысленны и некорректны, это поведение не определено и может привести к ошибке времени выполнения или непредсказуемому результату.
Кроме того, стоит отметить, что в C++ индексация массива начинается с 0, поэтому элемент с индексом 100 имеет номер 101 в этом потоке, и элемент с индексом 1024 * 1024 * 1024 * 25 имеет номер 25 в этом потоке.

Сам себя*, и такие ответы от ChatGPT ты называешь хорошей помощью начинающему?

Китайская_флешка_на_100500Тб.жпг

Докажи, что он ошибся.

Своих мозгов нет @ слушай электронные.

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

4.2, это поведение полностью определено.

, и элемент с индексом 1024 * 1024 * 1024 * 25 имеет номер 25 в этом потоке.

Лол.

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

1. Просто бредятина про бесконечный поток который нужно останавливать, к тому же он не бесконечен, у array есть размер .size() https://en.cppreference.com/w/cpp/ranges/repeat_view

2. https://en.cppreference.com/w/cpp/language/array expr - an integral constant expression (until C++14)a converted constant expression of type std::size_t (since C++14), which evaluates to a value greater than zero

Нет, это ему надо доказывать

Он это не умеет.

оценивать полезен он или нет для начинающего, лучше тому кто уже что то знает, а не начинающему

Даже начинающий может увидеть, что чатгпт часто лажает. Мечты о нейросетях, заменяющих людей, остаются влажными мечтами)

А что вообще должен вывести твой код?

А что вообще должен вывести твой код?

Два нуля, массив то из нулей

g++ -std=c++23 main.cpp; ./a.out

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

По-моему, никакого реального массива из нулей на 40960 ГБ этот код не создаёт)

В железе есть SSE/AVX

Только его нет в плашках памяти

за мгновение создается массив нулей на 40960 ГБ

Будет очень смешно, если оптимизатор выоптимизировал это до вывода двух нулей)

Будет очень смешно, если оптимизатор выоптимизировал это до вывода двух нулей)

Ну это наверняка так и есть)

Хотя по ассемблерному листингу непохоже, что бинарник просто выводит 2 нуля

Это не важно, даже с -O0 все отлично выведется.

Действительно ли данная операция является O(n)

И да и нет. Можно частично ускорить. Если у тебя n == 4,а 4 это отдельные байты то ты можешь сделать из O(n), O(1) обратившись на запись не как к char, а как к uint32_t например и всё остальное по той же аналогии можно по кусками 128 бит обнулять за раз через всякие SIMD или без них.

Ну то что выводится, это я вижу, а вот если например в цикле выводить случайные элементы - оно будет работать?

Да хоть все (но будет долго выводить, много элементов же) https://habr.com/ru/companies/otus/articles/594251/

Так реальная генерация будет при выводе, я так понимаю?

А какой, простите, практический смысл этой задачи? Пытаемся ускорить программу таким образом? Какую? Если вычислять pi на пхп с точностью 170 знаков после запятой (или ряд Фибоначчи), то скорее упираемся вопрос в пхп и алгоритм.

Если реальная тяжелая расчетная задача, типа гидродинамики или магнито-гидродинамики, то там всё определяется численным методом. Инициализировать массив на 4Тб одним махом – будет даже не каплей в море.