[FRAGE] PHP und das Memory Limit bei Primzahlen

[SteelWheel]

Hallo jswelt'ler,

ich habe hier eine XAMPP Installation und bin da auch sehr zufrieden mit. Aufgrund einer Unterhaltung im Skype habe ich mir ein Script gezimmert, was Zahlen von 1 bis N analysieren soll und die Primzahlen mitmeißeln darf. Klappt alles und ist auch keine Script- oder Verständnisfrage.

Ein Beinbruch wird es, wenn N größer wird! Für die Analyse von 1 bis 1.000.000 (Punkt als Lesehilfe) sind das 1,4 Sekunden (inkl. Ausgabe aller Primzahlen) ... mir fliegt allerdings PHP um die Ohren, wenn ich 1 bis 100.000.000.000 probiere. Die bekannte Meldung bzgl. "Fatal error: Allowed memory size of 262144 bytes exhausted (tried to allocate 35 bytes) ..." ist die Folge.

Tjoar, schnell nachgeschlagen, in der php.ini geschaut und sehe, dass dort das Memory-Limit bereits auf 2048M steht - das scheint auch der höchstmögliche Wert zu sein für PHP. Allerdings - und das macht mich stutzig -: Die angezeigte Byte-Zahl der Fehlermeldung ist nicht wirklich deckungsgleich mit der Vorgabe.

Der Versuch es mit ini_sets "memory limit" vorab zu definieren, endet exakt genauso.

Mit ein wenig Googlen kam ich auf "-1", um das Limit zu deaktivieren. Es ändert sich nichts ... eine Fehlermeldung (sehr schnell sogar; nur die Bytes weichen ab). Hmmm ...

Ich habe es dann in der Shell (aka Dosbox) probiert - ist ein reines PHP-Problemchen (nicht über XAMPP jetzt mittelbar).

Meine Suche nach einem "oberen, aber internen Limit" für PHP ergab nur, dass es eine physische Antwort ist, die die Hardware (Speicher) vorgibt (was ich in erster Linie merkwürdig finde - ist PHP x64 kompatibel?). Die Antwort ist aber auch nicht hilfreich, da das System hier eigentlich genügend Hauptspeicher (32GB) hat, das Script aber nicht darauf zurückgreifen kann (bei Bedarf).

Eine Anhöhung auf bspw. 4096M lässt XAMPP (aka Apache) bspw. gar nicht mehr starten.

Weiß jemand mehr? Schraube ich an der falschen Stelle? Wie kann ich für mein Script mehr Speicher zur Verfügung stellen? Es ist nur eine Spielerei - keine Hausaufgabe oder schlimmer.

Bereits jetzt schon vorab vielen Dank für mögliche Hilfestellungen.

Beste Grüße

 

[kkapsner]

PHP gibt es schon für 64-bit Systeme. Aber was da bei dir läuft, kannst nur du wissen. Aber dein XAMPP müsste dann auch 64-bit sein.
Aber ich denke mal, dass du ein 32-bit PHP hast, da du sonst keine 2GB Grenze für den Speicher haben solltest.

Dann wirst du aber mit 100.000.000.000 sowieso Probleme bekommen, da das größer als PHP_INT_MAX (bei 32-bit gleich 2.147.483.647) ist.

Zu deinem Problem: ich würde davon ausgehen, dass die Einstellung in der php.ini nicht angenommen wird bzw. von irgendwas anderem überschrieben wird (der Default sind 265 KB auch nicht...). Was gibt denn phpinfo() als memory limit aus?

 

[SteelWheel]

Hi, Grüße Dich ... an die phpinfo() dachte ich schon selbst und die spricht auch von 2048 MB (Screener lege ich gern bei, falls gewünscht). Dort hatte ich vor meinem Posting schon reingeschaut. Da dort aber der angelegte Wert steht, sah es für mich nach "hat er übernommen" auch aus (mit Zahlen darüber startet er nicht mehr - wie erwähnt).

Den INT-Max-Wert hatte ich ebenfalls schon im Verdacht - aber ließen sich Zahlen jenseits (nämlich größer) bearbeiten bzw. berechnen? Oder ist das Terrain dieser Zahlen nur Großrechnern vorbehalten? Ich muss meine Aussage von oben erweitern: Zum Glück ist es nichts auf dem Dienstweg!

