fibonacci(4784969)

[AIR]

Taking Heater's placing the fib calculations into a function, I modified the bottom of his code like this:

Code: ScriptBasic

1.  
2. count = 0
3. while count < 10
4.     fibo(4784969)
5.     count = count + 1
6.     print count,"\n"
7. wend
8.  

Here's what valgrind shows:

Code: Text

1.  
2. $ valgrind --leak-check=full --show-leak-kinds=all scriba heater.sb                            
3. ==511== Memcheck, a memory error detector                                                      
4. ==511== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.                        
5. ==511== Using Valgrind-3.12.0.SVN and LibVEX; rerun with -h for copyright info                
6. ==511== Command: scriba heater.sb                                                              
7. ==511==                                                                                        
8. 1                                                                                              
9. 2                                                                                              
10. 3                                                                                              
11. 4                                                                                              
12. 5                                                                                              
13. 6                                                                                              
14. 7                                                                                              
15. 8                                                                                              
16. 9                                                                                              
17. 10                                                                                            
18. ==511==                                                                                        
19. ==511== HEAP SUMMARY:                                                                          
20. ==511==     in use at exit: 32 bytes in 1 blocks                                              
21. ==511==   total heap usage: 190,305 allocs, 190,304 frees, 4,482,318,682 bytes allocated      
22. ==511==                                                                                        
23. ==511== 32 bytes in 1 blocks are still reachable in loss record 1 of 1                        
24. ==511==    at 0x4C2DBC5: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)      
25. ==511==    by 0x54DC60E: _dlerror_run (dlerror.c:141)                                          
26. ==511==    by 0x54DBF81: dlopen@@GLIBC_2.2.5 (dlopen.c:87)                                    
27. ==511==    by 0x11EFEC: dynlolib_LoadLibrary (in /home/riveraa/sb/bin/scriba)                  
28. ==511==    by 0x180A7F: modu_LoadModule (in /home/riveraa/sb/bin/scriba)                      
29. ==511==    by 0x180C95: modu_GetFunctionByName (in /home/riveraa/sb/bin/scriba)                
30. ==511==    by 0x12C0AA: COMMAND_EXTERNAL (in /home/riveraa/sb/bin/scriba)                      
31. ==511==    by 0x168DAC: execute_Execute_r (in /home/riveraa/sb/bin/scriba)                    
32. ==511==    by 0x169BE5: execute_Evaluate (in /home/riveraa/sb/bin/scriba)                      
33. ==511==    by 0x1431F7: COMMAND_LET (in /home/riveraa/sb/bin/scriba)                          
34. ==511==    by 0x168DAC: execute_Execute_r (in /home/riveraa/sb/bin/scriba)                    
35. ==511==    by 0x169BE5: execute_Evaluate (in /home/riveraa/sb/bin/scriba)                      
36. ==511==                                                                                        
37. ==511== LEAK SUMMARY:                                                                          
38. ==511==    definitely lost: 0 bytes in 0 blocks                                                
39. ==511==    indirectly lost: 0 bytes in 0 blocks                                                
40. ==511==      possibly lost: 0 bytes in 0 blocks                                                
41. ==511==    still reachable: 32 bytes in 1 blocks                                              
42. ==511==         suppressed: 0 bytes in 0 blocks                                                
43. ==511==                                                                                        
44. ==511== For counts of detected and suppressed errors, rerun with: -v                          
45. ==511== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
46.  

