## sbcl Log

Commit Date
[b31eab] (27.2 kB) by Nikodemus Siivola

move vm-array.lisp earlier in the build, remove %%SAETP-INFO%%

This way DEFINE-ARRAY-DISPATCH can use *S-A-E-T-P* directly.

2012-05-27 09:48:43 View
[436b2a] (27.2 kB) by Lutz Euler

Better equidistributed and faster/less consing integer RANDOM.

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 0a7604d54581d2c846838c26ce6a7993629586fa 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.

2012-05-01 16:59:12 View
[b71b8d] (27.1 kB) by Nikodemus Siivola

extensible CAS and CAS extensions

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.

* 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

(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...

2011-06-08 07:58:59 View
[65b5ab] (27.1 kB) by Alastair Bridgewater

* 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.

2010-08-04 17:58:15 View
[41248d] (27.0 kB) by Nathan Froyd

1.0.38.7: fix clisp build for ppc

LP #576587, thanks to Josh Elsasser for the patch.

2010-05-10 00:39:12 View
[77d7fd] (27.2 kB) by Christophe Rhodes

1.0.33.16: implement UTF external formats

UTF-16 and UTF-32, being strict about handling of surrogates and noncharacters
according to Unicode.

2009-12-16 22:12:35 View
[99a8f9] (27.1 kB) by Christophe Rhodes

1.0.33.14: improve UCS external formats

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.

2009-12-16 21:39:30 View
[f2db67] (27.1 kB) by Nathan Froyd

1.0.31.23: OAOOize external-format support

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.

2009-09-29 01:02:20 View
[d442c2] (27.1 kB) by Christophe Rhodes

1.0.30.41: Octets support for ebcdic-us
Continuing the theme of extensions no-one has ever asked for.

(There's a lot of duplicated code everywhere in
src/code/external-formats that could be replaced with a
sufficiently complicated macro-defining-macro...)

2009-08-07 11:21:21 View
[c461e2] (27.0 kB) by Nikodemus Siivola

* 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

* 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.

2009-06-22 16:06:22 View
[b42c75] (27.1 kB) by Alastair Bridgewater

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

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/

With this, source-location information in SBCL is now correct even
when used against an unbuilt source tree.

2009-05-05 17:11:18 View
[a16091] (27.1 kB) by Christophe Rhodes

1.0.27.31: repeatable fasl header and debug-source

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

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'

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.

2009-04-24 10:06:20 View
[5cf3c4] (27.1 kB) by Paul Khuong

1.0.24.34: IR2: additional representation for predicates, conditional 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.

2009-01-11 18:33:31 View
[fe1921] (27.1 kB) by Nikodemus Siivola

* 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

* The "try another pathname" restart in TRY-RELOAD-SHARED-OBJECT
changed the pathname but did not reload. Fix that.

2008-10-09 20:48:24 View
[682203] (27.1 kB) by Nikodemus Siivola

1.0.19.7: refactor stack allocation decisions

* 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.

2008-07-30 17:58:39 View
[45bc30] (27.0 kB) by Nikodemus Siivola

1.0.17.24: refactor handling of constants in the compiler

* 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

* 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

* 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.

2008-06-04 12:39:38 View
[edf8d3] (27.0 kB) by Nikodemus Siivola

1.0.12.18: faster member-type operations

* 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.

2007-12-09 14:37:22 View
[fe962b] (27.0 kB) by Nikodemus Siivola

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.

2007-04-29 21:57:39 View
[1cfea5] (26.9 kB) by William Harold Newman

1.0.4.8:
"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 1.0.4.5 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.)

2007-03-28 17:59:16 View
[0a7604] (27.0 kB) by William Harold Newman

1.0.4.6:
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.

2007-03-27 16:20:38 View
[b8a674] (26.9 kB) by sa2c

1.0.1.2: support for GBK external format
(thanks to Chun Tian (binghe))

2006-12-27 00:37:30 View
[cb83aa] (26.8 kB) by Juho Snellman

1.0.0.18:
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).
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.

2006-12-05 04:35:55 View
[0d5ff0] (26.8 kB) by Rudi Schlatte

0.9.18.45
"Patch to update Japanese external formats" (NIIMI Satoshi, 2006-11-10)
* New external format: Shift-JIS

2006-11-12 21:42:27 View
[2b90fd] (26.6 kB) by Nikodemus Siivola

0.9.18.6: Win32 get-internal-real-time improved
* 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.

2006-10-26 08:38:49 View
[f4820c] (26.6 kB) by Nikodemus Siivola

0.9.17.18: fix windows build, MAKE-ALIEN compiler note muffled fully
* 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.

2006-10-23 13:45:51 View