Jak szybki jest grep? -> grep vs awk, python, rugby, java, perl, C - przeszukiwanie logów - część 1.

Wpis musiałem podzielić na części, gdyż okazał sie za długi w porównaniu z możliwościami silnika tego bloga.



Przy pracach nad jednym z systemów bankowych powstała potrzeba optymalizacji czasu analizy logów z aplikacji. Przeprowadzone przy tej okazji testy pozwoliły bliżej przyjrzeć się problemowi doboru narzędzi do konkretnych zastosowań. W poniższym opracowaniu porównałem kilka programów mogących wyszukać w pliku sześć kolejnych znaków. Takie założenie odpowiada przeszukiwaniu plików logów wg. godziny i minuty, np. w poszukiwaniu zdarzeń, które zaszły w dwunastej minucie godziny dwunastej: "12:12:".
Testy rozpocząłem od przygotowania plików symulujących prawdziwe logi. Wygenerowałem plik mający 1 000 000 000 bajtów, składający się z 20 000 000 linii (w każdej linii znajduje sie 50 znaków):
0000001-> 2druga 3trzecia 4czwarta piata 11:59:50
...
2000000-> 2druga 3trzecia 4czwarta piata 12:24:57
Do stworzenia pliku testowego użyłem dwóch skryptów. Choć podobne, jeden z nich miał działać szybciej, przez tworzenie danych w pamięci RAM i zapisanie jednej porcji danych na dysku. Poniższy skrypt  "variable" teoretycznie powinien być szybszy:
Skrypt: variable
#!/bin/bash
# Copyright (c) 2016 Rafal Jackiewicz
#
mintime=10
hours=(`echo {10..23}`)
declare -i j=$mintime
tf100M="testfile_100M.txt"
if [ -f "$tf100M" ]; then
    rm "$tf100M"
fi
for (( i=1; $i<=2000000; i++ )) do {
    minutes=`shuf -i10-59 -n1`
    seconds=$(( $RANDOM % $mintime + 49 ))
    if  ((++j>23)) ; then
    j=$mintime
    echo $i
    echo -n "$bigstring" >> "$tf100M"
    bigstring=""
    fi
    # length: 50 chars per line
    bigstring+=`echo $( printf "%07u->" $i ) 2druga 3trzecia 4czwarta piata ${hours[(( $j-$mintime ))]}:$minutes:$seconds`$'\n'
} done
echo -n "$bigstring" >> "$tf100M"
#2 000 000 linii
echo -n "lines in the file: "; wc -l testfile_100M.txt
#20 000 000 linii
if [ -f testfile_1G.txt ]; then
    rm "testfile_1G.txt"
fi
for i in {0..9}; do cat testfile_100M.txt >> testfile_1G.txt; done
echo -n "Lines in the file: "; wc -l testfile_1G.txt
echo "End: fileCreate via variable."

Ten skrypt "direct" wykonujący wiele operacji zapisu do pliku powinien być wolniejszy:
Skrypt: direct
#!/bin/bash
# Copyright (c) 2016 Rafal Jackiewicz
# preferred /tmp in RAM
#
mintime=10
hours=(`echo {10..23}`)
declare -i j=$mintime
tf100M="/tmp/testfile_100M.txt"
if [ -f "$tf100M" ]; then
    rm "$tf100M"
fi
for (( i=1; $i<=2000000; i++ )) do {
    minutes=`shuf -i10-59 -n1`
    seconds=$(( $RANDOM % $mintime + 49 ))
    if  ((++j>23)) ; then
    j=$mintime
    echo $i
    fi
    # length: 50 chars per line
    echo $( printf "%07u->" $i ) 2druga 3trzecia 4czwarta piata ${hours[(( $j-$mintime ))]}:$minutes:$seconds >> "$tf100M"
} done
#2 000 000 linii
mv "$tf100M" testfile_100M.txt
echo -n "lines in the file: "; wc -l testfile_100M.txt
#20 000 000 linii
if [ -f testfile_1G.txt ]; then
    rm "testfile_1G.txt"
fi
for i in {0..9}; do cat testfile_100M.txt >> testfile_1G.txt; done
echo -n "Lines in the file: "; wc -l testfile_1G.txt
echo "End: fileCreateDirect."

Taki był rezultat uruchomienia powyższych skryptów:
Zaskakujące? Warto we własnym zakresie przetestować różnicę, gdy w poniższej linii zamienimy "bigstring+=" na "bigstring = "$bigstring +":
bigstring+=`echo $( printf "%07u->" $i ) 2druga 3trzecia 4czwarta piata ${hours[(( $j-$mintime ))]}:$minutes:$seconds`$'\n'
Skąd wynika ta nieoczekiwana różnica w czasach wykonania skryptów? Zakładam, że połączenie wolno działającego języka skryptowego z szybkim podsystemem dyskowym pozwoliło szybciej działać temu skryptowi, który wykonywał mniej operacji (pomimo dużej liczby dyskowych operacji IO).