Having an infinite loop doesn't allow SB to free up resources.  It also doesn't allow valgrind to report (I think I can have it write out to a file, but haven't tried that yet.)

This is a preliminary check, which is why I posted here instead of on the RasPi forum.


AIR.

[John]

What resouces aren't being released until scriba exits?

I don't see this million digit fibo as real world and only a challenge to break as many languages as they can. I do care about memory leaks but not SB memory manager caching.

I'm counting on you to make the call if there is a problem with the BASIC.

With the tests I have done only Heater's recursive fibo becomes a memory hog.

[John]

So where is the jury at with GMP2 leaking or not? I see no abnormal memory use when calling the GMP fibo function in a continuous loop.

I ran across this post that suggest that you create a buffer for the results rather than letting GMP do it. Interestingly the way you wrote the original fibo() function uses the buffer method and doesn't leak.

My old GMP module did the buffer method and didn't seem to help with the mystery memory problem.

https://gmplib.org/list-archives/gmp-discuss/2003-November/000891.html

[jack]

I am a bit late, just out of curiosity, I converted AIR's code https://www.allbasic.info/forum/index.php?topic=588.msg6963#msg6963
to FreeBASIC using mpfr, I did not expect the execution time to be good, but surprisingly it took only .61 seconds including printing

my conversion uses include files that overload the math operators and functions, they are quite large, so I won't post them here

Code: [Select]

#Include Once "gmp.bi"
#Include Once "mpfr.bi"

'we need to set mpfr_digits before including the overloded operators
Dim Shared As Long mpfr_digits_precision = 1000001 '<- set mpfr digits-precision
Dim Shared As mpfr_rnd_t mpfr_rounding_mode = MPFR_RNDN '<- set the rounding mode
' rounding options are
'  MPFR_RNDN    round to nearest, with ties to even
'  MPFR_RNDZ    round toward zero
'  MPFR_RNDU    round toward +Inf
'  MPFR_RNDD    round toward -Inf
'  MPFR_RNDA    round away from zero
'  MPFR_RNDF    faithful rounding (not implemented yet)
'  MPFR_RNDNA    round to nearest, with ties away from zero (mpfr_round)

#Include Once "mpfr-fb.bi" 'mpfr overloaded operators
''=============================================================================

sub fib2(byval n as long, byref b as mpfr)
dim as long count=n
dim as mpfr a = 1
dim as mpfr p = 0
dim as mpfr q = 1
dim psq as mpfr
dim qsq as mpfr
dim twopq as mpfr
dim bq as mpfr
dim aq as mpfr
dim ap as mpfr
dim bp as mpfr

b = 0
while count > 0
if (count mod 2) = 0 then
psq = p * p
qsq = q * q
twopq = p * q
twopq = twopq * 2
p = psq + qsq
q = twopq + qsq
count \= 2
else
bq = b * q
aq = a * q
ap = a * p
bp = b * p
a = bq + aq
a = a + ap
b = bp + aq
count-=1
end if
wend
end sub

dim as double t=timer
dim as mpfr b

fib2(4784969, b)
print b
print "elapsed time ";timer-t;" seconds"


[John]

Are you noticing any leaks with mpfr?  We are still searching for the cause of SB's abnormal memory use using GMP.

[jack]

hello John
I must admit that I am only an amateur programmer,  I have no idea how to detect a leak, it seems especially complicated due to the multitasking OS.
but I am willing to learn, if AIR reads this, perhaps he may be willing to instruct me on how to detect leaks on macOS high Sierra.
there's the leaks command, but how do you check for memory leaks on a process that takes less than a second from start to finish?
here's a screenshot of my attempt

[jack]

John, to the best of my ability, I don't see any memory leaks

[John]

How others have been testing for leaks is run your fibo in a WHILE loop and watch for abnormal memory consumption.

[jack]

I ran fibo in a loop, and as I understand, there are no leaks.
the reason for sum is so that the compiler won't optimize the loop out

Code: [Select]

dim as double t=timer
dim as mpfr b, sum
for i as integer=1 to 500
fib2(4784969, b)
sum+=b
next
print sum
print "elapsed time ";timer-t;" seconds"


[John]

It might be worthwhile to see if your BIGINT library would work better than GMP.

[jack]

Hi John
as I understand it, your GMP wrapper used SB strings, it seems to me, that perhaps the memory leak may be due, to perhaps inaccurate reporting of the strings memory usage.
in FB I not only overload the operators but setup constructors and destructors to allocate and deallocate the memory used by the mpfr type.
for example, DIM as mpfr x(100) would initialize all the elements of x from 0 to 100 to the set precision and after scope, clear all the elements.

[John]

AIR wrote the GMP2 module and I don't know where he stands with the abnormal memory usage and GMP.  From my testing it doesn't look like a bug in SB.

[AIR]

IF you properly exit an sb app, the memory is released.

With most apps, if you send a sigkill to it while monitoring for leaks, you will see that some of the memory allocated is not properly released.

So, the 'problem' is that sb never gets the chance to release allocated memory because of an artificial non-real world test.

I've tested this with a loop of 100 iterations while monitoring with valgrind.  I didn't see the memory usage jump up to the extent that others have.  And memory was released at the end.

That's as far as I'm going with this.  If y'all feel that the module is problematic, then either provide a fix or don't use it.

[John]

That's good enough for me.

[AIR]

John,
According to the docs, if you undef an array the memory allocated to it is freed.
Does the same apply to strings?
If so, maybe undef'ing the SB variables after printing the value of 'b' would address the leak that's occurring when you run the fibo example in an endless loop.