Virtueller Speicher Überlauf

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Bernd Jonsson
User
Beiträge: 9
Registriert: Sonntag 22. Oktober 2006, 21:05

Sonntag 22. Oktober 2006, 21:12

Betrifft: Virtueller Speicher Überlauf

Aus dem Python Cookbook ASPN entnahm ich den Algorithmus 410662 zur Primzahlbestimmung.
Ich wollte (fast aus Langeweile) die Zeitersparnis gegenüber dem üblichen Verfahren feststellen.
Dabei blieb das Programm bei sehr großen Zahlen 'hängen'. Mehr durch Zufall entdeckte ich einen Fehler-Hinweis: Mangel an virtuellem Speicher.
Ursache ist der immense Speicherbedarf in der Routine primes (Algorithmus 366178) im Statement "s=range(3,n+1,2)"
Damit entpuppte sich Algorithmus 410662 als Flop.

Meine Frage ist, sollte der Python-Interpreter diesen Fehler nicht entdecken und melden, statt sich stillschweigend in eine Dauerschleife zu begeben?

Gruß Bernd
murph
User
Beiträge: 622
Registriert: Freitag 14. April 2006, 19:23
Kontaktdaten:

Sonntag 22. Oktober 2006, 21:33

der pythoninterpreter macht das, was da steht.
der meldet keine fehler wie ein c/c++ compiler, er beachtet gar nicht,
was er macht. er weiß es auch gar nicht.
http://www.cs.unm.edu/~dlchao/flake/doom/
Bernd Jonsson
User
Beiträge: 9
Registriert: Sonntag 22. Oktober 2006, 21:05

Montag 23. Oktober 2006, 09:31

Danke Murph,
ich dachte schon, einen Fehler im Interpreter gefunden zu haben.
Dafür ist der Interpreter wenigstens schnell.
Gruß Bernd
BlackJack

Montag 23. Oktober 2006, 09:48

Argh! Murph schreibt mal wieder Müll. Er weiss nicht was er tut, der Pythoninterpretierer schon. Wenn der Speicher ausgeht, dann wird das Programm mit einer `MemoryError` Ausnahme abgebrochen:

Code: Alles auswählen

$ python forum.py
Traceback (most recent call last):
  File "forum.py", line 42, in ?
    main()
  File "forum.py", line 38, in main
    print isprime(999999999999999999)
  File "forum.py", line 11, in isprime
    klist = primes(int(math.sqrt(aNumber+1)))
  File "forum.py", line 20, in primes
    s=range(3,n+1,2)
MemoryError
Bernd Jonsson hat geschrieben:Dabei blieb das Programm bei sehr großen Zahlen 'hängen'. Mehr durch Zufall entdeckte ich einen Fehler-Hinweis: Mangel an virtuellem Speicher.
Wo hast Du den denn zufällig entdeckt? Wie sieht Dein Programm aus und wie hast Du es gestartet?
Ursache ist der immense Speicherbedarf in der Routine primes (Algorithmus 366178) im Statement "s=range(3,n+1,2)"
Damit entpuppte sich Algorithmus 410662 als Flop.
Wieso Flop? Er tut das was er soll.
Meine Frage ist, sollte der Python-Interpreter diesen Fehler nicht entdecken und melden, statt sich stillschweigend in eine Dauerschleife zu begeben?
Sollte nicht nur, er tut es auch.
murph
User
Beiträge: 622
Registriert: Freitag 14. April 2006, 19:23
Kontaktdaten:

Montag 23. Oktober 2006, 13:17

@blackjack:
das habe ich so direkt gelesen!
der schaut beim compilieren des byte-codes nicht nach, was gemacht wird,
das passiert erst, wenn der code ausgeführt wird.
das stand in einem artikel im internet, den ich sehr aufmerksam gelesen habe.
falls du daran zweifel haben solltest, kann ich den vllt nochmal raussuchen.
kann auch sein, dass der autor falsch lag.
http://www.cs.unm.edu/~dlchao/flake/doom/
CM
User
Beiträge: 2464
Registriert: Sonntag 29. August 2004, 19:47
Kontaktdaten:

