From: Christophe R. <cs...@ca...> - 2002-05-23 15:36:10
Attachments:
sbcl.diff
|
Hi, all. The attached patch fixes bugs 158 and 164. The bad news: it's yet another type-system patch... The offending code, slightly simplified, was: (defun foo (array) (declare (optimize (safety 0) (space 0) (debug 0) (speed 3))) (loop for i from 0 to 10 by 2 do (foo (svref array i)))) and the BUG being reported was "full call to DATA-VECTOR-REF". The problem was that sbcl was deducing that the type of I in the loop was (AND (MOD 536870911) (OR (INTEGER 0 0) (INTEGER 2 536870912))) and that the current type system made that a HAIRY type, so that when the IR2 translation phase came around and the compiler wanted to know if a given DATA-VECTOR-REF VOP was suitable, it had to ask whether this above HAIRY type was a subtype of INDEX, and the best that the current type system could do was say "dunno" (NIL, NIL). The patch implements distribution of intersections over unions. It could do with a look, and perhaps a worry over WHN's comment (in TYPE-INTERSECTION) about why it wasn't done (have I really excluded cases which will lead to stupidly large type specifiers? I don't know). Building sbcl with this patch didn't feel as though it took noticeably longer than before, and those of Eric's benchmarks that test the compiler are in the same ballpark, so I'm inclined to think that it's alright, but I'd like another pair of eyes (and for 0.7.4 to be released) before this or something like it goes in. Test cases: (subtypep '(AND (MOD 536870911) (OR (INTEGER 0 0) (INTEGER 2 536870912))) '(MOD 536870911)) should return T, T and (sb-kernel:type= (sb-kernel:specifier-type '(REAL 4 7)) (sb-kernel:specifier-type '(AND (REAL 0 7) (REAL 4 9)))) also. Cheers, Christophe -- Jesus College, Cambridge, CB5 8BL +44 1223 510 299 http://www-jcsu.jesus.cam.ac.uk/~csr21/ (defun pling-dollar (str schar arg) (first (last +))) (make-dispatch-macro-character #\! t) (set-dispatch-macro-character #\! #\$ #'pling-dollar) |
From: Raymond T. <to...@rt...> - 2002-05-23 16:50:05
|
>>>>> "Christophe" == Christophe Rhodes <cs...@ca...> writes: Christophe> The problem was that sbcl was deducing that the type of I in the loop Christophe> was Christophe> (AND (MOD 536870911) (OR (INTEGER 0 0) (INTEGER 2 536870912))) Christophe> and that the current type system made that a HAIRY type, so that when Is the type system for SBCL that different from CMUCL? CMUCL converts this to (OR (INTEGER 0 0) (INTEGER 2 536870910)), and I think CMUCL was doing this before SBCL forked off. Ray |
From: Christophe R. <cs...@ca...> - 2002-05-23 16:59:44
|
On Thu, May 23, 2002 at 12:49:17PM -0400, Raymond Toy wrote: > >>>>> "Christophe" == Christophe Rhodes <cs...@ca...> writes: > > Christophe> The problem was that sbcl was deducing that the type of I in the loop > Christophe> was > Christophe> (AND (MOD 536870911) (OR (INTEGER 0 0) (INTEGER 2 536870912))) > Christophe> and that the current type system made that a HAIRY type, so that when > > Is the type system for SBCL that different from CMUCL? CMUCL converts > this to (OR (INTEGER 0 0) (INTEGER 2 536870910)), and I think CMUCL > was doing this before SBCL forked off. It's a uniquely sbcl problem, yes. I'm not entirely sure how cmucl does it; the current type logic in sbcl has added an intersection-type (analogous to the union-type that exists in both sbcl and cmucl); but not all AND type specifiers are converted to intersection-types -- if any unions (OR types) are among the types to be ANDed together, the type system punts. I think that the change in my patch (to apply the distributive rule) gets us back to where we want to be; it's more of an issue for sbcl, because of the slightly twistier logic we have to get e.g. (subtypep '(real 0 10) 'ratio) [should be NIL, T] and (subtypep '(and (rational 0 10) (not integer)) 'ratio) [T, T] right. Cheers, Christophe -- Jesus College, Cambridge, CB5 8BL +44 1223 510 299 http://www-jcsu.jesus.cam.ac.uk/~csr21/ (defun pling-dollar (str schar arg) (first (last +))) (make-dispatch-macro-character #\! t) (set-dispatch-macro-character #\! #\$ #'pling-dollar) |
From: Christophe R. <cs...@ca...> - 2002-05-26 15:22:27
|
On Thu, May 23, 2002 at 04:35:32PM +0100, Christophe Rhodes wrote: > The patch implements distribution of intersections over unions. It could > do with a look, and perhaps a worry over WHN's comment (in > TYPE-INTERSECTION) about why it wasn't done (have I really excluded > cases which will lead to stupidly large type specifiers? I don't know). I've been brave (foolhardy, maybe) and committed this patch into sbcl-0.7.4.1 (well, it is early in the development cycle :-) Also in sbcl-0.7.4.1 are one or two things that I should mention; firstly, there's a fix for bug 140 (redefined classes not being correctly placed in the type hierarchy) from Pierre Mai. The scary thing about the patch is that it _removes_ ":invalidate nil" from a call to REGISTER-LAYOUT; the fact that it was there explicitly before indicates that someone at some point thought that the layout shouldn't be invalidated, but neither I nor Pierre could see why... in any case, there are no obvious regressions, but if anyone out there has an application that makes heavy use of CLOS and class redefinition perhaps they might wish to check that things still work... The other thing is that I've made a start (hooray!) on the sbcl performance issue; there are two minor enhancements to the array transforms: firstly, changed a failing %with-array-data call to be a call to failed-%with-array-data (which the compiler knows never returns). This improved performance in some of Eric's benchmarks (FILL-STRINGS, BENCH-STRING-CONCAT) by of the order of 10%, as well as being a readability win :-); the second is to extend the deftransform for %with-array-data to simple-array (from vector[*]); this improves performance on the 2D-ARRAYS benchmark by 15% (leaving us a mere 5 times slower than cmucl-18d :-/) and PUZZLE by 60% (3 times). Inevitably, a set of canned benchmarks isn't the best way of measuring things, and also not necessarily terribly realistic, but that (and recompiling sbcl :-) is the only one I have... Cheers, Christophe [*] It has just occurred to me that vector is not a subtype of simple-array, as the vector type includes adjustable arrays of one dimension or vectors with fill-pointers. Please report if this causes a problem. -- Jesus College, Cambridge, CB5 8BL +44 1223 510 299 http://www-jcsu.jesus.cam.ac.uk/~csr21/ (defun pling-dollar (str schar arg) (first (last +))) (make-dispatch-macro-character #\! t) (set-dispatch-macro-character #\! #\$ #'pling-dollar) |