Программа при запуске выделяет большой кусок памяти (512 ГБ) под массив double-ов. Сейчас это делается вот так:

vector <double> vect(N);

Это занимает около 10 минут времени при 100% загрузке одного ядра.

Компилятор — g++ 4.8
OS — CentOS 7

Можно ли как-то ускорить это дело? Распараллелить например. Что там вообще менеджер кучи так долго делает?

Здравствуйте, cures, Вы писали:

C>Проще всего специализировать uninitialized_default_n_a для итератора вектора по даблам в пустой, все вопросы решатся. Зачем он нужен для неинициализированных простых типов?

Проще делать malloc, а ещё лучше-mmap. STL контейнеры были придуманы для приближения C++ к высотам
и требованиям развитых высокоуровневых ЯП типа java/python/lisp и пр, с сохранением возможностей
баловаться на низком C-шном уровне. Как известно, одной и то же жо...ой невозможно усидеть
на двух противоположных поездах. Поэтому в C++ то крест спадает, то трусы сами надеваются.
И программист, пишущий на C++, только и занят тем, что пытается одновременно и крест на шее удержать
и трусы снять. Зрелище не очень так.

Здравствуйте, Mazay, Вы писали:

M> Что там вообще менеджер кучи так долго делает?

А точно менеджер кучи тупит, а не забивание этой памяти дефолтными нулями? Цапните её стандартным маллоком, он ничем не заполняет. Если не поможет — вручную ммапом.
И общий совет при таких размерах: включите HugeTLB хотя бы двухметровое, а можно попробовать и гигабайтное.
Насчёт не свопится — тоже лучше проверить, оно и профилактически может, отключите все своп-разделы.
В любом случае очень подозрительно, даже если заполнение, скорость меньше гига в секунду — это странно.
Вы точно не под валгриндом пускаетесь? Или у Вас винда?

Здравствуйте, Mazay, Вы писали:

M>Программа при запуске выделяет большой кусок памяти (512 ГБ) под массив double-ов. Сейчас это делается вот так:
M>vector <double> vect(N);
M>Это занимает около 10 минут времени при 100% загрузке одного ядра.

Когда делаете так vector <double> vect(N); запускается это

template<typename _ForwardIterator, typename _Size, typename _Allocator>
  void
  __uninitialized_default_n_a(_ForwardIterator __first, _Size __n,
  _Allocator& __alloc)
  {
  _ForwardIterator __cur = __first;
  __try
  {
  typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
  for (; __n > 0; --__n, ++__cur)
  __traits::construct(__alloc, std::__addressof(*__cur));
  }
  __catch(...)
  {
  std::_Destroy(__first, __cur, __alloc);
  __throw_exception_again;
  }
 }

что быстро выполнится при больших N не может.

M>Можно ли как-то ускорить это дело? Распараллелить например. Что там вообще менеджер кучи так долго делает?

Да, делайте просто malloc() без этих stl дурковатостей.

M>Компилятор — g++ 4.8
M>OS — CentOS 7

M>Можно ли как-то ускорить это дело? Распараллелить например. Что там вообще менеджер кучи так долго делает?

Смотря что за железка, если там NUMA (что скорее всего имеет место быть, так как массив памяти очень уж большой), то выделять (и инициализировать) одним большим куском столько памяти — бессмысленно. Каждая NUMA нода должна выделять память, с которой она потом будет работать преимущественно самостоятельно, так как менеджер памяти в ОС — NUMA aware и будет давать потоку память из той же ноды. Можно выделить большой кусок виртуальной памяти через valloc или mmap и потом инициализировать те куски, с которыми ты будешь работать из разных потоков этими же потоками и тогда менеджер памяти, по идее, должен раздать им страницы физической памяти из соответствующих NUMA-нод.

