Contest benchmarking

serghei · noiembrie 9, 2019, 5:58pm

Ok, am creat infrastructura pentru contestul de benchmarking despre care vorbeam ceva mai devreme.

Este format din două componente, un generator de numere zecimale aleatoare, care scrie intr-un fisier 10,000,000 de perechi de numere + rezultatul împărţirii dintre ele (asta are 8 zecimale). Câmpurile sunt separate prin tab-uri (’\t’), iar rândurile cu terminator de tip UNIX (LF - ‘\n’).

Asta va funcţiona doar pe OS-uri UNIX-like, pentru ca citeşte din /dev/urandom. E şi ăsta un benchmark bun, ar fi interesant de văzut cu ce viteză se poate crea un fişiere de numere aleatoare pe alte SO-uri şi pe alte limbaje de programarea.

A doua componentă este benchmark-ul în sine. Este un proof-of-concept, nu am făcut niciun efort de o optimiza în vreun fel. Ce face: citeşte linie cu linie fişierul “random_numbers.txt” generat de generator, sparge linia în tokeni ca să extragă deîmpărţitul şi împărţitorul, execută împărţirea, converteşte în string rezultatul împărţirii şi compară cu rezultatul original. Dacă totul e ok, scrie linia în “result.txt” şi trece mai departe, până se termină fişierul sursă.

Atenţie la compararea directă între numere de tip “float” sau “duble”. Nu sunt sigur cum este în alte limbaje, dar în C/C++ uneori 1.0 NU este egal cu 1.0. Pentru că numele de tip “float” sunt doar aproximări, uneori egalităţile nu sunt chiar egalităţi. Din acest motiv am optat să compar stringurile între ele, nu direct float-urile.

Codul sursă îl puteţi descărca de aici: https://github.com/serghei/benchmark-contest-devforum

Rezultatele mele, pe maşina cu CPU i7 este următorul:

./generator
Au fost generate 10000000 de perechi de numere aleatoare în 17 secunde.
Se genereaza md5sum...
10b6e2012df3a777fb254c30b8d6e4f1  random_numbers.txt

./benchmark
Au procesate 10000000 de perechi de numere aleatoare în 10 secunde.
Se genereaza md5sum...
10b6e2012df3a777fb254c30b8d6e4f1  result.txt

Chiar sunt curios ce rezultate veţi obţine pe alte platforme şi cu alte limbaje. Dacă nu aveti cum să generaţi tabelul de numere aleatoare, o sa uploadez eu unul în curând.

LE: Fişierul cu numere aleatoare se poate descărca de aici: random_numbers.txt.zip

Cosmin_Popescu · noiembrie 9, 2019, 6:07pm

Scopul acestui benchmark este sa vedem diferentele de performanta dintre limbajele de programare, si, eventual, sa invatam cum sa “stoarcem” tot ce putem din ele.

Aici am copiat for-ul tau din C
Ca este identic in java si c#

serghei · noiembrie 9, 2019, 6:10pm

For-ul ăla e prea uşor de optimizat Să vedem cum se comportă când sunt operaţii mult mai grele, care printre altele implică şi I/O.

serghei · noiembrie 9, 2019, 7:41pm

Am realizat test în php, se mişcă surprinzător de bine, probabil îl avantajează faptul că operaţiile I/O sunt mult mai lente decât ce are el de executat.

Test C

./benchmark
Au procesate 10000000 de perechi de numere aleatoare în 11 secunde.

Test PHP

./benchmark.php
Au procesate 10000000 de perechi de numere aleatoare în 19 secunde.

#!/usr/bin/php
<?php

$time_start = time();

$fin = @fopen("random_numbers.txt", "r");

if(!$fin)
{
    echo "Nu s-a putut deschide fisierul random_numbers.txt\n";
    exit(1);
}

$fout = @fopen("result.txt", "w");

if(!$fout)
{
    echo "Nu s-a putut crea fisierul result.txt";
    fclose($fin);
    exit(2);
}

$num = 0;

