История про realloc (и лень)

Original author: Xavier Roche
  • Translation

Простой макрос


Все началось с простого макроса: (приблизительный код)
#define ADD_BYTE(C) do {            \
  if (offset == capa) {             \
    if (capa < 16) {                \
      capa = 16;                    \
    } else {                        \
      capa <<= 1;                   \
    }                               \
    buffer = realloc(buffer, capa); \
    assert(buffer != NULL);         \
  }                                 \
  buffer[offset++] = (C);           \
} while(0)


Для тех, кто не знаком с языком программирования C, поясню: этот простой макрос добавляет байт «C» в динамически выделяемый буфер (buffer), размер которого (в байтах) равен capa. Следующая позиция для записи определяется при помощи параметра offset. При каждом заполнении буфера происходит двукратное увеличение его объема (начиная с минимального размера в 16 байт).

Мы добавляем байты в динамический буфер — это одна из наиболее распространенных операций практически в любой программе (для работы со строками, массивами и т. п.).

Но как понять, насколько эффективна стратегия перераспределения? Если вы посмотрите на эту проблему с точки зрения сложности, принимая сложность realloc() равной O(N), то сразу поймете, что добавление одного байта имеет сложность в среднем O(1), что вполне неплохо.

Но какова сложность в наихудшем случае — если требуется перераспределение памяти под буфер?
Анонимус: Уверен, что это хорошая стратегия? Ты нарвешься на серьезные проблемы с производительностью, если станешь увеличивать размер большого массива, скажем, в один гигабайт. Только представь себе последствия, особенно если буфер нужно переместить из файла подкачки.

Я: Хм… Честно говоря, никогда не задумывался над этим… Но уверен, все не так страшно. Система должна успешно справиться с этой задачей.

Анонимус: А мне кажется, что связанная структура — более удачный вариант, пусть даже с той же экспоненциальной стратегией.

Я: Да нет, это пустая трата времени.

Анонимус: Пруф?

Ах вот так, значит?!


Ладно, придется обосновать свою позицию. Как и все программисты, я весьма ленив. Точнее: «Как подобает программисту, я весьма ленив». Лень — отличный стимул стать умнее и эффективнее. Вы слишком ленивы для того, чтобы решать повторяющиеся или рутинные задачи; вам нужно что-то более интеллектуальное, что-то максимально быстрое. Да, именно это иногда называют ленью. Но, по-моему, это не что иное, как эффективность.

Связанный список блоков для хранения буфера — несколько громоздкое решение. Я не говорю, что это невозможно. «Невозможно — не французское слово», — говаривал Наполеон (правда, кончил он плохо). Решение возможно, но оно громоздкое. Копирование подмассива или сохранение его на диск потребует некоторых усилий. Нам, вероятно, пришлось бы поддерживать индекс указателей на начало каждого массива, брать логарифм по основанию два, чтобы получить адрес начала блока и еще много всякой нудятины… Ух, я уже устал…

Что-то подсказывает мне, что моя лень будет здесь как нельзя кстати. Ведь о маленьких блоках вовсе не стоит беспокоиться, а о больших позаботится виртуальная память системы.

Давайте разберемся.

Кстати, что такое realloc()?


Это обычная функция, соответствующая стандарту POSIX, которая реализована в библиотеке C. В случае с Linux это библиотека libc.so, в ней же находятся и родственные realloc функции malloc и free:

nm -D /lib/x86_64-linux-gnu/libc.so.6 | grep -E "T (malloc|realloc|free)$"
000000000007e450 T free
000000000007e030 T malloc
000000000007e4e0 T realloc


Для тех, кому это действительно интересно: «T» означает «text symbol» (текстовый символ), заглавная буква используется, чтобы показать, что символ этот общедоступный и видимый; текстовый сегмент программы — это код, сегмент данных — инициализированные данные (переменные), а сегмент bss — неинициализированные данные (переменные), а точнее данные (переменные), получившие в качестве начального значения ноль).

Для выделения, перераспределения и освобождения памяти используется распределитель памяти (спасибо, Капитан Очевидность!). Таких распределителей много (самый известный — buddy allocator).

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

