LINUX.ORG.RU
Форум — Development  

Инициализация массива

 ,


0

1

Надо создать и занулить (либо заполнить одним и тем же значением) массив произвольной длины.

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

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

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

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

alysnix ★★★
()
Последнее исправление: alysnix (всего исправлений: 1)

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

cobold ★★★★★
()

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

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

lovesan ★★
()
Ответ на: комментарий от vvn_black

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

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

vbr ★★★
()
Ответ на: комментарий от vvn_black

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

vbr ★★★
()

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

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

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

cocucka_B_TECTE
()
Ответ на: комментарий от lovesan

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

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

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

bugs-bunny ★
()

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

DumLemming ★★
()

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

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

hateyoufeel ★★★★★
()
Последнее исправление: hateyoufeel (всего исправлений: 2)

В железе есть 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;
}
MOPKOBKA ★★★
()

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

Практика:

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

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

soomrack ★★★★
()
Ответ на: комментарий от MOPKOBKA

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

В этой строке кода создается бесконечный поток значений "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 в этом потоке.
alex1101 ☆
()
Ответ на: комментарий от alex1101

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

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

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

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

Лол.

cudeta
()
Ответ на: комментарий от alex1101

Нет, это ему надо доказывать. Продолжу свою мысль по твоему комментарию о пользе 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

MOPKOBKA ★★★
()
Последнее исправление: MOPKOBKA (всего исправлений: 2)
Ответ на: комментарий от MOPKOBKA

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

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

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

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

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

alex1101 ☆
()
Ответ на: комментарий от MOPKOBKA

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

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

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

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

goingUp ★★★★★
()

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

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

LINUX-ORG-RU ★★★★★
()

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

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

sshestov ★
()
Development