Hmmm ... ich dachte auch schon an den Wechsel auf Python (sehr guter Math-Core), aber wenn es eh ein Bit-Ding ist, würde der Wechsel der Programmiersprache nun auch nichts bringen. Somit wäre man als User tatsächlich "eingegrenzt". Hmmm ... grübel, grübel ... nehmen wir doch in der Theorie an, ich hätte hier gewöhnliche Artikelnummern ohne führenden Letter o. ä. (da zieht man keine Primzahl - ), aber wie könnte ich diese handhaben, wenn ich ein Abbild im Speicher verwenden würde wollen?! Das würde ja dann ausnahmslos als String gehen. Oder nehmen wir nackte ISBN-Nummern: 781.449.393.908 (bspw. - und ohne Punkte; das ist O'Reilly bzgl. Canvas in HTML5). Hmmmmmmmmmmm ... alles irgendwie doof ...

Tjoar, wie gehen Zahlen > 2,1 Mrd.?!


EDIT: Bei PHP steht "The x64 builds of PHP for Windows should be considered experimental, and do not yet provide 64-bit integer or large file support."

 

[tsseh]

Tjoar, wie gehen Zahlen > 2,1 Mrd.?!

für php hab ich auf die schnelle das hier gefunden.
scheint mir nicht optimal zu sein. in c++ würde es da klassen geben, die 2-n int variablen verwalten und die entsprechenden operatoren überschrieben haben.
ob das auch in php geht keine ahnung, wenn ja, würde ich an deiner stelle eher nach sowas suchen.
das hat aber vermutlich nichts mit deinem eigentlichen problem zu tun, da dort ja 35 byte reserviert werden sollen. und es würde mich wundern, wenn du mit so einem problem die 2 gb Grenze knackst. selbst bei schweinischer speicherfragmentierung.

 

[kkapsner]

Kannst du mal das Skript zeigen, das die Probleme macht. Mal sehen, was mein lokaler Webserver dazu sagt. (Ev. sieht auch jemand einen Speicherfresser).

Zahlen größer als INT_MAX kann man hald (mit Standard-PHP) nur noch als Fließkommazahlen repräsentieren und dann werden Primzahlenberechnungen unmöglich. Es gibt aber Erweiterungen, die mit beliebig großen Zahlen umgehen können: bignum - Working with large numbers in PHP - Stack Overflow.

PS: ISBN würde ich als String speichern.

 

[SteelWheel]

Grundthese des Scripts ist das Sieb des Griechen namens Erastothenes - ich wollte auf den besagten Modulo und zig Prüfungen verzichten. Demnach baue ich mir ein Array von 1 bis einschl. N und setzte alle auf "jo, Primzahl!" Mittels for-Schleife ackert er dann das Script ab und führt eine Multiplikation zwischen Array-Index und dem Multiplikator 2 aus (Bedingung der for-Schleife: Zähler ist <= ceil(sqrt($N)). Um das Array dann von den nicht benötigten Zahlen zu entlasten, erfolgt gleich noch ein unset() auf den unerwünschten bzw. unnötigen Part. Das macht aber alles nicht diesen Fehler - der Fehler entsteht ausnahmslos im Array-Build, welcher als Source so ausschaut:

$array = array();
for($i = 1; $i <= $N; $i++){
    $array[$i] = 1;
}

Im Falle von $N = 100.000.000.000 - wie erwähnt - motzt er ... vorab hatte ich es als bool'schen Wert, hatte es dann auf 0/1 dezimiert, um dann festzustellen, dass der bool'sche Wert auch nur eine Zahl ist (kurioser Weise 1x für "false" (0) und alles andere der N (mit und ohne Vorzeichen) als "true"). Ich wäre übrigens für Einführung der trinären Zahlensysteme - nachrücken darf die "2", wodurch der Computer die Freigabe erhält, selbst an der Stelle zu entscheiden. Das wäre doch mal stark ... !! ^^ Aber ich schweife ab ...

Gefühlt würde ich sogar meinen, dass es der inkrementelle Zähler ist, der über den INT-max nicht hinaus kommen kann (ähnlich in der DB, wenn die Column als unsigned signiert ist, man aber dort ein -1 als rechnerisches Update anbringen will).

Kurzum: Mehr als der Vierzeiler da oben macht das Problem nicht.

Lachen musste ich bei "ISBN würde ich als String speichern" ... (nicht wegen dem Inhalt, sondern weil ich es nur als weiteres Muster anführte)

Jetzt wünsche ich euch eine gute Nacht ... mein Tag ist schon wieder viel zu lang. *ätz*

 

[Melewo]

Wir hatten mal einen Test gemacht, ging aber mehr um den Unterschied zwischen "Allowed memory size of..." und "Out of memory...", jedenfalls streikte PHP bei mir ab rund 1,7 GB:

WP 3.9 Fatal error: Out Of Memory - Seite 2

Mein Rechner hat ein 64-bit System, doch PHP und der Apache laufen dennoch in einer 32-bit Version. Der Speicher ist kleiner als Deiner, dennoch würde ich diesen Wert jetzt als normal ansehen, dient ja dem Schutz, damit der Rechner nicht abstürzt oder andere Programme. Nur eine Anwendung allein kann nicht den ganzen Speicher verbraten wollen, denke ich mir. Und wie der Ingo schrieb, soll ja der Server bei einem Hoster bei seinem Test in die Knie gegangen sein.

 

[tsseh]

der Fehler entsteht ausnahmslos im Array-Build, welcher als Source so ausschaut:

das wird so nicht funktionieren,
maximal könntest du bei einem 32 bit programm 2 gb speicher selbst nutzen, also 2147483648 byte. wenn php 32 bit integer nutzt also 536870912 integer. da php selbst aber auch noch speicher benötigt, du ja sicher auch noch, wird das nochmal weniger.
der ansatz funktioniert so nicht.

 

[SteelWheel]

Danke, das leuchtet mir auch alles ein - keine Frage.

Dann zurück zum Grundsätzlichen: Wie würde ich es lösen, da ja - anscheinend - eine andere Programmiersprache dieses Problem nur weiter transportieren, aber ebenfalls nicht lösen würde/könnte.

Hintergrund ist eine grundsätzliche Theorie von mir zu Möglichkeiten, Sinn und Unsinn auf solchen Systemen und wo eben die Limits liegen - und dann: wie man diese "umschreiben" könnte, um diese dann doch wieder verwendbar zu machen.

Ich sage auf jeden Fall vielen, vielen Dank für all diese Antworten.

 

[Melewo]

Oder nehmen wir nackte ISBN-Nummern: 781.449.393.908 (bspw. - und ohne Punkte; das ist O'Reilly bzgl. Canvas in HTML5)

Verstehe nicht alles, was Du so meinst, doch es wird viel in C geschrieben und wenn es dann ohne Punkte sein darf, so kennt C etwas mehr. Falls Du einen Compiler zur Hand hast, so teste mal Dein Sytem aus.

#include <stdio.h>
#include <limits.h>

int main() {

	printf("char  : %d Byte  | %d\n",   sizeof(char),      SCHAR_MIN);
	printf("char  : %d Byte  | %d\n",   sizeof(char),      SCHAR_MAX);
	printf("short : %d Byte  | %d\n",   sizeof(short),     SHRT_MIN );
	printf("short : %d Byte  | %d\n",   sizeof(short),     SHRT_MAX );
	printf("int   : %d Byte  | %d\n",   sizeof(int),       INT_MIN  );
	printf("int   : %d Byte  | %d\n",   sizeof(int),       INT_MAX  );
	printf("long  : %d Byte  | %ld\n",  sizeof(long),      LONG_MIN );
	printf("long  : %d Byte  | %ld\n",  sizeof(long),      LONG_MAX );
	printf("llong : %d Byte  | %lld\n", sizeof(long long), LLONG_MIN);
	printf("llong : %d Byte  | %lld\n", sizeof(long long), LLONG_MAX);

	getchar();
	return 0;
}

Ergibt bei mir:

char        -128 bis +127
short       -32768 bis +32767
int         -2147483648 bis +2147483647
long        -2147483648 bis +2147483647
long long   -9223372036854775808 bis +9223372036854775807

Lässt sich noch verdoppeln, in dem der Wertebereich von - auf 0 verschoben wird auf

unsigned long long  0 bis 18446744073709551615

Nachtrag:

Möglichkeiten, Sinn und Unsinn auf solchen Systemen und wo eben die Limits liegen

C kennt diese Limits und bietet Möglichkeiten zum Überschreiten von Limits, nur ich kenne C noch nicht soweit, um Dir das richtig erklären zu können. Jedenfalls kannst Du da wohl, falls der Wertebereich immer noch nicht genügt, Variablen kontrolliert überlaufen lassen. Wie sich das genau verhält, weiß ich nicht.
Und Du kannst, falls der Arbeitsspeicher nicht ausreicht, weiteren Speicher vom System anfordern, den Du als Programmierer dann selbst verwalten und wieder freigeben musst oder so. Habe ich auch noch nicht gemacht und möchte nichts Verkehrtes schreiben, weiß nur, dass man in C zwischen vom System verwalteten Speicher und vom Programmierer verwalteten Speicher unterscheidet.

 

[SteelWheel]

Melewo, auch Dir vielen Dank - ich habe zwar keinen Compiler jetzt zur Hand, kenne das Modell mit "unsigned" etc. aber natürlich aus dem Bereich der Datenbanken.

Dass mit ISBN sollte nur ein Beispiel für eine "lange Nummer" sein, die nur als String gehandhabt werden könnte - als reiner Integerwert führt das auch zum gleichen Verhalten.

Hmmmm ... okay, Speicherüberlauf, Selbstverwaltung ... es klingt gerade nach einem eigenen System, welches ausnahmslos ein in C (o. ä.: ++ oder # dürfte wohl auch gehen) geschriebenes Programm enthält, um diese Berechnung vorzunehmen. Das Ergebnis müsste dann als String weggeschrieben werden, um später verwendet werden zu können - sonst beginnt es ja wieder von vorn. Das mit der Datenbank war jedenfalls im Kopf angedacht - bereits als Zwischenträger.

Aber die Grenze ist erreicht - meine letzte C-Verwendung ist schon seeeehr lange her und wie erwähnt: es war nur eine fixe Idee. Aber es ist schön zu sehen, dass es mit ein wenig Umstand gehen würde.

An dieser Stelle nochmals allen Wort- und Ideengebern meinen aufrichtigen Dank.

 

[kkapsner]

Also das Speicherproblem kannst du umgehen, indem du deinen Algorithmus in Teilprobleme unterteilst, bei denen der Testarray in deinen Speicher passt:

ini_set("memory_limit", "2G");
set_time_limit(-1);

$n = 100000000;
$chunkSize = 20000000;

$primes = array();
$primesCount = 0;
$arr = array();

for (
	$chunkStart = 2, $chunkEnd = min($n, $chunkStart + $chunkSize - 1);
	$chunkStart <= $chunkEnd;
	$chunkStart += $chunkSize, $chunkEnd = min($n, $chunkEnd + $chunkSize)
){
	for ($i = $chunkStart; $i <= $chunkEnd; $i += 1){
		$arr[$i] = true;
	}
	for ($i = 0; $i < $primesCount; $i += 1){
		$prime = $primes[$i];
		$lowerBorder = ceil($chunkStart / $prime);
		$upperBorder = floor($chunkEnd / $prime);
		for ($j = $lowerBorder; $j <= $upperBorder; $j += 1){
			$arr[$prime * $j] = false;
		} 
	}
	
	for ($i = $chunkStart; $i <= $chunkEnd; $i += 1){
		if ($arr[$i]){
			$lowerBorder = max(2, ceil($chunkStart / $i));
			$upperBorder = floor($chunkEnd / $i);
			for ($j = $lowerBorder; $j <= $upperBorder; $j += 1){
				$arr[$j * $i] = false;
			}
			$primes[] = $i;
			$primesCount += 1;
		}
	}
	$arr = array();
}

- wobei hier PHP_INT_MAX natürlich trotzdem die Grenze ist, da darüber die Berechnungen nicht mehr exakt sind und die Arrayzugriffe nicht mehr gescheit funktionieren.


@Melewo: Wenn du C auf 64-bit compilierst, kann es natürlich auch 64-bit Zahlen speichern... aber so wie's aussieht, läuft PHP hier nur mit 32-bit.

PS: Hab' ein paar Tests mit dem Code oben laufen lassen:

  1.000.000 in ~1s
 10.000.000 in ~12s
 20.000.000 in ~25s
 30.000.000 in ~38s
 40.000.000 in ~52s
100.000.000 in ~200s

Das skaliert etwas höher as liniear und damit würde die Maximalgrenze von PHP_MAX_INT (~2.000.000.000) so um die 5000s (~1.5h) dauern...

PPS: Man könnte den Code oben auch noch so umbauen, dass er mit den Modulen für beliebig große Zahlen arbeitet...