#include <sys/types.h>
#include <unistd.h>
#include <string.h>

void *malloc(size_t size) {
  return sbrk(size);
}

void free(void *ptr) {
  /* Кого это волнует? */
}

/* Примечание: только для увеличения (да, я ленив) */
void *realloc(void *ptr, size_t size) {
  void *nptr = malloc(size);
  if (nptr == NULL) {
    return NULL;
  }
  // «old_size» должен быть известен :)
  // (например, запишите его в начало выделенного блока)
  memcpy(nptr, ptr, old_size);
  free(ptr);
  return nptr;
}


[Примечание. Как справедливо заметил один из читателей Hacker News, здесь нужно значение old_size, которое, например, можно было записать в начало блока после того, как блок был выделен. Но нет, мы не должны были освободить исходный блок в случае ошибок в работе realloc :)]

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

Чтобы понять, что происходит с большими блоками, нам придется поближе познакомиться с Glibc на Linux.

Знакомство с Glibc


Просто скачайте последнюю версию glibc и изучите дерево исходного кода.
Там есть один интересный каталог malloc. Найдите в нем файл malloc.c и откройте его в редакторе.

/*
  Основные свойства алгоритмов:
   * Это наиболее подходящий распределитель для больших запросов (>= 512 байт), связи обычно создаются с использованием FIFO (т. е. вытеснение по давности использования).
   * Для небольших запросов (<= 64 байт по умолчанию) это кэширующий распределитель, который управляет пулами интенсивно используемых блоков.
   * Что касается средних блоков, а также комбинаций из больших и маленьких блоков, делается все возможное для максимально эффективной работы и с теми, и с другими.
   * Для очень больших запросов (>= 128 Кб по умолчанию) используются системные средства сопоставления памяти, если они поддерживаются.

    Более подробная, хотя и слегка устаревшая, информация по этому поводу: http://gee.cs.oswego.edu/dl/html/malloc.html 
*/


Нас больше всего интересует вот эта часть: «Для очень больших запросов (>= 128 Кб по умолчанию) используются системные средства сопоставления памяти, если они поддерживаются».

Порог в 128 Кб настраивается функцией mallopt():

M_MMAP_THRESHOLD
          Если свободной памяти недостаточно, то для блоков, превышающих или равных лимиту (в байтах), установленному для M_MMAP_THRESHOLD, функции выделения памяти используют mmap(2), вместо того чтобы увеличивать размер сегмента данных с помощью sbrk(2).


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

В сущности, это означает, что:
  • malloc будет реализована с использованием mmap;
  • free будет реализована с использованием munmap;
  • realloc будет реализована с использованием mremap (Что?! Такого в POSIX еще нет? Серьезно?)

Ладно, давайте чуть-чуть расширим свои познания о mremap.

Итак, что мы знаем о man mremap:

mremap() использует схему таблиц страничной адресации Linux. mremap() изменяет отображение виртуальных адресов на страницы памяти. Таким образом, можно реализовать очень эффективный realloc(3).


Ага, очень эффективный realloc. Насколько эффективный?

Во-первых, mmap, munmap и mremap описаны в библиотеке glibc. На самом деле, только точки входа:
nm -D /lib/x86_64-linux-gnu/libc.so.6 | grep -E "(mmap|munmap|mremap)$"
00000000000e4350 W mmap
00000000000e9080 W mremap
00000000000e4380 W munmap


Обратите внимание на то, что точки входа по умолчанию — это в данном случае «слабые» символы. То есть они могут быть переопределены кем-то другим во время динамической компоновки. Например:

ldd /tmp/sample
        linux-vdso.so.1 (0x00007584a8aaa000)
        libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007584a86e6000)
        /lib64/ld-linux-x86-64.so.2 (0x00007584a8aac000


… символы могут быть переопределены библиотекой linux-vdso.so.1 — это волшебная библиотека, которая отображается во всех программах под Linux и позволяет ускорить некоторые вызовы, включая системные вызовы.
В любом случае наши символы в библиотеке glibc — это только каналы к вызовам ядра системы (syscall), будь то glibc или vdso (см. реализации по умолчанию: sysdeps/unix/sysv/linux/mmap64.c). Например:

void *
__mmap64 (void *addr, size_t len, int prot, int flags, int fd, off64_t offset)
{
  // проверка аргументов удалена
  void *result;
  result = (void *)
    INLINE_SYSCALL (mmap2, 6, addr,
                    len, prot, flags, fd,
                    (off_t) (offset >> page_shift));
  return result;
}


Итак, наш первоначальный вопрос уже связан не с glibc, а с ядром Linux.

Знакомство с ядром


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

Заглянув в руководство (The Linux Kernel Howto), вы найдете очень интересный каталог:

Каталог mm содержит весь необходимый код для работы с памятью. Код управления памятью, специфичный для конкретной архитектуры, размещается в каталогах вида arch/*/mm/, например arch/i386/mm/fault.c.


Отлично. Они-то нам и нужны!
Вот интересный файл: mm/mremap.c. В нем вы найдете точку входа для системного вызова функции mremap. Вот здесь:

/*  
* Увеличить (или уменьшить) существующее отображение, возможно, одновременно переместив его 
* (с учетом значения флага MREMAP_MAYMOVE и доступного пространства VM) 
*
* Опция MREMAP_FIXED добавлена 5 декабря 1999 г. Бенджамином Лахейзом (Benjamin LaHaise) 
* Эта опция подразумевает использование MREMAP_MAYMOVE.  
*/ 
SYSCALL_DEFINE5(mremap, unsigned long, addr, unsigned long, old_len,
                unsigned long, new_len, unsigned long, flags,
                unsigned long, new_addr)
{



Именно здесь мы входим в ядро при выполнении соответствующего системного вызова в пользовательском коде (через glibc или соответствующий канал vdso).

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

Затем ядро попытается расширить отображенную область путем ее увеличения (то же самое делал бы распределитель в библиотеке C при помощи sbrk). В случае успешного расширения функция возвращает результат.

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

А что в наихудшем случае?
        /*
         * Мы не могли просто расширить или уменьшить область
         * нам пришлось создать новую и затем переместить.         
         */
        ret = -ENOMEM;
        if (flags & MREMAP_MAYMOVE) {
                unsigned long map_flags = 0;
                if (vma->vm_flags & VM_MAYSHARE)
                        map_flags |= MAP_SHARED;

                new_addr = get_unmapped_area(vma->vm_file, 0, new_len,
                                        vma->vm_pgoff +
                                        ((addr - vma->vm_start) >> PAGE_SHIFT),
                                        map_flags);
                if (new_addr & ~PAGE_MASK) {
                        ret = new_addr;
                        goto out;
                }

                map_flags = vma->vm_flags;
                ret = move_vma(vma, addr, old_len, new_len, new_addr);
                if (!(ret & ~PAGE_MASK)) {
                        track_exec_limit(current->mm, addr, addr + old_len, 0UL);
                        track_exec_limit(current->mm, new_addr, new_addr + new_len, map_flags);
                }
        }


На первый взгляд, ядро делает то же самое, что делаем мы в своем простом распределителе:
  • выделяет новую область;
  • копирует исходную область в новую, а затем освобождает ее (т. е. выполняется операция перемещения).

Но давайте посмотрим повнимательнее.

Вот вызов move_vma:
static unsigned long move_vma(struct vm_area_struct *vma,
                unsigned long old_addr, unsigned long old_len,
                unsigned long new_len, unsigned long new_addr)
{
...
        new_pgoff = vma->vm_pgoff + ((old_addr - vma->vm_start) >> PAGE_SHIFT);
        new_vma = copy_vma(&vma, new_addr, new_len, new_pgoff,
                           &need_rmap_locks);
        if (!new_vma)
                return -ENOMEM;

        moved_len = move_page_tables(vma, old_addr, new_vma, new_addr, old_len,
                                     need_rmap_locks);



Здесь есть два интересных вызова:
  • copy_vma;
  • move_page_tables.

Функция copy_vma описана в файле mm/mmap.c; она перемещает структуру типа vm_area_struct — это внутренняя структура ядра, описывающая блок памяти.

Определение можно найти здесь: include/linux/mm_types.h. Эта небольшая структура содержит всю информацию об области: начальный и конечный адрес, файл на диске (если область памяти используется для отображения файла) и т. д.

Итак, эта операция перемещения достаточно проста — O(1).

А что делает функция move_page_tables?

Самое интересное, похоже, вот в этом цикле:

...
        for (; old_addr < old_end; old_addr += extent, new_addr += extent) {
...
                move_ptes(vma, old_pmd, old_addr, old_addr + extent,
                          new_vma, new_pmd, new_addr, need_rmap_locks);
...



Этот код несколько сложноват (кроме того, нет комментариев), но в основном это базовые арифметические операции и расчеты.

Функция move_ptes содержит внутренний цикл самого нижнего уровня:

...
        for (; old_addr < old_end; old_pte++, old_addr += PAGE_SIZE,
                                   new_pte++, new_addr += PAGE_SIZE) {
                if (pte_none(*old_pte))
                        continue;
                pte = ptep_get_and_clear(mm, old_addr, old_pte);
                pte = move_pte(pte, new_vma->vm_page_prot, old_addr, new_addr);

...
                set_pte_at(mm, new_addr, new_pte, pte);
        }
...


Так что же в этом цикле происходит?! Мы просто перемещаем строки таблицы страниц (PTE, Page Table Entries), соответствующие области памяти, в другое место. По сути, это целые числа, назначенные каждой странице.

Итак, что мы имеем: фактически ядро не притрагивалось к данным из нашего сопоставленного блока; для перемещения всей области достаточно было поменять местами несколько битов.
Формально сложность по-прежнему O(N), но
  • вместо копирования целых страниц по 4 Кб (или 2 Мб для очень больших страниц), мы меняем местами целые числа внутри структуры ядра;
  • мы работаем с «горячей» памятью ядра, не притрагиваясь к «холодной» и тем более к данным, вытолкнутым в файл подкачки.

Поэтому мы используем O(N), но с огромным отличием.

Да, кстати, вы знаете, что O(N) во многих случаях сбивает с толку?

В нашем случае максимальным значением N является 248 (максимальный размер виртуального пространства). Большинство компьютеров работают лишь с несколькими гигабайтами памяти — не более 64 Гб для большинства архитектур (то есть 236 байт). Большая станица — это 221 байт, максимальное число операций составляет 215 для move_ptes (да, это всего лишь 32 768 операций).

Итак, в наихудшем случае затраты всегда крайне низкие, и я почему-то не сомневался в этом с самого начала.

Также рекомендую к прочтению: книгу Understanding the Linux Virtual Memory Manager Мела Гормана (Mel Gorman).

«Ниасилил многабукаф»? Не парьтесь. Лень и realloc — наше все.
ABBYY
Решения для интеллектуальной обработки информации

Comments 51

    +13
    Ну вообще да. Если мы говорим о системах способных запускать Линукс, то там уже не надо париться об эфективности управления памятью. Всё уже украдено сделано до нас.

    Другое дело — всякие OSless системы, где аллокатор вроде бы и есть, но чаще всего сделан довольно топорно. В основном из-за ограничений самой архитектуры (например — нету MMU).

    Иными словами — если у вас не жёсткий embedded и вы не пишете числодробилку/БД/высоконагруженный сервис — не думайте о сложности, делайте как вам удобнее. Всё равно, когда дело дойдет до узких мест — они будут совершенно не там, где вы ожидаете.
      0
      А в системах, в которых можем упереться в фрагментацию памяти — виртуальное адресное пространство IMO первое, что надо сделать. А дальше можно realloc-ать направо и налево.
        +2
        А в жёстком embedded'е всё тем более не имеет смысла заниматься оптимизациями не имея данных о том, что тормозит. Ибо в «больших» системах у вас есть хотя бы путеводитель в лице «O большого», а в системах, которые по своей природе ограничены проблемы могут быть совсем-совсем не там где вы их ждёте и на тех объёмах, на которых вы собрались работать O(N³) легко может оказаться быстрее, чем O(N²), а иногда может быть и быстрее, чем O(N).
          0
          tcmalloc & jemalloc нам в помощь

          за статьи спасибо, а так же за книгу
          думаю знания пригодятся в жизни
          +2
          Отличная статья, спасибо!

          Интересно, как это реализовано в Win32…
            0
            Вызова VirtualRealloc нет — поэтому оно работает хуже линуксовой версии. Хотя это ограничение и можно обойти через явное отображение файла подкачки на память — сильно сомневаюсь, что стандартная библиотека C использует этот механизм.
              0
              Я покопался в коде ReactOS, смотрел, как ReallocHeap реализован. Тоже через копирование.

              через явное отображение файла подкачки на память

              Можно подробнее, что вы имеете в виду, что это даст?
                0
                Это даст возможность перемапить кусок в другую область виртуального адресного пространства без копирования, очевидно же.

                PS Под «явным отображением файла подкачки на память» я имел в виду CreateFileMapping(INVALID_HANDLE_VALUE, ...)
                  0
                  Это понятно. Перемапить кусок можно. Я задумался над тем, как стыковать с новым буфером — ведь файлмаппинг займет свой адрес, и нет гарантии, что можно получить кусок встык за ним.
                    0
                    А, ну можно задать size of mapping больше, чем надо, а потом смапить столько, сколько надо в MapViewOfFile.
            +7
            buffer = realloc(buffer, capa);

            Так может утекать память. Если realloc не смог выделить память, теряется предыдущий адрес, на который указывал buffer.

            В остальном разбор неплохой, спасибо.
              +2
              Там же в следующей строке assert торчит.

              Всё равно мало какая программа умеет корректно обрабатывать недостачу памяти.
                +2
                Хм, действительно. Конечно да, упасть при нехватке памяти — решение. Но для embedded, к примеру, не подойдёт.
                  0
                  Для драйверов тоже не пойдет.
                  Мне почему-то кажется, что не только меня бесит, когда при работе на грани доступной памяти система в произвольный момент времени может умереть.
                  Для прояснения контекста: работаю без SWAP, т.к. если Java начинает вытесняться в SWAP все становится ну очень печально — проще все закрыть и открыть заново.

                  P.S. В Windows 7 по сравнению с предыдущими версиями получить эту ошибку на уровне драйвера намного труднее.
              +2
              Только лучше всё-таки не x2 а x1.5 делать, чтобы не получилось так, что памяти еще вагон, а адресное пространство уже закончилось.
                0
                По-моему правильнее делать oldCapacity + (oldCapacity >> 1);
                  +4
                  это и есть x1.5
                    0
                    При oldCapacity = 1 отлично сработает
                      –1
                      :-) Отлично! Жаль, поздно плюсик ставить.
                    +1
                    Недавно как раз была статья про fbvector, там подробно объяснялось!
                    +2
                    В чем суть стратегии «увеличивать вдвое»? Почему именно вдвое? Если неизвестно, какие данные записываются и с какой скоростью, непонятно, какой необходим прирост. Есть ли какие-то изыскания по этой теме?
                      0
                      Если мне не изменяет память, то у Кнута (по моему в первом томе в конце) есть пример аллокатора, подбирающего свободный блок за O(1) время. Особенность этого аллокатора была в том, что пространство выделяется размером равным степени двойки. Возможно поэтому повелось удваивать пространство при реаллокации.
                      Кроме того не вижу ни одного повода не удваивать его, ибо если мы удваиваем куски, то теоретически его можно эффективнее менеджить, т.к. любой свободный кусок может быть представлен как 2^n+2^(n-1)+2^(n-2)+...+2^1+2^0 (часть членов может остутсвовать)
                        0
                        Особенность этого аллокатора была в том, что пространство выделяется размером равным степени двойки. Возможно поэтому повелось удваивать пространство при реаллокации.

                        Я наивно думал, что любой аллокатор стремится оперировать блоками размера степени двойки. Более того, точно знаю, что с некоторыми аллокаторами (например, FastMM для Delphi) затребование блоков именно такого размера уменьшает фрагментацию.

                        Кроме того не вижу ни одного повода не удваивать его

                        Размер растет слишком быстро, в итоге получается, что после определенного момента мы для записи лишнего байта будем выделять мегабайты памяти, это неоптимально.
                        Мне кажется, логичным был бы множитель вроде логарифма от какого-то параметра, т.е. крутой рост в самом начале, когда будет много вызовов и более пологий рост в конце.
                          +1
                          Размер растет слишком быстро, в итоге получается, что после определенного момента мы для записи лишнего байта будем выделять мегабайты памяти, это неоптимально.
                          А вы уверены, что менджер памяти не выделяет на самом деле степень двойки, при запросе блока произвольного размера? Я считаю что прежде чем вот так свободно оперировать множителем (мол 1.5х лучше чем 2х) — нужно изучить конкретный аллокатор памяти. Ну и опять же 2x нам обеспечивает значительно меньшую фрагментацию памяти (но за это мы платим оверхедом используемой памяти до 50% в худшем случае).

                          Мне кажется, логичным был бы множитель вроде логарифма от какого-то параметра, т.е. крутой рост в самом начале, когда будет много вызовов и более пологий рост в конце.
                          Не забываем, что при реаллокации может производится копирование, а чаще ёрзать блоком в кучу мегабайт — не самый оптимальный вариант, имхо.
                            0
                            А вы уверены, что менджер памяти не выделяет на самом деле степень двойки, при запросе блока произвольного размера?

                            Зависит от конкретного менеджера памяти.

                            Я считаю что прежде чем вот так свободно оперировать множителем (мол 1.5х лучше чем 2х) — нужно изучить конкретный аллокатор памяти.

                            И я тоже. Странно, что вы мне это пишете.

                            Ну и опять же 2x нам обеспечивает значительно меньшую фрагментацию памяти (но за это мы платим оверхедом используемой памяти до 50% в худшем случае).


                            Значительно меньшую чем при каком выделении?

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

                            Все как всегда — нельзя выиграть одновременно в силе и перемещении.
                        0
                        ну вот совсем недавно писали, что
                        можно математически доказать, что константа 2 — строго худшее из всех возможных значений
                          0
                          Там же были комменты, наполненные куда меньшей категоричностью по данному вопросу. Этот, например.
                      • UFO just landed and posted this here
                          +7
                          Если у вас в 32-х битном приложении массив одним куском размером в 1.5Гб — то у вас явно проблема с архитектурой. Выделять такой кусок памяти — явно не здоровая идея.
                            +1
                            Необходимо выделить, как минимум, 2 буфера под изображение 24576*6000 px. Посоветуете, как мне улучшить архитектуру приложения? </ирония>
                              0
                              Очевидно: пользуйтесь изображениями 245*60
                                0
                                Тайлы? Вы бы всю задачу описали. А то выглядит в духе:
                                > А мне надо пол гига одним куском </конец иронии>
                                  0
                                  Могу ответить за автора. Если у вас какая-нибудь числодробилка или обработка изображений (например, сделать euclidean distance transform с картинкой—да или просто инвертировать биты в изображении), то часто перфоманс будет ограничен скоростью доступа к памяти. Если выделить память под картинку одним куском, то перфоманс вполне может быть в полтора раз больше, чем, к примеру, если выделять массив массивов (потому что у вас в два раза меньше прыжков по памяти) или выделять тайлы (те быстрые алгоритмы EDT, что я знаю, не могут обрабатывать тайл за тайлом). А если это не одна картинка, а тысяча штук таких картинок (реконструкция человеческой почки какая-нибудь для исследований), то обработка в 1,5 раза быстрее очень даже желательна. Так или иначе, выделять одним куском—самая лучшая стратегия с точки зрения производительности (в первом приближении).
                                    +1
                                    В euclidean distance transform перфоманс будет ограничен кеш линией процессора. Тайлы будут эффективнее одного куска. А еще эффективнее тайлы + кривая мортона, ибо в изображении шириной 24576 пикселей кешмиссы будут лететь направо и налево.
                                    Если инвентировать биты — то между тайлами и цельным куском вы без микроскопа не разберете. О полутора раз тут не может быть и речи.

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

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

                                      — что копируется быстрее из одного участка памяти, в другой?
                                      1) данные лежащие последовательно.
                                      2) данные лежащие разрозненно.

                                      — поиск в каком бинарном дереве будет производиться быстрее?
                                      1) в том, в котором узлы лежат в памяти последовательно (дочерние узлы лежат в памяти сразу за родительским).
                                      2) в том, в котором узлы разбросаны по памяти как попало.

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

                                      То есть, если данные у нас в памяти лежат последовательно, то будет больше промахов кэша? Вы серьезно?:)
                                        0
                                        То есть, если данные у нас в памяти лежат последовательно, то будет больше промахов кэша? Вы серьезно?:)
                                        Именно так, только надо был всю мою фразу цитировать. Там был разговор о euclidean distance transform, а эти преобразования предполагают обращение строками выше и строками ниже.
                                        Да и вообще я предлагаю заканчивать ваш троллинг. Почитайте вот тут сначала:
                                        en.wikipedia.org/wiki/Z-order_curve
                                        а еще вот тут хорошее, но тяжелое чтиво:
                                        etd.uwaterloo.ca/etd/wmyee2004.pdf
                                          0
                                          1) Вы, я так понимаю, не в курсе, что в L2 кэш даже старичка Pentium III свободно помещаются от 7 до 21 (в зависимости от битности) строки изображения шириной 24576 px. Что уж говорить о современных процессорах, где появился L3 кэш >= 3Mb. Если данные разбросаны в памяти, вот тогда и имеет смысл говорить о кэш промахах. А когда они лежат друг за другом, то программист сделал все правильно и свел явление Cache Miss к минимуму.
                                          2) Если у Вас заканчиваются контраргументы, это не значит, что Вас троллят.
                                          3) Читал. Не понимаю как эти ссылки доказывают Ваши утверждения или опровергают мои.
                                          4) Привет от SSE/AVX инструкций.
                                            0
                                            1. Интересно, вы слышали про виртуальное адресное пространство? В одной 24576px строке аж 6 страниц памяти. Вы я так понимаю наивно полагаете, что если вы выделили кусок памяти, то он так и лежит в памяти, одним куском. В общем даже не смотря на то, что помещается аж 7 строк — кешмиссы будут значительно чаще. Почему — оставлю вам в качестве домашнего задания. Мне надоело объяснять. Я на современном процессоре получал прирост до 3-4 раз в рендере частиц на CPU используя того же мортона.
                                            2. У меня нет контраргументов к вам, только потому что вы никогда не занимались подобными оптимизациями. Иначе вы бы не говорили такую чушь.
                                            3. Плохо читали. То что я вам дал — показывает как можно оптимизировать данные под кеш, и там нет требований в «одном куске»
                                            4. Да да, кунгфу и еще много страшных слов.
                                              0
                                              1) Более того, я даже про TLB и про блок предсказаний ничего не слышал. Да что там, аппаратный Prefetch для меня пустой звук:)
                                              В общем даже не смотря на то, что помещается аж 7 строк — кешмиссы будут значительно чаще.

                                              По сравнению с чем? Я так и не дождался ответа.
                                              Почему — оставлю вам в качестве домашнего задания.

                                              Нет уж, Ваши домашние задания за Вас я не выполню.

                                              2) Вам видней. Но есть одно НО! Зачем нужен большой кусок памяти и почему архитектура тут не причем, я обосновал, пример привел. Почему работа с последовательно расположенными в памяти данными идет быстрей, выше привел 2 тривиальных примера, которые отвечают на этот вопрос. От Вас в свой адрес я пока слышу только слова о моей не компетентности. Делаем выводы.

                                              3) Под чей кэш? Мы может про разные устройства говорим. Я вот про CPU.
                                              UPD: Даже, специально для Вас нашел перевод. Обратите внимание на «Однопоточный последовательный доступ» и на «Измерение однопоточного доступа, осуществляемого в произвольном порядке».

                                              4) То есть, все таки не поняли намека, и как он связан со всем, что я говорил про выравнивание и последовательность в памяти.
                                                +1
                                                Почему работа с последовательно расположенными в памяти данными идет быстрей

                                                Последовательно расположенными в физической памяти?
                                                  –1
                                                  А Вы умеете выделять физически непрерывную память в user mode? Расскажете как?
                                                    0
                                                    Об этом и речь. Понятно, что TLB. Насколько быстрее работа с последовательными данными именно в виртуальной памяти? Что именно кешируется в L2? Я спрашиваю, без подколок. Интересно же.
                                                      0
                                                      Лучше один раз увидеть, чем сто раз услышать.
                                                        0
                                                        Я переписал Ваш код на C и что меня удивило. Если компилировать без оптимизации — то результат: небольшое отставание когерентного массива.
                                                        sh-4.3$ gcc  -o main *.c
                                                        sh-4.3$ main
                                                        Coherent array avg search - 5187.44 μs
                                                        1048575
                                                        Random array avg search - -4005.54 μs
                                                        1048575
                                                        

                                                        Но при оптимизации (Bang!) Random выхватывает по полной.
                                                        sh-4.3$ gcc -O3 -pipe -fomit-frame-pointer -Wall -Werror -o main *.c
                                                        sh-4.3$ main
                                                        Coherent array avg search - 2837.95 μs
                                                        1048575
                                                        Random array avg search - 4514.26 μs
                                                        1048575
                                                        

                                                        И это ещё не самое главное. При ещё большем ускорении ситуация для Random только хуже (Тарарах-тах-тах!):
                                                        sh-4.3$ gcc -march=native -O3 -pipe -fomit-frame-pointer -Wall -Werror -o main *.c
                                                        sh-4.3$ main
                                                        Coherent array avg search - 2686.56 μs
                                                        1048575
                                                        Random array avg search - 4637.16 μs
                                                        1048575
                                                        

                                                        Прикол в том, что, чем сильнее оптимизация тем сильнее замедляется Random и сильнее ускоряется Coherent. Ну и ну. Хотел бы я знать про эти подводные камни.
                                                        Вот код.
                                    0
                                    Такие требования — данность. И не важно какая архитектура всего приложения. Необходимо просто выделять буферы большого размера для хранения и обработки изображений в режиме реального времени(двойная буферизация: один обрабатывается, другой заполняется). Как и сказал Bas1l, такой буфер выделять лучше в непрерывной памяти, а также необходимо, чтобы адрес был выровнен (2 профита — данные в кэше + скорость выполнения машинных инструкций на кратных адресах).
                                    Я это все к тому, что не всегда верно утверждать —
                                    Если у вас в 32-х битном приложении массив одним куском размером в 1.5Гб — то у вас явно проблема с архитектурой.
                                      +1
                                      Такие требования — данность. И не важно какая архитектура всего приложения. Необходимо просто выделять буферы большого размера
                                      Вы задачу можете привести в пример? Задачу которая требует одним куском такой буфер. А то пока только аргумент «а мне нужно». Двойная буферизация — не аргумент. Храните оба буфера как тайлы 512*512, какие проблемы?
                                      Есть куча возможностей работать с огромными данными. Винда вон например маппит адресное пространство. Так что я не верю в такую данность.
                                        0
                                        То есть, фраза
                                        буферы большого размера для хранения и обработки изображений в режиме реального времени

                                        для Вас не пример?:) Хорошо, распишу подробней.

                                        Необходимо в режиме реального времени обработать изображение, которое приходит с N камер. Конечное изображение получается «склеиванием» кадров со всех камер. В зависимости от количества камер и их разрешения, может получится изображение 24576*6000, а может и больше. Время на обработку данного изображения ~200мс. Какого рода обработка? Буду краток — сложные алгоритмы и их много.

                                        Вангую, сейчас будет вопрос, почему эти 2 буфера должны быть в непрерывном куске памяти:)

                                        <ирония>Так Вы что-то говорили про тайлы и маппинг?</ирония>
                                          0
                                          Ну что могу сказать… просто не используйте realloc и буфер динамического размера. Вы ведь сразу знаете требуемый размер выходного буфера?
                                0
                                В худшем случае все стратегии, кроме экспоненциальных, дают квадратичную сложность, к сожалению.
                                +7
                                Лень!
                                  +3
                                  Отсталость только подумать как код с realloc() будет работать в случае OMP_NUM_THREADS>1 на современном 12-корнике например.

                                  Only users with full accounts can post comments. Log in, please.