Fibonacci-Folge / Benchmarks

Pascal, Basic und andere nicht aufgelistete
Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8486
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Fibonacci-Folge / Benchmarks

Beitrag von Xin » Fr Feb 24, 2017 3:21 pm

Zusammengefasste Benchmarks:

Quelltextlänge:

Code: Alles auswählen

-rw-r--r-- 1 xin xin  154 Feb 22 21:46 fib.g    (Genesys)
-rw-rw-r-- 1 xin xin    156 Feb 24 21:36 fib.f  (Forth)
-rw-rw-r-- 1 xin xin    158 Feb 24 21:36 fib.tcl  (TCL)
-rw-rw-r-- 1 xin xin  165 Feb 22 21:35 fib.py  (Python)
-rw-rw-r-- 1 xin xin  189 Feb 22 21:35 fib.php  (PHP)
-rw-rw-r-- 1 xin xin  194 Feb 22 21:52 fib.c     (C)
-rw-rw-r-- 1 xin xin    208 Feb 24 19:50 fib.rs   (Rust)
-rw-r--r-- 1 xin xin  221 Feb 22 20:40 fib.pl   (Perl)
-rw-rw-r-- 1 xin xin  297 Feb 22 21:56 fib.java   (Java)
Laufzeit auf einem Xeon X5675:

Code: Alles auswählen

GCC 6.2:    ~0,012s Nativ Optimiert
Clang 3.8:  ~0,014s Nativ Optimiert
Rust 1.10:  ~0,015s Nativ Optimiert
GCC 6.2:    ~0,021s Nativ
Clang 3.8:  ~0,023s Nativ
Genesys:    ~0,024s JIT
Rust 1.10:  ~0,033s Nativ
Java:       ~0,139s JIT
Forth:      ~0,149s JIT
PHP 7.0:    ~0,270s ByteCode
Python 2.7: ~0,570s ByteCode
Python 3.5: ~0,642s ByteCode
Perl 5.22:  ~1,480s ByteCode
TCL:        ~2,162s ByteCode
Genesys:    ~6,520s AST 

Ursprüngliches Posting

Ich mache für meine eigene Programmiersprache gerade ein paar Benchmarks, weswegen ich die Fibonacci-Zahlenreihe von 1-30 rekursiv berechne. Dabei habe ich zwei Ziele: Erstens will ich schnell sein. Hier verkacke ich total, was aber auch nicht verwunderlich ist, denn bisher konzentriere ich mich nicht auf Geschwindigkeit, sondern auf Syntax.

Daher meine Frage nach Implementationen von Fibonacci-Berechnungsprogrammen. Könnt ihr eine Programmiersprache, in der ihr das unten stehende C-Programm übersetzen könnt, die hier noch nicht aufgeführt ist? Vielleicht auch etwas ausgefallenere wie Haskell oder F# oder Scala?

Bei der Syntax liege ich bisher vorne: Programmlänge

Code: Alles auswählen

-rw-r--r-- 1 xin xin  154 Feb 22 21:46 fib.g
-rw-rw-r-- 1 xin xin  165 Feb 22 21:35 fib.py
-rw-rw-r-- 1 xin xin  189 Feb 22 21:35 fib.php
-rw-rw-r-- 1 xin xin  194 Feb 22 21:52 fib.c
-rw-r--r-- 1 xin xin  221 Feb 22 20:40 fib.pl
-rw-rw-r-- 1 xin xin  297 Feb 22 21:56 fib.java
Bei der Geschwindigkeit besteht noch "etwas" Nachholbedarf, allerdings bin ich auch noch per AST unterwegs, was gut zum Entwickeln ist, aber leider alles andere als schnell in der Ausführung:

Benchmark, der zweite: Laufzeit auf einem Xeon X5675

Code: Alles auswählen

GCC 6.2:    ~0,02sek Nativ
Java:       ~0,14sek Jit
PHP 7.0:    ~0,27sek ByteCode
Python 2.7: ~0,56sek ByteCode
Python 3.5: ~0,65sek ByteCode
Perl 5.22:  ~1,5sek  ByteCode
Genesys:    ~8,8sek  AST 
Interessant ist, dass PHP deutlich schneller als Python 2 ist, Python 2 spürbar schneller als Python 3 und Perl als ursprünglich mal als schnell angesehene Sprache eigentlich unter Ferner liefen läuft...

Folgendes Programm suche ich anderen Sprachen:

Code: Alles auswählen

#include <stdio.h>

int fib( int f )
{
  if( f <= 2 )
    return 1;
  else
    retunr fib( f-1 ) + fib( f-2 );
}

int main( void )
{
  for( int value=1; value <= 30; value++ )
    printf( "%d: %d\n", value, fib( value ));

  return 0;
}
Vielleicht kann ja jemand etwas esotherisches?
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

canlot
Beiträge: 393
Registriert: Di Mär 08, 2011 11:01 pm
Wohnort: NRW

