November 29th, 2009

404

lstorrents

Итак, что успешно:
Обычные мелкие торренты (ещё надо допроверять)
Everything.torrent
Кстати, к ворпосу о том, почему не питон:

 time ./test samples/Everything.torrent >/dev/null

real	0m0.383s
user	0m0.044s
sys	0m0.336s

./test samples/Everything.torrent |wc -l
10113


А вот easy_john подложил мне свинью под названием TOSEC Unpack.torrent

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

После того, как я прибил на машине дигикам, объём выделенной памяти догнался до 2.7Гб (хехе, на i386 такого бы не получилось :)

Ща прибью оперу и прочий хлам, посмотрю, сколько максимум оно отъест. //VSIZE 143Gb и рост со скоростью 200Мб/с; RSIZE 3.7Gb.

Но проблему надо фиксить...
404

lstorrent

Изин торрент мне открыл глаза на кривость prealloc словарей. Особенно, если вы хотите открыть (MAX_RECORDS)^4 словарей...

Переделываю в старые-(не)добрые списки.

или оставить массивом с realloc? Дилемма. Помнится, когда я над этим заморачивался, лучшее моё изобретение было цепочкой массивов. Т.е. с одной стороны динамический список, с другой - каждый элемент динамического списка (с указателем next*) содержит в себе массив элементов (так увеличивается скорость и уменьшаются накладные расходы на указатель).

Примерная оценка: если у нас будет торрент с кучей мелких файлов, размером 15Мб, при размере строки с именем в 16 байт (1 байт размер, 1 байт двоеточие, 8 байт строка, 6 байт 'path'), то мы будем иметь (за вычетом ерунды вокруг), 10 байт на файл, ещё, допустим, 10 байт на размер (length:i10d). Итого 20 байт на запись о файле. Это примерно 700000 строк. Для запаса поставим, что нам надо обработать не менее миллиона записей.

Структура, которая это будет хранить:
typedef struct{
    enum type_e type;
    union{
        long long num;
        unsigned char* str;
        struct dict_s* dict;
        struct list_s* list;
    };
}item_t; - 4+8 = 12 байт. (заметить тип на чар? 3 байта экономии...)

для строки, дополнительно, нам надо иметь саму строку +1 байт, для числа - +0.

если мы делаем list_t таким:
typedef struct list_s{
    list_t* next;
    item_t* item;
}list_t;

то мы имеем 16 байт.

Словарь:
typedef struct dict_s{
    item_t* key;
    item_t* value;
    dict_t* next;
}dict_t;

даст нам ещё 24 байта. Итого на файл: 13+12+24+16=65+len(str)

Для миллиона файлов с именем в 8 символов это 73 мегабайта. Если же в действии будет выравнивание по словам, то это даст нам минимум 128Мб, если не больше.

Если мы заменяем next на массив с индексным указателем, то оверхед уменьшается (хотя не так сильно, как хотелось бы). Во-первых, мы имеем необходимость хранить count в dic_t/list_t, что даст нам всего 4 байта экономии на каждом list/dict. В принципе, вот она, экономия: 8 мегабайт. Заметим, цена этой экономии - realloc. Если же мы делаем компромисс с превыделенным массивом, то это приводит к проблеме перебора по памяти (90% словарей в 1 элемент размером).

Так что не маяться дурью и делать списки, как учили на первом курсе. А вот байтики с type можно и подэкономить...


Теперь относительно возможности "не грузить" всё это в память. Она сильно осложнена: 'name' хранится где-то ближе к концу списка файлов (читай, в середине). Таким образом, чтобы нормально вывести список файлов, мы должны сначала дойти до 'name', потом вернуться назад и выводить имена файлов Несколько сиков по файлу туда/сюда... Плюс - отсутствие необходимости хранить это в памяти (т.е. получающийся парсер отработает и гиговый торрент без особых напрягов). Минус - скорость, т.к. вместо одного могучего fread() мы получаем кучу мелких fread в рандомном порядке. Ещё один плюс - pieces в память вообще не грузится.

Есть, конечно, третий вариант, это "умная" версия bdecode, которая роет только то, что нужно, т.е. парсер, который работает не на уровне представления, а на уровне приложения (у меня пока один такой хак, это дроп 'pieces', который содержит SHA-хэши). С тем же успехом я могу пытаться выгрызать только имена файлов, без создания паразитных словарей... Но этот путь мне не нравится.

PS, Да, ещё, важный момент. Если мы делаем адекватный по скорости список/словарь, то надо решить, как добавлять элементы.

Быстрее всего добавлять элементы в начало списка/словаря (но тогда мы получаем обратный порядок). Можно сделать линк на хвост - но это увеличит затраты памяти (+16 байт на файл, т.е. +16Мб на миллион файлов)...

Пока делаю с обратным порядком.