Montag 23. Oktober 2006, 13:30

@murph: Das stimmt zwar, ist aber nicht relevant: Der Interpreter, soll und wird, wenn das Problem so auftritt wie beschrieben, die entsprechende Fehlermeldung abgeben.

Gruß,
Christian
murph
User
Beiträge: 622
Registriert: Freitag 14. April 2006, 19:23
Kontaktdaten:

Montag 23. Oktober 2006, 13:44

ok
http://www.cs.unm.edu/~dlchao/flake/doom/
BlackJack

Montag 23. Oktober 2006, 13:46

Und das ist auch bei C/C++ nicht anders, auch die Erkennen beim Übersetzen nicht, ob das Programm während der Laufzeit irgendwann einmal zuviel Speicher verbrauchen könnte. Wie sollte das auch gehen!?
murph
User
Beiträge: 622
Registriert: Freitag 14. April 2006, 19:23
Kontaktdaten:

Montag 23. Oktober 2006, 14:05

indem man mitzählt...^^ *scherz*
aber hier geht es um eine endlosschleife, die den speicher auffrisst,
dass könnte man sehr wohl mitverfolgen, ob die schleife sinnvoll ist.
hatte nur noch im hinterkopf, dass C-compiler ganz komische sachen manchmal machen...
http://www.cs.unm.edu/~dlchao/flake/doom/
CM
User
Beiträge: 2464
Registriert: Sonntag 29. August 2004, 19:47
Kontaktdaten:

Montag 23. Oktober 2006, 14:45

murph hat geschrieben: aber hier geht es um eine endlosschleife, die den speicher auffrisst,
dass könnte man sehr wohl mitverfolgen, ob die schleife sinnvoll ist.
Ist aber reichlich theoretisch: Jeder Interpreter / Compiler müsste für alle (auch zukünfigen) Maschinen wissen, wie groß Speicherplätze für bestimmte Typen sind (was bei dynamischen Sprachen nochmal so witzig sein dürfte wie für statische ;-)). Und dann müßte der Interpreter / Compiler für jedes Nesting Level die Logik überprüfen. Das ist hier noch vergleichsweise einfach, aber grundsätzlich nicht ohne, wenn nicht gar unmöglich (vielleicht wisse da "echte" Informatiker mehr).
Außerdem: Wo gibt es hier bitte eine Endlosschleife, jedenfalls nicht in den beiden Recipies.

Gruß,
Christian
Benutzeravatar
keppla
User
Beiträge: 483
Registriert: Montag 31. Oktober 2005, 00:12

Montag 23. Oktober 2006, 14:51

dass könnte man sehr wohl mitverfolgen, ob die schleife sinnvoll ist.
Sofern man definiert, was man für sinnvoll hält, könnte, je nach definition, da etwas überlegt werden.
Allerdings bezweifele ich das, da das ziemlich in Richtung Halteproblem geht.
BlackJack

Montag 23. Oktober 2006, 16:37

murph hat geschrieben:aber hier geht es um eine endlosschleife, die den speicher auffrisst,
dass könnte man sehr wohl mitverfolgen, ob die schleife sinnvoll ist.
Nein hier geht es nicht um eine Endlosschleife sondern um eine einfache Speicheranforderung bei der Erstellung einer Liste mit `range()`.

Und ob eine Schleife sinvoll ist bestimmt der Programmierer weil der den Sinn kennt. Solange Computer nicht denken können, können sie auch solche Sinnfragen nicht beantworten.
Bernd Jonsson
User
Beiträge: 9
Registriert: Sonntag 22. Oktober 2006, 21:05

Dienstag 24. Oktober 2006, 18:55

