[gambit-list] Re: Re: Regarding garbage collection

peter lo peter19852001 at yahoo.com.hk
Wed Sep 9 22:42:30 EDT 2009

As the code is very long and spans a number of files, maybe I only post a fragment of it.
I will explain just a bit what I am doing. Basically given a number of input DNA sequences, I would like to find "similar" (in terms of edit distance) subsequences and rank them using a scoring scheme. The length of subsequences range from 5 to 20. Previously, for each subsequence length, I go through all the subsequences, find their similar occurrences, and rank them. But this is too slow, so I use a heuristic, which is to record the similar occurrences of each subsequence of length L, then using them to refine the search for subsequences of length L+1. This is the part that is causing trouble. As the total length of input sequences increase and L increase, the number of unique subsequences increase very rapidly, and since each of them keeps a list of occurrences, the amount of live objects when going from length L to length L+1 can get very large.

As I have mentioned earlier, previously I use a structure to keep the occurrences, so too much memory is used, now I use a cons cell for the occurrences when going from L to L+1, the amount of memory used is reduced by a significant fraction, but the basic problem is in the heuristic itself.

I have thought of doing things in a different order, which is to push the loop of L from 5 to 20 inner than before, then I need not keep that many occurrences, but then there may be duplicated work.

By the way, I am currently trying to reduce the allocation of short-lived objects, I am sure there are general tips on the web about this, but I am not sure if there are tips more specific to Gambit Scheme, taking into account its garbage collector.


;;; Here is the code
;;; Note that for a pattern of length L to match with score >= threshold, its subpatterns
;;; must also match with score >= threshold, therefore, when going from length L to L+1,
;;; for a given pattern, we use the occurrences of its L subpattern to reduce some search.
;;; For simplicity, we check at the occurrences of one of its L subpattern

;;; Since there are too many occurrences, the occurrence structure takes too much space,
;;; now try to use a single cons cell, to record the minimum information
(define (make-trimed-occ seq-no pos)
  (cons seq-no pos))
(define (trimed-occ-seq-no oc)
  (car oc))
(define (trimed-occ-pos oc)
  (cdr oc))
(define (occurrence-vlist->trimed-occ oc)
  (make-trimed-occ (occurrence-vlist-seq-no oc)
   (occurrence-vlist-start oc)))

(define (find-motif-by-pattern pat fasta errL bg)
  ;; pat and fasta are the codified sequence(s) of pattern and fasta respectively.
  ;; Use the occurrences to estimate an hmm and give score to it, return the result as a motif.
  (let* ((th (inflated-threshold-by-L errL (coded-seq-length pat)))
 (occ (map occurrence->occurrence-vlist
   (find-in-fasta pat fasta *score-function* th)))
 (g (estimate-hmm-from-occurrence-vlist occ))
 (score (score-for-motif pat g occ bg)))
    ;(print "Motif: pat: " pat "\tscore: " score "\tocc-len: " (length occ) "\n")
    (make-motif g score pat occ)))

