Самый быстрый C-код для подсчета рекурсивных каталогов в Linux (без файлов) - PullRequest
Новая
       29

Самый быстрый C-код для подсчета рекурсивных каталогов в Linux (без файлов)

0 голосов
/ 28 июня 2019

Следующий код на C перечислит количество файлов и каталогов и сделает это в 4 раза быстрее, чем команда linux find.Мне нужен только подсчет папок, не интересует подсчет файлов и даже распечатка их.Есть ли способ оптимизировать приведенный ниже код и сделать его более эффективным?

#include <errno.h>
#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#include <unistd.h>
#include <dirent.h>

void listdir(char *path, size_t size) {
    DIR *dir;
    struct dirent *entry;
    size_t len = strlen(path);

    if (!(dir = opendir(path))) {
        fprintf(stderr, "path not found: %s: %s\n",
                path, strerror(errno));
        return;
    }

    puts(path);
    while ((entry = readdir(dir)) != NULL) {
        char *name = entry->d_name;
        if (entry->d_type == DT_DIR) {
            if (!strcmp(name, ".") || !strcmp(name, ".."))
                continue;
            if (len + strlen(name) + 2 > size) {
                fprintf(stderr, "path too long: %s/%s\n", path, name);
            } else {
                path[len] = '/';
                strcpy(path + len + 1, name);
                listdir(path, size);
                path[len] = '\0';
            }
        } else {
            printf("%s/%s\n", path, name);
        }

    }
    closedir(dir);
}

int main( int argc, char *argv[] ) {

   if( argc == 2 ) {
      printf("Path:  %s\n", argv[1]);
   }
   else if( argc > 2 ) {
      printf("Too many arguments supplied.\n");
   }
   else {
      printf("One argument expected.\n");
      return 0;
   }
    char path[1024];
    memcpy (path, argv[1],1024);
    listdir(path, sizeof path);
    return 0;
}

Удаление следующих строк, конечно, не отобразит файлы, но не ускорит время выполнения: 

} else {
            printf("%s/%s\n", path, name);
        }

1 Ответ

5 голосов
/ 28 июня 2019

Если вы не заинтересованы в печати имен файлов, просто удалите операторы printf.

Обратите внимание, что в коде есть некоторые проблемы:

  • memcpy(path, argv[1], 1024);может читать за концом строки, на которую указывает argv[1], что является неопределенным поведением, или не производить правильную строку C, что приводит к неопределенному поведению в функции listdir.

Youможно также избежать повторного вычисления длины имени каталога в каждом рекурсивном вызове.

Вот измененная версия, которую вы можете попробовать: 

#include <errno.h>
#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#include <dirent.h>
#include <unistd.h>

long long countdirs(char *path, size_t size, size_t len) {
    DIR *dir;
    struct dirent *entry;
    long long count;

    if (!(dir = opendir(path))) {
        fprintf(stderr, "path not found: %s: %s\n",
                path, strerror(errno));
        return 0;
    }

    count = 1; // count this directory
    while ((entry = readdir(dir)) != NULL) {
        if (entry->d_type == DT_DIR) {
            char *name = entry->d_name;
            size_t len1 = strlen(name);
            if (*name == '.' && (len1 == 1 || (len1 == 2 && name[1] == '.')))
                continue;
            if (len + len1 + 2 > size) {
                count++;
                fprintf(stderr, "path too long: %s/%s\n", path, name);
            } else {
                path[len] = '/';
                memcpy(path + len + 1, name, len1 + 1);
                count += countdirs(path, size, len + 1 + len1);
                path[len] = '\0';
            }
        }
    }
    closedir(dir);
    return count;
}

int main(int argc, char *argv[]) {
    char buf[4096];
    char *path;
    size_t len;

    if (argc != 2) {
        fprintf(stderr, "one argument expected.\n");
        return 1;
    }
    path = argv[1];
    len = strlen(path);
    if (len >= sizeof(buf)) {
        fprintf(stderr, "path too long: %s\n", path);
        return 1;
    }   
    memcpy(buf, path, len + 1);
    printf("%s: %lld directories\n", path, countdirs(buf, sizeof buf, len));
    return 0;
}

Дополнительные примечания:

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

  • Вам следует попробовать альтернативный подход, используя стандартную функцию POSIX nftw(), как описано в этом ответе: https://stackoverflow.com/a/29402705/4593267

  • В соответствии с предложением EOF , поскольку пути не используются, их построение не требуется.Может быть безопаснее и эффективнее использовать openat() и fdopendir().(задокументировано здесь: https://pubs.opengroup.org/onlinepubs/9699919799/functions/open.html https://pubs.opengroup.org/onlinepubs/9699919799/functions/fdopendir.html).

  • Нет особого смысла в оптимизации этой функции, так как большая часть времени проводится в ОС или в ожиданиидля запоминающего устройства.Эффект кэширования файловой системы может быть огромным: я измерил 15x на linux для 133000 каталогов.Использование другого набора системных вызовов может улучшить или ухудшить скорость, но небольшие улучшения, вероятно, сильно зависят от системы.

...