[Snelheid] Java > PHP > Perl > Python ?

[quexy]

Allen,

Om de vrijdag middag eens 'nuttig' in te vullen, ben ik eens de snelheid van een aantal veel gebruikte programmeertalen gaan vergelijken, door middel van een 'priemgetal' scriptje. De resultaten van vooral python zijn opvallend en ik vraag me af of ik iets fout doe. De code:

Java:

public class Prime {
    public void calculatePrimeNumbers() {

        int i = 0;
        int primeNumberCounter = 0;

        while (++i <= 100000) {

            int i1 = (int) Math.ceil(Math.sqrt(i));

            boolean isPrimeNumber = false;

            while (i1 > 1) {
                if ((i != i1) && (i % i1 == 0)) {
                    isPrimeNumber = false;
                    break;
                } else if (!isPrimeNumber) {
                    isPrimeNumber = true;
                }

                --i1;
            }

            if (isPrimeNumber) {
                ++primeNumberCounter;
            }
        }

        System.out.println("Nr of prime numbers found: " + primeNumberCounter);
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        new Prime().calculatePrimeNumbers();
    }
}

PHP:

<?
$i = 1;
$count = 0;

while ( ++$i <= 100000 ) {
    $n = ceil(sqrt($i));
    $isPrime = 0;

    while( $n > 1 ) {
        if ( ( $i != $n ) && ( $i % $n == 0 ) ) {
            $isPrime = 0;
            break;
        } elseif( $isPrime == 0 ) {
            $isPrime = 1;
        }

        --$n;
    }

    if ( $isPrime == 1 ) {
        $count++;
    }
}

print "Nr of prime numbers found: $count\n";
?>

Perl:

#! /usr/bin/perl -w

use strict;
use POSIX;

my ( $i ) = 1;
my ( $count ) = 0;

while ( ++$i <= 100000 ) {
    my ( $n ) = ceil(sqrt($i));
    my ( $isPrime ) = 0;

    while( $n > 1 ) {
        if ( ( $i != $n ) && ( $i % $n == 0 ) ) {
            $isPrime = 0;
            last;
        } elsif( $isPrime == 0 ) {
            $isPrime = 1;
        }

        --$n;
    }

    if ( $isPrime == 1 ) {
        $count++;
    }
}

print "Nr of prime numbers found: $count\n";

Python:

import math

i = 0
count = 0

for i in range( 2, 100000 ):
    n = math.ceil(math.sqrt(i))
    isPrime = 0

    while( n > 1 ):
        if ( ( i != n ) & ( i % n == 0 ) ):
            isPrime = 0
            break
        elif( isPrime == 0 ):
            isPrime = 1
        n -= 1

    if ( isPrime == 1 ):
        count += 1

print "Nr of prime numbers found:", count, "\n"

Om vervolgens goed de snelheid te testen gebruik ik hiervoor time:

code:

quexy@arachnid:~/prime$ time java Prime
Nr of prime numbers found: 9592

real    0m0.426s
user    0m0.372s
sys     0m0.028s

----

quexy@arachnid:~/prime$ time php Prime.php
Nr of prime numbers found: 9592

real    0m6.162s
user    0m6.156s
sys     0m0.008s

----

quexy@arachnid:~/prime$ time perl Prime.pl
Nr of prime numbers found: 9592

real    0m7.171s
user    0m7.160s
sys     0m0.012s

----

quexy@arachnid:~/prime$ time python Prime.py
Nr of prime numbers found: 9592


real    0m15.556s
user    0m15.005s
sys     0m0.012s

Op zich valt het me niet zo op dat Java veel sneller is; aangezien deze code gecompileerd is. Maar vooral het verschil tussen PHP/Perl en Python is enorm.

Kan iemand verklaren waarom Python 2x zo lang over het berekenen doet?

[!null]

Nee kan ik niet verklaren. Maar zou je op dezelfde machine ook eens de applicatie in C kunnen schrijven en timen? Eventueel ook nog met en zonder optimalisatie als je zin hebt

[Confusion]

Daar kunnen talloze redenen voor zijn, maar een suboptimale implementatie is de waarschijnlijkste oorzaak.
Sowieso reken je nu overal de startup time van de JVM / interpreter mee, terwijl dat niets zegt over de performance die een taal voor een bepaalde taak kan leveren. Voor langlopende taken is die tijd verwaarloosbaar.

Overigens bestaan dit soort overzichten natuurlijk allang:
http://shootout.alioth.de...test=binarytrees&lang=all

Een ingang naar vergelijkingen:
http://shootout.alioth.de...=java&lang2=python3&box=1

Overigens is performance op CPU-intensieve taken voor veel toepassingen helemaal geen interessant graadmeter. Leesbaarheid, aanpasbaarheid, IDE ondersteuning, kennis bij de developers, etc. zijn veel interessanter voor welke taal geschikt is voor een bepaalde toepassing.

[ Voor 60% gewijzigd door Confusion op 27-11-2009 13:03 ]

[DrClaw]

misschien omdat de 'for i in range' regel 2 comparisons doet ipv 1 in een while loop?

[ZpAz]

Ik denk zo en zo niet dat je op deze manier kan zeggen 'Zie je wel' taal X is sneller. Je gebruikt immers maar een heel klein gebied van mogelijkheden van de taal.

Misschien als je een andere 'benchmark' maakt wat een heel andere tak benchmarked de resultaten geheel anders zullen zijn. Daarnaast zijn benchmarks vaak niet een goede weergave van een 'real life' situatie.

[Phyxion]

Geen idee wat de bedoeling is van dit topic maar ik heb het even 1:1 omgezet naar C#.
0.095 sec average bij 1000x draaien.

[RayNbow]