(define (find-motif-in-fasta-L fasta L keeper errL bg)
  ;; fasta is a codified fasta file, and L is the length of the motif
  ;; wanted. Goes through the length L subsequences in fasta, and for
  ;; each one, find a motif for the pattern, and call keeper to add
  ;; it to the result list. errL is the error level allowed in finding
  ;; similar subsequences to estimate hmm.
  ;; Returns the patterns hash table which contains the patterns and its
  ;; associated occurrences.

  ;; memoize for the sub-pattern, so that we don't call find-motif-by-pattern
  ;; for the same pattern
  (let ((patterns (make-table)))
    (for s fasta
 (for-n i 0 (- (coded-seq-length (cdr s)) L)
(let ((pat (subcoded-seq (cdr s) i (+ i L))))
  (when (not (table-ref patterns pat #f))
;; not already in patterns, add entry
(let ((m (find-motif-by-pattern pat fasta errL bg)))
  (keeper 'in m)
  (table-set! patterns
      (map occurrence-vlist->trimed-occ (motif-occs m))))))))

(define (find-motif-in-occ-list in-fasta pat errL bg lst)
  ;; pat is a codified pattern, lst is an occurrence list in which we try to
  ;; find pat. Returns a motif.
  (define (subpattern seq oc L th)
    ;; oc is an trimed-occ, returns the subpattern with a bit longer length
    (let* ((i (trimed-occ-pos oc))
   (e (+ i L)))
      (subcoded-seq seq i (min (coded-seq-length seq) (- e th))))) ; th is negative

  (let* ((L (coded-seq-length pat))
 (inflated-th (inflated-threshold-by-L errL L))
 (th (threshold-by-L errL L))
 (occ '()))
    (for s lst
 (let* ((s-seq (cdr (list-ref in-fasta (trimed-occ-seq-no s))))
(ls (find-seq pat (subpattern s-seq s L th) *score-function* inflated-th))
(oc (if (null? ls) #f (car ls))))
   ;; now rectify the information in ls, if any.
   ;; we take at most only one occurrence from each s
   (when oc
 (set! occ (cons (make-occurrence-vlist
  (trimed-occ-seq-no s)
  (occurrence-score oc)
  (+ (trimed-occ-pos s) (occurrence-start oc))
  (+ (trimed-occ-pos s) (occurrence-end oc))
  (alignment->vertex-name (occurrence-alignment oc)))
    (let* ((g (estimate-hmm-from-occurrence-vlist occ))
   (score (score-for-motif pat g occ bg)))
      ;(print "Motif: pat: " pat "\tscore: " score "\tocc-len: " (length occ) "\n")
      (make-motif g score pat occ))))

(define (find-motif-in-fasta-pruned fasta L keeper errL bg sub-pats)
  ;; fasta is a codifed fasta file, L is the length of motif we are looking for.
  ;; sub-pats is a hash table associating subpatterns of length L-1 and their
  ;; occurrence list. For each pattern of length L in fasta, we only check the
  ;; positions of the occurrences of its L-1 left-most subpattern
  ;; Returns a new hash table associating length L patterns and its occurrence
  ;; list. Also memoize.
  (let ((patterns (make-table)))
    (for s fasta
 (for-n i 0 (- (coded-seq-length (cdr s)) L)
(let ((pat (subcoded-seq (cdr s) i (+ i L))))
  (when (not (table-ref patterns pat #f))
;; not already in patterns, add entry
(let ((sub-lst (table-ref sub-pats (subcoded-seq pat 0 (- L 1)) #f)))
  (when sub-lst
(let ((m (find-motif-in-occ-list fasta pat errL bg sub-lst)))
  (keeper 'in m)
  (table-set! patterns
      (map occurrence-vlist->trimed-occ (motif-occs m))))))))))

(define (find-motif-in-fasta fasta min-L max-L keeper errL reverse-complement?)
  ;; try the lengths, from short to long, and keep the good motifs by using keeper.
  ;; If reverse-complement? is true, then consider also the reverse-complement of 
  ;; the input sequences, but the reported positions are always relative to the
  ;; original sequences.

  ;; Allocating two large enough buffers once, one for bufs, one for bufp in find-seq
  (let* ((in-fasta (if reverse-complement?
       (append-reverse-complement-fasta fasta DNA-code-complement)
 (bg (m1-model->inexact (estimate-m1-model in-fasta 4)))
 (pats (find-motif-in-fasta-L in-fasta min-L keeper errL bg))
 (seq-Lens (map (@ coded-seq-length cdr) in-fasta))
 (max-Lens (reduce max 0 seq-Lens)))
    ; setup things properly
    (set! *g-prior* (/ 1.0 (mean seq-Lens)))
    (find-seq-bufs-set! (make-2d-s8array (+ max-L 1) (+ max-Lens 1) 0))
    (find-seq-bufp-set! (make-2d-s8array (+ max-L 1) (+ max-Lens 1) 0))
    (for-n i (+ min-L 1) max-L
   (set! pats (find-motif-in-fasta-pruned in-fasta i keeper errL bg pats)))
    (print-current-best-alignment keeper in-fasta errL reverse-complement? fasta)
    (keeper 'for-each print-motif)
    ; release the buffers
    (find-seq-bufs-set! #f)
    (find-seq-bufp-set! #f)))

;;;; End of code

----- 郵件原件 ----
寄件人﹕ Pavel Dudrenov <dudrenov at gmail.com>
收件人 Marc Feeley <feeley at iro.umontreal.ca>
副本(CC) peter lo <peter19852001 at yahoo.com..hk>; gambit-list at iro.umontreal.ca
傳送日期﹕ 2009 年 9月 9 日 星期三 下午 11:37:11
主題: Re: [gambit-list] Re: Regarding garbage collection

It be interesting to see your program, or at least the part cranks up
the mem usage so much. Maybe some of the people on the list would be
able to give you a hint on how better to represent/manipulate yourd

This thread has been going on for some time now and I feel that all
the general, or theoretical if you will, answers have been given.
It'll probably be time to show some relevant code if you continue
having trouble in the future.


On Wed, Sep 9, 2009 at 6:32 AM, Marc Feeley<feeley at iro.umontreal.ca> wrote:
> On 9-Sep-09, at 8:51 AM, peter lo wrote:
>> Dear all,
>>    Thanks for the replies and clarifications. After some
>> investigations, I believe that the cause of heap overflow is not
>> memory leakage. The whole program is in Scheme, so it cannot be
>> leakage due to external C libraries. And I have checked the program,
>> it seems that there are no "really useless" data hanging around that
>> cannot be garbage collected. The real reason is simply that the
>> input data size is too large, so there are too many intermediate
>> results, therefore needing > 1.6 GB of live memory.
>>    It was my fault, as I do not expect the program to need that much
>> memory, so the representation of the intermediate result is not
>> particularly compact. Previously I used a structure with 6 members,
>> but in fact I really need 2 of them to do the computations. After I
>> have changed the representation to use a simple cons cell instead,
>> the program seem to manage to continue to run using only a peak
>> amount of 1700MB ram.
>>    Another thing that I have noticed is that the system holds at
>> most ~1700MB ram for heap, even though 100% of them are live
>> objects, is this by design or just an accident in Windows XP? When
>> the precentage of live objects gets closer to 100%, the GC's become
>> more frequent as each time there is little memory reclaimed, and
>> each one takes around 2 seconds, because a lot of memory objects are
>> examined to determine the reachability, therefore the system is
>> doing less useful work.  Now I am trying to reduce the allocation of
>> short-lived data, so that there will be less GC's. I am also
>> considering switching to a linux system.
> By default Gambit's memory management system resizes the heap so that
> after a GC there is 50% of the heap that is occupied by live objects
> (this can be changed with the -:lXXX runtime option).  If the resizing
> requires that the heap grow, then the runtime will allocate new
> "movable sections" (which are 512 Kbytes each) by calling the C
> "malloc" function.  If malloc returns NULL, indicating that no more
> memory is available to the process, then the system will keep on
> running, but with more that 50% of the heap occupied by live objects.
> If you are at 100% live occupation the GCs will be very frequent and
> very little useful computation will occur compared to the garbage
> collections.  Consider yourself lucky that the program managed to
> finish executing!
> Solutions?  Use a more compact data representation (you have started
> doing that).  Use "still" objects (i.e. ##still-copy) that are more
> compactly represented when objects have 5 fields or more.  Enable
> virtual memory (but then your system will slow down due to swapping).
> Buy more RAM.  Switch from a 64 bit system to a 32 bit system (if you
> are using a 64 bit system).
> Marc
> _______________________________________________
> Gambit-list mailing list
> Gambit-list at iro.umontreal.ca
> https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list

      Yahoo!香港提供網上安全攻略,教你如何防範黑客! 請前往 http://hk.promo.yahoo.com/security/ 了解更多!

More information about the Gambit-list mailing list