How much memory may a HPPL program use on a G2?

[Stefan Falk]

Hello everybody,

I have a HPPL program running on my HP Prime G2 with nearly no RAM used. However, when it runs, it ends with "out of memory", and then gets displayed in the program list as using just about 2 MB. The G2 should have 256 MB RAM, and even if the OS gets copied into it, I would expect more RAM usable. Mem shows still well over 100 MB free. What is happening here?

Best Regards,
Stefan

[matalog]

Your program may handling menory badly or filling the stack, which would be cleared up by the time you got to look at the memory. You could share the code and someone might have a look, but if it is 2MB they may not.

Try disabling parts of the code that you suspect might be filling up the stack.

[Stefan Falk]

Hello matalog,

Thanks for your prompt answer! The stack is "clean", only a handful of objects, and always eaten by operators. The one thing that will eat up memory is a list (of length 1 to several hundred) of arrays of (1 to, say, 15, numbers). If I calculate 11 bytes for a real number, times 15 per array, times 1000, I calculate < 200 KB. I have one GROB object (quadratic, not higher than 64 pixel), and draw onto PICT. I don't even know where those 2 MB get occupied, not to speak of over 100 MB which should be available. Perhaps lots of RAM get consumed by internal temporal computation results, I don't know better.

The main question is: May a program use up (nearly) all available RAM, or is there some magic limit per program?

Best Regards,
Stefan

[Joe Horn]

(08-23-2023 06:45 PM)matalog Wrote:  Your program may handling menory badly or filling the stack, which would be cleared up by the time you got to look at the memory. You could share the code and someone might have a look, but if it is 2MB they may not.

Try disabling parts of the code that you suspect might be filling up the stack.

If you are referring to the data stack, that CAN be the problem, but it's usually not, because the Prime's "history stack" is limited to 128 items (a little-known fact), unlike RPL's "infinite stack". Of course, if the objects on Prime's data stack are gargantuan (e.g. huge matrices or lists or algebraic expressions), yes, that can use up all your free memory.

However, if you are referring to the program environment's return stack, then yes, it's easy to unintentionally create a bottomless subroutine hole, or a recursive routine that gobbles up memory. A listing of the program is needed to find memory leaks like these.

[Stefan Falk]

Hello everybody,

Sorry for the delay, but here is my N-Queens program:

Code:

LOCAL
 POSI,SOLCNT,UNICNT,
 COLS,DU,DD,ALLSOLS,UNISOLS;
LOCAL LASTP;

EXPORT QUEENS(DIMENSION)
BEGIN
 LOCAL N,START;
 START:=TICKS;
 N:=DIMENSION;
 //PRINT(N+" Queens");
 SOLCNT:=0;
 UNICNT:=0;
 POSI:=MAKELIST(0,X,1,N,1);
 COLS:=MAKELIST(0,X,1,N,1);
 DU:=MAKELIST(0,X,1,2*N-1,1);
 DD:=MAKELIST(0,X,1,2*N-1,1);
 ALLSOLS:={};
 UNISOLS:={};
 TRY(N,1);
 SOLCNT:=SOLCNT*2;
 //PRINT(SOLCNT+" solutions, "+UNICNT+" unique");
 //PRINT((TICKS-START)/1000+" seconds")
 TEXTOUT_P("FIN",0,40);
 WAIT(0)
END;