Можно, например, завести битовый массив, каждый бит которого соответствовал бы странице памяти из этих 512-ти ГБ, если поток пытается обратиться к какой-либо странице, то он сначала должен проверить соответствующий бит а затем, если этот бит равен 0 — инициализировать соответствующий участок памяти (+ синхронизация этого всего, вероятно оптимистичная, так как памяти дохрена и конфликты будут редким явлением). Это позволит отложить инициализацию и, соответственно, не выделять физическую память сразу. Естественно, нужно сделать так, чтобы повторное обращение к тому же участку памяти с высокой долей вероятности происходило из того же потока.

В любом случае, запросить сразу 50% физической памяти у системы с помощью единственного объекта std::vector — не будет хорошо работать на NUMA системе никогда и нужно специально под эту архитектуру что-нибудь придумывать.

Здравствуйте, Mazay, Вы писали:

M>Программа при запуске выделяет большой кусок памяти (512 ГБ) под массив double-ов.

Я тут покурю в сторонке.

M>Можно ли как-то ускорить это дело?

Не совсем по делу просто вспомнилось:

Урок в итальянской школе.
— Джованни, сколько будет дважды два?
— Мне бы Ваши заботы, господин учитель!

Здравствуйте, Mazay, Вы писали:

M>Можно ли как-то ускорить это дело?

гипотеза:
используй new[]
std::vector инициализирует нулями всю эту память в цикле, что и занимает столько времени

Так вы кроме выделения ещё и инициализацию делаете. Используйте reserve() — это как раз и есть просто выделение памяти.

Здравствуйте, Mazay, Вы писали:

M>Обязательно выделять память через valloc? malloc или new дадут другое поведение?
Зависит от реализации, но обычно после превышения размера некоторого порога все вызовы malloc или new просто передаются в системный вызов mmap как есть. Так что разницы практически не будет. С другой стороны через mmap можно получить чуть больше контроля (те же большие страницы использовать).

Здравствуйте, Mazay, Вы писали:

M>Программа при запуске выделяет большой кусок памяти (512 ГБ) под массив double-ов. Сейчас это делается вот так:

Точно Гигабайт ? 512 ? А сколько RAM на машине ?

M>Программа при запуске выделяет большой кусок памяти (512 ГБ) под массив double-ов. Сейчас это делается вот так:
M>

M>vector <double> vect(N);
M>

M>Это занимает около 10 минут времени при 100% загрузке одного ядра.
M>Что там вообще менеджер кучи так долго делает?
...свопится, наверное

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Здравствуйте, Mazay, Вы писали:

M>>Программа при запуске выделяет большой кусок памяти (512 ГБ) под массив double-ов. Сейчас это делается вот так:

PD>Точно Гигабайт ? 512 ? А сколько RAM на машине ?

Один террабайт. Там кроме этого мегавектора есть ещё несколько помельче. В пике получается около 85% памяти занято.

Здравствуйте, ononim, Вы писали:

M>>Программа при запуске выделяет большой кусок памяти (512 ГБ) под массив double-ов. Сейчас это делается вот так:
M>>

M>>vector <double> vect(N);
M>>

M>>Это занимает около 10 минут времени при 100% загрузке одного ядра.
M>>Что там вообще менеджер кучи так долго делает?
O>...свопится, наверное

Не Там террабайт памяти. В своп точно не уходит.

Здравствуйте, Mazay, Вы писали:

PD>>Точно Гигабайт ? 512 ? А сколько RAM на машине ?

M>Один террабайт. Там кроме этого мегавектора есть ещё несколько помельче. В пике получается около 85% памяти занято.

Под Windows решение простое — VirtualAlloc. Под линукс см. здесь

http://linux.die.net/man/3/valloc

Здравствуйте, smeeld, Вы писали:

S>что быстро выполниться при больших N не может.

Интересно, что этот construct делает, и можно ли его попросить этого не делать?
По крайней мере, new раньше спокойно оставлял примитивные типы неинициализированными, а vector так не умеет?

S>Да, делайте просто malloc() без этих stl дурковатостей.

