[Sbcl-devel] static (or immobile) conses

Rob Sumners

2017-06-12 04:47:48 UTC

Hi Doug,

Thanks so much for your thoughtful response. It definitely did help. I
don't want to take up too much more of your time at the moment.. I will
make some changes to incorporate the notes you made and I thank you again
for bringing up so many things to consider.. several of them I had
addressed, but a couple were certainly potential gotchas that I need to
review carefully.

But, the main big issues for now are twofold as I see it..

1. I fully understand that you don't want to add any further warts to the
immobile space management (especially given you would like to make it work
for 32-bit first) and while I have tried to fit the immobile conses in a
natural way into the existing fixed immobile space management.. there are
still some warts.. I don't think it adds any performance hit to the
existing cases (basically a few muxes in a few places on a page attribute
flag).. but it can certainly complicate your efforts in this area and may
not be anywhere close to what you would like to do once you have made the
other changes you want to make.. especially considering point #2..

2. As you said, our (the subset of the ACL2 community) need to allocate a
LOT (as in potentially GBs) of immobile conses may not fit with the current
usage model of immobile space and immobile space location constraints and
management. It may just need to be something different (and perhaps it
really should be something different).

So, I think for now, I'm gonna try to implement something which is viable
for our needs and then we can test it and refine it -- and I think I will
try to make some new "space" between IMMOBILE and DYNAMIC which is
specifically designed for immobile conses). If we get something reasonable
and stable, then we may put together a review request for the SBCL
development group and it can remain a patch for select ACL2 users to apply
to their build for the purposes of using SBCL in this mode until something
can be added to an SBCL release.

In any case, thanks again for your feedback and if you get to a point where
you might work on immobile conses, please let David Rager and I know and we
would really like to resync on the topic.

Cheers,
-Rob

Hi,
This all sounds plausible but somewhat scary. I had planned to do a
different thing for immobile conses.
My overall feeling is that your use of immobile space in its current
implementation runs contrary to the intent.
Immobile objects were supposed to be infrequently allocated for some
definition of "infrequent". The objects that go there now are all ones
which compile-file/load create many of: functions, symbols, layouts
(essentially the manifestation of a defstruct), and some other
system-internal things. This is "infrequent" enough that not having a
native Lisp allocator was a net win, not a net loss, in terms of
performance.
So I would be wary of having to call into C to allocate an immobile cons.
Nonetheless I could potentially take a look at what you've done, and I say
potentially in that it would not be anywhere near the top of my priority
list; review could be delayed indefinitely.
* I'm sad that there are already separate build-time features for
immobile-space, immobile-code, immobile-symbols, compact-instance-header.
I claim that we should remove some features, and just make them the same as
immobile-space, prior to adding yet another feature conditioned on
immobile-space. The problem with dependent features is that it's error
prone to verify that the build works in 2^n different ways.
* I was hoping to get marknsweep working on 32-bit before making any more
major changes to it for 64-bit, and this sounds fairly major to me. If we
can be confident that without the immobile-cons features there is no
performance penalty, that would be a plus, and ease the burden of review.

Post by Rob Sumners
2. Currently, a cell in a immobile-obj page is marked to be "free" if
cell[0]
is a fixnum. Assuming no added header to the cons cells in the immobile-cons
page, then cell[0] is the car of the cons and certainly could be a
fixnum.. so,
for immobile-cons pages, I used an other-immediate tag which basically
didn't
satisfy is_cons_half and then embedded the offset to the next freelist entry
with a different shift.

The purpose of the fixnum was to ensure that the unused word pair looks
like a cons, and that any number of following word pairs do as well, up to
the first non-fixnum word on the page signifying the start of the next
object.
Does your change let code that needs to step through the space work
properly? Does sizetab[] return the right thing for a header that marks a
free cons? Does map-allocated-objects distinguish real conses from
available space?
Also note that the representation of holes was specifically chosen so that
an immobile page which gets bzeroed() is exactly in the state it needs to
be to represent a linked list of objects of the size for that. I surmise
that there is code which depends on this representation.

Post by Rob Sumners
3. The other immobile-objs have headers, and the visited/generation info. is
stored in the header. With no header for a cons-cell in the
immobile-cons, I
decided that for immobile-cons pages only, I would allocate a 256-byte array
using just calloc with a pointer to this array stored in the
fixedobj_pages
entry.

You can't use calloc() unless you do this prior to the start of any Lisp
code.
See https://sourceforge.net/p/sbcl/sbcl/ci/85bdc4b4e9a24c6a7a9125f6903426
c0ca78950d which was a bugfix for logic that tried similarly to use one
extra word per page table entry for a per-page bitmap that was only
sometimes needed.

Post by Rob Sumners
I would
like to add build-time options to be able to move and size IMMOBILE space
(and
fixed immobile subspace) and move the start of DYNAMIC space.