LOCAL TRY(N,ROW)
BEGIN
 LOCAL M,COL,DUI,DDI,DUP,DUP2,I;
 IF ROW>2 THEN
  M:=N
 ELSE
  IF ROW=1 THEN
   M:=IP((N+1)/2)
  ELSE
   IF N MOD 2=1 AND POSI(1)=(N+1)/2 THEN
    M:=IP(N/2)
   ELSE
    M:=N
   END
  END
 END;
 FOR COL FROM 1 TO M DO
  DUI:=ROW-COL+N;
  DDI:=ROW+COL-1;
  IF COLS(COL)=0 AND DU(DUI)=0 AND DD(DDI)=0 THEN
   POSI(ROW):=COL;
   IF ROW=N THEN
    SOLCNT:=SOLCNT+1;
    IF POS(ALLSOLS,POSI)=0 THEN
     ALLSOLS:=CONCAT(ALLSOLS,{POSI});
     DUP:=POSI;
     DUP2:=MIRR(N,DUP);
     ALLSOLS:=CONCAT(ALLSOLS,{DUP2});
     FOR I FROM 1 TO 3 DO
      DUP:=TURN(N,DUP);
      ALLSOLS:=CONCAT(ALLSOLS,{DUP});
      DUP2:=MIRR(N,DUP);
      ALLSOLS:=CONCAT(ALLSOLS,{DUP2}); 
     END;
     UNISOLS:=CONCAT(UNISOLS,{POSI});
     UNICNT:=UNICNT+1;
     SHOW(N,POSI)
    END
   ELSE
    COLS(COL):=1; DU(DUI):=1; DD(DDI):=1;
    TRY(N,ROW+1);
    COLS(COL):=0; DU(DUI):=0; DD(DDI):=0
   END
  END
 END
END;

LOCAL MIRR(N,P)
BEGIN
 LOCAL R,M;
 M:=P;
 FOR R FROM 1 TO N DO
  M(R):=N+1-P(R)
 END;
 RETURN M; 
END;

LOCAL TURN(N,P)
BEGIN
 LOCAL R,T;
 T:=P;
 FOR R FROM 1 TO N DO
  T(P(R)):=N+1-R
 END;
 RETURN T;
END;

LOCAL SHOW(N,P)
BEGIN
 LOCAL D,I,T,E,OX,OY,M;
 LOCAL GRAY,WHITE,BLACK,CLR;
 D:=IP(237/N);
 OY:=IP((239-N*D)/2);
 OX:=319-N*D-OY;
 GRAY:=RGB(224,224,224);
 WHITE:=RGB(255,255,255);
 BLACK:=RGB(0,0,0);
 M:=IP(D/6);
 IF UNICNT=1 THEN
  RECT();
  E:=N*D;
  FOR I FROM 0 TO N DO
   T:=I*D; 
   LINE_P(OX,T+OY,E+OX,T+OY);
   LINE_P(T+OX,OY,T+OX,E+OY)
  END;
  FOR I FROM 1 TO N DO
   FOR E FROM 1 TO N DO
    IF (E+I) MOD 2 = 0 THEN
     RECT_P((E-1)*D+1+OX,(N-I)*D+1+OY,E*D-1+OX,(N-I+1)*D-1+OY,GRAY)
    END;
    IF P(I)=E THEN
     RECT_P((E-1)*D+M+OX,(N-I)*D+M+OY,E*D-M+OX,(N-I+1)*D-M+OY,WHITE,BLACK)
    END
   END
  END
 ELSE
  FOR I FROM 1 TO N DO
   IF P(I)≠LASTP(I) THEN
    RECT_P((LASTP(I)-1)*D+M+OX,(N-I)*D+M+OY,LASTP(I)*D-M+OX,(N-I+1)*D-M+OY,IFTE((LASTP(I)+I) MOD 2=0,GRAY,WHITE));
    RECT_P((P(I)-1)*D+M+OX,(N-I)*D+M+OY,P(I)*D-M+OX,(N-I+1)*D-M+OY,WHITE,BLACK)
   END 
  END
 END;
 LASTP:=P;
 TEXTOUT_P(UNICNT,0,0,3,BLACK,100,WHITE);
 TEXTOUT_P(SOLCNT,0,20,3,BLACK,100,WHITE)
END;

Or should I post that elsewhere?

The program runs, on my HP Prime G2 with current firmware, fine for up to 11x11 queens, but fails with out of memory for 12x12 and above. For 12x12, there are a few hundred different solutions, and for each 8 variants are stored (original, turned 3 times, and each mirrored). That should be much less than 1000 elements, each a 12-element array of real numbers. I guess that should easily fit in main memory.

