Memory shift или самый быстрый способ перемещения блока памяти

@-THE_MASTER666- · 30.10.2014, 18:45. **Показов** 7188. **Ответов** 50

Студворк — интернет-сервис помощи студентам

C++
1
2
3
4
5
6
7
int* dataField = new int[100]{0};
for (int i = 0; i < 50; i++)
    dataField[i] = 777;
 
    //тут должен быть memory shift
 
delete dataField;

В общем допустим есть массив под инты размером в 100. В первых 50-и содержаться какие - то полезные данные, какой существует самый быстрый способ перемещения этих данных в уже выделенной памяти из первых 50-и ячеек в последние? То есть сдвинуть надо вправо. Ну то есть чтоб значения, которые записаны в первых 50-и элементах массива, перенеслись бы в последние 50.

Речь идёт о памяти DDR SDRAM.
1. Может есть специальные процессорные команды процессоров последних поколений для такого перемещения памяти? 2. Может есть специальный тип памяти, не который позволяет делать memory shift?
3. Может есть специальный тип процессора для этих целей?

P.S. ассемблерный код приветствуется.

Evg · 30.10.2014, 23:19

Сообщение от -THE_MASTER666-

1. В SDRAM в плане скорости чтения / записи есть разница между чтением блоков одинаково размера из случайных позиций в адресном пространстве памяти или же из последовательной цепочки?

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

Сообщение от -THE_MASTER666-

Писал долго...потом понял, что всё равно объяснять ещё дольше и стёр весь текст

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

Но для копирования блоков памяти никаких велосипедов изобретать не надо - используй memcpy/memmove (в зависимости от того, перекрываются блоки, или нет), либо просто присваивай один экземпляр структуры в другой, а умный компилятор сам родит хороший код

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

@-THE_MASTER666- · 30.10.2014, 23:23 **[ТС]**

Сообщение от Evg

Т.е. если на твоей левой картинке вся нефрагментированная область влезает в диапазон 4 килобайт, то нет никакой разницы, фрагментирована она, или нет

Чисто для ориентира, каждая ячейка памяти размером в ~ 1 Kb, таких ячеек очень много...около 10..15-и миллионов. Ну как ты понимаешь, планок памяти много

Вот в таком случае есть резон дефрагментировать память и выстраивать всё в один паровозик или с такой же скоростью можно читать рандом аксесом?

ValeryS · 30.10.2014, 23:35

Сообщение от -THE_MASTER666-

Вот в таком случае есть резон дефрагментировать память и выстраивать всё в один паровозик

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

Evg · 30.10.2014, 23:42

Зависит от того, в каком порядке ты потом эту память будешь читать. В реальности вся память с точки зрения исполняемой задачи - виртуальная и разбита на страницы. Как эти страницы отобразятся на физическую память - зависит от операционной системы, т.е. ты этим никак не управляешь. Как страницы памяти разлягутся по страницам внутри планок (тут две разных сущности, которые я назвал "страница", потому что не знаю точно, как она называется на аппаратном уровне) - это процесс, который не полностью контролируется операционной системой, т.к. при двух установленных планках памяти порядок будет один, при четырёх - другой.

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

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

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

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

@-THE_MASTER666- · 31.10.2014, 09:04 **[ТС]**

Сообщение от Evg

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

А можно под какой - то операционной системой на процессорах x64 сделать так, чтоб я мог явно указывать, по какому адресу в памяти мне нужно хранить ту или иную информацию? Ну понятно, что нужен будет свой менеджер памяти всё такое, но всё же, есть такая возможность? Может под DOS? Может под своей ОС ?

@MickeyBlueEyes · 31.10.2014, 10:14

Сообщение от -THE_MASTER666-

Может под DOS? Может под своей ОС ?

Такое впечатления что прямо какая-то литература сюда пересказывается + фантазия.

@-THE_MASTER666- · 31.10.2014, 10:37 **[ТС]**

Сообщение от MickeyBlueEyes

Такое впечатления что прямо какая-то литература сюда пересказывается + фантазия.

