amarao (amarao_san) wrote,
amarao
amarao_san

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;
}
Tags: lstorrent
Subscribe

  • 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.
  • 8 comments