Best Regards,
Stefan

[komame]

(09-03-2023 06:47 PM)Stefan Falk Wrote:  The program runs, on my HP Prime G2 with current firmware, fine for up to 11x11 queens, but fails with out of memory for 12x12 and above. For 12x12, there are a few hundred different solutions, and for each 8 variants are stored (original, turned 3 times, and each mirrored). That should be much less than 1000 elements, each a 12-element array of real numbers. I guess that should easily fit in main memory.

You simply exceeded the maximum number of entries for the list. In PPL, a list can contain only 10000 elements.

Add the following line to the end of the program:

Code:

TEXTOUT_P(STRING(SIZE(ALLSOLS)),0,60,3,BLACK,150,WHITE);

It displays the current size of the ALLSOLS list. You can see that for dimensions 9x9, the list contains 368 elements, for 10x10 => 736, for 11x11 => 2728, and for 12x12, it exceeds 10000, which results in an error report.

It's a pity that there's such a limit; unfortunately, it kills some algorithms or makes their implementation very challenging. The HP Prime has a lot of RAM, but these limitations make it very difficult to utilize it fully with a program. At the moment of reporting the error, the ALLSOLS list is only 1.91 MB in size, which is very little considering the available free RAM. These restrictions are entirely senseless.

[Stefan Falk]

Hello komame!

Thank you for your superb answer! That makes things clear. So let's hope there will be an update some day ;-)

Best Regards,
Stefan

[StephenG1CMZ]

I suggested that there were benefits in doubling the list size almost 4 years ago (to avoid a mismatch between the size limits of lists and vectors), were that to happen it would be a pleasant surprise.
Apparently an update is planned for "summer" 2023
https://www.hpmuseum.org/forum/thread-19...ight=Klaas
So perhaps soon we will discover what the next update will bring.

[matalog]

With the knowledge of the problem, then you should be able to access a new list everytime a counter of 10000 (or slightly less) has been reached, and your program will work as planned even with the current limitation.

[Stefan Falk]

Sure, there will be ways to overcome the limitation. One just needs to know the problem ;-) Thanks for all input.

[komame]

(09-04-2023 06:02 PM)Stefan Falk Wrote:  Sure, there will be ways to overcome the limitation. One just needs to know the problem ;-) Thanks for all input.

You can use a text string to emulate a list. The HP Prime allows you to create very long text strings. I managed to create a text string with a length of over 500000 characters.
You can use characters from A to Z as equivalents for values from 1 to 27, or even directly manipulate the string chars using the ASC and CHAR commands. For entries longer than one character, each entry should start with an unusual character, like "|" (pipe), so you can search for entries using the INSTRING command (equivalent to the POS function for lists). If such a solution is correctly used for lists, it can be quite efficient.

[Tyann]

Bonjour

Il y a une autre solution qui consiste à utiliser des sous listes,
en effet une liste est limitée à 10 000 éléments mais chaque élément peut être lui même une liste pouvant contenir 10 000 éléments.
J'ai déjà utilisé ce principe pour mes besoins.


Hello

Another solution is to use sub-lists,
A list is limited to 10,000 elements but each element can itself be a list containing 10,000 elements.
I've already used this principle for my needs.

[Stefan Falk]

Hello Tyann,

That is the plan I have, to use lists of lists. :-)

Best Regards and thanks for the input,
Stefan

[komame]

(09-08-2023 08:06 AM)Stefan Falk Wrote:  That is the plan I have, to use lists of lists. :-)

