Pytanie Dlaczego sscanf glibc jest znacznie wolniejszy niż fscanf w systemie Linux?


Korzystam z GCC 4.8 i glibc 2.19 na Linuxie x86_64.

Podczas gry z różnymi metodami wprowadzania dla inne pytaniePorównałem fscanf i sscanf. W szczególności, albo bym skorzystał fscanf na standardowe wejście bezpośrednio:

char s[128]; int n;

while (fscanf(stdin, "%127s %d", s, &n) == 2) { }

Albo najpierw odczytałbym całe wejście do bufora, a następnie przechodzę przez bufor sscanf. (Czytanie wszystkiego w buforze zajmuje trochę czasu.)

char s[128]; int n;
char const * p = my_data;

for (int b; sscanf(p, "%127s %d%n", s, &n, &b) == 2; p += b) { }

Ku mojemu zaskoczeniu, fscanf wersja jest bardzo szybciej. Na przykład, przetwarzanie seveal dziesiątki tysięcy linii z fscanf trwa tak długo:

10000       0.003927487 seconds time elapsed
20000       0.006860206 seconds time elapsed
30000       0.007933329 seconds time elapsed
40000       0.012881912 seconds time elapsed
50000       0.013516816 seconds time elapsed
60000       0.015670432 seconds time elapsed
70000       0.017393129 seconds time elapsed
80000       0.019837480 seconds time elapsed
90000       0.023925753 seconds time elapsed

Teraz to samo z sscanf:

10000       0.035864643 seconds time elapsed
20000       0.127150772 seconds time elapsed
30000       0.319828373 seconds time elapsed
40000       0.611551668 seconds time elapsed
50000       0.919187459 seconds time elapsed
60000       1.327831544 seconds time elapsed
70000       1.809843039 seconds time elapsed
80000       2.354809588 seconds time elapsed
90000       2.970678416 seconds time elapsed

Użyłem narzędzi perfekcyjnych Google do pomiaru tego. Na przykład dla 50000 linii fscanf kod wymaga około 50M cykli, a sscanf kod około 3300M cykli. Więc zepsułem najlepsze strony z ogłoszeniami perf record/perf report. Z fscanf:

 35.26%  xf  libc-2.19.so         [.] _IO_vfscanf
 23.91%  xf  [kernel.kallsyms]    [k] 0xffffffff8104f45a
  8.93%  xf  libc-2.19.so         [.] _int_malloc

I z sscanf:

 98.22%  xs  libc-2.19.so         [.] rawmemchr
  0.68%  xs  libc-2.19.so         [.] _IO_vfscanf
  0.38%  xs  [kernel.kallsyms]    [k] 0xffffffff8104f45a

Więc prawie cały czas z sscanf jest wydawane w rawmemchr! Dlaczego to? Jak można fscanf kod unikaj tego kosztu?

Próbowałem tego szukać, ale najlepsze, co mogłem wymyślić, to ta dyskusja zablokowany realloc Połączenia, o których nie sądzę, mają tu zastosowanie. Myślałem o tym fscanf ma lepszą lokalizację pamięci (używanie tego samego bufora w kółko), ale to nie może zrobić dużej różnicy.

Czy ktokolwiek ma wgląd w tę dziwną rozbieżność?


18
2018-05-29 00:26


pochodzenie


Kompletny kod dla: fscanf, sscanf - Kerrek SB
Mam problem ze znalezieniem kodu źródłowego _IO_vfscanf. To jest najlepszy, jaki mogłem znaleźć, ale to niekoniecznie glibc 2.19. - Kerrek SB
Pokaż przetwarzanie pętli - wygląda na to, że masz Problem "Schlemiel the Painter". - Michael Burr
@MichaelBurr: Połączyłem kod testowy i opublikowałem pętle w pytaniu. Czy myślisz sscanf skanuje do końca łańcucha za każdym razem? Byłoby to sprzeczne z wartością przechowywaną w b, który ma oczekiwaną wartość (tj. w każdym wywołaniu zużywana jest jedna linia danych wejściowych). - Kerrek SB
@MichaelBurr: Właściwie, myślę, że Michael Burr ma rację, wygląda na to sscanf przeszukuje cały plik dla końcowego znaku zerowego, a następnie analizowania trzech zmiennych, które chcesz. Spójrz na przykład na linux.die.net/man/3/rawmemchr - Mooing Duck


Odpowiedzi:


sscanf () konwertuje ciąg znaków, który przekazujesz do _IO_FILE* aby napis wyglądał jak "plik". Jest tak, aby ten sam wewnętrzny _IO_vfscanf () mógł być użyty zarówno dla łańcucha, jak i dla pliku *.

Jednak w ramach tej konwersji, wykonanej w funkcji _IO_str_init_static_internal (), wywołuje __rawmemchr (ptr, '\0'); w zasadzie wywołanie strlen () na twoim łańcuchu wejściowym. Ta konwersja jest wykonywana przy każdym wywołaniu sscanf (), a ponieważ twój bufor wejściowy jest raczej duży, poświęci sporo czasu na obliczenie długości wejściowego łańcucha.

Tworzenie pliku * z łańcucha wejściowego za pomocą fmemopen () i użycie fscanf () może być inną alternatywą.


17
2018-05-29 00:49



Bardzo ciekawe - kto by pomyślał ?! Wielkie dzięki! - Kerrek SB
Sugerowałbym złożenie zgłoszenia błędu na glibc. Ta kwestia mogłaby definitywnie zostać naprawiona przez uczynienie wirtualnym FILE dostarczone przez sscanf używać niestandardowych operacji, które nie wymagają zaawansowanej znajomości długości ciągu znaków. W rzeczywistości nasza implementacja w bibliotece muzycznej libl omija problem, więc wiem, że to możliwe. :-) - R..
@R ..: Nigdy wcześniej nie słyszałem o musl - dzięki za wskazanie! - Kerrek SB


Wygląda jak glibc sscanf() skanuje łańcuch źródłowy na długość, zanim zrobi cokolwiek innego.

sscanf() (w stdio-common/sscanf.c) jest zasadniczo opakowaniem wokół wywołania _IO_vsscanf() (w libio/iovsscanf.c). I jedną z pierwszych rzeczy, które _IO_vsscanf() robi jest zainicjować własny _IO_strfile struktura przez wywołanie _IO_str_init_static_internal() (w libio/strops.c), który oblicza długość ciągu, jeśli nie jest podany.


7
2018-05-29 00:49