Где хранится структура файловой системы?

Я это к тому веду, что хотя задачу построения списка распараллеливать не нужно (нет профита), но вот задачу сортировки - можно и нужно.

То есть добавлять файлы в связный список/массив указателей на строки из одной нити и сортировать его из параллельной нити по мере необходимости? Есть какие-то алгоритмы на эту тему?

а что не /usr/ Не дождался?

Ну usr уже кешировался когда я find показывал. find и ls -R на /usr у меня за одно время отрабатывают. ls -U - раз в 100 быстрее.

алиас на sudo сам придумал?

Тут это не обязательно, просто привычка - перенаправления вроде sudo cat foo > /root не работают.

Что не устраивает в стандартных утилитах find|sort ?

bin/ls/ls.c из BSD довольно наглядно сделана, там fts(3). В GNU coreutils несколько посложнее.

То есть добавлять файлы в связный список/массив указателей на строки из одной нити и сортировать его из параллельной нити по мере необходимости? Есть какие-то алгоритмы на эту тему?

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

find и ls -R на /usr у меня за одно время отрабатывают. ls -U - раз в 100 быстрее.

у меня примерно также.

Тут это не обязательно, просто привычка - перенаправления вроде sudo cat foo > /root не работают.

это я ошибся. думал, у вас sudo время показывает...

ну либо добавлять, либо сортировать на месте.

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

_многопроцессорный_

NUMA?

у меня примерно также.

Попробовал на хомяке - find даже дольше.

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

мои поздравления: вы изобрели сортировку слиянием. http://ru.wikipedia.org/wiki/Сортировка_слиянием

Хотя лучше прочитать не вику, а купить книжку: Knuth D.E. The Art of Computer Programming. Volume 3: Sorting and Searching. — 2nd. — Addison-Wesley, 1998. — P. 159. — ISBN 0-201-89685-0 (есть по-русски)

NUMA

не. Просто несколько CPU со _своей_ памятью. Вот там это действительно даёт выигрыш - делим список на M частей, и сортируем. Потом сливаем результаты. Такие мамки раньше делали, до многоядерных CPU. Туда и памяти можно было навтыкать побольше(ограничение было всегда). Сейчас не знаю.

А на многоядерных мамках выигрыш невелик.

мои поздравления: вы изобрели сортировку слиянием.

Не вижу ничего общего. Я говорил про new_sorted_data = insert(new_element, old_sorted_data), которое будет делать вторая нить, получая при этом new_element (путь, какие-то индексы директорий) из queue - new_element = get_next_from_queue(shared_queue), класть new_element в queue будет первая нить - put_to_queue(shared_queue, new_element), shared_queue - конкурентная структура данных.

так ещё более непонятно. но в целом я понял: т.е. одна нить обходит каталог, вторая нить вставляет в отсортированный список. Если так, то такой метод нам НЕ подходит. Проблема в списке:

1. если это массив, то для вставки туда нужно сдвинуть O(N) эл-тов. Общая сложность O(N*N)

2. если это список, то для вставлять быстро, искать куда - медленно. тоже O(N*N)

3. с деревом O(log(N)) но константа пропорциональности чудовищно велика, этож надо спустится на 19й уровень в поисках узла, потом подняться к корню по пути исправляя структуру... Жуть, сортировать намного быстрее, уверен, что раз в 100, и при этом те же O(N*log(N)).

Узкое место у нас сортировка, я проверял (как-то выполнил ls от 100К файлов. Устал ждать... Не дождался, почитал ман, узнал про -U). Однако на малом числе файлов это незаметно. Всё дело в том, что время чтения O(N), потому на наборе 1000К файлов сортировка будет в 20 раз дороже, чем она была дорога на маленьких наборах по сравнению с чтением.

Если так

Так. То есть не существует структуры данных с очень быстрой insert поддерживающей порядок?

Так. То есть не существует структуры данных с очень быстрой insert поддерживающей порядок?

старые маразматики типа меня и Кнута о таких не в курсе.

Есть ещё хешированные списки, вот там всё отлично. Только одна беда - они не дают ПОРЯДОК. Точнее дают, но СВОЙ, не тот, который нам нужен. Именно такой способ и используется в EXT2/3/4 - мы быстро находим нужный файл, вот только если нам понадобится _упорядоченный_ список, то приходится сортировать. Т.е. fs хеширует имена, и потом их ищет в дереве отталкиваясь от хеша. Это очень быстро и хорошо для одного файла, но для выборки от..до, и для полного списка - не пойдёт.

Ну и кроме того, есть ещё проблема в utf-8, если сортировать в ней, то время сортировки возрастает ещё в 2..20 раз. ИМХО тут уже будет выигрыш для многоядерных устройств. Если-бы в этом был какой-то практический смысл, я-бы проверил.