Собрал подборку самых отслеживаемых сериалов в 2016 году, по результатам работы Swatcher_bot.

Обратил я тут внимание на то что архивирование в Linux через tar занимает только одно ядро и решил поискать как это можно исправить и утилизировать все 4 ядра своего процессора.

В мануале по tar я нашел такую опцию:

-I, –use-compress-program PROG
filter through PROG (must accept -d)

А поиск по интернету выдал мне многопоточные архиваторы:

• gz:   pigz
• bz2: pbzip2
• xz:   pxz

Установить все три можно в Ubuntu командой:

sudo apt-get install pxz pigz pbzip2

Команды для архивации:

• gz:   tar -czf tarball.tar.gz files
• bz2: tar -cjf tarball.tar.bz2 files
• xz:   tar -cJf tarball.tar.xz files

Команды для разархивации:

• gz: tar -xzf tarball.tar.gz
• bz2: tar -xjf tarball.tar.bz2
• xz: tar -xJf tarball.tar.xz

А теперь параллельная версия архивации:

• gz:   tar -I pigz -cf tarball.tar.gz files
• bz2: tar -I pbzip2 -cf tarball.tar.bz2 files
• xz:   tar -I pxz -cf tarball.tar.xz files

И разархивации:

• gz:   tar -I pigz -xf tarball.tar.gz
• bz2: tar -I pbzip2 -xf tarball.tar.bz2
• xz:   tar -I pxz -xf tarball.tar.xz

Воспользуюсь исходниками ядра Linux версии 4.15 буду архивировать и разархивировать на M.2 SSD диске используя CPU Intel(R) Core(TM) i5-6200U CPU @ 2.30GHz 4 cores, 4 threads, 8Gb RAM

Время архивации(больше проверять не вижу смысла):

.                                    gzip           bzip2                 xz
Однопоточное          26.409s    1m23.939s    6m43.628s
Многопоточное        10.048s      34.784s       2m45.230s

Решил я тут разобраться с атомарными командами, что это такое, какими они бывают и что делают. В целом если объяснять на пальцах, то атомарные или неделимые операции, как следуют из названия, неделимые. Т.е. команда либо еще не выполнена, либо уже выполнена, мы не сможем застать эту операцию в середине процесса. Естественно это реализуется за счет аппаратной поддержке. И у разных архитектур эти команды могут и отличаются, но что бы с вами не зарывались в спецификациях разработчики компиляторов унифицировали работу с этими операциями, описание всех команд можно найти в документации к компилятору(например gcc).

Читая эту документацию и разбираясь с тем как все это работает, мне пришла в голову идея легкого spinlock’a на атомарных функциях. В чем же легкость этого spinlock’a относительного того же mutex’a?! Легкость заключается в том что эта блокировка не приводит к системному вызову, как например блокировка mutex’a.

Итак для создание легкого spinlock’a в userspace нам потребуются 2 функции:

• bool __atomic_test_and_set (void *ptr, int memorder)
• void __atomic_clear (bool *ptr, int memorder)

__atomic_test_and_set — устанавливает байт *ptr в некое предопределенное значение ‘set’. Функция вернет true только в том случае если байт *ptr до этого уже находился в состояние ‘set’, иначе функция вернет false. Функцию стоит использовать только с типами char и bool, иначе *ptr будем модифицировано только частично.

__atomic_clear — функция сбрасывает байт *ptr в 0.

int memorder переменная обозначающая используемый способ упорядочения памяти. Это отдельная, довольно обширная тема барьеров памяти разбирать которую в рамках этой статьи я не буду, нам вполне значение по умолчанию __ATOMIC_SEQ_CST, самый строгий ordering. Хотя, если я правильно понял принципы memory ordering’a, то можно использовать более оптимальный Acquire/Release memory ordering.

Теперь сами функции:

void spinlock_lock(bool *lock)
{
    /*
     * Крутимся в цикле(spinlock же) пока функция не вернет false,
     * что будет означать что мы захватили блокировку
     */
    while(__atomic_test_and_set(lock, __ATOMIC_SEQ_CST) != false);
}

void spinlock_unlock(bool * lock)
{
    __atomic_clear(lock, __ATOMIC_SEQ_CST);
}

Ничего сложного. Не требует подключения дополнительных заголовочных файлов.

Продолжаю записи про язык программирования С, точней про различные структуры и простейшие алгоритмы. Следующей в очереди идет быстрая сортировка, вот что о ней пишут в википедии:

Быстрая сортировка, сортировка Хоара (англ.quicksort), часто называемая qsort (по имени в стандартной библиотеке языка Си) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем обменов при упорядочении элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.

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

Вот собственно вся функция сортировки массива целых чисел(int):

void swap(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void quick_sort(int *s_arr, int first, int last)
{
	int i = first, j = last, x = s_arr[(first + last)/2];

	do {
		while(s_arr[i] < x) i++; while(s_arr[j] > x) j--;

		if(i <= j) { if(s_arr[i] > s_arr[j])
				swap(&s_arr[i], &s_arr[j]);
			i++;
			j--;
		}
	} while(i <= j);

	if(i < last)
		quick_sort(s_arr, i, last);
	if(first < j)
		quick_sort(s_arr, first, j);
}

Следующим за поиском в глубину идет поиск в ширину или BFS. Так как и в случае поиска в глубину, реализация будет итеративной, с использованием реализованной ранее очереди.

Немного инфы из вики:

Поиск в ширину (англ. breadth-first search, BFS) — метод обхода графа и поиска пути в графе. Поиск в ширину является одним из неинформированных алгоритмов поиска^[1].

Будем использовать структуру данных из прошлого поста:

typedef struct tree_node {
    /* указатель на левую вершину */
    struct tree_node * left;
    /* указатель на правую вершину */
    struct tree_node * rigth;
    /* указатель на хранимые в вершине данные */
    void *data;
    /* необходимая при обходе пометка */
    int mark;
} tree_node_t;

Так же нужно определить указатель на функцию которая быдет вызывается для обработки данных находящихся в обрабатываемой вершине.

typedef void (*visit_node_f)(tree_node_t *node, void *visit_data);

Т.е. нам нужно определить функцию которая будет проводить некоторые манипуляции с данными хранимыми в вершине tree_node_t *node, а void * data будет расшариваться между всеми вызовами, например в нем можно сохранить счетчик или еще что-нибудь что может пригодиться при обработке данных.

А теперь сам алгоритм:

void bfs(tree_node_t * root, visit_node_f node_function, void *visit_data)
{
    list_t *st = create_list();

    list_push_back(st, root);

    /* Посещаем корневую вершину */
    (*node_function)(root, visit_data);
    root->mark = 1;

    while(st->size != 0) {
        tree_node_t * node = (tree_node_t *)list_pop(st);

        if(node->left != NULL && !node->left->mark){
            list_push_back(st, node->left);
            /* посещаем левую вершину */
            (*node_function)(node->left, visit_data);
            node->left->mark = 1;

        }

        if(node->rigth != NULL && !node->rigth->mark){
            list_push_back(st, node->rigth);
            /* посещаем правую вершину вершину */
            (*node_function)(node->rigth, visit_data);
            node->rigth->mark = 1;
        }
    }
}

Вот и все.