X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=OPTIMIZATIONS;h=42119acef2c0fd7a33780ca56d3204fa5fd5ec6a;hb=HEAD;hp=53438ab4a996f18951a81d5f7b69e453200b522a;hpb=f846a7a310d630cf538811959916492a28a75fb1;p=sbcl.git diff --git a/OPTIMIZATIONS b/OPTIMIZATIONS index 53438ab..42119ac 100644 --- a/OPTIMIZATIONS +++ b/OPTIMIZATIONS @@ -157,20 +157,6 @@ sbcl-0.8.12.30, this affects at least DUMP-OBJECT through COMPOUND-OBJECT-P, and (LABELS MAYBE-EMIT-MAKE-LOAD-FORMS GROVEL) through TYPEP UNBOXED-ARRAY, within the compiler itself. -------------------------------------------------------------------------------- -#18 -(lambda (x) (declare (null x)) (sxhash x)) goes through SYMBOL-HASH -rather than either constant-folding or manipulating NIL-VALUE or -NULL-TN directly. --------------------------------------------------------------------------------- -#19 - (let ((dx (if (foo) - (list x) - (list y z)))) - (declare (dynamic-extent dx)) - ...) - -DX is not allocated on stack. --------------------------------------------------------------------------------- #20 (defun-with-dx foo (x) (flet ((make (x) @@ -182,42 +168,15 @@ DX is not allocated on stack. (declare (dynamic-extent l)) (mapc #'print l)))) -Result of MAKE is not stack allocated, which means that -stack-allocation of structures is impossible. --------------------------------------------------------------------------------- -#21 -(defun-with-dx foo () - (let ((dx (list (list 1 2) (list 3 4) - (declare (dynamic-extent dx)) - ...))))) - -External list in DX is allocated on stack, but internal are not. +Result of MAKE is not stack allocated. -------------------------------------------------------------------------------- #22 IR2 does not perform unused code flushing. -------------------------------------------------------------------------------- -#23 -Python does not know that &REST lists are LISTs (and cannot derive it). --------------------------------------------------------------------------------- #24 -a. Iterations on &REST lists, returning them as VALUES could be - rewritten with &MORE vectors. +a. Iterations on &REST lists could be rewritten with &MORE vectors. b. Implement local unknown-values mv-call (useful for fast type checking). -------------------------------------------------------------------------------- -#25 -EQL is implemented generically in situations where this isn't necessary. - -(defun f (x y) - (declare (type (or symbol fixnum) x) - (optimize speed (safety 0) (debug 0))) - (eql x y)) - -SUBTYPEP is smart enough to determine that this type is a subtype -of (and (or (not number) fixnum) (not character)) - -This sitation where the type is (OR NULL FIXNUM) comes up -in cl-bench, for example in the value returned by POSITION. --------------------------------------------------------------------------------- #26 SBCL cannot derive upper bound for I and uses generic arithmetic here: @@ -232,3 +191,216 @@ SBCL cannot derive upper bound for I and uses generic arithmetic here: (So the constraint propagator or a possible future SSA-convertor should know the connection between an NLE and its CLEANUP.) +-------------------------------------------------------------------------------- +#27 +Initialization of stack-allocated arrays is inefficient: we always +fill the vector with zeroes, even when it is not needed (as for +platforms with conservative GC or for arrays of unboxed objectes) and +is performed later explicitely. + +(This is harder than it might look at first glance, as MAKE-ARRAY is smart +enough to eliminate something like ':initial-element 0'. Such an optimization +is valid if the vector is being allocated in the heap, but not if it is being +allocated on the stack. You could remove this optimization, but that makes +the heap-allocated case somewhat slower...) + +To do this, extend ALLOCATE-VECTOR with ALLOW-JUNK argument, and when +stack allocating don't zero if it is true -- and probably ALLOW-JUNK iff +the vector is a specialized one (cannot have pointers.) +-------------------------------------------------------------------------------- +#28 +a. Accessing raw slots in structure instances is more inefficient than +it could be; if we placed raw slots before the header word, we would +not need to do arithmetic at runtime to access them. (But beware: +this would complicate handling of the interior pointer). + +b. (Also note that raw slots are currently disabled on HPPA) +-------------------------------------------------------------------------------- +#29 +Python is overly zealous when converting high-level CL functions, such +as MIN/MAX, LOGBITP, and LOGTEST, to low-level CL functions. Reducing +Python's aggressiveness would make it easier to effect changes such as + +x86-64: +* direct MIN/MAX on {SINGLE,DOUBLE}-FLOATs ({MIN,MAX}S{S,D}) + +x86-64: +* direct LOGBITP on word-sized integers and fixnums (BT + JC) + +x86{,-64}/PPC: +* branch-free MIN/MAX on word-sized integers and fixnums (floats could + be handled too, modulo safety considerations on the PPC) + +x86-64: +* efficient LOGTESTs on word-sized integers and fixnums (TEST) + +etc., etc. + +(The framework for this has been implemented as of 0.9.9.18; see the +vm-support-routine COMBINATION-IMPLEMENTATION-STYLE and its use in +src/compiler/ir1opt.lisp, IR1-OPTIMIZE-COMBINATION. The above +optimizations are left as an exercise for the reader.) +-------------------------------------------------------------------------------- +#31 +The typecheck generated for a declaration like (integer 0 45) on x86 looks +like: + +; 12B: F6C203 TEST DL, 3 +; 12E: 753B JNE L1 +; 130: 8BC2 MOV EAX, EDX +; 132: 83F800 CMP EAX, 0 +; 135: 7C34 JL L1 +; 137: 8BC2 MOV EAX, EDX +; 139: 3DB4000000 CMP EAX, 180 +; 13E: 7F2B JNLE L1 + +A better code sequence for this would be: + + TEST DL, 3 + JNE L1 + MOV EAX, EDX + CMP EAX, 180 + JBE L1 + +Doing an unsigned comparison means that, similarly to %CHECK-BOUND, we can +combine the <0 and >=bound tests. This sort of test is generated often +in SBCL and any array-based code that's serious about type-checking its +indices. +-------------------------------------------------------------------------------- +#32 +The code for a vector bounds check on x86 (similarly on x86-64) where +the vector is in EDX and the index in EAX looks like: + +; 49: L0: 8B5AFD MOV EBX, [EDX-3] +; 4C: 39C3 CMP EBX, EAX +; 4E: 7632 JBE L2 + +because %CHECK-BOUND is used for bounds-checking any array dimension. +A more efficient specialization (%CHECK-BOUND/VECTOR) would produce: + + CMP [EDX-3], EAX + JBE L2 + +Which is slightly shorter and avoids using a register. +-------------------------------------------------------------------------------- +#33 +Reports from the Java camp indicate that using an SSE2-based +floating-point backend on x86 when possible is highly preferable to +using the x86 FP stack. It would be nice if SBCL included an SSE2-based +floating point backend with a compile-time option to switch between the +two. +-------------------------------------------------------------------------------- +#35 +Compiling + +(defun foo (a i) + (declare (type simple-vector a)) + (aref a i)) + +results in the following x86 code: + +; 115886E9: F7C703000000 TEST EDI, 3 ; no-arg-parsing entry point +; 6EF: 7510 JNE L0 +; 6F1: 8BC7 MOV EAX, EDI +; 6F3: 83F800 CMP EAX, 0 +; 6F6: 7C09 JL L0 +; 6F8: 8BC7 MOV EAX, EDI +; 6FA: 3DF8FFFF7F CMP EAX, 2147483640 +; 6FF: 7E0F JLE L1 +; 701: L0: 8B057C865811 MOV EAX, [#x1158867C] ; '(MOD + ; 536870911) +; 707: 0F0B0A BREAK 10 ; error trap +; 70A: 05 BYTE #X05 +; 70B: 1F BYTE #X1F ; OBJECT-NOT-TYPE-ERROR +; 70C: FECE01 BYTE #XFE, #XCE, #X01 ; EDI +; 70F: 0E BYTE #X0E ; EAX +; 710: L1: 8B42FD MOV EAX, [EDX-3] +; 713: 8BCF MOV ECX, EDI +; 715: 39C8 CMP EAX, ECX +; 717: 7620 JBE L2 +; 719: 8B540A01 MOV EDX, [EDX+ECX+1] + +... plus the standard return sequence and some error blocks. The +`TEST EDI, 3' and associated comparisons are to ensure that `I' is a +positive fixnum. The associated comparisons are unnecessary, as the +%CHECK-BOUND VOP only requires its tested index to be a fixnum and takes +care of the negative fixnum case itself. + +{HAIRY-,}DATA-VECTOR-REF are DEFKNOWN'd with EXPLICIT-CHECK, which would +seem to take care of this, but EXPLICIT-CHECK only seems to be used when +compiling calls to unknown functions or similar. Furthermore, +EXPLICIT-CHECK, as NJF understands it, doesn't have the right +semantics--it suppresses all type checking of arguments, whereas what we +really want is to ensure that the argument is a fixnum, but not check +its positiveness. +-------------------------------------------------------------------------------- +#36 + +In #35, the CMP EAX, $foo instructions are all preceded by a MOV. They +appear to be unnecessary, but are necessary because in IR2, EDI is a +DESCRIPTOR-REG, whereas EAX is an ANY-REG--and the comparison VOPs only +accept ANY-REGs. Therefore, the MOVs are "necessary" to ensure that the +comparison VOP receives an TN of the appropriate storage class. + +Obviously, it would be better if a) we only performed one MOV prior to +all three comparisons or b) eliminated the necessity of the MOV(s) +altogether. The former option is probably easier than the latter. + +-------------------------------------------------------------------------------- +#38 + +(setf (subseq s1 start1 end1) (subseq s2 start2 end1)) + +could be transformed into + +(let ((#:s2 s2) + (#:start2 start2) + (#:end2 end2)) + (replace s1 #:s2 :start1 start1 :end1 end1 :start2 #:start2 :end2 #:end2)) + +when the return value is unused, avoiding the need to cons up the new sequence. + +-------------------------------------------------------------------------------- +#39 + +(let ((*foo* 42)) ...) + +currently compiles to code that ensures the TLS index at runtime, which +is both a decently large chunk of code and unnecessary, as we could ensure +the TLS index at load-time as well. + +-------------------------------------------------------------------------------- +#40 + +When FTYPE is declared -- to say (function (t t t t t) t), and +function has a compiler-macro, + + (apply #'foo 'x1 x2 'x3 more) + +can be transformed into + + (apply (lambda (x2 x4 x5) (foo 'x1 x2 'x3 x4 x5)) x2 more) + +which allows compiler-macro-expansion for FOO. (Only constant +arguments can be moved inside the new lambda -- otherwise evaluation +order is altered.) + +-------------------------------------------------------------------------------- +#41 + +The unibyte external formats are written in a very generic way. Three +optimizations immediately applicable that could be automatically +generated: + +(a) if the external format merely permutes the first 256 characters, a + constant-time lookup (rather than a binary search) could be + performed on output. This applies at least to EBCDIC, which + currently has a hand-rolled mapper instead. + +(b) if there are no undefined characters corresponding to the 256 + codes, then no error checking need be done on input. + +(c) if there is a way to use particular bits of the exceptional + characters, constant-time output (rather than binary search) can + still be achieved as used to be done by the latin-9 external + format before 1.0.31.