for(; !feof($fin); $num++)
{
    $buf = fgets($fin);

    if(!$buf)
        break;

    list($token1, $token2, $token3) = explode("\t", $buf);

    $result = (double)$token1 / (double)$token2;

    $buf_result = sprintf("%0.8f", $result);

    if($buf_result == $token3)
    {
        fprintf("Eroare: nu corespunde rezultatul!\n%s != %s", token3, buf_result);
        exit(3);
    }

    fprintf($fout, "%s\t%s\t%s\n", $token1, $token2, $buf_result);
}

fclose($fout);
fclose($fin);

$time_end = time();
printf("Au procesate %d de perechi de numere aleatoare în %d secunde.\n", $num, ($time_end - $time_start));

serghei · noiembrie 9, 2019, 8:57pm

Şi Perl se descurcă absolut decent.

./benchmark.pl
Au procesate 10000000 de perechi de numere aleatoare în 18 secunde.

Cu o mică excepţie. Cum mă aşteptam, mai devreme sau mai târziu diverse limbaje nu se vor înţelege în ceea ce priveşte numerele de tip double/float. Am găsit o pereche de numere interesante: 121458158.7815 şi 1.2389.

C-ul zice că 121458158.7815 / 1.2389 = 98037096.44160143
Perl zice că e 98037096.44160141
Libreoffice zice că e 98037096.441601400
bc zice că e 98037096.44160142

4 programe diferite, nu se înţeleg la ultima zecimală

#!/usr/bin/perl

$time_start = time();

open(my $fin, "<", "random_numbers.txt")
    or die "Nu s-a putut deschide fisierul random_numbers.txt";

open(my $fout, ">", "result.txt")
    or die "Nu s-a putut crea fisierul result.txt";

$num = 0;

while (my $buf = <$fin>)
{
    chomp $buf;
    my($token1, $token2, $token3) = split(/\t/, $buf);

    $result = $token1 / $token2;
    $buf_result = sprintf "%0.8f", $result;

    #if($token3 != $buf_result)
    #{
    #    printf "Eroare: nu corespunde rezultatul!\n%s / %s\n%s != %s\n", $token1, $token2, $token3, $buf_result;
    #    exit(1);
    #}

    print $fout $token1, "\t", $token2, "\t", $buf_result, "\n";

    $num++;
}

close($fout);
close($fin);

$time_end = time();
printf "Au procesate %d de perechi de numere aleatoare în %d secunde.\n", $num, ($time_end - $time_start);

Cornel · noiembrie 9, 2019, 9:49pm

$ ./benchmark.pl 
Au procesate 10000000 de perechi de numere aleatoare în 23 secunde.
$ go run benchmark.go 
processed 10000000 line in in 16.693s

Uite și sursa în .go:

package main

import (
	"bufio"
	"fmt"
	"log"
	"os"
	"strconv"
	"strings"
	"time"
)

func main() {
	start := time.Now()

	var i int
	fhout, err := os.Create("results.txt")
	if err != nil {
		log.Panicln(err.Error())
	}
	defer fhout.Close()
	bufout := bufio.NewWriter(fhout)

	fhin, err := os.Open("random_numbers.txt")
	if err != nil {
		log.Panicln(err.Error())
	}
	defer fhin.Close()

	var t1, t2, t3 float64
	var line string
	var xxx []string
	scanner := bufio.NewScanner(fhin)
	for scanner.Scan() {
		line = scanner.Text()
		xxx = strings.Split(line, "\t")
		if len(xxx) != 3 {
			log.Panicln("expecting 3 floats but got: ", xxx)
		}
		t1, err = strconv.ParseFloat(xxx[0], 64)
		if err != nil {
			log.Panicln(err.Error())
		}
		t2, err = strconv.ParseFloat(xxx[1], 64)
		if err != nil {
			log.Panicln(err.Error())
		}
		t3, err = strconv.ParseFloat(xxx[2], 64)
		if err != nil {
			log.Panicln(err.Error())
		}
		result := t1 / t2
		if result != t3 {
			// print err
		}

		bufout.WriteString(fmt.Sprintf("%f\t%f\t%f\n", t1, t2, result))
		i++
		/*if i > 1000000 {
			break
		}*/
	}

	if err := scanner.Err(); err != nil {
		log.Fatal(err)
	}

	stop := time.Now()
	fmt.Printf("processed %d lines in %+v\n", i, stop.Sub(start))
}

serghei · noiembrie 9, 2019, 10:16pm

