Re: [Sbcl-devel] static (or immobile) conses

[Douglas K. <do...@go...>]

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.

That said, I have a couple of technical concerns:
* 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.

Now to respond as best I can to your design notes:

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


> 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/85bdc4b4e9a24c6a7a9125f6903426c0ca78950d
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.


> 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

On Sun, Jun 11, 2017 at 12:03 PM, Rob Sumners <rob...@gm...> wrote:

> 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.
>
> ---------------------------------------------------------
> A. Adding support for allocating immobile-conses to SBCL:
> ---------------------------------------------------------
>
> This is primarily changes to marknsweepgc.c as follows:
>
> 1. add alloc_immobile_cons:
>
> 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
> set the "header":
>   // 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.
>
> ----------------------------------------------------------
> B. The need to move and resize IMMOBILE and DYNAMIC space:
> ----------------------------------------------------------
>
> 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).
>
> ---------------------------------------------
> C. Implementing the ACL2 interface functions:
> ---------------------------------------------
>
> 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
> Sbc...@li...
> https://lists.sourceforge.net/lists/listinfo/sbcl-devel
>
>