W tym miejscu zamieszczę kilka słów wyjaśnienia.

1) Skrypty i programy zamieszczone na tej stronie są wersjami testowymi, a nie produkcyjnymi. Nie obsługują wszystkich wyjątków i możliwych błędów, nawet w miejscach, o których wiem. Nie było to potrzebne do zaprezentowania wyników testów i porównania ich.
2) Kod nie jest optymalny w wielu miejscach - i taki ma być. W programach użyłem wielu funkcji jako demonstracje technologii. Np. w skryptach tworzących plik testowy użyłem dwóch różnych funkcji tworzących losowe dane, a w programach, które będą zamieszczone poniżej, zaprezentowane są różne funkcje wspierające programowanie wieloprocesorowe:
  • Pamieć współdzielona zgodna z System V API i POSIX API, odwzorowanie plików w pamięci.
  • Semafory {wait4()}; pomiar czasu w trybie użytkownika i systemu (rusage), oraz high_resolution_clock.
  • Tworzenie procesów: fork, exit, execl.

3) Mimo tego, że testy wykażą różnice w czasach działania programów, co automatycznie skłania do ich wartościowania, to ja nie dyskredytuję żadnego z tych programów, czy języków. Każdy z nich ma pewne właściwości czyniące go użytecznym. Jedne mają działać szybko, przy ograniczonej funkcjonalności. Inne mają wiele możliwości, dużą ilość opcji i przełączników. Jeszcze inne mają służyć do szybkiej implementacji. Jak wyglądała by dzisiejsza informatyka bez awk, czy Javy?

Wykorzystany serwer:
Do testów w wirtualnym środowisku dostępne jest 16 rdzeni, co przy technologii Hyper-Threading udostępnia systemowi operacyjnemu możliwość uruchomienia 32 współbieżnych procesów. Macierz dysków i 120 GB RAM i zapewnia, że system pamięci masowej nie będzie wpływał na testy.

Testy:

Grep
Pierwszy test z tytułowym programem. Do niego będziemy odnosić wszystkie inne wyniki. Każdy z programów będę uruchamiać dwukrotnie, by mieć pewność powtarzalności uzyskanych wyników.

AWK

#!/bin/bash
awk  '/'"$1"'/ { print $0}' $2

Python

#!/usr/bin/python
import re
import sys
file = open(sys.argv[2], "r")
for line in file:
        if re.search(sys.argv[1], line):
              print line,

Ruby

Trzy wersje i porównanie czasów ich wykonania.
grepruby_slow_1
#!/usr/bin/ruby
File.open(ARGV[1]).each_line do |line|
  puts line if line.match(/#{ARGV[0]}/)
end
grepruby_slow_2
#!/usr/bin/ruby
File.open(ARGV[1]) { |f|
    f.each { |line|
        puts line if line.match(/#{ARGV[0]}/)
    }
}
grepruby_fast
#!/usr/bin/ruby
File.foreach(ARGV[1]).grep /#{ARGV[0]}/ do |f|
 puts f
end

Perl

#!/usr/bin/perl
use strict;
use warnings;
my ($bigfile, $needle) = @ARGV;
open my $fd, '<', $bigfile or die "Cannot open file: $!\n";
while(<$fd>) {
   print $_ if ($_ =~ /$needle/);
}

Java

W bonusie obsługa wyrażeń regularnych.
import java.util.regex.*;
import java.io.*;
class grepjava {
    public static void main(String args[]) {
        if (args.length != 2) {
            System.err.println("Podaj dwa argumenty: needle file");
            System.exit(1);
        }
        Pattern needleCompile = null;
        try {
            needleCompile = Pattern.compile(args[0]);
        } catch (PatternSyntaxException e) {
            System.err.println("Skladnia: " + e.getDescription());
            System.exit(1);
        }
        BufferedReader in = null;
        try {
            in = new BufferedReader(new InputStreamReader(new FileInputStream(args[1])));
        } catch (FileNotFoundException e) {
            System.err.println("Open: "+ e.getMessage());
            System.exit(1);
        }
        try {
            String searchString;
        Matcher match;
            while ( ( searchString = in.readLine() ) != null) {
                match = needleCompile.matcher( searchString);
                if (match.find())
                    System.out.println(searchString);
            }
        } catch (Exception e) {
            System.err.println("Read:  " + e.getMessage());
            System.exit(1);
        }
    }
}

********

Więcej informacji:
Informatyka, FreeBSD, Debian


***

Inne wpisy:



Update: 2018.07.17
Create: 2018.07.17
Autor:
Etykiety: , , , , , , , ,

Brak komentarzy:

Prześlij komentarz

Subskrybuj: Komentarze do posta (Atom)