Verplichte link: The Dangers of Benchmarks

Verder geven deze benchmarks (en vele andere benchmarks op 't web) alleen een totaaltijd. Waarom worden er niet meer benchmarks gemaakt zoals in deze blogpost wordt toegelicht? Gooi er wat meer statistiek tegenaan.

Interessante fragmenten uit de blogpost:

The first thing that Fibber does is measure how long it takes for the system clock to tick. It will then run our benchmarked code enough times that the resolution of the clock will not introduce a significant error.

[...]

Once we've characterised the system clock's period, we figure out how expensive it is to actually use the clock.

[...]

Why do we measure so many times? Because we're going to do some statistical analysis of our measurements to see whether they are trustworthy.

bootstrapping with 100000 resamples

The bootstrap step takes a second or two, and this is where the interesting stuff takes place. The performance of real-world applications doesn't follow some kind of tidy statistical pattern such as the normal distribution, especially when people are measuring in realistic, noisy environments.

If you run a time-consuming benchmark on your laptop, you're likely to want to switch to your web browser, watch a video on youtube, check your mail, and so on. Your CPU might slow down because it's overheating, or your laptop's ACPI subsystem might change the CPU frequency to conserve power.

[...]

[ Voor 62% gewijzigd door RayNbow op 27-11-2009 13:13 ]

[.oisyn]

Ik vind je hele loopje maar raar. Waarom isPrimeNumber niet gewoon op true initialiseren, dan is die else if ook niet meer nodig. De enige issue die je dan nog hebt is dat je 1 aanmerkt als priemgetal, maar dat kun je oplossen door simpelweg niet te beginnen bij 1 maar bij 2. En al initialiseer je 'm niet op true dan zou ik alsnog niet de check doen, gewoon een waarde schrijven terwijl dat niet nodig is is goedkoper dan een conditional jump.

Niet dat het voor je test verder uitmaakt aangezien je toch in iedere taal hetzelfde doet. Maar ja, je test zegt zelf verder ook geen drol. Je kunt er iig niet mee aantonen dat een bepaalde taal sneller is dan een bepaalde andere taal

[ Voor 77% gewijzigd door .oisyn op 27-11-2009 13:14 ]

[user109731]

Je gebruikt een bitwise-and (&) in Python, waar je denk ik 'and' bedoelt. Verder heeft Python booleans (True, False) naast 1 en 0: if x: is mogelijk sneller dan: if x == 1. Probeer verder eens 'xrange' ipv 'range'. Verder zou een Python-goeroe dit misschien m.b.v. map/reduce/etc. schrijven.
Welke versie gebruik je trouwens?

Probeer het ook eens met Psyco of (diens opvolger) PyPy. Het probleem met Python is dat het een van de meest dynamische (mogelijk zelfs de meest dynamische) talen is. Pypy werkt aan een tracing-JIT generator* voor Python die voor loopjes als deze in de buurt komt van unoptimized C

* offtopic: Men genereert automatisch een JIT-compiler voor een bytecode-interpreter geschreven in RPython (een subset van Python). Ontzettend krachtig: je schrijft een interpreter, voegt wat hints toe en het framework genereert een JIT-compiler voor je. Het heeft een paar jaar onderzoek gekost, maar nu begint het eindelijk resultaat op te leveren...

[ Voor 39% gewijzigd door user109731 op 27-11-2009 13:29 ]

[Phyxion]

.oisyn schreef op vrijdag 27 november 2009 @ 13:11:
Ik vind je hele loopje maar raar. Waarom isPrimeNumber niet gewoon op true initialiseren, dan is die else if ook niet meer nodig. De enige issue die je dan nog hebt is dat je 1 aanmerkt als priemgetal, maar dat kun je oplossen door simpelweg niet te beginnen bij 1 maar bij 2. En al initialiseer je 'm niet op true dan zou ik alsnog niet de check doen, gewoon een waarde schrijven terwijl dat niet nodig is is goedkoper dan een conditional jump.

Niet dat het voor je test verder uitmaakt aangezien je toch in iedere taal hetzelfde doet. Maar ja, je test zegt zelf verder ook geen drol. Je kunt er iig niet mee aantonen dat een bepaalde taal sneller is dan een bepaalde andere taal

Helemaal gelijk in, maar volgens jou optimalisatie manieren kan je net zo goed meteen alles in een list zetten en niks meer doen want ze zijn toch wel bekend
Sowieso is deze gehele test vrij kansloos, code is nooit perfect om 1:1 over te zetten voor elke taal. Als je iets goed wilt doen moet je het per taal doen en kijken wat de snelste variant is voor die taal.

[.oisyn]

Phyxion schreef op vrijdag 27 november 2009 @ 13:19:
[...]

Helemaal gelijk in, maar volgens jou optimalisatie manieren kan je net zo goed meteen alles in een list zetten en niks meer doen want ze zijn toch wel bekend

Klopt, en een compiler kan dat in feite net zo goed, dus wie weet komt er wel een programma uitrollen die niets meer doet dan "Nr of prime numbers found: 9592" uitvoeren . Ga je het maximum echter af laten hangen van programma-input, dan kan dat niet meer, en werkt de optimalsiatie die jij voorstelt ook niet meer. Echter, je weet dan nog wel dat 1 iig nog altijd geen priemgetal is, en dus kun je de optimalisaties die ik voorstelde wél toepassen.

Bovendien, als de topic toch al nergens over gaat blijft er niets anders over dan code bekritiseren. Dus laat ik daar maar mee doorgaan : een ander punt is dat bij de Java implementatie calculatePrimeNumbers niet static is, waardoor er eerst een nieuwe Prime aangemaakt moet worden. Slaat natuurlijk ook nergens op, en dit zorgt voor een verschil tov de andere implementaties.

[ Voor 43% gewijzigd door .oisyn op 27-11-2009 13:30 ]

[quexy]

@JanDM bedankt voor je reactie, ik zal het eens proberen.

[Soultaker]

De suggesties van JanDM zijn waardevol als je nette Python code wil schrijven, maar hebben niet (veel) met performance te maken. Het gebruik van xrange versus range maakt niet altijd veel uit (zeker in jouw code, alloceer je één keer een lijst met een miljoen getallen; dat kost één keer 100ms ofzo, wat op het totaal weinig uitmaakt. (.oisyn's suggestie m.b.t. static methods in de Java class is nog meer verwaarloosbaar.)

Maar het is wel belangrijk om code te schrijven die eigen is aan de taal. In Python zijn expliciete loops (met while) relatief kostbaar. Je kunt dan beter (x)range gebruiken. (In Python 3 werkt range overigens als xrange in Python 2, dus hoef je dat onderscheid niet te maken.)

Ik zou geneigd zijn je code als volgt te herschrijven (zonder je algoritme te verbeteren):

Python:

from math import *

count = 0

for i in xrange(2, 100000):
    for n in xrange(int(ceil(sqrt(i))), 1, -1):
        if i != n and i % n == 0:
            break
    else:
        count += 1

print "Nr of prime numbers found:", count, "\n"

Dit is hier sneller dan Perl en ongeveer even snel als PHP, maar de vergelijking is niet helemaal eerlijk omdat ik je rare isPrime logica eruit heb gehaald (en daar zouden de andere implementaties waarschijnlijk ook van profiteren).

[Confusion]

Sowieso is de vraag: wat wil je bereiken met deze vergelijking? Vooralsnog is de enige conclusie die je kunt trekken dat jouw implementatie van dit algoritme op jouw computer, op dat moment, het snelste draaide.

Als je een snellere priemgetallengenerator wilt, dan moet je aan het algoritme sleutelen, niet aan de taal. Als je wilt weten hoe snel computers priemgetallen kunnen genereren, dan moet je zeker weten dat er geen andere taken tussendoor komen en dat je de cores volledig benut. Als je wilt weten in welke taal je het snelst priemgetallen kunt genereren, dan moet je van alle talen voldoende verstand hebben om de algoritmen optimaal te implementeren. Etc.

[Neverwinterx]

Dit is overigens wat interessanter als benchmark, professioneler en uitgebreider: http://shootout.alioth.debian.org/

[ACM]

Confusion schreef op vrijdag 27 november 2009 @ 18:23:
Sowieso is de vraag: wat wil je bereiken met deze vergelijking? Vooralsnog is de enige conclusie die je kunt trekken dat jouw implementatie van dit algoritme op jouw computer, op dat moment, het snelste draaide.

Je kan ook wel moeilijk doen om het moeilijk doen he? Tuurlijk is het geen zinnige implementatie van een priem-generator, daar zijn zat betere implementaties voor te verzinnen, zelfs deze triviale versie kan geoptimaliseerd worden door bij 3 te beginnen en daarna met 2 te verhogen (en floor voor i1 ipv ceil is ook nog een kleintje, kan je dan mooi met een harde cast naar int doen).
Desalniettemin heeft hij nu wel een serie berekeningen die zo - op het oog - in elke taal hetzelfde doet. Dus je kan wel degelijk een uitspraak doen, dat in ieder geval met deze serie triviale berekeningen php de snelste van de drie dynamische talen is. De kans is verder groot dat dat op diverse systemen van anderen te reproduceren is en zelfs dat het met andere soorten berekeningen na te bootsen is.
Als benchmark van de complete taal zegt het inderdaad niet zoveel, behalve dat als je veel moet rekenen dat je dan beter af bent met Java of een andere naar native instructies gecompileerde en geoptimaliseerde executiemethode. Maar dat wisten we al. Als je de diverse low-level kosten wilt verzamelen moet je sowieso ook nog een benchmark introduceren die heel veel functiecalls genereert, veel en/of grote objecten genereert, etc.

Dat de opstarttijd nu is meegeteld, zal alleen voor de JVM echt nadelig zijn, want die is nu al zo snel dat een relatief groot deel aan opstarttijd verspild zal zijn en bovendien heeft die waarschijnlijk de krachtigste runtime optimizer van het stel.

Als je een snellere priemgetallengenerator wilt, dan moet je aan het algoritme sleutelen, niet aan de taal. Als je wilt weten hoe snel computers priemgetallen kunnen genereren, dan moet je zeker weten dat er geen andere taken tussendoor komen en dat je de cores volledig benut. Als je wilt weten in welke taal je het snelst priemgetallen kunt genereren, dan moet je van alle talen voldoende verstand hebben om de algoritmen optimaal te implementeren. Etc.

Tuurlijk, maar dan is het geen benchmark meer van exact (?) dezelfde berekeningen in verschillende talen

[Confusion]

ACM schreef op zaterdag 28 november 2009 @ 10:18:
Tuurlijk is het geen zinnige implementatie van een priem-generator, daar zijn zat betere implementaties voor te verzinnen, zelfs deze triviale versie kan geoptimaliseerd worden door bij 3 te beginnen en daarna met 2 te verhogen

En dan test je nog 1/3 teveel, want een priemgetal heeft altijd de vorm 6n +/- 1.

Desalniettemin heeft hij nu wel een serie berekeningen die zo - op het oog - in elke taal hetzelfde doet. Dus je kan wel degelijk een uitspraak doen, dat in ieder geval met deze serie triviale berekeningen php de snelste van de drie dynamische talen is.

De 'zo op het oog' is precies mijn punt. Het lijkt betekenisvol, maar dat is het niet. Het is zelfs geen indicatie, tenzij je een heel helder doel voor ogen hebt. Want wat vertellen dit soort resultaten je? Naar welke andere situaties/programma's/algoritmen wil je deze resultaten te kunnen extrapoleren? Je kan ze naar werkelijk geen enkel ander algoritme extrapoleren, als je niet precies weet wat je getest hebt. En daarom vraag ik de topicstarter: wat denk je dat je getest hebt? Welke conclusie wil je uit de resultaten kunnen trekken?

Tuurlijk, maar dan is het geen benchmark meer van exact (?) dezelfde berekeningen in verschillende talen

Precies, maar dat moet je ook niet willen doen, want het benchmarken van schijnbaar dezelfde berekening in verschillende talen is een zinloze exercitie. Prima voor de lol, om talen te leren of wat dan ook, maar niet om "de snelheid van een aantal veel gebruikte programmeertalen [te] vergelijken".

[ Voor 4% gewijzigd door Confusion op 28-11-2009 11:04 ]

[Gomez12]

Tussendoor vraagje dan. Als je nou in de functie eerst de tijd eenmalig opslaat en aan het einde de eindtijd - begintijd ( je opgeslagen waarde ) toont schakel je dan het hele VM-loading etc definitief uit?

[RayNbow]

Gomez12 schreef op zaterdag 28 november 2009 @ 11:10:
Tussendoor vraagje dan. Als je nou in de functie eerst de tijd eenmalig opslaat en aan het einde de eindtijd - begintijd ( je opgeslagen waarde ) toont schakel je dan het hele VM-loading etc definitief uit?

Op die manier neem je niet de laadtijd van de VM op in je meting, aannemende dat je programma pas begint met uitvoeren als de VM volledig geladen is.

Het zou kunnen dat je programma al gedeeltelijk van start gaat terwijl er nog delen van de VM geladen moeten worden.

[.oisyn]

Confusion schreef op zaterdag 28 november 2009 @ 11:02:
[...]

En dan test je nog 1/3 teveel, want een priemgetal heeft altijd de vorm 6n +/- 1.

Dan test je nog 1/5 teveel, want een priemgetal heeft altijd de vorm 30n +/- 1, 30n +/- 7, 30n +/- 11 of 30n +/- 13 (muv 2, 3 en 5). En dan test je nog 1/7 teveel, want... nou ja, you get the point.

ACM schreef op zaterdag 28 november 2009 @ 10:18:
(en floor voor i1 ipv ceil is ook nog een kleintje, kan je dan mooi met een harde cast naar int doen)

Dat is geen optimalisatie, omdat het exact dezelfde operatie is (een float round met een bepaalde rounding mode)

[ Voor 39% gewijzigd door .oisyn op 28-11-2009 18:56 ]

[RayNbow]

.oisyn schreef op zaterdag 28 november 2009 @ 18:33:
[...]

Dat is geen optimalisatie, omdat het exact dezelfde operatie is (een float round met een bepaalde rounding mode)

Maar floor ipv ceil scheelt wel 1 iteratie...

[JKVA]

RayNbow schreef op zaterdag 28 november 2009 @ 12:10:
[...]

Op die manier neem je niet de laadtijd van de VM op in je meting, aannemende dat je programma pas begint met uitvoeren als de VM volledig geladen is.

Het zou kunnen dat je programma al gedeeltelijk van start gaat terwijl er nog delen van de VM geladen moeten worden.

Goede microbenchmarks op een VM zoals de Java VM zijn vrijwel onmogelijk. Je hebt zoveel variabelen waar je rekening mee moet houden, zoals classloading, JIT compilatie, GC, etc.

Ik zou (in je Java Prime) sowieso beginnen met een meting in de applicatie (System.nanotime()). Daarna zou ik een stel warmup rounds toevoegen, om daarmee een JIT compilatie te "forceren". Ook kun je het beste voor de server VM kiezen. Hiervoor heb je de -server startup flag nodig.

Ook zou ik je test in een loop zetten en het gemiddelde pakken (en eventueel de std dev, min en max). Daarmee middel je de impact van eventuele GC cycli uit. Je warmup rounds moet niet meenemen in de berekening.

Ten slotte, de Java VMs (zowel Sun, IBM als Oracle) zijn erg goed in het optimaliseren van code. Ik zou altijd iets met een random waarde meenemen in je berekening en de uitkomst achteraf naar de console printen, want anders is het "dead" code en wordt het door de VM verwijderd. Het heeft dan niks meer met priemgetallen te maken, maar je test wordt er wel betrouwbaarder van omdat de VM minder kan optimaliseren.

Maar microbenchmarks in Java blijven extreem moeilijk. Zie link: http://www.ibm.com/develo...a/library/j-jtp02225.html

[Gomez12]

JKVA schreef op zondag 29 november 2009 @ 11:01:
[...]
Ik zou (in je Java Prime) sowieso beginnen met een meting in de applicatie (System.nanotime()). Daarna zou ik een stel warmup rounds toevoegen, om daarmee een JIT compilatie te "forceren". Ook kun je het beste voor de server VM kiezen. Hiervoor heb je de -server startup flag nodig.

Ook zou ik je test in een loop zetten en het gemiddelde pakken (en eventueel de std dev, min en max). Daarmee middel je de impact van eventuele GC cycli uit. Je warmup rounds moet niet meenemen in de berekening.

Ten slotte, de Java VMs (zowel Sun, IBM als Oracle) zijn erg goed in het optimaliseren van code. Ik zou altijd iets met een random waarde meenemen in je berekening en de uitkomst achteraf naar de console printen, want anders is het "dead" code en wordt het door de VM verwijderd. Het heeft dan niks meer met priemgetallen te maken, maar je test wordt er wel betrouwbaarder van omdat de VM minder kan optimaliseren.

Tja, en dan heb je een benchmark gemaakt die door iedereen met het boek java for dummies qua prestaties is te verbeteren, oftewel hij heeft niets meer met de realiteit te maken...

Voorgecompileerde code / code-optimalisaties horen gewoon allemaal bij een programmeertaal, dat kun je er wel allemaal uit gaan slopen in een poging om dezelfde assembly te krijgen om te vergelijken, maar dan heb je het gewoon niet meer over die programmeertaal.

De enige manier afaik om echt programmeertalen te vergelijk is om mensen met hetzelfde kennisniveau 1 jaar aan een project te laten werken en dan de totaaltijd van het project te bekijken.

Of een println in java nou 0,0001 ms sneller is dan een print in php is totaal niet relevant in het gemiddelde project.

[JKVA]

Gomez12 schreef op zondag 29 november 2009 @ 12:40:
[...]

Tja, en dan heb je een benchmark gemaakt die door iedereen met het boek java for dummies qua prestaties is te verbeteren, oftewel hij heeft niets meer met de realiteit te maken...

Voorgecompileerde code / code-optimalisaties horen gewoon allemaal bij een programmeertaal, dat kun je er wel allemaal uit gaan slopen in een poging om dezelfde assembly te krijgen om te vergelijken, maar dan heb je het gewoon niet meer over die programmeertaal.

De enige manier afaik om echt programmeertalen te vergelijk is om mensen met hetzelfde kennisniveau 1 jaar aan een project te laten werken en dan de totaaltijd van het project te bekijken.

Of een println in java nou 0,0001 ms sneller is dan een print in php is totaal niet relevant in het gemiddelde project.

Dat het zinloos is, daar zijn we het volgens mij wel over eens. Maar als je dan toch een benchmark wilt doen (voor de gein), probeer dan tenminste een echte test te doen. De efficiency van je algoritme is daarbij niet echt van belang.

Door iets als random in je test op te nemen maak je hem realistischer, want vrijwel geen applicaties doen 10000000 keer exact hetzelfde. Met iets als random voorkom je dan dergelijke ongewenste optimalisaties.

Maar het blijft gefröbel...

[Phyxion]

JKVA schreef op maandag 30 november 2009 @ 08:40:
[...]

Dat het zinloos is, daar zijn we het volgens mij wel over eens. Maar als je dan toch een benchmark wilt doen (voor de gein), probeer dan tenminste een echte test te doen. De efficiency van je algoritme is daarbij niet echt van belang.

Door iets als random in je test op te nemen maak je hem realistischer, want vrijwel geen applicaties doen 10000000 keer exact hetzelfde. Met iets als random voorkom je dan dergelijke ongewenste optimalisaties.

Maar het blijft gefröbel...

Maar random is gevaarlijk want veel randoms zijn totaal niet random maar genereren rustig 80% hetzelfde getal.

[Juup]

Om nog wat aan de onbetrouwbare test toe te voegen: Javascript!

HTML:

<html>
<body>
<script>
var start = new Date();
var i = 1;
var count = 0;

while ( ++i <= 100000 ) {
    var n = Math.ceil(Math.sqrt(i));
    var isPrime = 0;

    while( n > 1 ) {
        if ( ( i != n ) && ( i % n == 0 ) ) {
            isPrime = 0;
            break;
        } else if( isPrime == 0 ) {
            isPrime = 1;
        }
        --n;
    }

    if ( isPrime == 1 ) {
        count++;
    }
}
document.write("Nr of prime numbers found: " + count + ". Tijd: " + ((new Date()) - start) + "ms");
</script>
</body>
</html>

Deze is eigenlijk nog minder betrouwbare omdat de tijd op een andere manier gemeten wordt.

Maar goed:

In mijn webkit (safari) doet hij er ongeveer 400ms over. Firefox is veel langzamer (2129ms).
Ik dacht altijd dat Javascript veel langzamer was dan php/perl/python etc.

Edit: ter referentie de andere talen op mijn machine:

Bash:

$ time perl prime.pl
Nr of prime numbers found: 9592

real    0m7.317s
user    0m7.231s
sys     0m0.041s

$ time php prime.php
Nr of prime numbers found: 9592

real    0m10.376s
user    0m10.274s
sys     0m 0.059s

$ time python prime.py
Nr of prime numbers found: 9592 

real    0m22.323s
user    0m22.158s
sys     0m 0.107s

Dus Java > Javascript >> Perl > PHP > Python.

[ Voor 18% gewijzigd door Juup op 30-11-2009 14:56 ]

[Juup]

Ruby

Ruby:

#!/usr/bin/ruby

i = 1
count = 0

while i <= 100000
    n = Math.sqrt(i).ceil
    isPrime = 0

    while n > 1
        if ( i != n ) && ( i % n == 0 )
            isPrime = 0
            break
        elsif isPrime == 0
            isPrime = 1
        end

        n -= 1
    end

    if isPrime == 1
        count += 1
    end
    i += 1
end

puts "Nr of prime numbers found: ", count, "\n";

Tijd:

Bash:

$ time ruby prime.rb
Nr of prime numbers found: 
9592

real    0m16.427s
user    0m16.226s
sys     0m 0.038s

Dus Java > Javascript >> Perl > PHP > Ruby > Python

[RayNbow]

Juup schreef op maandag 30 november 2009 @ 12:57:
Om nog wat aan de onbetrouwbare test toe te voegen: Javascript!

Nou, hier is een onbetrouwbare Haskell test...

Haskell:

isPrime n | n > 1 = test 2
  where test i | i * i > n = True
               | mod n i == 0 = False
               | otherwise = test (i+1)

main = do putStr "Nr of prime numbers found: "
          print $ length.filter isPrime $ [2..100000]

Java implementatie als referentie:

rvliegendhart@afsgw:..rvliegendhart/primebench> ghc --make -O2 Prime.hs
[1 of 1] Compiling Main             ( Prime.hs, Prime.o )
Linking Prime ...
rvliegendhart@afsgw:..rvliegendhart/primebench> time ./Prime
Nr of prime numbers found: 9592

real    0m0.683s
user    0m0.636s
sys     0m0.000s
rvliegendhart@afsgw:..rvliegendhart/primebench> time ./Prime
Nr of prime numbers found: 9592

real    0m0.637s
user    0m0.628s
sys     0m0.008s
rvliegendhart@afsgw:..rvliegendhart/primebench> time java Prime
Nr of prime numbers found: 9592

real    0m1.059s
user    0m0.404s
sys     0m0.036s
rvliegendhart@afsgw:..rvliegendhart/primebench> time java Prime
Nr of prime numbers found: 9592

real    0m0.534s
user    0m0.460s
sys     0m0.012s

Niet een eerlijke vergelijking, aangezien de Haskell versie wat dingen anders doet. Zoek de verschillen

[Juup]

Ik ben benieuwd hoe snel c hier zou zijn maar mijn c kennis is te mager (lees: afwezig) om dit om te meubelen naar c.

[user109731]

Dit programma is vrij eenvoudig om te zetten naar C, aangezien je vooral met integers werkt

C:

#include <stdio.h>
#include <math.h>

void calculatePrimeNumbers() { 
    int i = 0; 
    int primeNumberCounter = 0; 

    while (++i <= 100000) { 
        int i1 = (int) ceil(sqrt(i));
        int isPrimeNumber = 0;

        while (i1 > 1) { 
            if ((i != i1) && (i % i1 == 0)) { 
                isPrimeNumber = 0; 
                break; 
            } else if (!isPrimeNumber) { 
                isPrimeNumber = 1;
            } 
            --i1; 
        } 
        if (isPrimeNumber) { 
            ++primeNumberCounter; 
        } 
    } 
    printf("Nr of prime numbers found:%d\n", primeNumberCounter); 
} 
int main()
{
    calculatePrimeNumbers();
    return 0;
}

Copy/paste uit de TS en Java functies vervangen door die in C. Te compilen met gcc dmv:

gcc -O2 prime.c -o prime -lm

[ Voor 3% gewijzigd door user109731 op 30-11-2009 22:35 ]

[RayNbow]

JanDM schreef op maandag 30 november 2009 @ 22:33:
aangezien je vooral met integers werkt

Hmm... volgens mij kan ik m'n Haskell versie sneller krijgen door isPrime minder polymorf* te maken door de volgende regel toe te voegen:

Haskell:

isPrime :: Int -> Bool

* Als een argument van een functie elk integraal type kan zijn, dan heb je vaak de kans dat de compiler default naar Integer, wat een arbitraire-precisie integer is. Int is daarentegen minstens 29 bits (meestal 32 op 32 bits systemen).

Nieuwe timing:

rvliegendhart@afsgw:..rvliegendhart/primebench> time ./Prime
Nr of prime numbers found: 9592

real    0m0.114s
user    0m0.068s
sys     0m0.004s

Maar goed, zoals ik al zei doet mijn Haskell programma wat dingen anders, dus het is geen eerlijke vergelijking.

(Al mensen een idee wat de verschillen zijn? )

[ Voor 18% gewijzigd door RayNbow op 30-11-2009 23:07 ]

[user109731]

RayNbow schreef op maandag 30 november 2009 @ 23:03:
(Al mensen een idee wat de verschillen zijn? )

De andere versies beginnen bij sqrt(x) en tellen af. Jouw code doet het omgekeerd (en gebruikt dus geen sqrt). Verder test je niet of n != i (en mis je de nutteloze isPrimeNumber else-if)

[ Voor 7% gewijzigd door user109731 op 30-11-2009 23:30 ]

[Marcj]

Ik krijg hier het gevoel dat je allemaal nogal de sqrt functie in de verschillende talen aan het vergelijken bent. Als je een iets slimmere implementatie maakt die niet afhankelijk is van dit soort interne functie kun je misschien al een iets betere vergelijking trekken. Al ben je dan nog steeds puur integer berekeningen aan het testen...

Volgens mij is dat ook de voornaamste reden waarom de implementatie in Haskell nu zo snel is, die heeft een vermenigvuldiging ipv een sqrt

En dan nog... waar hebben we het over???

[.oisyn]

Da's ook onzin, het is niet alsof sqrt() in de inner loop aangeroepen wordt. En 100.000 keer sqrt aanroepen kost ook geen drol.

.edit: ik kom op gemiddeld 66.3 cycles per std::sqrt() in C++ op een Core 2, hij draait op 3.2GHz dus dat is 2ms voor 100.000 aanroepen. Poe hee!

[ Voor 40% gewijzigd door .oisyn op 30-11-2009 23:53 ]

[RayNbow]

JanDM schreef op maandag 30 november 2009 @ 23:28:
[...]

De andere versies beginnen bij sqrt(x) en tellen af. Jouw code doet het omgekeerd (en gebruikt dus geen sqrt). Verder test je niet of n != i (en mis je de nutteloze isPrimeNumber else-if)

Correct

* RayNbow haat trouwens sqrt in Haskell omdat het een Fractional type vraagt. Dan moet je dus eerst je Int of Integer omzetten via fromInteger... wordt je code niet mooier van.

[Soultaker]

Wees blij dat je niet in OCaml programmeert.

spoiler:

In OCaml bestaat geen overloading, waardoor je een operator * hebt voor het vermenigvuldigen van twee integers, *. voor het vermenigvuldigen van floats, Int64.mul (!!!) voor het vermenigvuldigen van 64-bit integers (nuttig, want de default integers zijn maar 31 (!) bits breed. Iets simpels als een integer met een float vermenigvuldigen kan niet eens.

[.oisyn]

JanDM schreef op maandag 30 november 2009 @ 23:28:
[...]

De andere versies beginnen bij sqrt(x) en tellen af. Jouw code doet het omgekeerd (en gebruikt dus geen sqrt). Verder test je niet of n != i (en mis je de nutteloze isPrimeNumber else-if)

Overigens kun je de kwadraat ook wegwerken mbv forward differencing, al zal dat tegenwoordig niet zoveel nut meer hebben

C++:

// mul
for (int i = 2; i * i < n; i++)
    // ...

// adds
int i2 = 4;
int d = 5;
for (int i = 2; i2 < n; i2 += d, d += 2, i++)
    // ...

[user109731]

Wel grappig om te zien hoe GCC dit optimaliseert:

GAS:

.L6:
    // sqrt, ceil, etc.
    // i in %ebx, i1 in %ecx, primeNumberCounter in %esi
.L8:
    cmpl    %ecx, %ebx
    je  .L4
    movl    %ebx, %edx
    movl    %ebx, %eax
    sarl    $31, %edx
    idivl   %ecx
    testl   %edx, %edx
    je  .L3
.L4:
    subl    $1, %ecx
    cmpl    $1, %ecx
    jg  .L8
    addl    $1, %esi
.L3:
    addl    $1, %ebx
    cmpl    $100001, %ebx
    jne .L6

Ongeveer dit:

C:

int i = 0;
int primeNumberCounter = 0;

do 
{
  int i1 = ceil(sqrt(i));
  if(i1 <= 1) 
    goto L3;
  do 
  {
    if(i1 == i)
      continue;
    if(i % i1 == 0)
      goto L3;
  } 
  while(--i1 > 1);
  
  primeNumberCounter++;
L3:
} 
while(++i != 100001);

De isPrimeNumber is dus compleet weggeoptimaliseerd

[ Voor 4% gewijzigd door user109731 op 01-12-2009 10:35 ]

[Juup]

JanDM schreef op maandag 30 november 2009 @ 22:33:
Dit programma is vrij eenvoudig om te zetten naar C, aangezien je vooral met integers werkt
...
Copy/paste uit de TS en Java functies vervangen door die in C. Te compilen met gcc dmv:

gcc -O2 prime.c -o prime -lm

Bash:

$ time ./prime
Nr of prime numbers found:9592

real    0m0.414s
user    0m0.398s
sys     0m0.007s

Dus c is vergelijkbaar in snelheid met Java. Verrassend.

[.oisyn]

Ik heb jou anders geen Java tijden zien posten. En aan de tijden van de TS kun je niet refereren want dat draaide op een hele andere PC.

[ Voor 40% gewijzigd door .oisyn op 01-12-2009 13:04 ]

[Juup]

Goed punt. Java bij mij:

Bash:

$ time java Prime
Nr of prime numbers found: 9592

real    0m0.676s
user    0m0.566s
sys     0m0.090s

Dus C > Java > Javascript >> Perl > PHP > Ruby > Python
(de Haskell test zal ik maar even buiten beschouwing laten)

[ Voor 29% gewijzigd door Juup op 01-12-2009 15:18 ]

[.oisyn]

Wat ik wel frappant vind is dat PHP bij jou relatief een stuk langzamer dan bij de topicstarter

[Soultaker]

Ik kom hier ook op 7.2s voor PHP (5.2.11) en 9.3s voor Perl (5.8.8) beide onder x86_64 Linux.

Voor de volledigheid maar even alle data op mijn systeem (alleen usertime); Athlon64 3000+ onder 64-bit Linux.

Taal	Versie	Tijd
Java	1.6.0.17	0.40s
PHP	5.2.11	7.00s
Perl	5.8.8	9.21s
Python	3.1.1	15.92s
Python	2.6.4	17.65s
Ruby	1.8.7	20.28s

Deze resultaten komen overeen met de algemene tendens: Ruby is toch echt het traagst, Python is iets beter. PHP en Perl zijn de snelste scripttalen. Wel moet gezegd worden dat Ruby en Python beiden (by default) met willekeurig grote integers werken, terwijl de overige talen native (of 32-bits) integers gebruiken. Misschien dat dat het verschil verklaart.

[ Voor 98% gewijzigd door Soultaker op 01-12-2009 17:31 ]

[Juup]

.oisyn schreef op dinsdag 01 december 2009 @ 15:22:
Wat ik wel frappant vind is dat PHP bij jou relatief een stuk langzamer dan bij de topicstarter

Misschien is PHP op Mac OS minder geoptimaliseerd?

[Verwijderd]

Hier op Mac:

mbGH:~ guido$ time php ~/test.php 
Nr of prime numbers found: 9592

real	0m3.649s
user	0m2.675s
sys	0m0.165s

[ Voor 3% gewijzigd door Verwijderd op 01-12-2009 18:15 ]

[RayNbow]

JanDM schreef op maandag 30 november 2009 @ 22:33:
Dit programma is vrij eenvoudig om te zetten naar C, aangezien je vooral met integers werkt

C:

/* snip */

Heb dit C programma omgezet naar een Haskell versie. Het is geen mooie code, maar ja, dat krijg je als je de while loop 1:1 omzet naar een recursieve functie.

code:

sqrt' :: Int -> Int
sqrt' = ceiling . sqrt . fromIntegral

isPrime n = go (sqrt' n) False
  where go i p | i > 1 =
                    if n /= i && mod n i == 0
                    then False
                    else if not p
                         then go (i-1) True
                         else go (i-1) p
               | otherwise = p

main = do putStr "Nr of prime numbers found: "
          print $ length.filter isPrime $ [1..100000]

Oude GHC 6.6 versus Java 1.6:

rvliegendhart@afsgw:..rvliegendhart/primebench> ghc --make -O2 PrimeTrue.hs
[1 of 1] Compiling Main             ( PrimeTrue.hs, PrimeTrue.o )
Linking PrimeTrue ...
rvliegendhart@afsgw:..rvliegendhart/primebench> time ./PrimeTrue
Nr of prime numbers found: 9592

real    0m0.515s
user    0m0.512s
sys     0m0.000s
rvliegendhart@afsgw:..rvliegendhart/primebench> time java Prime
Nr of prime numbers found: 9592

real    0m0.535s
user    0m0.460s
sys     0m0.020s

[Juup]

Cool. Zullen we zeggen dat Java en Haskell in dezelfde snelheids-grootteorde zitten?

[RayNbow]

Juup schreef op woensdag 02 december 2009 @ 14:59:
Cool. Zullen we zeggen dat Java en Haskell in dezelfde snelheids-grootteorde zitten?

Dat kun je nooit zo zeggen. Alleen in dit soort priemprogramma's waar niet al te veel bijzonders gedaan wordt kan de GHC compiler veel dingen wegoptimaliseren. De tail recursive isPrime/go functie kan makkelijk worden omgezet naar een loop. Verder kan de lijst [1..100000] in de main worden weggeoptimaliseerd aangezien elk element van de lijst meteen geconsumeerd wordt. Dit wordt dus ook vertaald naar een loop.

[Rob]

Soultaker schreef op dinsdag 01 december 2009 @ 17:07:
Ik kom hier ook op 7.2s voor PHP (5.2.11) en 9.3s voor Perl (5.8.8) beide onder x86_64 Linux.

Voor de volledigheid maar even alle data op mijn systeem (alleen usertime); Athlon64 3000+ onder 64-bit Linux.

Taal	Versie	Tijd
Java	1.6.0.17	0.40s
PHP	5.2.11	7.00s
Perl	5.8.8	9.21s
Python	3.1.1	15.92s
Python	2.6.4	17.65s
Ruby	1.8.7	20.28s

Deze resultaten komen overeen met de algemene tendens: Ruby is toch echt het traagst, Python is iets beter. PHP en Perl zijn de snelste scripttalen. Wel moet gezegd worden dat Ruby en Python beiden (by default) met willekeurig grote integers werken, terwijl de overige talen native (of 32-bits) integers gebruiken. Misschien dat dat het verschil verklaart.

Zou je 'm ook met gecompileerde PHP kunnen uitvoeren?

[Sypher]

Wow mijn Atompje (Ubuntu 9.10 i386) doet er soms wel verrekte lang over zeg

PHP 5.2.10 + Suhosin

Nr of prime numbers found: 9592

real    0m22.039s
user    0m21.573s
sys     0m0.040s

Perl v5.10.0

Nr of prime numbers found: 9592

real    0m15.449s
user    0m15.193s
sys     0m0.016s

Python2

Nr of prime numbers found: 9592

real    0m47.080s
user    0m46.299s
sys     0m0.012s

Python2.5

Nr of prime numbers found: 9592

real    0m54.339s
user    0m52.879s
sys     0m0.068s

Python 2.6

Nr of prime numbers found: 9592

real    0m46.995s
user    0m46.211s
sys     0m0.012s

Andere scriptje

Nr of prime numbers found: 9592

real    0m16.362s
user    0m16.073s
sys     0m0.008s

Die is betrekkelijk sneller in mijn geval

Ruby 1.8.7

Nr of prime numbers found:
9592

real    0m42.717s
user    0m41.987s
sys     0m0.048s

C

Nr of prime numbers found:9592

real    0m0.597s
user    0m0.592s
sys     0m0.004s

Java kan ik niet testen wat dat heb (en hoef ) ik niet.

Overigens draait deze Atom de nodige processen (150 stuks) wat ongetwijfeld wel iets impact heeft.

[ Voor 91% gewijzigd door Sypher op 03-12-2009 12:27 ]

[Confusion]

Juup schreef op woensdag 02 december 2009 @ 14:59:
Cool. Zullen we zeggen dat Java en Haskell in dezelfde snelheids-grootteorde zitten?

Haskell kon toch zeker snelheden van een paar honderd kilometer per uur ten opzichte van Java bereiken.

[farlane]

Eigenlijk moet ik best gniffelen om deze nutteloze test omdat C weer de snelste blijkt te zijn in nutteloze benchmarks.

Juup schreef op dinsdag 01 december 2009 @ 12:53:
Dus c is vergelijkbaar in snelheid met Java. Verrassend.

C is op jouw systeem meer dan 30% sneller dan Java [in deze nutteloze benchmark].

[ Voor 4% gewijzigd door farlane op 03-12-2009 14:12 ]

[Juup]

farlane schreef op donderdag 03 december 2009 @ 14:11:
C is op jouw systeem meer dan 30% sneller dan Java [in deze nutteloze benchmark].

Ja maar omdat de test zo onbetrouwbaar is hebben we het over grootteordes. Het gaat mij niet om 10% meer of minder maar 10x zo langzaam zegt (mij) wel iets.

En ja ik weet dat deze test uitermate onbetrouwbaar, nietszeggend en nutteloos is.