Можно с придурковатостями, в shared_ptr засунуть, но после malloc
Другой вопрос — нужен ли в программе этот здоровый массив? Если его нулями заливает 10 минут, то какое время займёт его обычное использование? Если 10 минут — ничтожная доля в общем времени, то имеем классическую причину всех зол, по Кнуту. Если доля существенная, то массив как таковой практически не исползуется, только небольшие его участки, и его хорошо бы заменить на подходящую структуру меньшего размера.
А если его таки надо забить изначально нулями, то может быть проще его в .bss завести, система сама инициализирует, если умная — аппаратно. Ну или правда через OpenMP распараллелить, обычно в машине несколько каналов к памяти, может в несколько раз ускориться. Или memset позвать, вдруг он что-то знает

Здравствуйте, cures, Вы писали:

C>По крайней мере, new раньше спокойно оставлял примитивные типы неинициализированными, а vector так не умеет?

вектор не умеет

Здравствуйте, cures, Вы писали:

C>Интересно, что этот construct делает, и можно ли его попросить этого не делать?

Тупо зовёт __alloc.construct() который в std::allocator такой

 template<typename _Up, typename... _Args>
  void
  construct(_Up* __p, _Args&&... __args)
  { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }

Если его заменить пустышкой, то это всё равно не избавит от самого цикла, к тому же, vector станет
кастрированным, вся инициализация элементов в push*, emplace*, insert проводится через __alloc.construct()

Здравствуйте, cures, Вы писали:
C>В любом случае очень подозрительно, даже если заполнение, скорость меньше гига в секунду — это странно.
Оно примерно так и работает 512ГБ ~600 секунд

Здравствуйте, cures, Вы писали:
C>то имеем классическую причину всех зол, по Кнуту. Если доля существенная, то массив как таковой практически не исползуется, только небольшие его участки, и его хорошо бы заменить на подходящую структуру меньшего размера.

Там по ходу программа запускается 10 минут. А учитывая 1ТБ памяти, оно еще и сервер. А значит программа, скорее всего — служба.
Если все так, то оптимизировать уже пора

Здравствуйте, smeeld, Вы писали:

S>Если его заменить пустышкой, то это всё равно не избавит от самого цикла,

Пустой цикл выкинется оптимизатором, да и 64 миллиарда итераций не займут 10 минут, от силы — одну

S> к тому же, vector станет кастрированным, вся инициализация элементов в push*, emplace*, insert проводится через __alloc.construct()

Это же чудесно! Можно будет пользоваться как нормальным массивом.
А если не совсем пустышкой, скажем, перекрыть размещающий new для конкретного типа double?

Здравствуйте, MTimur, Вы писали:

MT>Там по ходу программа запускается 10 минут. А учитывая 1ТБ памяти, оно еще и сервер. А значит программа, скорее всего — служба.
MT>Если все так, то оптимизировать уже пора

Если служба, то работает 24*7, нет смысла оптимизировать запуск
Да и где это виданы самописные службы на терабайт?
"Это служба — так уж служба, тут нужна моя вся дружба!"
Но всё же хотелось бы послушать начальника транспортного цеха.

MT> Оно примерно так и работает 512ГБ ~600 секунд

Обычно скорость работы с памятью не меньше 2 гигов в секунду, даже в один канал. Тут видимо ещё цикл не оптимизировался и мимо ТЛБ всё время ходят.

Здравствуйте, cures, Вы писали:

C>Это же чудесно! Можно будет пользоваться как нормальным массивом.

Зачем тогда vector, когда достаточно просто массива? Или всем отделом смеяться будут? Типа modern C++ не осилил.
И цикл будет не пустой, Вы ведь не реализацию std::vector будете корректировать, а просто назначите свой allocator,
вместо дефолтного, с пустым методом construct, который и будет вызываться в цикле, и пустота которого предотвратит
выделение реальных страничных фреймов в ядре в момент создания vector.