Ни у кого примера быстрого и нежручего FIFO списка нет?

... Упс, я забыл, что для path order matter... Надо думать. Тогда, list получается двунаправленный. Добавляем в прямом порядке, читаем в обратном. +8Мб на миллион файлов.

Нет, лист всё-таки однонаправленный, но мееедленный... Надо думать.

Всё, придумал:
typedef struct list_s{
    union{
        item_t* value;
        list_t* last; /*last filled only for first element of list, so, actual value will be stored starts from second element*/
    }
    list_t* next;

}list_t;


Интересно, как такое называется?

PPS

Изящно получается. Всё апи:

list_t* new_list(){
    list_t* newlist=calloc(1,sizeof(list_t));
    if(!newlist)
        oops(err_nomem);
    return newlist;
}

void add_to_list(list_t* list, item_t* item){
    list_t* newlist=malloc(sizeof(list_t));
    if(!newlist)
        oops(err_nomem);
    list->last->next=newlist;
    list->last=newlist;
    newlist->value=item;
}
404

lstorrent

Мухаха!

Изин торрент не выдержал списков!

./test samples/TOSEC\ Unpack.torrent |wc -l
55465

 time ./test samples/TOSEC\ Unpack.torrent >/dev/null

real	0m0.167s
user	0m0.132s
sys	0m0.036s

 time ./test samples/Everything.torrent >/dev/null

real	0m0.050s
user	0m0.036s
sys	0m0.016s



В пике потребление (в дебаг-режиме) - 44Мб. ИМХО для 7.5Мб торрента с 55.5тыс файлов - вполне разумно.

(хотя мне не нравится масштабирование этого. 550тыс. файлов - 440Мб, миллион файлов - 880Мб...)

Сейчас напишу тестсьют на миллион файлов. Заодно потестим некоторые торрент-клиенты на способность такое съесть...

За вычетом памяти, 0.1-0.3с на торрент... Мне это нравится.
404

free

Я так и думал, что будет какая-нибудь херня. При попытке добавить free (то бишь написать del для всех данных) оно где-то падает с ошибкой сегментирования. В упор не понимаю где и почему... Такое ощущение, что где-то прихватываю лишнюю память при free(). Если free убрать, то всё работает на ура.
404

ура

Нашёл. Неинициализированная память, так что однократный free кому-то там сносил крышу.
$time ./test /srv/anime/torrents-archive/* >/dev/null

real	0m0.007s
user	0m0.004s
sys	0m0.000s
$ls -1 /srv/anime/torrents-archive/*|wc -l
71


Ещё один комплект торрентов (который в составе Minitokyo\ Backup\ 01-01-2008)

./test /srv/anime/anime/in/Minitokyo\ Backup\ 01-01-2008/*.torrent|wc -l
118111
 time ./test /srv/anime/anime/in/Minitokyo\ Backup\ 01-01-2008/*.torrent>/dev/null

real	0m0.471s
user	0m0.412s
sys	0m0.060s


http://desunote.ru/pub/Minitokyo%20Backup%2001-01-2008/

(все торренты оттуда)

Ща пойду делать торрент на миллион файлов...
404

1000000

Хе, торрент на миллион файлов больше 30Мб в размере.

Надо (для престижу) поднять квоту по размеру файла до 40Мб... Ща делюга мучается, делает. Я почти на 100% уверен, что она его не откроет потом... :-/

Он доделался.

./test ~/example.torrent |wc -l
1000000
amarao@desunote:~/prg/lstorrent$ time ./test ~/example.torrent >/dev/null

real 0m2.954s
user 0m2.544s
sys 0m0.388s

Память: 648Мб.

Для сравнения, питоновский скрипт:

(постили в комментах только что)

real 0m20.575s
user 0m20.073s
sys 0m0.488s

Пик по памяти - 640-670Мб (мне его трудно поймать, потому что куча прыгает всё время).

PS Всем любителям ронять торрент-клиенты: http://desunote.ru/pub/example.torrent
PPS rtorrent рулит - всего гиг памяти и торрент в работе. deluge умирает с двумя с гаком гигами... У кого есть мюторрент, проверьте?
404

wa

Насколько я понимаю, в этом году, кроме зетсубо (сваливающегося в безнадёжность), ничего хотя бы чуть-чуть близкого к wa нам не показали?

Хотя нет, вру. Был Sowa wo kakeru Shoujou, который забылся чуть быстрее, чем посмотрелся...
404

(no subject)

Начал пересматривать Гуу.

Да, тогда не теперь. Теперь такого больше не делают. Эх.
404

хехе

Всего лишь заменил 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-битными, то тогда два счётчика займут столько же, сколько и один указатель, т.е. всегда будут "не хуже". Единственным исключением будет чуть более медленный доступ к первым элементам списков. Но, всё это окупится огромной экономией памяти на "списке-миллионнике".