This way DEFINE-ARRAY-DISPATCH can use *S-A-E-T-P* directly.
Up to now the implementation of RANDOM with an integer argument just generated a few more random bits than the length of the argument and took this value MOD the argument. This led to a slightly uneven distribution of the possible values unless the argument was a power of two. Moreover, for bignums, the algorithm was quadratic both in time and space dependent on the number of bits of the argument. Instead generate random integers using an accept-reject loop and change the bignum implementation to an algorithm that is linear in time and space. I took some inspiration from WHN's attempt at an accept-reject loop implementation in commit 0a7604d and following. Thanks to Christophe Rhodes for reviewing this patch! Some details: The implementation works correctly with both a random chunk size equal to the word size and equal to half the word size. This is currently necessary as a 32-bit pseudo random generator is used both under 32 and under 64 bit word size. In the generic RANDOM case, fixnum and bignum limits are differentiated: With a fixnum limit an accept-reject loop on a masked random chunk is always used. Under 64 bit word size two random chunks are used only if the limit is so large that one doesn't suffice. This never conses. With a bignum limit four cases are differentiated to minimize consing. If just one random chunk is needed to supply a sufficient number of bits the implementation only conses if the result is indeed a bignum: * If the limit is a power of two, a chunk is generated and shifted to get the correct number of bits. * If the limit is not a power of two an accept-reject loop with shifting is used. If more than one random chunk is needed, a bignum is always consed even if it happens to normalize to a fixnum: * If the limit is a power of two a straightforward algorithm is used to fill a newly created bignum with random bits. * If the limit is not a power of two an accept-reject loop is used that detects rejection early by starting from the most significant bits, thus generating on the average only one random chunk more than needed to fill the result once. The test for power of two is non-consing, too. In the case of a compile-time constant integer argument (of at most word size) a DEFTRANSFORM triggers, that, in the general case, compiles an accept-reject loop. For values of the limit where this sufficiently reduces the rejection probability the largest multiple of the limit fitting in one or two random chunks is used instead inside the loop. To bring the result in the correct range a division is then necessary (which the compiler converts into a multiplication). Powers of two are optimized by leaving out the rejection test. In those cases where a word has more bits than a random chunk, the generated expression uses two chunks only if necessary.
DEFINE-CAS-EXPANDER and DEFCAS are analogous to DEFINE-SETF-EXPANDER and DEFSETF, including CAS-functions similar to SETF-functions: (defun (cas foo) (old new ...) ...) THis is exported from SB-EXT for users to play with, and used to implement our CAS places internally. Add support for CAS of: * SLOT-VALUE * STANDARD-INSTANCE-ACCESS * FUNCALLABLE-STANDARD-INSTANCE-ACCESS In case of SLOT-VALUE we don't yet support any optimizations or specify results when SLOT-VALUE-USING-CLASS or friends are in play -- perhaps later we can add (CAS SLOT-VALUE-USING-CLASS) &co in order to support it for arbitrary instances. Adding support for permutation vector optimization should not be too hard either, but let's let the dust settle first...
* New file, src/code/barrier.lisp, containing the baseline implementation. * Added the barrier functions to the compiler function database. * Export the interface macro, BARRIER, from SB!THREAD and the underlying barrier functions from SB!VM. * Document a new architecture-dependent build-time feature, MEMORY-BARRIER-VOPS, for controlling the behavior and inlining of the interpreter stubs for the barrier functions.
Fix a simple bug in the CHAR->UCS-2BE error case. Fix error-handling UCS-2 cases, by actually being careful about using the return values of the encoding-error/decoding-error octet functions, and by using adjustable vectors. Include tests for this. Implement UCS-4, as a straight-through 32-bit encoding of the char-code. Move external-formats/ucs-2.lisp to external-formats/enc-ucs.lisp, and include a comment header explaining the distinction in our terms between UCS and UTF external formats.
fd-streams and octets support independently kept records of external-format->function maps, suitable for the purposes of each. This revision stores all the relevant information for an external format in a single place--a new EXTERNAL-FORMAT structure--and has both clients reference things in that single place. Doing so offers opportunities for other cleanups and speedups. fd-streams external-format storage was an alist of lists, which was bad for client code, since everything referred to fields with NTH or SECOND/FOURTH/FIFTH. A proper DEFSTRUCT helps here and should be slightly more space-efficient, as we're replacing a list with (effectively) a vector. Also, since clients had to scan through an alist to find an external-format, this design was hurting performance in streams code, most notably OPEN. Replacing the alist with a hash table (which the octets code was already using) should make things a lot snappier.
* Nuke PCOUNTER stuff, and replace it with a COUNTER local to profile.lisp: ** New counter uses ATOMIC-INCF for atomicity, plus a lock and an overflow counter to handle counts over word in size. ** Stack allocate counters and counter value cells when possible to reduce overhead. * Nuke the FASTBIG-stuff. A generic arithmetic call with fixnum args is not that slow -- and if it turns out to be too slow after all, then the compiler should take care of this under appropriate policy instead of us using hacks like this. * Test case from Volkan Yazici.
Changed the object filename computation function to use a different suffix for files in target-compile mode with the :assem flag. Changed the src/compiler/assembly/ paths in build-order.lisp-expr to refer to src/assembly/ instead. Changed the duplicate-stem check in src/cold/shared.lisp to operate in terms of target-compile object file names. Changed both the source and object filename computation functions to call a new function to remap stem path segments matching "/target/" to the appropriate per-arch directory. Removed the code for creating the compiler/assembly/ and target/ symlinks from make-config.sh. With this, source-location information in SBCL is now correct even when used against an unbuilt source tree.
The fasl header is easy to deal with; writing "at cross-compile time" instead of something depending on the host is easy. The debug-source is harder; we set the structure slots to 0 in the cross-compiler, and arrange for cold-init to patch sensible values in (by inventing a new FOP to note the debug-source's arrival). made up of 5 commits, whose individual messages follow: deal with trivial volatile contents of fasl files Don't try to preserve, even in the header, information about which implementation or machine was used for the compilation. Similarly, don't emit the timestamps in the debug-source into the fasls. comments: delete a FIXME and explain a bare `2' consistent source pathname for output/stuff-groveled-from-headers.lisp At the moment it's the only compiled file not in src/; code defensively around that fact. fix a longstanding KLUDGE Find the index of the source slot by introspection rather than using a baffling literal `2'. Unfortunately, in doing so we run into bug #117. patch in the source created/compiled information in cold-init We can't do it before without making our fasls or cold-sbcl.core dependent on filesystem timestamps or current time. The way we do it is perhaps overcomplicated, compared with simply assuming that the file timestamps are right, but has the advantage that it's demonstrably correct: we implement a new FOP specifically for noting our DEBUG-SOURCE, dumped only during cross-compilation, and in genesis we interpret that FOP to build a list of debug-sources, which we can frob in cold-init. Everything should now be restored to its previous functionality.
… moves * :CONDITIONAL VOPs can now specify how to interpret the test they compute without performing the branch directly. How the test is specified is completely platform-dependent and only affects new-style :CONDITIONAL VOPs and a new BRANCH-IF VOP (src/compiler/$ARCH/pred.lisp). * Candidates for conversion to conditional moves are found and may be converted, depending on CONVERT-CONDITIONAL-MOVE-P, a new VM support routine. C-C-M-P returns NIL to punt on the conversion, or 5 values: 1. name of the VOP to use 2. TN for the first argument (NIL if none) 3. TN for the second argument (NIL if none) 4. TN for the result 5. A list of info data, which will be appended to the flags The correct values will be MOVEd in the argument TNs if needed before computing the condition, and the result MOVEd to the right TN after the conditional move VOP.
* Add &key :DONT-SAVE to control interaction with SAVE-LISP-AND-DIE. * Better documentation, including mention of LD_LIBRARY_PATH. * Refactor the OAOOM mess between win32-foreign-load.lisp and foreign-load.lisp: add unix-foreign-load.lisp, and move the shared code to foreign-load.lisp. * The "try another pathname" restart in TRY-RELOAD-SHARED-OBJECT changed the pathname but did not reload. Fix that.
* Remove SB-C::STACK-ALLOCATE-* policies. * Obey DYNAMIC-EXTENT declarations if SB-EXT:*STACK-ALLOCATE-DYNAMIC-EXTENT* is true (the default), with the following exceptions: ** Value cells are not stack allocated. ** Vectors that may be longer then a single page are stack allocated only in SAFETY 0 policies. * New declaration: SB-INT:TRULY-DYNAMIC-EXTENT. Always stack-allocates, regardless of SB-EXT:*STACK-ALLOCATE-DYNAMIC-EXTENT*. Also causes stack allocation of value cells and potentially large vectors. Used exclusively inside SBCL. * Move STACK-ALLOCATE-RESULT optimizers from backends to src/compiler/generic/vm-ir2tran.lisp. * Documentation.
* Coalesce non-circular lists, bit-vectors, and non-base-strings in the file-compiler. (We could do more, but these are the "easy" ones.) Takes care of OPTIMIZATIONS #34 in practice: outside the file compiler one can still trick the system into similar behaviour, but that seems a fairly academic concern. * Never go through SYMBOL-VALUE at runtime to fetch the value of a constant variable in compiled code. * Use (SYMBOL-VALUE <NAME>) as the load-form to dump references to named constants into fasls. * Signal a continuable error if an attempt to change the SYMBOL-VALUE of a constant variable is made. * Assignments to undefined variables go through SET, so that one cannot accidentally modify a constant by doing something like: (defun set-foo (x) (setq foo x)) (defconstant foo 42) (set-foo 13) * Gets rid of INFO :VARIABLE :CONSTANT-VALUE, and just uses SYMBOL-VALUE to store constant values. * Move definition of SB!XC:LAMBDA-LIST-KEYWORDS to be beginning of the build, and use it instead of the host LAMBDA-LIST-KEYWORDS where appropriate. * Tests.
* XSET is a generic set implementation, that uses lists of small sets, and switches to hashes for larger ones. Current switchoff point is 12 -- but some operations would benefit from a larger one. TODO: There are other places in SBCL that will probably want to use XSET as well. * Instead of storing members directly in the set object, store them in an XSET -- except for floating point zeros which go into a list of their own, simplifying the canonicalization a bit. (By adding complexity elsewhere, of course. Maybe this is not TRT after all...) * ...now member type arithmetic is mostly O(1) or O(N), instead of O(BAD), but some operations cons more then before: old implemenation manageg eg. union without consing when either set was the subset of the other one -- not so anymore.
* WITH-DEADLINE provides an interface to a synchronous deadline/timeout facility that can interrupt execution only on blocking IO and when waiting on locks (latter Linux only for now.) * DECODE-DEADLINE provides an interface that implementors of blocking functions can use to hook into the deadline mechanism. * Add SB-IMPL::*ON-DANGEROUS-SELECT* for debugging: can be used to warn/ signal an error / obtain a backtrace when SBCL calls select without a timeout while interrupts are disabled. * Undocumented and unexported periodic polling functionality has been removed from SERVE-EVENT, but can be reinstated should it be desired.
"What's old is new again" or "what was he thinking?" At least in the wisdom of hindsight I can see that my new RANDOM is not ready for release, so I have reverted it. This version should be essentially 126.96.36.199 with a new version number. (It also has an extra, orphaned file in src/compiler/integer-tran.lisp. When I revisit the problem later, that should be cleaned up one way or another, meanwhile I don't feel like deleting it and then likely recreating it later.) Sorry about the confusion.:-(
rewrote RANDOM for INTEGER case to eliminate (small) bias Alas, it doesn't seem practical to test this properly. (Difficulty of building a nice test suite seems to be a pervasive problem for randomized code.) I could write a test case narrowly targeted to detect the old bug, but I don't think I could make even that single test simultaneously fast enough and reliable enough that it would be a good candidate for run-tests.sh. And aiming at a more comprehensive set of tests just makes the making-it-fast-enough problem that much harder.
Add an xref facility, exported from sb-introspect. * Support who-calls/macroexpands/binds/sets/references, with full source path information for extra Slime-goodness. * Only causes relatively small amounts of compilation slowdown or fasl bloat, so enable it by default (unless (= SPEED 3)). * Does not handle: expanded compiler-macros, code in macrolet definition bodies, toplevel code * Xref data is currently stored in a new simple-fun slot (the FUN_RAW_ADDR mess has been cleaned up a little), in reverse format (that is, we store who-is-called rather than who-calls). * sb-introspect gets access to the simple-funs through the infodb, so each lookup requires looping through the whole db. This is snappy enough on my machine even with lots of code loaded, but some other storage strategy might be worth looking at later.
* The old version was accurate only to the second, new one gets milliseconds right. * Move unix/win32 implementation bodies of GET-INTERNAL-*-TIME to unix.lisp and win32.lisp (less conditionalization). * Move *GC-RUN-TIME* zeroing to GC-REINIT. * Initialize the system epoch to start time, not to time of first call to GET-INTERNAL-REAL-TIME, document system epoch in GET-INTERNAL-REAL-TIME. * Sort the stub function calls in src/runtime/win32.c nicely.
* Win32 build needs MAKE-ALIEN much earlier then other platforms, so restore MAKE-ALIEN to its old place in target-alieneval.lisp, and muffle the %SAP-ALIEN note from there unconditionally.
… policy * Uses of MAKE-ALIEN are a common source of unavoidable notes about unoptimized %SAP-ALIEN, which only serve to mask the ones the user can do something about.
Rewrite the single-stepper to solve the compilation/run-time performance and type-inference inaccuracy problems with the old approach. Also make some UI improvements to the stepper. * The IR1 stage no longer instruments the code. Instead it only detects function call forms which should (according to the policy) be steppable, and records a string representation of those forms in the matching combination nodes (to be stored in the debug-info). * Modify the function call vops to emit some instrumentation just before the actual call happens. This will check either the symbol-value of *STEPPING* (unithreaded) or the new STEPPING slot of threads (multithreaded) and trap if it's true. The trap handler will replace the closure / fdefn that was about to be called with a wrapper, which will signal a stepper condition and then call the original function. * Emit a similar bit of instrumentation before any call that got optimized to a simple VOP. The difference is that the only thing that the trap handler will do is to directly signal the condition. * The necessary VOP / runtime changes have only been done on x86, x86-64 and ppc so far. Alpha, Mips and Sparc should still compile, but the stepper won't work there. * Remove the old single-stepper REPL, and instead integrate the stepper into the debugger. * Add STEP-OUT functionality (stop stepping temporarily, resuming it once the current function returns).
A couple of type-system fixups for #+sb-eval ... we have to have sb-eval:interpreted-function defined on the host, so that the deftype for COMPILED-FUNCTION does not involve any unknown types. So ... make !defstruct-with-alternate-metaclass compilable by the host compiler, similarly to sb-xc:defstruct. Don't quite do it properly: put a FIXME note in for posterity. ... move early-full-eval.lisp earlier in the build, and split out the definition for compiled-function from deftypes-for-target to late-deftypes-for-target (after the interpreted-function class is defined) ... (declare (type compiled-function x)) should do a type check for compiled-function, not for simply FUNCTION. ... the problem was actually in PRIMITIVE-TYPE on intersection types; the computation was fairly bogus. Make it less bogus. ... also delete some stale classoid symbols.
Add an interpreting EVAL, for cases where the compiler is unsuitable due to e.g. compilation overhead. * The old EVAL is still the default. To use the new one, (SETF SB-EXT:*EVALUATOR-MODE* :INTERPRET). Making the interpreter the default might be the purer choice, since there's a standard way of ensuring that code is compiled, and no standard way of ensuring that it's not. On the other hand, there are practical reasons for keeping the compiler as the default. The interpreter is very slow, doesn't have proper debugger support (either for backtraces or inspecting frames), and it doesn't have stepper support. * The interpreter doesn't treat THE or type declarations for lexical variables as assertions. The regression tests that assume otherwise have been disabled when running in interpreted mode. The intepreter will however type-check the proclaimed types of specials.
* Less sucky toplevel-init: use PARSE-NATIVE-NAMESTRING to deal with user-supplied init-file names, and refactor the logic between Posix and Windows. * New runtime option: --debug-environment, prints out the command line arguments and environment before anything fancy gets done to them. Good for debugging startup from Windows shortcuts, etc. * Less magic constants, more groveled stuff. * SB-WIN32::GET-FOLDER-PATH renamed to SB-WIN32::GET-FOLDER-PATHNAME, and it now returns pathnames instead of strings. * Add internal function SBCL-HOMEDIR-PATHNAME, and centralize the SBCL_HOME stuff there. * Still LESS_SHOUTING. * Move stuff-groveled-from-headers.lisp earlier in the build-order, so toplevel.lisp can use it. * No localtime_r and gmtime_r on Windows.
Implement and document SB-EXT:*CORE-PATHNAME*. ... communicate from runtime via SB-INT:*CORE-STRING*, rather than constructing a pathname in C. Related refactoring. ... since OS-COLD-INIT-OR-REINIT has exactly the same functionality on all currently supported platforms, move it into a common file; ... define common *common-static-symbols* and *c-callable-static-symbols* for use in constructing the per-backend *static-symbols* list, and to remove the need for maintaining a separate list of callable symbols in genesis.
* Make CHAR-NAME and NAME-CHAR aware of the Unicode names when building with :SB-UNICODE.