Re: Fibonacci-Folge / Benchmarks

Beitrag von canlot » Fr Feb 24, 2017 6:23 pm

Rust:

Code: Alles auswählen

fn fib(num: u32) -> u32 {
    if num <= 2 { return 1; } 
    else { return fib(num - 1) + fib(num - 2); }
}
fn main() {
    for i in 1..31 { println!("{} - {}", i, fib(i)); }
}
https://is.gd/bRcE8a

edit: Was bedeute AST?
Unwissenheit ist ein Segen

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8486
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Fibonacci-Folge / Benchmarks

Beitrag von Xin » Fr Feb 24, 2017 7:43 pm

canlot hat geschrieben:Rust:
Sehr schön, Rust wollte ich eh mal lernen.
Danke :)

Code: Alles auswählen

    for i in 1..31 { println!("{} - {}", i, fib(i)); }
Das ist ja jeck... die gleiche Syntax mit den 2 Punkten (1..31) habe auch für Ranges.
canlot hat geschrieben:edit: Was bedeute AST?
Abstract Syntax Tree.

Der Compiler baut eine Baumstruktur auf, die den Quelltext repräsentiert. Ich interpretiere diesen Baum. Das ist langsamer in der Ausführung, aber man kann sehr einfach mal Änderungen an der Sprache vornehmen.


Edit: Ich habe den Quelltext mal angepasst (gleiche Variablennamen etc) und kompiliert.

Die Datei ist damit 208 Bytes groß, die Ausführung dauert 0,03 Sekunden.
Mit Optimizier braucht C 0,012 Rust 0,015 Sekunden.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

mfro
Beiträge: 305
Registriert: Mi Jan 16, 2013 4:58 pm

Re: Fibonacci-Folge / Benchmarks

Beitrag von mfro » Fr Feb 24, 2017 8:40 pm

FORTH

Code: Alles auswählen

: fib
  DUP 1 > IF 
  1- DUP 1- RECURSE SWAP RECURSE + THEN
;


: main
    30 1 ?DO
        i DUP . ." = " fib . CR
    LOOP
;

main
bye

Code: Alles auswählen

1 = 1 
2 = 1 
3 = 2 
4 = 3 
5 = 5 
6 = 8 
7 = 13 
8 = 21 
9 = 34 
10 = 55 
11 = 89 
12 = 144 
13 = 233 
14 = 377 
15 = 610 
16 = 987 
17 = 1597 
18 = 2584 
19 = 4181 
20 = 6765 
21 = 10946 
22 = 17711 
23 = 28657 
24 = 46368 
25 = 75025 
26 = 121393 
27 = 196418 
28 = 317811 
29 = 514229 

real	0m0.061s
user	0m0.060s
sys	0m0.000s
It's as simple as that. And remember, Beethoven wrote his first symphony in C.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8486
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Fibonacci-Folge / Benchmarks

Beitrag von Xin » Fr Feb 24, 2017 8:46 pm

mfro hat geschrieben:FORTH
:)

Wie kompiliert man das? ^^

Code: Alles auswählen

: fib
  DUP 1 > IF 
  1- DUP 1- RECURSE SWAP RECURSE + THEN
;

: main
    30 1 ?DO
        i DUP . ." = " fib . CR
    LOOP
;

main
bye
Kannst Du mir den Code etwas erklären?
Ich verstehe weder die Funktion fib, noch kann ich mir den Loop sicher herleiten.

Code: Alles auswählen

29 = 514229 

real	0m0.061s
Da fehlt die 30 ^^
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

mfro
Beiträge: 305
Registriert: Mi Jan 16, 2013 4:58 pm

Re: Fibonacci-Folge / Benchmarks

Beitrag von mfro » Fr Feb 24, 2017 9:27 pm

Xin hat geschrieben: Wie kompiliert man das? ^^
Gar nicht. Forth ist ursprünglich ein Interpreter (es gibt allerdings auch Compiler).

Code: Alles auswählen

gforth fib.f
Xin hat geschrieben: Kannst Du mir den Code etwas erklären?
Ich kann's eigentlich auch nicht richtig, dachte aber, das wär' mal was zum Ausprobieren ;)

In Forth dreht sich alles um den Stack (deswegen sieht alles ein wenig "rückwärts" aus). Literale und alles, was kein WORD ist, kommt auf den Stack. WORDS "verbrauchen" Elemente vom Stack, wenn sie ein Ergebnis haben, kommt das wieder auf den Stack (TOS). WORDS sind also praktisch Funktionen.

Hier kurz die verwendeten WORDS:

DUP: dupliziert das oberste Element (TOS) des Stacks
. holt das oberste Element des Stacks und gibt es aus
> nimmt die beiden obersten Elemente vom Stack und vergleicht sie. Ergebnis entweder -1 (TRUE) oder 0 kommt wieder auf den Stack
IF Code bis THEN wird ausgeführt, wenn TRUE auf dem Stack gefunden
: definiert ein neues WORD, Ende bei ;
RECURSE ruft das WORD auf, in dem es steht (der Name eines Words ist vor dem ; nicht bekannt)
Xin hat geschrieben: Ich verstehe weder die Funktion fib, noch kann ich mir den Loop sicher herleiten.
fib geht also folgendermaßen:

