interrupting for overflow and loop termination
|
From: David Hopwood on 12 Sep 2005 11:05 glen herrmannsfeldt wrote: > David Hopwood wrote: > >> But to answer the question, some examples of where this approach can be >> effective are using unmapped guard pages to detect stack overflows, >> exhaustion of an allocation space, or null pointer accesses in >> languages that require null pointer checks. >> >> Note that these are cases in which the relevant operation >> (allocating a stack frame or object, indirecting through a pointer) >> is extremely common, and the interrupt-based optimization is in >> "infrastructure" code so that a single implementation can apply >> to many programs. Even then it may not pay off: hacks like this >> should be reevaluated every so often to see whether they are really >> giving a performance improvement that justifies their complexity. > > They should, but a protected mode system must check for invalid > addresses, and a virtual memory system must check for a valid > page table entry. Right; I was referring to complexity of the software (e.g. language implementation). The hardware complexity cost has to be paid anyway in a system with virtual memory. -- David Hopwood <david.nospam.hopwood(a)blueyonder.co.uk>
From: David Hopwood on 12 Sep 2005 11:09 David Hopwood wrote: > glen herrmannsfeldt wrote: >> David Hopwood wrote: >> >>> But to answer the question, some examples of where this approach can be >>> effective are using unmapped guard pages to detect stack overflows, >>> exhaustion of an allocation space, or null pointer accesses in >>> languages that require null pointer checks. >>> >>> Note that these are cases in which the relevant operation >>> (allocating a stack frame or object, indirecting through a pointer) >>> is extremely common, and the interrupt-based optimization is in >>> "infrastructure" code so that a single implementation can apply >>> to many programs. Even then it may not pay off: hacks like this >>> should be reevaluated every so often to see whether they are really >>> giving a performance improvement that justifies their complexity. >> >> They should, but a protected mode system must check for invalid >> addresses, and a virtual memory system must check for a valid >> page table entry. > > Right; I was referring to complexity of the software (e.g. language > implementation). The hardware complexity cost has to be paid anyway in > a system with virtual memory. .... but portability to systems that don't support virtual memory is a good reason to make such optimizations optional. -- David Hopwood <david.nospam.hopwood(a)blueyonder.co.uk>
From: David Hopwood on 12 Sep 2005 11:24 glen herrmannsfeldt wrote: > David Hopwood wrote: > > (snip regarding interrupt loop termination) > >> If the speculative execution circuitry is "overloaded", then the same is >> likely to be true of the interrupt checking under the same circumstances. >> Checking for interrupts (which then need to be delivered precisely) is >> not free; in terms of complexity it is similar to speculative execution. >> That is, you strongly speculate that the interrupt is not taken on each >> instruction, and have to recover if it is. The difference is that you >> need dedicated hardware resources to check the interrupt conditions on >> *every* instruction, rather than using shared resources to do it only when >> the condition is relevant. > > Well, how about an imprecise interrupt, where possibly one or more > additional loop cycles will be executed. For it to be feasible to recover from the execution of those additional loop cycles in software, it's necessary for the loop to have no irreversible side effects (including side effects internal to the language implementation, even if the code is pure functional). In some cases, you could record what side effects would have been performed in the loop and then do them afterward, or you could attempt to undo side effects. But in general this optimization is probably too hard. Just to save one predicted-not-taken conditional branch per loop iteration, it's not worth it. -- David Hopwood <david.nospam.hopwood(a)blueyonder.co.uk>
From: Frode Vatvedt Fjeld on 12 Sep 2005 11:32 Terje Mathisen <terje.mathisen(a)hda.hydro.com> writes: > I really can't see any way implicit interrupt handling would help > with _any_ of this code though! FWIW, I recently implemented in my compiler that addidion of two addends known to be immediates (i.e. through type inference) and where the result might overflow into the bignum range, compiles to something like ADDL eax ebx, INTO. While I hope there's something to be gained by avoiding the conditional branch, perhaps equally important is the gain in code-size; I think some 10-15 bytes of machine code are saved here, for what is a fairly common operation. BTW I thought the (relevant part of) the overflow exception handler turned out rather cute :) (let ((eax (dereference $eax))) (setf (dereference $eax) (if (plusp eax) (- most-negative-fixnum 1 (- most-positive-fixnum eax)) (+ most-positive-fixnum 1 (- eax most-negative-fixnum)))) (It follows that INTO is only used/allowed after an add to eax.) -- Frode Vatvedt Fjeld
From: andrewspencers on 12 Sep 2005 11:42
chl wrote: > Yes, and this eventually means the caller or the callee have to save the current > interrupt vector. You still believe this is efficient? No, not anymore. |