Hallo BlackJack,
a) Wie ich auf die Meldung 'virtueller Speichermangel' gestoßen bin,
wusste ich nicht - Panikstimmung.
Ich arbeite mit Python unter Windows XP, das Internet nutze ich unter Linux.
Das ist natürlich für diese Diskussion umständlich.
Inzwischen habe ich das Programm erneut gestartet und dann mittels AltGr/F4
abgebrochen.
Unten rechts erschien die Meldung: Windows - nicht genügend virtueller Speicher.
... Die Auslagerungsdatei wird vergrößert. Speicheranforderungen können
während dieses Vorgangs abgelehnt werden. ...

Das Ganze scheint wohl ein Fehler von Windows XP zu sein und nicht vom Python-
Interpreter! Sch....önes Windows!

b) Dass Dein Programm ordnungsgemäß mit Fehlermeldung abbrach, wunderte mich
zunächst, aber Du arbeitest vermutlich mit Linux? Erst wollte ich Dir meinen
Quelltext zusenden, aber das erübrigt sich jetzt wohl, denn unsere
Progmme sind im Kern ja identisch.

c) Wieso Flop? Weil das Programm schon bei relativ kleinen Zahlen
etwa bei 10**15 aussteigt. Bis dahin ist der Zeitgewinn noch relativ klein,
wenn als Divisor nur die zuvor ermittelten Primzahlen benutzt werden.
Die Idee von gian paolo ciceri ist zwar gut, bringt aber letztlich nichts.

Habe das Programm jetzt abgeändert, ohne Speicherplatz für das
Eratosthenes-Sieb, komme dadurch auf Primzahlen wie (10**20 + 17)
bei ca. 90 Minuten Rechenzeit.
Klar, ist alles nur Spielerei, selbst auf Superrechnern dürfte mit
diesem Algorithmus spätestens nach zehn weiteren Dezimalen Schluss
sein.
Trotzdem würde ich das verbesserte Programm gern hier ins Netz stellen,
zur Diskussion, Anregung und zur Kritik. Wie und wo mache ich das?
Gruß Bernd
BlackJack

Dienstag 24. Oktober 2006, 22:21

Bernd Jonsson hat geschrieben: a) Wie ich auf die Meldung 'virtueller Speichermangel' gestoßen bin,
wusste ich nicht - Panikstimmung.
Ich arbeite mit Python unter Windows XP, das Internet nutze ich unter Linux.
Das ist natürlich für diese Diskussion umständlich.
Ich habe mein Windows, das ich ab und zu leider noch brauche, in einen VMWare Server gesperrt. Ist mittlerweile kostenlos. Also der VMWare Server, nicht Windows. ;-)
c) Wieso Flop? Weil das Programm schon bei relativ kleinen Zahlen
etwa bei 10**15 aussteigt.
Eher schon bei 2**31-1, das ist zumindest bei 32-Bit Systemen die maximale Anzahl an Elementen in einer Liste. Bei 64-Bit Systemen und Python 2.5 geht dann mehr. :-)
Habe das Programm jetzt abgeändert, ohne Speicherplatz für das
Eratosthenes-Sieb, komme dadurch auf Primzahlen wie (10**20 + 17)
bei ca. 90 Minuten Rechenzeit.
Klar, ist alles nur Spielerei, selbst auf Superrechnern dürfte mit
diesem Algorithmus spätestens nach zehn weiteren Dezimalen Schluss
sein.
Und für praktische Anwendungen nimmt man dann doch lieber in Kauf ein kleines Restrisiko einer Nicht-Primzahl zu haben und benutzt Miller-Rabin zum Testen. Ist wesentlich schneller.
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Mittwoch 25. Oktober 2006, 15:55

Bernd Jonsson hat geschrieben: Trotzdem würde ich das verbesserte Programm gern hier ins Netz stellen,
zur Diskussion, Anregung und zur Kritik. Wie und wo mache ich das?
Du kannst es entweder, wenn es nicht zu lang ist direkt hier rein stellen oder anderfalls einen Paste-Service verwenden. Mein Lieblingspaste ist inzwischen paste.e-scribe.com geworden, weil es mit Python gemacht ist :)
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Antworten