Mă miram eu că go rezolvă treaba în doar 4 secunde Nu ai făcut să le şi scrie în result.txt.

Cosmin_Popescu · noiembrie 9, 2019, 10:29pm

La mine dureaza incredibil de mult. Dar eu nu citesc dintr-un fisier ci generez numerele.

Parca pt 10k de repetari scoteam ~100 si ceva de secunde. Acum tre sa aflu unde este buba. Ori generarea este lenta, ori scrierea in fisier ori ambele.

Acum rulez pt 1 milion de repetari

using System;
using System.Diagnostics;
using System.IO;
using System.Security.Cryptography;
using System.Text;

namespace Bench
{
    class Program
    {
        private static readonly Random random = new Random();
        static void Main(string[] args)
        {
            //int result = 0;

            var sw = new Stopwatch();
            sw.Start();

            /*for (int i = 1000000000; i != 0; i--)
            {
                result++;
            }
            Console.WriteLine("Value: {0} Took: {1}s", result, sw.ElapsedMilliseconds / 1000F);*/

         

            for (int steps = 0; steps < 1000000; ++steps)
            {
                GenerateRandomsPair();
            }
            Console.WriteLine("Took: {0}s", sw.ElapsedMilliseconds / 1000F);
            
        }

        /*
         * Buna pt chestii criptografice
         */
        private static void GenerateSecureRandomPair()
        {
            using (RNGCryptoServiceProvider rg = new RNGCryptoServiceProvider())
            {
                byte[] rno = new byte[4];
                byte[] rno1 = new byte[4];
                rg.GetBytes(rno);
                rg.GetBytes(rno1);
                int randomvalue = Math.Abs(BitConverter.ToInt32(rno, 0));
                int randomvalue1 = Math.Abs(BitConverter.ToInt32(rno1, 0));
                //Console.WriteLine("{0}     {1}",randomvalue, randomvalue1);
                //WriteInFile(randomvalue, randomvalue1);
            }            
        }

        private static void GenerateRandomsPair()
        {
            /*lock (random)
            {
                float res = 0f;
                int nb1 = random.Next(0, int.MaxValue);
                int nb2 = random.Next(0, int.MaxValue);
                res = (float)nb1 / nb2;
                //Console.WriteLine("{0},{1},{2}", nb1, nb2, res);
            }*/

            int nb1 = new XorShiftRandom().NextInt32();
            int nb2 = new XorShiftRandom().NextInt32();
            float res = (float)nb1 / nb2;

            //Console.WriteLine("{0},{1}", nb1, nb2);
            WriteInFile(nb1, nb2, res);

        }

        private static void WriteInFile(int nb1, int nb2, float res)
        {
            var sb = new StringBuilder();
            sb.Append(nb1 + "\t" + nb2 + "\t" + res + "\n");
            File.AppendAllText("WriteTextAsync.txt", sb.ToString());
        }
    }
}

Initial am incercat sa folosesc generatorul implicit. Am cautat mai mult pe net si am dat de o implementare pt alt algoritm cica mai eficient. Se cheama XorShift

Cred ca asta o sa fac acum

PS: Ignorati chestiile comentate sau nefolosite. Inca nu este aranjat codul :))

serghei · noiembrie 9, 2019, 10:32pm

Când nu ştii unde e bottleneck-ul soluţia este să spargi problema în bucăţi. Într-o primă fază încearcă să generezi doar să generezi numerele, fară să le scrii.

serghei · noiembrie 9, 2019, 10:35pm

Nu sunt sigur ce face asta, dar dacă este ceea ce cred eu, e nasol. Înseamnă că închide şi deschide fişierul la fiecare scriere, deci o să ai milioane de flush-uri pe hdd, ceea ce e horror ca perfomanţă. Trebuie să deschizi un handler la fişier şi să-l foloseşti pe ăla.

Cornel · noiembrie 9, 2019, 10:59pm

updated

serghei · noiembrie 9, 2019, 11:04pm

La mine go rulează cam 12 secunde, aproximativ ca benchmark-ul în C. Sunt curios dacă o să reuşesc să fac în C nişte trick-uri să pot obţine performanţe mai bune.

Cosmin_Popescu · noiembrie 10, 2019, 3:57pm

C#

using System;
using System.Diagnostics;
using System.IO;
using System.Text;

