Oberon space

Она 64 разрядная, но другой архитектуры http://www.tilera.com/

Кто нибудь префетчем памяти пользовался для оптимизации быстродействия?

На x64 это:

#include <xmmintrin.h>

_mm_prefetch(pointer, flags)

Я попробовал -- охрененно термоядерная штукенция. Загрузка данных из DDR3 1600 в кэш процессора отнимает примерно 80 наносекунд. Это около 300 тактов ничегонеделания. Если знаешь наперёд какие данные понадобятся в будущем, то заранее говоришь процу чтоб он загрузил их в кэш. Программа реально в несколько раз быстрее начинает работать.

Вчера случайно узнал о существовании дневника Чокнутого Доктора (была ссылка на форумах dxdy), почитал немного. Он жжёт ядерным напалмом:

http://vteninn.livejournal.com/48306.html

[словарь] войлок (приматол.); лупанистические сети

vteninn
24 июня, 2012
Где:всё там же
Настроение:допишем и отдыхатеньки
Хойрос -- простейший тип лупанистических формаций внутринаучного Приматического Элемента.

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

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

Однако есть ещё один тип лупанистических формаций:

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

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

***

Важная приматологическая деталь механизма формирования войлока (приматол.):

Гонорит т.наз. организаторов науки, положительно коррелирующий со степенью их всплытия, способствует формированию горизонтальных дружбанско-лупанистических связей в каждом слое:
(взаимное) уважительное выделение своих гомологов среди прочих — это лишь простая психологическая проекция вовне ожиданий в отношении себя любимых.
[Upd 2014-09-20: это не что иное как стайная разновидность мастурбации гонорита.]

А в целом следует признать, что приматические иерархические структуры, паразитирующие на Науке, как внешние, так и внутренние, подлежат уничтожению.
Метки: Словарь, войлок, лупанизм

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

for (int j = 0; j < 100; j++)
{
    a[j] = arena.allocate();
}

есть над чем призадуматься.

Можно, например, кэшировать несколько тысяч (2048) указателей в небольшом массиве в arena, а остальные миллионы указателей оставить в списке.

С другой стороны у нас такого кода то, вообще-то, не будет. Мы будем аллоцировать 1 объект, чего-то с ним делать. К моменту когда понадобиться аллоцировать следующий объект в L1/L2 кэше от данных arena скорее всего ничего и не останется. А значит при поштучном аллоцировании выгоды не будет.

Значит, я правильно понял. И нюанс здесь в том, что сначала мы вычитываем пустой блок, заполняем его и записываем обратно. Хотя ничего не мешает просто записать данные по заранее известному адресу. Со связным списком сразу записывать не получится: по адресу, по которому мы хотим записывать, находится адрес очередного блока.

Я бы адреса свободных блоков хранил отдельно. Например, в стеке. Даже если потребуется этот стек хранить в тех же самых блоках.

Ниже простая арена выделяющая память блоками по 64 байта. Список свободных блоков реализован на памяти самих же свободных блоков. В какой строчке происходит лишнее чтение блока?

class Arena
{
    struct Block
    {
        Block* next;
        uint8_t appendix[56];
    };

    Block* first;

public:
    Arena (uint8_t* memory, size_t size)
    {
        // Нарезаем память на куски по sizeof(Block),
        // организуем их в список,
        // указатель на первый - first
    }

    inline void* allocate ()
    {
        if (first != 0)
        {
            void* p = first;
            first = first->next;
            return p;
        }
        return 0;
    }

    inline void free (void* p)
    {
        ((Block*)p)->next = first;
        first = ((Block*)p);
    }
};

Спасибо ответившим!

Вобщем, я пока склоняюсь к следующему частному компромисному решению...

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

Когда запрашивается 64 байта, тогда выдаётся элемент из списка 64-байтных, а когда этот список становится пустым, то, скрипя зубами, выдаётся, отрывается от сердца, элемент из списка 128 байтных блоков.

Как то так (число 48Mb взято просто для примера):

Когда указатель на 64 байтный объект возвращается, то одной проверкой if (p < 48Mb) выясняется кто он на самом деле: истинный 64 байтный или 128 байтовый. Соответственно, ставится в список свободных 64 или 128 байтных блоков.

Оптимальный размер памяти отдаваемый под 64 байтные объекты надо будет выяснить экспериментально.

Почему так, а не иначе:
 1) Есть жёсткое ограничение на количество обращений к DDR3 памяти (пропускная способность контроллера памяти является "бутылочным горлышком" для нашего программного продукта).
 2) Аллокация/деаллокация 64 байтных блоков происходит на порядок чаще чем 128 байтных.
Поэтому приходится отказываться от алгоритмов делающих слияние свободных блоков 64+64=128.

Если кто нибудь придумает как ещё больше сэкономить память не слишком сильно замедляя алгоритм, то это будет круто...

Пока есть идея размещать объекты размером Q с одной стороны имеющегося куска памяти, а размера 2*Q с другой стороны.



При деаллокации "крайние" блоки можно возвращать обратно в "общую сырую память". А "некрайние" блоки ставить в список неиспользуемых (связный список организовать разумеется на самих же неиспользуемых блоках).


Не понятно как эффективно возвратить в "общую сырую память" более одного блока...