Всё, по этому вопросу я понял, что никаких шифтоф нет, ну и ладно, это не смертельно

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

Не по теме:

MickeyBlueEyes, зацени на ютюбе мелодию Darkman007 - Pill of sorrow ;)

Так, в продолжение развития тематики. Если я отказываюсь от всяких дефрагментаций и надеюсь на менеджер памяти и прочие механизмы, тогда становится очень заманчивой идея не алоцировать память под огромное поле данных, в котором будут размещаться мои маленькие блочки, а выделять память под каждый блочок отдельно, то есть у меня 10 миллионов блочков, вот на каждый блочок будет указатель, то есть будет 10 миллилонов указателей. Плюс в чём - мне не надо парится, в какой области памяти будет выделена память под новый блочок, он может вставится и между уже существующих и тд, минусы:
1. Как известно, выделение памяти, ну взять тот же new, происходит достаточно медленно.
2. Надо хранить указатели на все элементы, то есть это неплохой оверхед по памяти.

Если с п.2 ещё можно смириться, то по п.1, вот подскажите, если у меня милилоны элементов, и на каждой итерации цикла например у меня сотни тысяч удаляются и такие же сотни появляются, речь идёт о блоках (размер каждого блока возьмём для примера 1 Кб), то это ж будет очень медленно, если на каждой итерации цикла new expression-ном выделять память под сотни тысяч новых объектов? Верно?

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

Evg · 31.10.2014, 10:54

Сообщение от -THE_MASTER666-

1. Как известно, выделение памяти, ну взять тот же new, происходит достаточно медленно

Это никак не связано с аппаратными особенностями работы памяти. Это всего лишь медленная программная реализация.

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

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

Сообщение от -THE_MASTER666-

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

Опять тот же вопрос: зачем? Если двигать ради того, чтобы двигать (i like to move it move it), то смысла нет. Если двигать ради того, чтобы работало быстрее - то идея весьма сомнительная, потому что для этого надо понимать, как работает вся система памяти + операционная система. Единственное, ради чего имело бы место делать - сократить расход памяти за счёт уплотнения. Но такие операции всё равно будут делаться сравнительно редко, а потому нет смысла заморачиваться и выполнять их с максимально возможной скоростью

@-THE_MASTER666- · 31.10.2014, 11:08 **[ТС]**

Сообщение от Evg