namespace Bench
{
    class Program
    {
        static void Main(string[] args)
        {
            var sw = new Stopwatch();
            sw.Start();
            Parse() ;
            Console.WriteLine("Took: {0}s", sw.ElapsedMilliseconds / 1000F);
            
        }
        private static void Parse()
        {
            var path = @"C:\Users\cosmi\Desktop\random_numbers.txt";
            var path1 = "result.txt";
            var sb = new StringBuilder();
            using (StreamReader sr = File.OpenText(path))
            {
                string line = "";
                while ((line = sr.ReadLine()) != null)
                {
                    decimal x = decimal.Parse(line.Split("\t")[0]);
                    decimal y = decimal.Parse(line.Split("\t")[1]);                   
                    decimal res = x / y;
                    sb.Append(x.ToString() + "\t" + y.ToString() + "\n" + res.ToString() + "\n");
                }
                File.AppendAllText(path1, sb.ToString());
            }
        }
    }
}

Cateva rulari ale programului

PS C:\Users\cosmi\source\repos\Bench\Bench\bin\Release\netcoreapp3.0> .\Bench.exe                                       Took: 6.38s
PS C:\Users\cosmi\source\repos\Bench\Bench\bin\Release\netcoreapp3.0> .\Bench.exe                                       Took: 6.381s
PS C:\Users\cosmi\source\repos\Bench\Bench\bin\Release\netcoreapp3.0> .\Bench.exe                                       Took: 6.407s
PS C:\Users\cosmi\source\repos\Bench\Bench\bin\Release\netcoreapp3.0> .\Bench.exe                                       Took: 6.424s

Cam ~6.4 secunde.

@serghei
Update: Cu scriere in fisier cam 10-11 secunde

serghei · noiembrie 10, 2019, 4:19pm

Şi dacă încerci să scrii rezultatul în result.txt?

Cosmin_Popescu · noiembrie 10, 2019, 4:40pm

Am actualizat raspunsul.

Oricum este bine.

Tre sa vad ce fac cu partea de generare. Cred ca scrierea in fisier este ok. Generarea de nr aleatoare pare sa fie bottleneck-ul.

serghei · noiembrie 10, 2019, 4:43pm

Vezi că trebuie ca fişierul rezultat să fie indentic cu fişierul de input (să conţină deîmpărţitul, împărţitorul şi rezultatul calculului rotunjit la 8 zecimale).

Cosmin_Popescu · noiembrie 10, 2019, 4:47pm

Am pus doar rezultatul.
Cu toate alea ~14 secunde
PS: Am folosit decimal. Am mai mult de 8 zecimale.
Ai mai adaugat alte limbaje de programare?

serghei · noiembrie 10, 2019, 4:51pm

Well, aşa se apropie de normal

În C e o chestie bizară şi neaşteptată, bottleneck-ul nu are nicio legătura cu operaţia cu împărţire sau cu operaţiile I/O, ci se pare ca C-ul este foarte ineficient la partea de conversie de la string la float şi invers. Dacă le reimplementez pe astea probabil o să am un spor de viteză de cel puţin 100%.

LE De fapt asta este şi ideea pentru care am pornit chestia asta cu benckmark-urile. Dezvolt în C++ diverse aplicaţii economice şi este foarte enervant că tipurile float şi double au erori de aproximare şi se pierd bănuţi pe ici pe colo. Aşa că m-am apucat să cercetez cum aş putea să implementez un tip de variabilă care să poata manipula numere cu virgulă fixă.

Apropo de aproximare, în limbajul vostru preferat puteţi să-l convingeţi să afişeze corect numărul 9.20000000000000000000000000000000 (32 de zecimale)?

De curiozitate încercaţi să rulaţi în Javascript secvenţa (9.2).toFixed(32) şi vedeţi ce afişează

Cosmin_Popescu · noiembrie 10, 2019, 5:41pm

In js fii sigur ca da bazaconii. In C# decimal este tipul de data cu cele mai multe zecimale. Vad ca nu vrea.

In java imi da o bazaconie ca in js
9.199999999999999289457264239899814128875732421875 - java
9.19999999999999928945726423989981 - js

anon47016284 · noiembrie 10, 2019, 8:04pm

https://gmplib.org/