C>А если не совсем пустышкой, скажем, перекрыть размещающий new для конкретного типа double?

Это и есть пустышка, если не будет производиться запись любого значения по адресу std::__addressof(*__cur).

Здравствуйте, cures, Вы писали:

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

Здравствуйте, cures, Вы писали:

C>Здравствуйте, Mazay, Вы писали:

M>> Что там вообще менеджер кучи так долго делает?

C>А точно менеджер кучи тупит, а не забивание этой памяти дефолтными нулями? Цапните её стандартным маллоком, он ничем не заполняет. Если не поможет — вручную ммапом.
C>И общий совет при таких размерах: включите HugeTLB хотя бы двухметровое, а можно попробовать и гигабайтное.
C>Насчёт не свопится — тоже лучше проверить, оно и профилактически может, отключите все своп-разделы.
C>В любом случае очень подозрительно, даже если заполнение, скорость меньше гига в секунду — это странно.
C>Вы точно не под валгриндом пускаетесь? Или у Вас винда?


Отвечу не всем, но всем спасибо!

Замена вектора на new double[] помогла. Выделяется мгновенно. Причём оптимизатор похоже переупорядочил вызовы — фактическое выделение происходит, кажется, по первому обращению к указателю. Детально ещё не копал. Может просто top и /proc/meminfo реагируют с задержкой. До свопов пока руки не дошли.

Гиг в секунду на заполнение — может это и нормально. У меня же всё-таки NUMA, thread affinity пока не настраивал. Но буду копать.

HugeTLB — это интересно. Поэкспериментирую — отпишусь в этот же тред.

Здравствуйте, cures, Вы писали:

C>Здравствуйте, smeeld, Вы писали:

S>>что быстро выполниться при больших N не может.

C>Интересно, что этот construct делает, и можно ли его попросить этого не делать?
C>По крайней мере, new раньше спокойно оставлял примитивные типы неинициализированными, а vector так не умеет?

S>>Да, делайте просто malloc() без этих stl дурковатостей.

C>Можно с придурковатостями, в shared_ptr засунуть, но после malloc
C>Другой вопрос — нужен ли в программе этот здоровый массив? Если его нулями заливает 10 минут, то какое время займёт его обычное использование? Если 10 минут — ничтожная доля в общем времени, то имеем классическую причину всех зол, по Кнуту. Если доля существенная, то массив как таковой практически не исползуется, только небольшие его участки, и его хорошо бы заменить на подходящую структуру меньшего размера.

Там всё плохо с точки зрения оптимизации — массив не разрежен и сразу после запуска инициализируется рандомными числами в многопоточном режиме. Но это делается быстро, ибо 64 ядра отлично параллелятся. А "выделение" памяти делалось одним потоком и долго, что сильно раздражало. Теперь то я понимаю, что это было не само выделение, а дураковатости в конструкторе вектора.

C>А если его таки надо забить изначально нулями, то может быть проще его в .bss завести, система сама инициализирует, если умная — аппаратно. Ну или правда через OpenMP распараллелить, обычно в машине несколько каналов к памяти, может в несколько раз ускориться. Или memset позвать, вдруг он что-то знает

Ээээ. А как компилятору сказать что вектор нужно в .bss завести? Размер в компайл-тайм известен.

Здравствуйте, cures, Вы писали:


MT>>Там по ходу программа запускается 10 минут. А учитывая 1ТБ памяти, оно еще и сервер. А значит программа, скорее всего — служба.
MT>>Если все так, то оптимизировать уже пора

Надо сначала отладиться. Только тяжело дебажиться, когда программа стартует по 10 минут, а падает через 15. Собственно я поэтому и озадачился.

C>Если служба, то работает 24*7, нет смысла оптимизировать запуск
C>Да и где это виданы самописные службы на терабайт?
C>"Это служба — так уж служба, тут нужна моя вся дружба!"
C>Но всё же хотелось бы послушать начальника транспортного цеха.

