Changeset 22053 in project


Ignore:
Timestamp:
12/17/10 14:08:47 (9 years ago)
Author:
Alan Post
Message:

genturfa'i: replace assoc list in memoization routine with hash.

This is a dramatic speedup to the parser. I found this problem
looking at performance issues after writing some parsers for
jbogenturfa'i.

Location:
release/4/genturfahi/trunk
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • release/4/genturfahi/trunk/chicken-ext.scm

    r21953 r22053  
    9393   nunjavni-jonai
    9494
     95   genturfahi-semorji
    9596   genturfahi-tolmohi
    9697   nunjavni-morji
  • release/4/genturfahi/trunk/genturfahi.scm

    r21888 r22053  
    5151                     (make-lerfu-porsi-port lefpoi)
    5252                     (make-lerfu-porsi-string lefpoi))))
     53      (genturfahi-semorji (string-length (lerfu-porsi-poi porsi)))
    5354      (javni porsi mapti namapti))))
    5455
  • release/4/genturfahi/trunk/nunjavni.scm

    r22051 r22053  
    348348;;        na selci javni.
    349349;;
    350 (define-values (genturfahi-tolmohi nunjavni-morji)
    351   (let ((clear-mapti-caches '())
    352         (clear-namapti-caches '())
    353         (clear-recurse-caches '()))
     350(define-values (genturfahi-semorji genturfahi-tolmohi nunjavni-morji)
     351  (let ((rodasemorji '())
     352        (rodatolmohi '()))
    354353    (values
     354      (lambda (nilcla)
     355        (map (lambda (semorji) (semorji nilcla)) rodasemorji))
     356
    355357      (lambda ()
    356         (for-each (lambda (x) (x)) clear-mapti-caches)
    357         (for-each (lambda (x) (x)) clear-namapti-caches)
    358         (for-each (lambda (x) (x)) clear-recurse-caches)
    359         '())
     358        (map (lambda (tolmohi) (tolmohi)) rodatolmohi))
    360359
    361360      (lambda (javni)
    362         (let ((mapti-cache '())
    363               (namapti-cache '())
    364               (recurse-cache '()))
    365           (define (javni-morji cache-porsi mapti namapti)
    366             (define (set-mapti-cache! cache-porsi porsi nunvalsi)
    367               (set! mapti-cache
    368                 (cons (cons cache-porsi (list porsi nunvalsi))
    369                       mapti-cache)))
    370 
    371             (define (set-namapti-cache! cache-porsi porsi)
    372               (set! namapti-cache
    373                 (cons (cons cache-porsi (list porsi))
    374                       namapti-cache)))
    375 
    376             (define (set-recurse-cache!)
    377               (set! recurse-cache
    378                 (cons (cons cache-porsi (list cache-porsi))
    379                       namapti-cache)))
    380 
    381             ;; call the cached |mapti|
    382             (define (mapti-morji assv-valsi)
    383               (apply mapti (cdr assv-valsi)))
    384 
    385             ;; call the cached |namapti|
    386             (define (namapti-morji assv-valsi)
    387               (apply namapti (cdr assv-valsi)))
    388 
    389             ;; left recursion support.
    390             (define (recurse-morji assv-valsi)
    391               (apply namapti (cdr assv-valsi)))
     361        (let ((morji '()))
     362          (define (semorji nilcla)
     363            (let ((klani (quotient nilcla 2)))
     364              (set! morji (make-hash-table = size: (if (= 0 klani) 1 klani)))))
     365
     366          (define (tolmohi)
     367            (set! morji '()))
     368
     369          (define (javni-morji morji-porsi mapti namapti)
     370            ;; mapti
     371            (define (set-mapti-morji! porsi nunvalsi)
     372              (define (mapti-morji mapti ignore-namapti)
     373                (mapti porsi nunvalsi))
     374
     375              (hash-table-set! morji
     376                               (lerfu-porsi-zva morji-porsi)
     377                               mapti-morji))
     378
     379            ;; namapti
     380            (define (set-namapti-morji! porsi)
     381              (define (namapti-morji ignore-mapti namapti)
     382                (namapti porsi))
     383
     384              (hash-table-set! morji
     385                               (lerfu-porsi-zva morji-porsi)
     386                               namapti-morji))
     387
     388            ;; recurse
     389            (define (set-recurse-morji!)
     390              (define (recurse-morji ignore-mapti namapti)
     391                (namapti morji-porsi))
     392
     393              (hash-table-set! morji
     394                               (lerfu-porsi-zva morji-porsi)
     395                               recurse-morji))
    392396
    393397            (define (javni-nomorji)
    394398              (define (mapti-morji porsi nunvalsi)
    395                 (set-mapti-cache! cache-porsi
    396                                   porsi
    397                                   nunvalsi)
     399                (set-mapti-morji! porsi nunvalsi)
    398400                (mapti porsi nunvalsi))
    399401
    400402              (define (namapti-morji porsi)
    401                 (set-namapti-cache! cache-porsi porsi)
     403                (set-namapti-morji! porsi)
    402404                (namapti porsi))
    403405
    404406              ; register this parse position to detect left
    405407              ; recursion.
    406               (set-recurse-cache!)
    407 
    408               (javni cache-porsi mapti-morji namapti-morji))
    409 
    410                    ; search the match results
    411             (cond ((assv cache-porsi mapti-cache) => mapti-morji)
    412                    ; search the non-match results
    413                   ((assv cache-porsi namapti-cache) => namapti-morji)
    414                    ; search for left recursion
    415                   ((assv cache-porsi recurse-cache) => recurse-morji)
    416                    ; run the rule.
    417                   (else (javni-nomorji))))
    418 
    419           ; register this cache so we can clear if we want to use this
    420           ; parser on a new |lerfu-porsi|.
     408              (set-recurse-morji!)
     409
     410              (javni morji-porsi mapti-morji namapti-morji))
     411
     412            (let ((nunjalge
     413                    (hash-table-ref/default morji
     414                                            (lerfu-porsi-zva morji-porsi)
     415                                            #f)))
     416              (if nunjalge (nunjalge mapti namapti) (javni-nomorji))))
     417
     418          ; register this cache so we can initialize and clear.
     419          ; This routine customizes itself based on the input size,
     420          ; and we can free up a substantial amount of memory if
     421          ; we clear the caches after we're done parsing.
    421422          ;
    422           (set! clear-mapti-caches
    423             (cons (lambda () (set! mapti-cache '()))
    424                   clear-mapti-caches))
    425           (set! clear-namapti-caches
    426             (cons (lambda () (set! namapti-cache '()))
    427                   clear-namapti-caches))
    428           (set! clear-recurse-caches
    429             (cons (lambda () (set! recurse-cache '()))
    430                   clear-recurse-caches))
     423          (set! rodasemorji (cons semorji rodasemorji))
     424          (set! rodatolmohi (cons tolmohi rodatolmohi))
    431425
    432426          javni-morji)))))
Note: See TracChangeset for help on using the changeset viewer.