From 9e83b4ef7ad4ed1a4336a1e9258ea23be7b17f3e Mon Sep 17 00:00:00 2001 From: Chris Hanson Date: Thu, 24 Apr 1997 06:35:29 +0000 Subject: [PATCH] Complete reimplementation of the number parser. New parser is 3.5 times as fast as the old one (see data below), and includes the contribution due to the improved EXACT->INEXACT. New switch FLONUM-PARSER-FAST? allows the number parser to sacrifice accuracy for performance, and gains another factor of 2.4 in performance on flonums. ---------------------------------------------------------------------- Tests performed with a list of 100000 randomly-generated strings. The strings were generated by "test-numpar.scm", which implements the R4RS number BNF, so the strings are arbitrary numeric syntax. This is a test of general number-reading performance. Results for old exact->inexact and old string->number: process time: 9690 (9060 RUN + 630 GC); real time: 9690 process time: 9460 (8830 RUN + 630 GC); real time: 9458 process time: 9450 (8820 RUN + 630 GC); real time: 9451 process time: 9460 (8830 RUN + 630 GC); real time: 9456 average real time: 9514 msec Results for new exact->inexact and new string->number: process time: 2800 (2800 RUN + 0 GC); real time: 2800 process time: 2790 (2790 RUN + 0 GC); real time: 2786 process time: 2700 (2700 RUN + 0 GC); real time: 2703 process time: 2680 (2680 RUN + 0 GC); real time: 2686 average real time: 2744 msec Average improvement is a factor of 3.5 in speed. --- v7/src/runtime/numpar.scm | 560 +++++++++++++++++++------------------ v7/src/runtime/runtime.pkg | 3 +- v8/src/runtime/runtime.pkg | 3 +- 3 files changed, 296 insertions(+), 270 deletions(-) diff --git a/v7/src/runtime/numpar.scm b/v7/src/runtime/numpar.scm index 31d6ddbc8..c2204de2b 100644 --- a/v7/src/runtime/numpar.scm +++ b/v7/src/runtime/numpar.scm @@ -1,8 +1,8 @@ #| -*-Scheme-*- -$Id: numpar.scm,v 14.9 1995/06/27 22:15:06 adams Exp $ +$Id: numpar.scm,v 14.10 1997/04/24 06:35:04 cph Exp $ -Copyright (c) 1989-95 Massachusetts Institute of Technology +Copyright (c) 1989-97 Massachusetts Institute of Technology This material was developed by the Scheme project at the Massachusetts Institute of Technology, Department of Electrical Engineering and @@ -37,272 +37,296 @@ MIT in each case. |# (declare (usual-integrations)) -(define (string->number string #!optional radix-default) - (parse-chars (string->list string) - (if (default-object? radix-default) 10 radix-default) - 'STRING->NUMBER)) - -(define (substring->number string start end #!optional radix-default) - (parse-chars (substring->list string start end) - (if (default-object? radix-default) 10 radix-default) - 'SUBSTRING->NUMBER)) - -(define (parse-chars chars radix-default name) - (if (not (memv radix-default '(2 8 10 16))) - (error:bad-range-argument radix-default name)) - (with-values (lambda () (parse-prefix chars)) - (lambda (chars radix-prefix exactness) - ((if (eq? exactness 'INEXACT) - (lambda (number) - (and number - (exact->inexact number))) - identity-procedure) - (let ((radix (or radix-prefix radix-default))) - (with-values (lambda () (parse-sign chars)) - (lambda (chars real-sign) - (if (and real-sign (imaginary-suffix? chars)) - (make-rectangular 0 real-sign) - (with-values (lambda () (parse-unsigned-real chars radix)) - (lambda (chars real inexact?) - (let ((real - (combine-sign real-sign - real - exactness - inexact?))) - (cond ((or (null? chars) (not real)) - real) - ((and real-sign (imaginary-suffix? chars)) - (make-rectangular 0 real)) - ((char=? #\@ (car chars)) - (with-values - (lambda () - (parse-signed-real (cdr chars) - radix - exactness)) - (lambda (chars angle) - (and angle - (null? chars) - (make-polar real angle))))) - (else - (parse-imaginary-tail chars - radix - exactness - real)))))))))))))) - -(define (parse-imaginary-tail chars radix exactness real) - (with-values (lambda () (parse-sign chars)) - (lambda (chars sign) - (and sign - (if (imaginary-suffix? chars) - (make-rectangular real sign) - (with-values (lambda () (parse-unsigned-real chars radix)) - (lambda (chars imag inexact?) - (and imag - (imaginary-suffix? chars) - (make-rectangular - real - (combine-sign sign imag exactness inexact?)))))))))) - -(define (parse-prefix chars) - (parse-1-prefix chars - (lambda (chars radix) - (parse-1-prefix chars - (lambda (chars radix) - chars radix - (values '() false false)) - (lambda (chars exactness) - (values chars radix exactness)) - (lambda (chars) - (values chars radix false)))) - (lambda (chars exactness) - (parse-1-prefix chars - (lambda (chars radix) - (values chars radix exactness)) - (lambda (chars exactness) - chars exactness - (values '() false false)) - (lambda (chars) - (values chars false exactness)))) - (lambda (chars) - (values chars false false)))) - -(define (parse-1-prefix chars if-radix if-exactness if-neither) - (if (and (not (null? chars)) - (char=? (car chars) #\#) - (not (null? (cdr chars)))) - (let ((char (cadr chars)) - (chars* (cddr chars))) - (cond ((char-ci=? #\i char) (if-exactness chars* 'INEXACT)) - ((char-ci=? #\e char) (if-exactness chars* 'EXACT)) - ((char-ci=? #\b char) (if-radix chars* 2)) - ((char-ci=? #\o char) (if-radix chars* 8)) - ((char-ci=? #\d char) (if-radix chars* 10)) - ((char-ci=? #\x char) (if-radix chars* 16)) - (else (if-neither chars)))) - (if-neither chars))) - -(define (imaginary-suffix? chars) - (and (not (null? chars)) - (null? (cdr chars)) - (or (char-ci=? (car chars) #\i) - (char-ci=? (car chars) #\j)))) - -(define (parse-signed-real chars radix exactness) - (with-values (lambda () (parse-sign chars)) - (lambda (chars sign) - (with-values (lambda () (parse-unsigned-real chars radix)) - (lambda (chars real inexact?) - (values chars (combine-sign sign real exactness inexact?))))))) - -(define (parse-unsigned-real chars radix) - (with-values (lambda () (parse-integer chars radix)) - (lambda (chars* numerator inexact?) - (cond ((not numerator) - (if (= radix 10) - (parse-decimal chars) - (values chars false false))) - ((and (not (null? chars*)) - (char=? #\/ (car chars*))) - (with-values (lambda () (parse-integer (cdr chars*) radix)) - (lambda (chars* denominator inexact?*) - (if denominator - (values chars* - (/ numerator denominator) - (or inexact? inexact?*)) - (values chars false false))))) - (else - (values chars* numerator inexact?)))))) - -(define (parse-integer chars radix) - (if (or (null? chars) - (not (char->digit (car chars) radix))) - (values chars false false) - (let loop ((chars* (cdr chars)) (n (char->digit (car chars) radix))) - (if (null? chars*) - (values chars* n false) - (let ((digit (char->digit (car chars*) radix))) - (cond (digit - (loop (cdr chars*) (+ (* n radix) digit))) - ((dot-or-exponent? (car chars*)) - (values chars false false)) - ((char=? (car chars*) #\#) - (let loop ((chars* (cdr chars*)) (n (* n radix))) - (cond ((null? chars*) - (values chars* n true)) - ((char=? (car chars*) #\#) - (loop (cdr chars*) (* n radix))) - ((dot-or-exponent? (car chars*)) - (values chars false false)) - (else - (values chars* n true))))) - (else - (values chars* n false)))))))) - -(define (dot-or-exponent? char) - (or (char=? #\. char) - (char-ci=? #\e char) - (char-ci=? #\s char) - (char-ci=? #\f char) - (char-ci=? #\d char) - (char-ci=? #\l char))) +(define (string->number string #!optional radix) + (parse-number string 0 (string-length string) + (if (default-object? radix) #f radix) + 'STRING->NUMBER)) + +(define (substring->number string start end #!optional radix) + (parse-number string start end + (if (default-object? radix) #f radix) + 'SUBSTRING->NUMBER)) + +(define (parse-number string start end radix name) + (if (not (or (eq? #f radix) + (eq? 2 radix) (eq? 8 radix) (eq? 10 radix) (eq? 16 radix))) + (error:bad-range-argument radix name)) + (parse-top-level string start end #f radix)) + +(define (parse-top-level string start end exactness radix) + (and (fix:< start end) + (let ((char (string-ref string start)) + (start (fix:+ start 1))) + (cond ((sign? char) + (find-leader string start end + exactness (or radix 10) + char)) + ((char=? #\. char) + (and (or (not radix) (fix:= 10 radix)) + (parse-decimal-1 string start end + (or exactness 'IMPLICIT-INEXACT) #f))) + ((char=? #\# char) + (and (fix:< start end) + (let ((char (string-ref string start)) + (start (fix:+ start 1))) + (let ((do-radix + (lambda (r) + (and (not radix) + (parse-top-level string start end + exactness r)))) + (do-exactness + (lambda (e) + (and (not exactness) + (parse-top-level string start end + e radix))))) + (cond ((or (char=? #\b char) (char=? #\B char)) + (do-radix 2)) + ((or (char=? #\o char) (char=? #\O char)) + (do-radix 8)) + ((or (char=? #\d char) (char=? #\D char)) + (do-radix 10)) + ((or (char=? #\x char) (char=? #\X char)) + (do-radix 16)) + ((or (char=? #\e char) (char=? #\E char)) + (do-exactness 'EXACT)) + ((or (char=? #\i char) (char=? #\I char)) + (do-exactness 'INEXACT)) + (else #f)))))) + ((char->digit char (or radix 10)) + => (lambda (digit) + (parse-integer string start end digit + exactness (or radix 10) #f))) + (else #f))))) + +(define (find-leader string start end exactness radix sign) + ;; State: leading sign has been seen. + (and (fix:< start end) + (let ((char (string-ref string start)) + (start (fix:+ start 1))) + (cond ((char->digit char radix) + => (lambda (digit) + (parse-integer string start end digit + exactness radix sign))) + ((char=? #\. char) + (and (fix:= 10 radix) + (parse-decimal-1 string start end + (or exactness 'IMPLICIT-INEXACT) sign))) + ((i? char) + (and (fix:= start end) + (make-rectangular 0 (if (char=? #\+ sign) 1 -1)))) + (else #f))))) -(define (parse-decimal chars) - (cond ((null? chars) - (values chars false false)) - ((char=? #\. (car chars)) - (let ((chars* (cdr chars))) - (if (and (not (null? chars*)) - (char->digit (car chars*) 10)) - (with-values (lambda () (parse-decimal-fraction chars*)) - (lambda (chars x) - (parse-decimal-suffix chars x true))) - (values chars false false)))) - (else - (let ((digit (char->digit (car chars) 10))) - (if digit - (parse-decimal-integer (cdr chars) digit) - (values chars false false)))))) - -(define (parse-decimal-integer chars n) - (if (null? chars) - (parse-decimal-suffix '() n false) - (let ((digit (char->digit (car chars) 10))) - (if digit - (parse-decimal-integer (cdr chars) (+ (* n 10) digit)) - (cond ((char=? #\. (car chars)) - (with-values - (lambda () (parse-decimal-fraction (cdr chars))) - (lambda (chars fraction) - (parse-decimal-suffix chars (+ n fraction) true)))) - ((char=? #\# (car chars)) - (let loop ((chars (cdr chars)) (n (* n 10))) - (cond ((null? chars) - (parse-decimal-suffix '() n true)) - ((char=? #\# (car chars)) - (loop (cdr chars) (* n 10))) - ((char=? #\. (car chars)) - (let loop ((chars (cdr chars))) - (if (and (not (null? chars)) - (char=? #\# (car chars))) - (loop (cdr chars)) - (parse-decimal-suffix chars n true)))) - (else - (parse-decimal-suffix chars n true))))) +(define (parse-integer string start end integer exactness radix sign) + ;; State: at least one digit has been seen. + (parse-digits string start end integer exactness radix + (lambda (start integer exactness sharp?) + (if (fix:< start end) + (let ((char (string-ref string start)) + (start+1 (fix:+ start 1))) + (cond ((char=? #\/ char) + (parse-denominator-1 string start+1 end + integer exactness radix sign)) + ((char=? #\. char) + (and (fix:= radix 10) + (if sharp? + (parse-decimal-3 string start+1 end + integer 0 exactness sign) + (parse-decimal-2 string start+1 end + integer 0 + (or exactness 'IMPLICIT-INEXACT) + sign)))) + ((exponent-marker? char) + (and (fix:= radix 10) + (parse-exponent-1 string start+1 end + integer 0 + (or exactness 'IMPLICIT-INEXACT) + sign))) (else - (parse-decimal-suffix chars n false))))))) - -(define (parse-decimal-fraction chars) - (let loop ((chars chars) (f 0) (exponent 0)) - (let ((done - (lambda (chars) - (values chars (* f (expt 10 exponent)))))) - (if (null? chars) - (done '()) - (let ((digit (char->digit (car chars) 10))) - (if digit - (loop (cdr chars) (+ (* f 10) digit) (-1+ exponent)) - (let loop ((chars chars)) - (cond ((not (char=? #\# (car chars))) (done chars)) - ((null? (cdr chars)) (done '())) - (else (loop (cdr chars))))))))))) - -(define (parse-decimal-suffix chars x inexact?) + (parse-complex string start end + (finish-integer integer exactness sign) + exactness radix sign)))) + (finish-integer integer exactness sign))))) + +(define (parse-digits string start end integer exactness radix k) + (let loop ((start start) (integer integer)) + (if (fix:< start end) + (let ((char (string-ref string start))) + (cond ((char->digit char radix) + => (lambda (digit) + (loop (fix:+ start 1) + (+ (* integer radix) digit)))) + ((char=? #\# char) + (do ((start (fix:+ start 1) (fix:+ start 1)) + (integer (* integer radix) (* integer radix))) + ((not (and (fix:< start end) + (char=? #\# (string-ref string start)))) + (k start integer (or exactness 'IMPLICIT-INEXACT) #t)))) + (else + (k start integer exactness #f)))) + (k start integer exactness #f)))) + +(define (parse-denominator-1 string start end numerator exactness radix sign) + ;; State: numerator parsed, / seen. (let ((finish - (lambda (chars exponent) - (if exponent - (values chars (* x (expt 10 exponent)) true) - (values chars x inexact?))))) - (if (and (not (null? chars)) - (or (char-ci=? #\e (car chars)) - (char-ci=? #\s (car chars)) - (char-ci=? #\f (car chars)) - (char-ci=? #\d (car chars)) - (char-ci=? #\l (car chars)))) - (with-values (lambda () (parse-sign (cdr chars))) - (lambda (chars* sign) - (let ((digit - (and (not (null? chars*)) - (char->digit (car chars*) 10)))) - (if digit - (let loop ((chars* (cdr chars*)) (n digit)) - (let ((digit - (and (not (null? chars*)) - (char->digit (car chars*) 10)))) - (if digit - (loop (cdr chars*) (+ (* n 10) digit)) - (finish chars* (if (eqv? -1 sign) (- n) n))))) - (finish chars false))))) - (finish chars false)))) - -(define (parse-sign chars) - (cond ((null? chars) (values chars false)) - ((char=? (car chars) #\+) (values (cdr chars) 1)) - ((char=? (car chars) #\-) (values (cdr chars) -1)) - (else (values chars false)))) - -(define (combine-sign sign real exactness inexact?) - (let ((real (if (and real (eqv? -1 sign)) (- real) real))) - (if (and inexact? - (not (eq? exactness 'EXACT))) - (exact->inexact real) - real))) \ No newline at end of file + (lambda (denominator exactness sign) + (finish-rational numerator denominator exactness sign)))) + (parse-digits string start end 0 exactness radix + (lambda (start integer exactness sharp?) + sharp? + (parse-complex string start end + (finish integer exactness sign) + exactness radix sign))))) + +(define (parse-decimal-1 string start end exactness sign) + ;; State: radix is 10, leading dot seen. + (and (fix:< start end) + (let ((digit (char->digit (string-ref string start) 10)) + (start (fix:+ start 1))) + (and digit + (parse-decimal-2 string start end digit -1 exactness sign))))) + +(define (parse-decimal-2 string start end integer exponent exactness sign) + ;; State: radix is 10, dot seen. + (let loop ((start start) (integer integer) (exponent exponent)) + (if (fix:< start end) + (let ((char (string-ref string start)) + (start+1 (fix:+ start 1))) + (cond ((char->digit char 10) + => (lambda (digit) + (loop start+1 + (+ (* integer 10) digit) + (- exponent 1)))) + ((char=? #\# char) + (parse-decimal-3 string start+1 end + integer exponent exactness sign)) + (else + (parse-decimal-4 string start end + integer exponent exactness sign)))) + (finish-real integer exponent exactness sign)))) + +(define (parse-decimal-3 string start end integer exponent exactness sign) + ;; State: radix is 10, dot and # seen. + (let loop ((start start)) + (if (fix:< start end) + (let ((char (string-ref string start)) + (start+1 (fix:+ start 1))) + (if (char=? #\# char) + (loop start+1) + (parse-decimal-4 string start end + integer exponent exactness sign))) + (finish-real integer exponent exactness sign)))) + +(define (parse-decimal-4 string start end integer exponent exactness sign) + (if (exponent-marker? (string-ref string start)) + (parse-exponent-1 string (fix:+ start 1) end + integer exponent exactness sign) + (parse-decimal-5 string start end integer exponent exactness sign))) + +(define (parse-exponent-1 string start end integer exponent exactness sign) + ;; State: radix is 10, exponent seen. + (define (get-digits start esign) + (and (fix:< start end) + (let ((digit (char->digit (string-ref string start) 10))) + (and digit + (let loop ((start (fix:+ start 1)) (eint digit)) + (if (fix:< start end) + (let ((digit + (char->digit (string-ref string start) 10))) + (if digit + (loop (fix:+ start 1) + (+ (* eint 10) digit)) + (continue start eint esign))) + (continue start eint esign))))))) + + (define (continue start eint esign) + (let ((exponent (+ exponent (if (char=? #\+ esign) eint (- eint))))) + (if (fix:= start end) + (finish-real integer exponent exactness sign) + (parse-decimal-5 string start end + integer exponent exactness sign)))) + + + (and (fix:< start end) + (let ((esign (string-ref string start)) + (start (fix:+ start 1))) + (and (sign? esign) + (get-digits start esign))))) + +(define (parse-decimal-5 string start end integer exponent exactness sign) + (parse-complex string start end + (finish-real integer exponent exactness sign) + exactness 10 sign)) + +(define (parse-complex string start end real exactness radix sign) + (if (fix:< start end) + (let ((char (string-ref string start)) + (start+1 (fix:+ start 1)) + (exactness (if (eq? 'IMPLICIT-INEXACT exactness) #f exactness))) + (cond ((sign? char) + (let ((imaginary + (parse-top-level string start end exactness radix))) + (and (complex? imaginary) + (= 0 (real-part imaginary)) + (+ real imaginary)))) + ((char=? #\@ char) + (let ((angle + (parse-top-level string start+1 end exactness radix))) + (and (real? angle) + (make-polar real angle)))) + ((i? char) + (and sign + (fix:= start+1 end) + (make-rectangular 0 real))) + (else #f))) + real)) + +(define (finish-integer integer exactness sign) + ;; State: result is integer, apply exactness and sign. + (finish integer exactness sign)) + +(define (finish-rational numerator denominator exactness sign) + ;; State: result is rational, apply exactness and sign. + (finish (/ numerator denominator) exactness sign)) + +(define (finish-real integer exponent exactness sign) + ;; State: result is integer, apply exactness and sign. + (if (and (or (eq? 'INEXACT exactness) (eq? 'IMPLICIT-INEXACT exactness)) + flonum-parser-fast?) + (if (eq? #\- sign) + (flo:- 0. + (flo:* (int:->flonum integer) + (flo:expt 10. (int:->flonum exponent)))) + (flo:* (int:->flonum integer) + (flo:expt 10. (int:->flonum exponent)))) + (apply-exactness exactness + (* (apply-sign sign integer) + (expt 10 exponent))))) + +(define flonum-parser-fast? + #f) + +(define (finish number exactness sign) + (apply-sign sign (apply-exactness exactness number))) + +(define (apply-sign sign number) + (if (eq? #\- sign) + (- number) + number)) + +(define (apply-exactness exactness number) + (if (or (eq? 'INEXACT exactness) (eq? 'IMPLICIT-INEXACT exactness)) + (exact->inexact number) + number)) + +(define-integrable (exponent-marker? char) + (or (char=? #\e char) (char=? #\E char) + (char=? #\s char) (char=? #\S char) + (char=? #\f char) (char=? #\F char) + (char=? #\d char) (char=? #\D char) + (char=? #\l char) (char=? #\L char))) + +(define-integrable (sign? char) + (or (char=? #\+ char) (char=? #\- char))) + +(define-integrable (i? char) + (or (char=? #\i char) (char=? #\I char))) \ No newline at end of file diff --git a/v7/src/runtime/runtime.pkg b/v7/src/runtime/runtime.pkg index 9090478e7..5a552df98 100644 --- a/v7/src/runtime/runtime.pkg +++ b/v7/src/runtime/runtime.pkg @@ -1,6 +1,6 @@ #| -*-Scheme-*- -$Id: runtime.pkg,v 14.275 1997/02/21 05:42:58 cph Exp $ +$Id: runtime.pkg,v 14.276 1997/04/24 06:35:29 cph Exp $ Copyright (c) 1988-97 Massachusetts Institute of Technology @@ -1488,6 +1488,7 @@ MIT in each case. |# (files "numpar") (parent ()) (export () + flonum-parser-fast? string->number substring->number)) diff --git a/v8/src/runtime/runtime.pkg b/v8/src/runtime/runtime.pkg index 2b98b4796..c29641849 100644 --- a/v8/src/runtime/runtime.pkg +++ b/v8/src/runtime/runtime.pkg @@ -1,6 +1,6 @@ #| -*-Scheme-*- -$Id: runtime.pkg,v 14.282 1997/02/21 05:42:48 cph Exp $ +$Id: runtime.pkg,v 14.283 1997/04/24 06:35:14 cph Exp $ Copyright (c) 1988-97 Massachusetts Institute of Technology @@ -1488,6 +1488,7 @@ MIT in each case. |# (files "numpar") (parent ()) (export () + flonum-parser-fast? string->number substring->number)) -- 2.25.1