Code: Alles auswählen

DUP 1 > IF 
TOS (unser WORD-Argument) doppeln, eine 1 pushen, vergleichen

Code: Alles auswählen

 1 - DUP 1 - RECURSE SWAP RECURSE + THEN
ziehe 1 von TOS ab, Ergebnis wieder da hin,
TOS duplizieren
1 abziehen
fib aufrufen
die beiden obersten Stackelemente tauschen
fib aufrufen
die beiden obersten Stackelemente addieren
Xin hat geschrieben:

Code: Alles auswählen

29 = 514229 

real	0m0.061s
Da fehlt die 30 ^^
Ja, das muß 31 sein (LOOP ist ausschliessend)
It's as simple as that. And remember, Beethoven wrote his first symphony in C.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8486
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Fibonacci-Folge / Benchmarks

Beitrag von Xin » Fr Feb 24, 2017 10:02 pm

mfro hat geschrieben:
Xin hat geschrieben: Wie kompiliert man das? ^^
Gar nicht. Forth ist ursprünglich ein Interpreter (es gibt allerdings auch Compiler).
Die Ausführungszeiten fand ich beeindruckend und auch das Programm ist beeindruckend kurz.
Aber ich kann nicht draufgucken und sofort verstehen, was da passiert.
Gforth kompiliert mit Hilfe von GCC und führt dann sofort aus. Also Just-In-Time-Compiling.
mfro hat geschrieben:
Xin hat geschrieben: Kannst Du mir den Code etwas erklären?
Ich kann's eigentlich auch nicht richtig, dachte aber, das wär' mal was zum Ausprobieren ;)

In Forth dreht sich alles um den Stack (deswegen sieht alles ein wenig "rückwärts" aus). Literale und alles, was kein WORD ist, kommt auf den Stack. WORDS "verbrauchen" Elemente vom Stack, wenn sie ein Ergebnis haben, kommt das wieder auf den Stack (TOS). WORDS sind also praktisch Funktionen.
Alles klar, das ist also halb esoterisch.... so will man im Alltag wohl nicht kompilieren.

mfro hat geschrieben: . holt das oberste Element des Stacks und gibt es aus
Bzw. gibt den dranstehenden String aus?

Fib verstehe ich nun. Aber das will ich so nicht programmeiren :D

Aber vielen Dank für die Aufklärung, nun habe ich auch mal Forth gesehen. :)
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

mfro
Beiträge: 305
Registriert: Mi Jan 16, 2013 4:58 pm

Re: Fibonacci-Folge / Benchmarks

Beitrag von mfro » Fr Feb 24, 2017 10:38 pm

Xin hat geschrieben: Aber ich kann nicht draufgucken und sofort verstehen, was da passiert.
Ich denke, das ist hauptsächlich eine Frage der Übung. Wir sind's halt nicht gewohnt, in Stacks zu denken. Es gibt Menschen (ich gehöre nicht dazu), die schwören immer noch auf die UPN-Notation der alten HP Taschenrechner und können damit konkurrenzlos flott umgehen.
Xin hat geschrieben: Die Ausführungszeiten fand ich beeindruckend und auch das Programm ist beeindruckend kurz.
Ist doch eigentlich gar nicht schlecht für eine Programmiersprache, die (noch) älter ist als C?
It's as simple as that. And remember, Beethoven wrote his first symphony in C.

Benutzeravatar
Bebu
Beiträge: 562
Registriert: Mi Okt 21, 2009 6:19 pm
Wohnort: In der Nähe von Salzburg - Bin aber kein Österreicher!

Re: Fibonacci-Folge / Benchmarks

Beitrag von Bebu » Mi Mär 01, 2017 7:05 pm

Ich habe auch noch einen für euch:

Code: Alles auswählen

package main

import "fmt"

func fib(f int) int {
	if f <= 2 {
		return 1
	}
	return fib(f-1) + fib(f-2)
}

func main() {
	for i := 0; i < 31; i++ {
		fmt.Println(i, "=", fib(i))
	}
}
Ist jetzt nicht besonders esotherisch, aber Go ist eine ganz lustige Sprache.
Wer immer nach dem Unerreichbaren jagt, der wird irgendwann auf die Schnauze fallen!

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8486
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Fibonacci-Folge / Benchmarks

Beitrag von Xin » Do Mär 02, 2017 10:46 am

Vielen Dank. Werde ich am Wochenende mal ins Rennen schicken und dann das erste Posting aktualisieren.

Go sieht ja eigentlich noch recht unscheinbar aus. Hast Du damit mal tiefergehende Erfahrung gesammelt?
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Antworten