memory leak? antiprimes

[TedWalther]

I wrote some code to generate the list of antiprimes.  Had fun with it.  Sped it up by quite a large factor by using memoization.  But it blew up my memory usage beyond what I was expecting.  So I dropped back to an algorithm that I expected to not take up much memory at all, less than a megabyte.  But 2 hours in, it is taking up 20% of my system ram.  I have 8 gigs of ram.



Here is the code.

Code Select Expand


#!/usr/bin/newlisp

# Anti-primes are highly composite numbers
# Print each number that is more composite than all the numbers before it.

(define start-time (date-value))
(define maxiter 5000000)
(define lastn 1)

(define (prime? n) (= 1 (length (factor n))))

(define (combinations n k (r '()))
  (if (= (length r) k)
    (list r)
    (let (rlst '())
      (dolist (x n)
        (setq rlst (append rlst
                     (combinations ((+ 1 $idx) n) k (append r (list x))))))
      rlst)))

(define (all-factors lst)
  (let (r '())
    (for (j 1 (length lst))
      (extend r (combinations lst j)))))

(define antiprime
  (lambda ()
    (for (i 2 maxiter)
      (let (f (length (unique (sort (all-factors (factor i))))))
        (when (> f lastn)
          (println i ": " f (if (prime? f) " (prime)" ""))
          (setq lastn f))))))

(antiprime)

(println "Runtime: " (- (date-value) start-time) " seconds")

(exit)


So, is the memory leak in my code, or in newLisp?  Am I not understanding the automatic memory management correctly?

  PID USER      PR  NI    VIRT    RES    SHR S  %CPU %MEM     TIME+ COMMAND                        

23903 ted       20   0 1542988 1.456g   2624 R 100.0 18.9 130:51.61 antiprime.lsp                                                                  

[ssqq]

4: 2

ERR: invalid function in function if : (prime? f)

called from user function (antiprime)



"extend" would treat first argument as place and Increase by degress,you'd better use cons or other ...

[TedWalther]

Sorry, that function was in my init.lsp file.  I have a lot of little utility functions there.

Code Select Expand


(define (prime? n) (= 1 (length (factor n))))


I've added it into the original post now.  Should work.

[TedWalther]

"extend" would treat first argument as place and Increase by degress,you'd better use cons or other ...

Do you mind showing an example of what you mean?   I thought (extend foo bar) was supposed to be more (or as) efficient as (setq foo (append foo bar))  Newlisp doesn't have cons cells.  Also, if you look at the usage of extend, each function call should take very little memory, and the memory (I think) should be freed after the call.

[TedWalther]

I changed the "combinations" function to use the (extend foo bar) idiom instead of (setq foo (append foo bar))  The code is actually running faster, and using less memory too.  Instead of 18% of memory, it is using 3%.  This is still a lot more than I expect, so I am curious what is going on, if it is a leak.  Here is the updated source, guaranteed to work without my init.lsp file.

Code Select Expand


#!/usr/bin/newlisp -n

# Anti-primes are highly composite numbers
# Print each number that is more composite than all the numbers before it.

(define start-time (date-value))
(define maxiter 5000000)
(define lastn 1)

(define (prime? n) (= 1 (length (factor n))))

(define (combinations n k (r '()))
  (if (= (length r) k)
    (list r)
    (let (rlst '())
      (dolist (x n)
        (extend rlst (combinations ((+ 1 $idx) n) k (append r (list x)))))
      rlst)))

(define (all-factors lst)
  (let (r '())
    (for (j 1 (length lst))
      (extend r (unique (sort (combinations lst j)))))))

(define antiprime
  (lambda ()
    (for (i 2 maxiter)
      (let (f (length (all-factors (factor i))))
        (when (> f lastn)
          (println i ": " f (if (prime? f) " (prime)" ""))
          (setq lastn f))))))

(antiprime)

(println "Runtime: " (- (date-value) start-time) " seconds")

(exit)


How much faster?  The version with extend ran in an hour and a half, instead of 4 and a half hours.  That is 1/3 the time.  Wow.

[Lutz]

What you see, is memory not reclaimed by the the OS yet, but already given back to the OS by your newLISP process and accumulating over time.



Take out the 'exit' statement at the end of the program, so it will stay in newLISP, but not run. When monitoring (1) the process, you will see that the OS will slowly take back the memory, after newLISP comes to a halt. On my machine resting at about 5Mbyte coming down from about 550Mbyte. If you run your program on a machine with less memory, the maximum you see in the monitor would be less too, because the OS takes a different strategy reclaiming memory faster, but your program will also run slower.



(1) I am running the OS X monitor application and an 8Gig RAM Mac. I guess the Unix 'top' monitor app would work too.

[TedWalther]

Thank you Lutz.  Mystery solved.  Also, you may want to update the Coding Patterns document to use the version of "combinations" function in my last post; it is quite a lot more efficient.  Saves one line of code too.  (extend) is a real bonus function.

[rickyboy]

Hi Ted!



Actually, there is a way to make your program even faster -- a lot faster.  The idea is that there is a way to determine the number of divisors of a (natural) number which is a lot cheaper than computing the unique sub-groupings of its prime factors.  Here is a routine that does just that.

Code Select Expand

(define (number-of-divisors N)
  (if (< N 1) 0
      (= 1 N) 1
      (let (prime-factorization (factor N))
        (apply *
               (map (curry + 1)
                    (count (unique prime-factorization)
                           prime-factorization))))))
Now, call it from `antiprime` like this:

Code Select Expand

(define antiprime
  (lambda ()
    (for (i 2 maxiter)
      (let (f (number-of-divisors i))
        (when (> f lastn)
          (println i ": " f (if (prime? f) " (prime)" ""))
          (setq lastn f))))))
It flies now! :)

[TedWalther]

Hi Ted!



Actually, there is a way to make your program even faster -- a lot faster.  The idea is that there is a way to determine the number of divisors of a (natural) number which is a lot cheaper than computing the unique sub-groupings of its prime factors.  Here is a routine that does just that.



...

Wow.  Your Number Theory-fu is excellent!  http://www.cut-the-knot.org/blue/NumberOfFactors.shtml">http://www.cut-the-knot.org/blue/NumberOfFactors.shtml



Also, your algorithm does the standard count of the number of factors.  My count doesn't allow 1 as a factor, which offsets them by one.  And you know what I found?  60% of the antiprimes, have a prime number of factors.  If we don't allow 1 as a factor.  Shift by 1, and suddenly only the first 2 antiprimes have a prime number of factors.

Now, call it from `antiprime` like this:

...

It flies now! :)

That is an understatement... 4 and 1/2 hours of computing cut down to 41 seconds.  Nice!



Why curry rather than (fn (x) (+ 1 x)) in the map?  Performance, or just the code looks nicer?



The combinations function is useful for other things; can you advise?  I tried to shorten it a little, but it gives an error.  I've tried tracing the code and it is really puzzling me.



I'm replacing this code:

Code Select Expand


(let (rlst '())
  (dolist
    (extend rlst ...))
  rlst)


With this:

Code Select Expand


(let (rlst '())
  (dolist
    (extend rlst ...)))


Should work... but it errors with the error

ERR: list expected : (combinations ((+ 1 $idx) n) k (append r (list x)) true (+ 1 lvl))

called from user function combinations

called from user function all-factors

called from user function antiprime

Here is the instrumented code:

Code Select Expand


#!/usr/bin/newlisp -n

# Anti-primes are highly composite numbers
# Print each number that is more composite than all the numbers before it.

(define start-time (date-value))
(define maxiter 4)
(define lastn 1)

(define (prime? n) (= 1 (length (factor n))))

(define (combinations n k (r '()) (mysilent nil) (lvl 0))
  (unless mysilent (println "combinations " n " " k " " r ":" (if (list? r) "list" "not-a-list") " level " lvl))
  (if (= (length r) k)
    (list r)
    (let (rlst '())
      (dolist (x n)
        (unless mysilent (println "extend yields list? " (list? (extend (copy rlst) (combinations ((+ 1 $idx) n) k (append r (list x)) true (+ 1 lvl))))))
        (extend rlst (combinations ((+ 1 $idx) n) k (append r (list x)) nil (+ 1 lvl))))
      )))
;      rlst)))

(define (all-factors lst)
  (let (r '())
    (for (j 1 (length lst))
      (extend r (unique (sort (combinations lst j)))))))

(define antiprime
  (lambda ()
    (for (i 4 maxiter)
      (let (f (length (all-factors (factor i))))
        (when (> f lastn)
          (println i ": " f (if (prime? f) " (prime)" ""))
          (setq lastn f))))))

(antiprime)
(exit)


[TedWalther]

Also thanks for reminding me of the "count" function.  I tried to reimplement it in an ugly way using map.  Glad it is builtin.  I thought "there should be something to do this built in to the language."  I should have spent 20 minutes going down the list of functions.  The newLisp API is indeed rich and featureful.

[ssqq]

Code Select Expand


> (define (ex @x) (extend "a" @x))
(lambda (@x) (extend "a" @x))
> (map ex (explode "abc"))
("aa" "aab" "aabc")


[TedWalther]

ssqq, yes, thank you.  I did similar little tests to see that extend should work the way I am using it.  But in the code I posted, it doesn't.  Any ideas?  Are the debug messages sending me barking up the wrong tree?

[ssqq]

I could not run this code:

combinations (2 2) 1 ():list level 0

extend yields list? true

combinations (2) 1 (2):list level 1

extend yields list? true

combinations () 1 (2):list level 1

combinations (2 2) 2 ():list level 0

extend yields list? combinations () 2 (2 2):list level 2

true

combinations (2) 2 (2):list level 1

extend yields list? true

combinations () 2 (2 2):list level 2

extend yields list?

ERR: list expected : (combinations ((+ 1 $idx) n) k (append r (list x)) true (+ 1 lvl))

called from user function (combinations lst j)

called from user function (all-factors (factor i))

called from user function (antiprime)

[rrq]

I'd say the problem comes from that dolist results in nil if the repetition list is empty. E.g.

Code Select Expand

> (dolist (x '()) 1)
nil
Therefore you might need to wrap it into an or-clause, as in

Code Select Expand

(or (dolist ....) '()) so as to ensure that the nil case translates into an empty list case, with all else the same. Hopefully the performance penalty of that isn't too heavy.

[TedWalther]

Thank you Ralph, that explains it.



Update:



Although, that is a "surprise".  I expect dolist to return a list, then suddenly it doesn't... I'd expect nil in case of an error, but the empty list makes more sense as a return value.