☰

Leer una copia de `/usr/share/dict/words` es 10 veces más lento que el archivo mismo

tag-icon • tag-icon linux files c windows-subsystem-for-linux
Leer una copia de `/usr/share/dict/words` es 10 veces más lento que el archivo mismo

Estaba experimentando con implementaciones de diccionarios en C y descubrí /usr/share/dict/wordsque era un archivo bastante bueno para realizar pruebas. Por alguna razón, quería hacer una copia del archivo de palabras en mi directorio de trabajo, pero para mi sorpresa, el programa fue notablemente más lento al leer el archivo. ¿Qué podría explicar este comportamiento? Los dos archivos son idénticos.

Si tuviera que adivinar, ¿podría ser que /usr/share/dict/wordsya está almacenado en la memoria porque es un archivo de uso frecuente?

#define _GNU_SOURCE

#include <assert.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>

#define GET_TIME(now)                           \
    do {                                        \
        struct timeval t;                       \
        gettimeofday(&t, NULL);                 \
        now = t.tv_sec + t.tv_usec / 1000000.0; \
    } while (0)

#define REPORT(msg, time)                   \
    do {                                    \
        printf("%-10s- %f\n", msg, time);   \
    } while (0)

#define SHOW_INVALID    0

struct dict {
    int n;
    char *data[110000];
};

int valid_word(char *input)
{
    for (int i = 0; input[i]; i++) {
        if (!islower(input[i]) && !(input[i] == '\n')) {
            return 0;
        }
    }
    return 1;
}

struct dict *get_dict(char *file)
{
    struct dict *dict = calloc(1, sizeof(struct dict));
    FILE *fp = fopen(file, "r");
    char input[128];
    while (fgets(input, 128, fp)) {
        if (valid_word(input)) {
            dict->data[dict->n++] = strdup(input);
        } else {
#if SHOW_INVALID == 1
            printf("Skipping invalid word %s", input);
#endif
        }
    }
    fclose(fp);
    return dict;
}

void destroy_dict(struct dict *dict)
{
    for (int i = 0; i < dict->n; i++) {
        free(dict->data[i]);
    }
    free(dict);
}

int search(struct dict *dict, int l, int r, char *word)
{
    if (l > r) return -1;
    int mid = l + (r - l) / 2;
    if (!strcmp(dict->data[mid], word)) return mid;
    if (strcmp(dict->data[mid], word) > 0) return search(dict, l, mid - 1, word);
    return search(dict, mid + 1, r, word);
}

int match(struct dict *dict, char *word)
{
    return search(dict, 0, dict->n - 1, word);
}

void test(struct dict *dict, char *file)
{
    FILE *fp = fopen(file, "r");
    char input[128];
    while (fgets(input, 128, fp)) {
        if (valid_word(input)) {
            assert(match(dict, input) != -1);
        } else {
            assert(match(dict, input) == -1);
        }
    }
    fclose(fp);
}

int main(void)
{
    double init, start, end;
    GET_TIME(init);

    GET_TIME(start);
    struct dict *dict = get_dict("words");
    GET_TIME(end);
    REPORT("setup", end - start);

    GET_TIME(start);
    test(dict, "words");
    GET_TIME(end);
    REPORT("words", end - start);

    GET_TIME(start);
    test(dict, "words_random");
    GET_TIME(end);
    REPORT("randwords", end - start);

    GET_TIME(start);
    destroy_dict(dict);
    GET_TIME(end);
    REPORT("teardown", end - start);

    puts("");
    REPORT("total", end - init);

    return 0;
}

Respuesta1

Como señaló @Vilinkameni, el rendimiento de E/S puede diferir en GNU/Linux si los archivos a los que se accede están en un dispositivo físico o tipo de sistema de archivos diferente.

En mi caso, WSL2 usa un disco duro virtual, pero mi directorio de trabajo (al que estaba cdasignado WSL) estaba en realidad en mi C:/disco. Entonces, al acceder al /usr/share/dict/wordsarchivo, permanezco en el WSL2 VHD, pero si copio el archivo a mi C:/disco, ahí es donde ocurre el impacto en el rendimiento, porque tiene que leer el archivo en otro "sistema de archivos".

Probé esto moviendo mi programa a /usr/share/dict/, creando una copia del wordsarchivo allí, y el rendimiento ahora es idéntico.

información relacionada