Это не служба. Это числодробилка.


MT>> Оно примерно так и работает 512ГБ ~600 секунд

C>Обычно скорость работы с памятью не меньше 2 гигов в секунду, даже в один канал. Тут видимо ещё цикл не оптимизировался и мимо ТЛБ всё время ходят.

Может потому что это NUMA без привязки ядер к "своим" регионам памяти.

M>фактическое выделение происходит, кажется, по первому обращению к указателю

Фактическое выделение физической памяти под страницу происходит при первом обращении к этой странице. Теперь посчитай сколько у тебя там будет страниц памяти, в этих 512-ти ГБ. В общем — все эти 6 (или сколько там) минут будут размазаны по общему времени работы приложения

Зачем нужно столько памяти сразу выделять?

Здравствуйте, chaotic-good, Вы писали:

M>>Компилятор — g++ 4.8
M>>OS — CentOS 7

M>>Можно ли как-то ускорить это дело? Распараллелить например. Что там вообще менеджер кучи так долго делает?

CG>Смотря что за железка, если там NUMA (что скорее всего имеет место быть, так как массив памяти очень уж большой), то выделять (и инициализировать) одним большим куском столько памяти — бессмысленно. Каждая NUMA нода должна выделять память, с которой она потом будет работать преимущественно самостоятельно, так как менеджер памяти в ОС — NUMA aware и будет давать потоку память из той же ноды. Можно выделить большой кусок виртуальной памяти через valloc или mmap и потом инициализировать те куски, с которыми ты будешь работать из разных потоков этими же потоками и тогда менеджер памяти, по идее, должен раздать им страницы физической памяти из соответствующих NUMA-нод.

Да, конечно NUMA. На Intel QPI.
Обязательно выделять память через valloc? malloc или new дадут другое поведение?


CG>Можно, например, завести битовый массив, каждый бит которого соответствовал бы странице памяти из этих 512-ти ГБ, если поток пытается обратиться к какой-либо странице, то он сначала должен проверить соответствующий бит а затем, если этот бит равен 0 — инициализировать соответствующий участок памяти (+ синхронизация этого всего, вероятно оптимистичная, так как памяти дохрена и конфликты будут редким явлением). Это позволит отложить инициализацию и, соответственно, не выделять физическую память сразу. Естественно, нужно сделать так, чтобы повторное обращение к тому же участку памяти с высокой долей вероятности происходило из того же потока.

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

Здравствуйте, Mazay, Вы писали:


M>Ээээ. А как компилятору сказать что вектор нужно в .bss завести? Размер в компайл-тайм известен.
Через указывания в векторе собственного аллокатора, который и будет возвращать память для вектора из bss.
Другое дело, что в таком случае вообще не понятно зачем вам хочется использовать именно вектор. Используй простой массив double array[N]; или std::array в конце концов, но не вектор.

Здравствуйте, chaotic-good, Вы писали:

M>>фактическое выделение происходит, кажется, по первому обращению к указателю

CG>Фактическое выделение физической памяти под страницу происходит при первом обращении к этой странице. Теперь посчитай сколько у тебя там будет страниц памяти, в этих 512-ти ГБ. В общем — все эти 6 (или сколько там) минут будут размазаны по общему времени работы приложения

Если я правильно понял, HugeTLB увеличивает размер страницы памяти и ускорит выделение. Так?

CG>Зачем нужно столько памяти сразу выделять?
Это вектор, который нужно умножать на матрицу, чтобы искать её собственное значение. Матрица не разреженная, но умные люди придумали её разложение на произведение разреженных. Но вектор всё равно нужно хранить.

M>Да, конечно NUMA. На Intel QPI.
M>Обязательно выделять память через valloc? malloc или new дадут другое поведение?

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

M>Если я правильно понял, HugeTLB увеличивает размер страницы памяти и ускорит выделение. Так?

