1

Задача заключается в сортировке записей. Ограничение по памяти - 8 мб. По подсчетам программа ест не более 5 мб., но на деле всё происходит иначе.

stroka = (char **)malloc(sizeof(char *) * 200000);
    for (int i = 0; i < 200000; i++) {
        stroka[i] = (char *)malloc(sizeof(char) * 25);
    }

Отладчик и диспетчер задач показывает, что памяти выделяется ~9 мб. Откуда берутся лишние 3-4 мб.? Что сделать, чтобы избежать этого?

13
  • А откуда взялось ограничение? Ну и память может выделять и стандартная библиотека.
    – VladD
    27 мая 2016 в 9:43
  • 1
    а вы выделите 1 байт и посмотртие, сколко будет, память = секция данные + секция кода. А библиотеки могут вполне использовать оперативную память.
    – pavel
    27 мая 2016 в 9:45
  • А объясните, откуда взялась ваша оценка в 5 мб?
    – VladD
    27 мая 2016 в 9:45
  • Зачем насиловать свой мозг, когда много лет назад изобрели stl) - vector, map и т.д. и т.п., умные указатели, они намного упрощают жизнь программиста) используй их в своих проектах.
    – Duracell
    27 мая 2016 в 9:45
  • 1
    @pavel: Если это реально так (не конкурс, а примеры задач к нему), имеет смысл честно указать это в вопросе, и привести ссылку, чтобы обсуждение было полезно и другим.
    – VladD
    27 мая 2016 в 10:01

3 ответа 3

6

У malloc расход на управление как минимум 4-8 байт (ему ж надо где-то хранить размер, да?). Плюс выравнивание — вы никогда не получите ровно 25 байт, будет выравнивание на границу 16 байт — то есть, вместо 25 будет реально выделено 32 байта.

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

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


Да, и не забывайте, что массив из 200000 указателей тоже отжирает 0.8 или 1.6 мегабайт, в зависимости от архитектуры.

4
  • Это дает, конечно же дает выигрыш в ((32 - 25) * 200000 + ~200000) байт, но это это значительно усложняет, казалось бы, легкую задачу. К тому же, даже с таким выигрышем мы можем не пройти Memory Limit. 27 мая 2016 в 10:39
  • @KeltarHelviett: Хм, а почему вы считаете, что задача лёгкая с таким ограничением по памяти?
    – VladD
    27 мая 2016 в 10:42
  • Всё упирается в ограничение по памяти, которое мы превышаем всего лишь в ~1.5 мб. 27 мая 2016 в 10:49
  • @KeltarHelviett: Ну да. Ограничение памяти на то и дано, чтобы не дать пользоваться стандартными средствами.
    – VladD
    27 мая 2016 в 10:51
1

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

typedef char arr[200000][25];

int main(int argc, const char * argv[])
{
    arr& a = *(arr*)malloc(sizeof(arr));
    a[199999][24] = 'A';
}
0

200000*8 - память которая выделена под указатели на платформе х-64; 200000*25 - память которая выделена под 200000 массивов по 25 байт каждого нужно учитывать что при каждом обращении к малоку в памяти еще находится структура данных самого малока. + текст самой программы вот тебе и 9мб

Ваш ответ

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

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.