(i like to move it move it

Всё, понял, идея с shift-ом - полный бред, отказываюсь от неё

Сообщение от Evg

В таких случаях пишут свой менеджер памяти.

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

некоторые его куски как алоцированые куски памяти под мои нужды, а другие - как свободные, потом какие - то куски освобождать, а какие - то опять метить как алоцированые, то я так полагаю, по скорости работы это наверное не будет быстрее, чем просто без огромного куска так же отдельно с каждым куском памяти работать посредствам new, ведь это будет дублёр уже существующего менеджера памяти, да?

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

P.S.: замерил тут скорость удаления, она в разы медленней скорости алокации

C++
1
2
3
4
5
6
7
8
const size_t size = 1000000;
int** pointer = new int*[size];
 
for (size_t i = 0; i < size; i++)
    pointer[i] = new int{777};
 
for (size_t i = 0; i < size; i++)
    delete pointer[i];

Evg · 31.10.2014, 11:20

Сообщение от -THE_MASTER666-

Вот для того, чтоб мне в своём кусе памяти пометить некоторые его куски как алоцированые куски памяти под мои нужды, а другие - как свободные, потом какие - то куски освобождать, а какие - то опять метить как алоцированые, то я так полагаю, по скорости работы это наверное не будет быстрее, чем просто без огромного куска так же отдельно с каждым куском памяти работать посредствам new, ведь это будет дублёр уже существующего менеджера памяти, да?

Это будет быстрее, чем new/malloc, т.к. внутри себя new/malloc занимаются ровно тем же самым. Твоё преимущество перед new/malloc в том, что ты знаешь, что все блоки у тебя будут одинакового размера, а потому на хранение информации о свободности/занятости блока достаточно одного бита. Т.е. твой менеджер памяти выделает кусок памяти размером 1 мегабайт, что соответствует (для ровного счёта) 1024 блокам памяти по 1024 байта. Значит в нагрузку к 1 мегабайту требуется ещё маленький шматок памяти размером в 1024 бита (128 байт)

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

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

@-THE_MASTER666- · 31.10.2014, 11:32 **[ТС]**

Evg, спасибо за советы! Всё, тема закрыта. Сделаю для старта упрощённый вариант / симулятор, а там уже и буду смотреть по ситуации. В самом деле, а может весь этот бред и выкину потом, как появятся в массовых продажах девайсы на мемристорах и всё это мне разко перестанет быть нужным

Новые блоги и статьи Все статьи Все блоги /
Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .	Часы с будильником на основе класса QLCDNumber Uhbif79 12.08.2026 Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .	Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия	Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо anaschu 10.08.2026 Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .
Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .	Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .

Evg 21284 / 8309 / 637 Регистрация: 30.03.2009 Сообщений: 22,670 Записей в блоге: 30
	30.10.2014, 23:42
	Зависит от того, в каком порядке ты потом эту память будешь читать. В реальности вся память с точки зрения исполняемой задачи - виртуальная и разбита на страницы. Как эти страницы отобразятся на физическую память - зависит от операционной системы, т.е. ты этим никак не управляешь. Как страницы памяти разлягутся по страницам внутри планок (тут две разных сущности, которые я назвал "страница", потому что не знаю точно, как она называется на аппаратном уровне) - это процесс, который не полностью контролируется операционной системой, т.к. при двух установленных планках памяти порядок будет один, при четырёх - другой. Когда ты делаешь последовательный доступ в отфрагментированную память, то происходит чтение данных из одной физической страницы памяти, когда достиг её границы - переключаемся на следующую. Когда память НЕ фрагментирована, то есть вероятность того, что обращения к последовательным программным блокам памяти окажется в различных физических страницах, которые при некотором раскладе могут быть открыты параллельно и за один такт можно прочитать параллельно данные из двух разных физических страниц по двум разным каналам двухканальной памяти. Т.е. при определённом раскладе вполне может оказаться так, что нефрагментированные данные будут читаться быстрее Но в любом случае я не могу себе представить ни одного алгоритма, которому бы нужна была фрагментация подобного уровня. Если программа умеет работать с нефрагментированной памятью (причём в виртуальном пространстве и не более того), то все задержки лезут из алгоритма обхода нефрагментированной памяти, а вовсе не от особенностей работы железа. Т.е. если есть алгоритм, который по какому-то критерию обходит блоки памяти, которые в общем случае лежат где попало, то, честно говоря, нет уверенности, что если блоки будут расположены последовательно в виртуальной памяти, то это дать прирост по скорости, разве что если эти блоки маленькие (в разы меньше, чем размер строки кэша) Прежде, чем пытаться строить такой алгоритм, лучше провести эксперимент: создать данные фрагментированно и нефрагментированно и сравнить время их обработки Сравнивать с фрагментацией диска не совсем корректно, т.к. при фрагментации диска у программы-фрагментатора есть полный контроль над тем, где реально на диске лежит тот или иной блок данных. А при работе с памятью у пользовательского приложения такой свободы нет. Максимум что можно гарантировать - это упорядочивание данных внутри страницы памяти (единицы памяти с точки зрения ОС), который обычно составляет 4 килобайта. А как всё будет лежать в памяти за пределами 4 килобайт - на пользовательском уровне уже никак не контролируется 1

@-THE_MASTER666- Заблокирован
	31.10.2014, 11:32 [ТС]
	Evg, спасибо за советы! Всё, тема закрыта. Сделаю для старта упрощённый вариант / симулятор, а там уже и буду смотреть по ситуации. В самом деле, а может весь этот бред и выкину потом, как появятся в массовых продажах девайсы на мемристорах и всё это мне разко перестанет быть нужным 0