Страниц будет меньше, выделяться они будут реже и система будет тратить меньше ресурсов на управление ими. Можно передать флаг MAP_HUGETLB в вызов mmap, например.

Здравствуйте, smeeld, Вы писали:

S>Зачем тогда vector, когда достаточно просто массива? Или всем отделом смеяться будут? Типа modern C++ не осилил.

Объект типа массива, без изменения размера после создания, но с не компайл-тайм заданным размером.
Штука нужная, в стандартной библиотеке нету.

S>И цикл будет не пустой, Вы ведь не реализацию std::vector будете корректировать, а просто назначите свой allocator,
S>вместо дефолтного, с пустым методом construct, который и будет вызываться в цикле, и пустота которого предотвратит
S>выделение реальных страничных фреймов в ядре в момент создания vector.

А что в нём останется? Какой реально выполняемый код?

S>Это и есть пустышка, если не будет производиться запись любого значения по адресу std::__addressof(*__cur).

Хорошо, назовём это пустышкой, но хочется её сделать именно для заполнения элемента конкретного типа double без аргументов. Только способов сделать это я не вижу: перекрыть placement new можно, но он не будет знать аргументов конструктора, да и конструктор вызывает он неявно, неперекрываемым способом.
Другой вариант — научиться подсовывать вектору предвыделенную память и её размер, но и это я могу сделать только грязным непереносимым хаком — явным прописыванием его полей по адресам. В общем, комитету есть ещё над чем работать
Проще всего специализировать uninitialized_default_n_a для итератора вектора по даблам в пустой, все вопросы решатся. Зачем он нужен для неинициализированных простых типов?

Здравствуйте, push, Вы писали:

P>Так вы кроме выделения ещё и инициализацию делаете. Используйте reserve() — это как раз и есть просто выделение памяти.

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

Здравствуйте, Mazay, Вы писали:

M>Ээээ. А как компилятору сказать, что вектор нужно в .bss завести? Размер в компайл-тайм известен.

 static double vect[N];

вне тела функции. static — чтобы проще было ходить к его элементам, при динамической линковке хождение к глобальным переменным зависит от ABI и может быть очень чудесатым. Нужным потребителям можно передавать адрес его начала.
Интересно, поймёт ELF такое?

Здравствуйте, cures, Вы писали:

C>Это хак, при этом, строго говоря, он имеет полное право в любой момент переразместить массив либо просто испортить выделенные "неиспользованные" элементы. Обычно он так делать не будет, но сие зависит от реализации.
C>А если в какой-то момент попытаетесь в него добавить элементов — будет совсем весело.

Никакой это не хак. Для пустого vector это просто

 pointer
  _M_allocate(size_t __n)
  {
  typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
  return __n != 0 ? _Tr::allocate(_M_impl, __n) : 0;
  }

Для не пустого, после вышеприведённого, ещё перемещение существующих элементов на новое место жительства

 template<typename _ForwardIterator>
 pointer
 _M_allocate_and_copy(size_type __n,
 _ForwardIterator __first, _ForwardIterator __last)
 {
  pointer __result = this->_M_allocate(__n);
  __try
  {
  std::__uninitialized_copy_a(__first, __last, __result,
  _M_get_Tp_allocator());
  return __result;
  }
  __catch(...)
  {
  _M_deallocate(__result, __n);
  __throw_exception_again;
  }
 }

И далее контрольный

  this->_M_impl._M_start = __tmp;
  this->_M_impl._M_finish = __tmp + __old_size;
  this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;

Так что для выделения памяти без инициализации подходит. Другое дело, что это не что иное как вызов
malloc через пять посредников, и для использования функционала mmap, чтоб huge pages включить, например,
нужно алокатор расписывать.

Здравствуйте Mazay,

если у вас NUMA и работаете с матрицами, то есть смысл посмотреть в сторону OpenMP и попробовать распараллелить задачу.