amarao (amarao_san) wrote,
amarao
amarao_san

хехе

Всего лишь заменил dict(item_t:item_t) на dict(str:item_t) - итог (на example.torrent) (-0.5c)

real 0m2.432s
user 0m2.104s
sys 0m0.320s

пик по памяти - 550Мб. (-90Мб)

Это даёт мысль о том, что в существующей структуре слишком много указателей...

Следующая мысль: можно расформировать вообще item_t, как бы оно соблазнительно не было, и заменить


struct{
    enum type;
    union{
        int
        char*
        dict*
        list*
    }
}item_t;

struct {
    char* key;
    item_t* value;
     dict_t* next;
}dict_t;

на 

strcut{
    char* key;
    union {
        int;
        char*;
        dict*
        list*
    }
}dict_t;

(и аналогично list_t*)

Очевидная экономия - 8 байт на каждом элементе списка/словаря, т.е. минимум 32Мб, а то и больше (можно даже апроксимировать - замена item_t* на str* дала 90Мб, так что тут мы получим сильно больше 90Мб....)

И второе (раз уж рефакторинг делать буду) - realloc и массивы.

О, придумал, чтобы не ломать абстракцию, в dict_t должно быть не item_t *, а просто item_t (и копирование).


... А вот с массивами всё не так уж просто...

Куча массивов имеет размер 1-6 элементов. Т.е. для них counter и max_allocated (2 слова) дадут очень приличный оверхед. Больший, чем один указатель.

Однако, Будет ОДИН (единственный) список, у которого будет МНОГО элементов. Можно, конечно, под него подстелиться особым образом... Но пока оставим это на состоянии указателей...


Ну, и, наконец, ультимативный метод экономии...

У нас ЕСТЬ уже все данные в памяти. Те самые 40Мб торрент-файла. Что мешает построить к этому _индекс_ вместо копирования данных в структуры? Ну, в принципе, не очень приятно видеть Pstring'и. Но терпимо.

Индекс будет состоять из двух цифр: смещение (смело можем делать 32 бита) и размер (аналогично). По сути - это размер одного указателя.

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

Что должно быть в индексе?

1) Отношение вложенности элементов. //проблема в том, что вложенные элементы - переменного размера.
2) Указание на содержимое элементов. //с этим проблем нет.

Индекс будет построен всё-таки не в массиве, а в виде дерева, отображающего файл. Элементы str и num представляют собой указатели на на области в оригинальном буффере. Типы dict и list хранятся в новых структурах.

Подобная обработка, кстати, сильно ускорит парсинг, так как лишние данные можно будет не перекладывать ещё раз, а строки вообще будут пропускаться не будучи прочитанными (до момента, пока их не нужно будет вывести на самом деле).

Экономия памяти явно видна, однако, мне всё ещё не даёт покоя проблема больших/малых списков.

Очевидно, что для малых списков malloc окупится за список из 2х элементов (2 указателя вместо счётчика). Если же счётчики сделать 32-битными, то тогда два счётчика займут столько же, сколько и один указатель, т.е. всегда будут "не хуже". Единственным исключением будет чуть более медленный доступ к первым элементам списков. Но, всё это окупится огромной экономией памяти на "списке-миллионнике".
Tags: lstorrent
Subscribe

  • systemd-networkd, netlink и arp флуд

    Нереально странный баг пофикшен с помощью eBPF затычки. Для меня большой неожиданностью является реакция на него.…

  • Rust soundness

    Каждый раз, когда я сталкиваюсь с маленькими "но" в Rust'е, это ощущение тщательной продуманности. Например, простейшие fold-функции для итераторов:…

  • still_ntp

    В ходе локального мозгового штурма у меня родилась суперидея. Надо написать ntp сервер, который может отдавать указанную дату. Т.е. сказали при…

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 2 comments