This is yet another bandaid when the right fix is that spaces should work
wherever the OS kernel puts them.
Everybody is waiting for (without holding of breath) the ability to have
spaces be relocated as necessary, so I feel like it's strictly worse to add
a build-time flag that lets us muddy the waters further by not needing the
right fix. Also, dynamic space sizing on demand would be the holy grail of
space placement, and I feel those are tied together.
A local patch to src/compiler/x86-64/parms.lisp has served our needs in
the interim, despite being sensitive to changes in C compilers and/or libc.
I suspect that you would already have to provide ACL2 users with build
instructions and/or patches, right?
More importantly: It will probably never work to place the immobile space
above 4GB, because pointers have to be such that the high 32 bits are all
zero. Or maybe it will work if you disable compact-instance-header. It
might also not work above 2GB due to accidental sign-extension of bit 31
(i.e. "bugs"), though I can't say for sure, since have never tested it.
Again this is due to the intent of immobile space with regard to code
generation and gencgc optimizations; it was not striving to be a
general-purpose non-moving GC.
I hope this helps.
Doug

Post by Rob Sumners
Hi All,
My name is Rob Sumners, and like David Rager, I work a lot with ACL2 and am
interested in adding static conses (or immobile conses) to SBCL as David
described. David submitted a request on this a week or so ago and the
conversation can be seen -- I didn't know how to respond directly.. so sorry
for not knowing how to respond to that conversation and potentially
creating a
new one.
I've looked through SBCL code and added what I think should be a workable
solution, but I wanted to go over the changes to see if they made sense
and if
I am missing something.
I am running tests now and will for a while and have put all of these
changes
behind a build-time feature called "immobile-cons" which itself is only
relevant if one has the immobile-space feature enabled of course.
---------------------------------------------------------
---------------------------------------------------------
lispobj alloc_immobile_cons(lispobj car, lispobj cdr)
{
struct cons* c = (struct cons*)
alloc_immobile_obj(MAKE_ATTR(CEILING(CONS_SIZE,2), // spacing
CEILING(CONS_SIZE,2), // size
1), // is a cons page
car
&immobile_cons_page_hint);
// we already set this in the compare_and_swap of alloc_immobile_obj to
// s->car = car;
s->cdr = cdr;
return make_lispobj(s, LIST_POINTER_LOWTAG);
}
The setting of "1" for the "flags" of the attributes of the page is
because I
needed to tag which pages were "immobile_cons" pages vs. other immobile
object
pages. The reason is that for immobile-cons-pages, we need to change how a
couple of things are handled (both of which are predicated on having conses
(16-bytes on 64-bit platforms) laid out sequentially in the pages with no
extra
space inserted for headers).
2. Currently, a cell in a immobile-obj page is marked to be "free" if
cell[0]
is a fixnum. Assuming no added header to the cons cells in the immobile-cons
page, then cell[0] is the car of the cons and certainly could be a
fixnum.. so,
for immobile-cons pages, I used an other-immediate tag which basically
didn't
satisfy is_cons_half and then embedded the offset to the next freelist entry
with a different shift.
3. The other immobile-objs have headers, and the visited/generation info. is
stored in the header. With no header for a cons-cell in the
immobile-cons, I
decided that for immobile-cons pages only, I would allocate a 256-byte array
using just calloc with a pointer to this array stored in the
fixedobj_pages
entry. This does add a pointer to the fixedobj page structure (taking it
from
12 bytes to 16 or 20 bytes and I realize this may not be desirable). This
is a
little unfortunate but I don't know where I could stuff the
visited/generation
info. in the cons-cells. Since it seems that the current generations
(0-7) and
a visited bit could be stored in a nibble, it might be possible to reduce
this
array in half, but since the generation_index_t type is "signed char" and
there
are comments about possibly supporting more generations, then I would
prefer to
stay consistent with the current code.
----------------------------------------------------------
----------------------------------------------------------
Because of how we use ACL2, we need a lot of memory.. a disgusting
amount. And
this will transfer to the new immobile-cons pages as well. So, currently,
the
IMMOBILE space on linux/x86-64 is allocated to be 128MBs with only 24MB for
fixed immobile. So, we need these to be much bigger (many GBs).. so I would
like to add build-time options to be able to move and size IMMOBILE space
(and
fixed immobile subspace) and move the start of DYNAMIC space. This would be
something that members of the ACL2 community would be informed of .. i.e. if
you plan to use certain features of ACL2 that would likely exceed the
default
memory allocations in SBCL, then you need to rebuild SBCL with these
options.. (and obviously, if the mmap allocations failed (I'm talking
linux/x86-64 more than likely here).. then we can provide help in trying to
relocate the spaces in order to work).
I know that IMMOBILE SPACE must be lower in memory than DYNAMIC SPACE (and
IMMOBILE FIXED is below IMMOBILE VARY) but other than those constraints
being
upheld and aligning the start of these spaces on proper boundaries, are
there
any other limitations or constraints that we should take into account?
I believe it is safe to assume x86-64 for certain and probably Linux
(although
maybe BSD).
---------------------------------------------
---------------------------------------------
There are a lot of issues that I will go over with the ACL2 folks, but I
don't
think are relevant for the SBCL folks..
thanks so much for your time and attention,
-Rob
------------------------------------------------------------
------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
_______________________________________________
Sbcl-devel mailing list
https://lists.sourceforge.net/lists/listinfo/sbcl-devel