Yes, you can do it that way if you don't care about performance.
But implementing a list based on the string type is much simpler. You just need to change a few lines of code in your program to make it work (you don't even need to create additional functions). Additionally, for cases exceeding the dimensions of 9x9 and larger, it's even faster than the built-in PPL list even for less than 10000 items (which surprised me as well) - tested on G2.
So if you use a list of lists (meaning you iterate through multiple nested lists to simulate the POS or CONCAT instruction), the performance can decrease even several times compared to a string-based list.

[Tyann]

Bonjour

C'est quelque chose que je vais tester, car effectivement je crois avoir remarqué
que les grandes listes posent des problèmes de rapidité, notamment lorsqu'elles sont retournées comme résultat.

Comme je l'ai déjà signalé dans un autre poste, il serai bien que INSTRING évolue pour avoir un troisième paramètre définissant la position de départ de la recherche, cela pourrait être utile pour POS aussi.
Espérant être entendu.


Hello

This is something I'm going to try out, because I think I've noticed that
that large lists cause speed problems, especially when they are returned as results.

As I already mentioned in another post, it would be nice if INSTRING evolved to have a third parameter defining the starting position of the search, this could be useful for POS too.
Hoping to be heard.

[komame]

(09-09-2023 05:52 AM)Tyann Wrote:  As I already mentioned in another post, it would be nice if INSTRING evolved to have a third parameter defining the starting position of the search, this could be useful for POS too.
Hoping to be heard.

Completely agree! Additionally, a fourth parameter would be helpful, where you can specify which occurrence of the desired phrase should be found. This would allow simulating indexing of list entries and quickly referencing them, even when individual entries have different lengths.

[komame]

By the way, I managed to create a string with a length of 16,777,216 characters. It occupies 32MB of memory. Such a result can only be achieved on the G2 or in the emulator. For the G1, I was able to achieve a maximum of 8MB (4,194,304 characters).
As you can see, the potential of strings is incredible.
   

[Tyann]

Par contre avec les chaînes, je vois un problème.
Par exemple:
soit une liste {1285,128} si je recherche 128 POS, me renverra bien 2 .
si j'utilise une chaîne avec "," comme séparateur par exemple .
cela donne "1285,128" ici INSTRING me renverra 1 au lieu 6.
il faudra donc ensuite faire un test d'égalité, puis relancer la recherche si <>.

However, I do see a problem with chains.
For example:
either a list {1285,128} if I search for 128 POS, will return 2 .
if I use a string with "," as a separator, for example .
this gives "1285,128" here INSTRING will return 1 instead of 6.
you then have to do an equality test, then run the search again if <>.

[komame]

(09-09-2023 10:21 AM)Tyann Wrote:  However, I do see a problem with chains.
For example:
either a list {1285,128} if I search for 128 POS, will return 2 .
if I use a string with "," as a separator, for example .
this gives "1285,128" here INSTRING will return 1 instead of 6.
you then have to do an equality test, then run the search again if <>.

You have to use a little trick. Here's an example:

Code:

EXPORT LIST_EMU()
BEGIN
 local l1,s1;
 PRINT();
 l1:={1285,128,999,50000};
 s1:=CHAR(l1);
 PRINT(INSTRING(s1,CHAR(999)));
END;

Of course, there are other solutions for emulating a list based on strings, but the solution I've shown is the most efficient. There's just one limitation with this approach: the list can store only values from 1 to 65535. It cannot store the value 0. In the QUEENS algorithm, this is not a problem, and according to my tests, this approach was an excellent solution.
For very small lists, such emulation might be slower than a PPL list. However, the larger the list, the more the string-based emulation will outperform the PPL list. With lists on the order of tens of thousands of entries or more, the difference in performance can even be tenfold.

Within the next few days, I will prepare a description of various approaches to emulate a list using the string and publish it in a separate thread. Without the appropriate tools, we might not be able to efficiently replace 100% of the PPL list functionality, but in most cases, this could prove to be sufficient and, in fact, highly efficient, especially when the number of elements exceeds 10,000.

Best regards,

[Stefan Falk]

Hello everybody,

What a nice discussion!

In this specific program, I only need to know if or of not a given solution was already found (just rotated or mirrored), but the number of that existing solution is only interesting for displaying it. Also, all of my substrings would be of the same size, so I could easily compute the solution number from the INSTR position.

I guess string search is so much faster because INSTR - I assume - is implemented with a sophisticated algorithm like Bayer-Moore or so.

Something like a hash table does not exist in the Prime, does it?

Best Regards,
Stefan