[BDW-GC] Static allocation of subrs

[BDW-GC] Static allocation of subrs

[Ludovic Courtès]

Hello!

The `bdw-gc-static-alloc' branch now contains an implementation of
statically allocated subrs.  This was done in 2 steps:

  1. Using double-cells instead of single-cells for subrs [0].  The
     patch is quite nice in that it simplifies `procs.[ch]'.  This
     change is needed so that subrs don't contain a subr entry number
     allocated at run-time (the subr entry number is the index of the
     subr in the subr table).

     It does not introduce any storage overhead: previously, a subr
     consumed one cell and sizeof (scm_t_subr_entry), i.e., 2 + 4 = 6
     words; with the patch, a subr consumes one double cell and 2 words
     for `meta_info', i.e., 4 + 2 = 6.

     The change leaves the 24 MSBs of the first word of the cell unused.
     We might want to do something smart with all these bits.

     For these reasons, we may want to merge this patch in `master' as
     well.

  2. The second step does the actual work [1].  Currently, it only
     deals with subrs, i.e., primitive procedures with "relatively few"
     arguments (see `create_gsubr ()').

     To distinguish subrs (few arguments) from gsubrs (unrestricted
     arity, see `default:' in `create_gsubr ()'), a Dirty Hack(tm) was
     needed.  The hack is that `SCM_DEFINE' is an alias for a new macro
     `SCM_DEFINE_SUBR_reqX_optY_rstZ', where X, Y and Z are the number
     of required, optional and rest arguments.  If X, Y and Z are such
     that a raw subr can be used, then the macro is an alias for
     `SCM_DEFINE_SUBR', which does the actual static allocation;
     otherwise, it's an alias for `SCM_DEFINE_GSUBR', which is the same
     as `SCM_DEFINE' in `master'.

     The dirtiest part of the hack is the generation of "snarf-gsubr.h"
     which contains definitions of `SCM_DEFINE_SUBR_reqX_optY_rstZ' for
     a "reasonable" number of combinations of X, Y and Z (C++ template
     specialization would solve this problem much more elegantly...).

The good news is that it actually works.  :-)

I ran `gcbench.scm' with both BDW-GC branches and didn't observe any
significant difference.  The benefits are that (i) initialization should
be slightly faster, and (ii) running several instances of guile should
consume less memory since statically allocated data can be mapped
read-only by the loader and, consequently, the underlying physical
memory can be shared across instances.

Thanks,
Ludo'.

[0] http://git.savannah.gnu.org/gitweb/?p=guile.git;a=commitdiff;h=2ee5aa25dbd679b175707762f5961585027e1397
[1] http://git.savannah.gnu.org/gitweb/?p=guile.git;a=commitdiff;h=46f9baf49a8ea4461e8494c75a88b87d0f5c5195

Re: [BDW-GC] Static allocation of subrs

[Ludovic Courtès]

Hello Ken,

[Cc: guile-devel.]

Ken Raeburn <raeburn@raeburn.org> writes:

> On Jan 31, 2009, at 16:43, Ludovic Courtès wrote:
>> I ran `gcbench.scm' with both BDW-GC branches and didn't observe any
>> significant difference.  The benefits are that (i) initialization
>> should
>> be slightly faster, and (ii) running several instances of guile should
>> consume less memory since statically allocated data can be mapped
>> read-only by the loader and, consequently, the underlying physical
>> memory can be shared across instances.
>
> I've only looked at some of the sources, not built it (various missing
> dependencies, and I don't have much time to play with guile anyways),
> but I'm not sure this is the case.  For the main program, perhaps, but
> the library is generally built as a shared library, which won't have a
> fixed address; anything with addresses in it needs to be adjusted by
> the dynamic loader.

Ah ah, you're right: item (ii) is indeed wrong.  This statically
allocated data needs to be relocated, so it ends up in the
`.data.rel.ro' section, which is initially mapped read-write by the
loader and modified according to the relocations (linking with GNU ld's
"-z relro" forces this memory region to be mprotect()d read-only as soon
as relocations have been processed), so there's no sharing among
multiple guile instances.

(I realized this while rereading Drepper's `dsohowto.pdf'.)

Thanks,
Ludo'.

Re: [BDW-GC] Static allocation of subrs

[Neil Jerram]

ludo@gnu.org (Ludovic Courtès) writes:

> Hello!
>
> The `bdw-gc-static-alloc' branch now contains an implementation of
> statically allocated subrs.  This was done in 2 steps:
>
>   1. Using double-cells instead of single-cells for subrs [0].  The
>      patch is quite nice in that it simplifies `procs.[ch]'.  This
>      change is needed so that subrs don't contain a subr entry number
>      allocated at run-time (the subr entry number is the index of the
>      subr in the subr table).

I agree that this is a nice improvement.

>      It does not introduce any storage overhead: previously, a subr
>      consumed one cell and sizeof (scm_t_subr_entry), i.e., 2 + 4 = 6
>      words; with the patch, a subr consumes one double cell and 2 words
>      for `meta_info', i.e., 4 + 2 = 6.
>
>      The change leaves the 24 MSBs of the first word of the cell unused.
>      We might want to do something smart with all these bits.
>
>      For these reasons, we may want to merge this patch in `master' as
>      well.

Yes, I think so.

>   2. The second step does the actual work [1].  Currently, it only
>      deals with subrs, i.e., primitive procedures with "relatively few"
>      arguments (see `create_gsubr ()').

Presumably that is in practice almost all of the primitives, though?

>      To distinguish subrs (few arguments) from gsubrs (unrestricted
>      arity, see `default:' in `create_gsubr ()'), a Dirty Hack(tm) was
>      needed.  The hack is that `SCM_DEFINE' is an alias for a new macro
>      `SCM_DEFINE_SUBR_reqX_optY_rstZ', where X, Y and Z are the number
>      of required, optional and rest arguments.  If X, Y and Z are such
>      that a raw subr can be used, then the macro is an alias for
>      `SCM_DEFINE_SUBR', which does the actual static allocation;
>      otherwise, it's an alias for `SCM_DEFINE_GSUBR', which is the same
>      as `SCM_DEFINE' in `master'.

Not so bad, IMO.

>      The dirtiest part of the hack is the generation of "snarf-gsubr.h"
>      which contains definitions of `SCM_DEFINE_SUBR_reqX_optY_rstZ' for
>      a "reasonable" number of combinations of X, Y and Z (C++ template
>      specialization would solve this problem much more elegantly...).

This part is quite dirty, as you say.  I'm not sure what's the
advantage of the generation at make time.  Wouldn't it be simpler, and
have the same function, just to hardcode all these definitions
directly in snarf.h?

> [0] http://git.savannah.gnu.org/gitweb/?p=guile.git;a=commitdiff;h=2ee5aa25dbd679b175707762f5961585027e1397

Should probably remove the comments about how many subrs there are,
since it's no longer relevant.

I see there's no NEWS in the commit; is that because there's no impact
on the API?  Even if so, I imagine it might merit a line in the 2.0
release notes.  If you agree, I'd encourage you to write the NEWS now,
rather than adding it later.

+  meta_info = scm_gc_malloc (2 * sizeof (* meta_info),
+                            "subr meta-info");

I found the space between "*" and "meta_info" confusing for a few
seconds, so would have a preference for "*meta_info".

> [1] http://git.savannah.gnu.org/gitweb/?p=guile.git;a=commitdiff;h=46f9baf49a8ea4461e8494c75a88b87d0f5c5195

Why does the macro code sometimes use scm_i_paste, and sometimes ##
directly?

Finally SCM_SUBR_ARITY_TO_TYPE... The implementation feels a bit
messy, but I don't have any alternative to suggest, so I guess that's
OK.  But what about the fact that it's added to the libguile API?  I
realize that this is necessary to some extent so that snarf.h can be
used by application code - but can we somehow restrict
SCM_SUBR_ARITY_TO_TYPE to being used in that context, so that it
doesn't become on ongoing constraint for us?

Regards,
        Neil

Re: [BDW-GC] Static allocation of subrs

[Ludovic Courtès]

Hi Neil,

Note: I reply to messages in order of least difficulty.  ;-)

Neil Jerram <neil@ossau.uklinux.net> writes:

> ludo@gnu.org (Ludovic Courtès) writes:

>>      For these reasons, we may want to merge this patch in `master' as
>>      well.
>
> Yes, I think so.

Noted, will do.

>>   2. The second step does the actual work [1].  Currently, it only
>>      deals with subrs, i.e., primitive procedures with "relatively few"
>>      arguments (see `create_gsubr ()').
>
> Presumably that is in practice almost all of the primitives, though?

That's 200 gsubrs, vs. 873 "simple" subrs.

>>      To distinguish subrs (few arguments) from gsubrs (unrestricted
>>      arity, see `default:' in `create_gsubr ()'), a Dirty Hack(tm) was
>>      needed.  The hack is that `SCM_DEFINE' is an alias for a new macro
>>      `SCM_DEFINE_SUBR_reqX_optY_rstZ', where X, Y and Z are the number
>>      of required, optional and rest arguments.  If X, Y and Z are such
>>      that a raw subr can be used, then the macro is an alias for
>>      `SCM_DEFINE_SUBR', which does the actual static allocation;
>>      otherwise, it's an alias for `SCM_DEFINE_GSUBR', which is the same
>>      as `SCM_DEFINE' in `master'.
>
> Not so bad, IMO.

It breaks cases like primitive procedures with more than 16 arguments
(because I arbitrarily decided that `snarf-gsubr.h' would contain
definitions up to 16 req/opt args), and situations like:

  SCM_DEFINE (scm_foo, "foo", 0001, 0002, 0003, ...)

This is probably acceptable in practice.

>>      The dirtiest part of the hack is the generation of "snarf-gsubr.h"
>>      which contains definitions of `SCM_DEFINE_SUBR_reqX_optY_rstZ' for
>>      a "reasonable" number of combinations of X, Y and Z (C++ template
>>      specialization would solve this problem much more elegantly...).
>
> This part is quite dirty, as you say.  I'm not sure what's the
> advantage of the generation at make time.  Wouldn't it be simpler, and
> have the same function, just to hardcode all these definitions
> directly in snarf.h?

Given the size of `snarf-gsubr.h' (there are 16 * 16 * 2 = 512
combinations), I'd rather keep it separated.  The makefile rule is an
efficient way to compress it.  ;-)

>> [0] http://git.savannah.gnu.org/gitweb/?p=guile.git;a=commitdiff;h=2ee5aa25dbd679b175707762f5961585027e1397
>
> Should probably remove the comments about how many subrs there are,
> since it's no longer relevant.

Right.

> I see there's no NEWS in the commit; is that because there's no impact
> on the API?  Even if so, I imagine it might merit a line in the 2.0
> release notes.  If you agree, I'd encourage you to write the NEWS now,
> rather than adding it later.

Right.  It's just that I have not maintained any NEWS file for
BDW-GC-related changes, initially.

> +  meta_info = scm_gc_malloc (2 * sizeof (* meta_info),
> +                            "subr meta-info");
>
> I found the space between "*" and "meta_info" confusing for a few
> seconds, so would have a preference for "*meta_info".

Yes, I feel the same today (I probably felt differently that day).  :-)

>> [1] http://git.savannah.gnu.org/gitweb/?p=guile.git;a=commitdiff;h=46f9baf49a8ea4461e8494c75a88b87d0f5c5195
>
> Why does the macro code sometimes use scm_i_paste, and sometimes ##
> directly?

The `scm_i_paste ()' macro is needed so that macro-expansion of
definitions like those of `srfi-4.i.c' work as expected.  There are a
few cases where it isn't used (e.g., in `SCM_IMMUTABLE_DOUBLE_CELL ()'),
but I guess it didn't cause any problem because `scm_i_paste ()' was
properly used by callers.  We could unify that but `scm_i_paste ()' has
the drawback of having a long name.

> Finally SCM_SUBR_ARITY_TO_TYPE... The implementation feels a bit
> messy, but I don't have any alternative to suggest, so I guess that's
> OK.

The problem is that this information is shared among 3 places:
`SCM_SUBR_ARITY_TO_TYPE ()', `create_gsubr ()', and
`SCM_DEFINE_SUBR_reqX_optY_rstZ ()'.  Ideally, all 3 would be generated
from a single source.

Besides, I think we need to review the use of subr/gsubr tag in detail
to see whether we can make better use of them.

> But what about the fact that it's added to the libguile API?  I
> realize that this is necessary to some extent so that snarf.h can be
> used by application code - but can we somehow restrict
> SCM_SUBR_ARITY_TO_TYPE to being used in that context, so that it
> doesn't become on ongoing constraint for us?

I share your concern, but I have no idea of how to avoid it.  We could
add `_I_' in its name, perhaps.  Hopefully, it's too low-level for
anyone to try it.

Thanks,
Ludo'.

Re: [BDW-GC] Static allocation of subrs

[Neil Jerram]

ludo@gnu.org (Ludovic Courtès) writes:

>> Presumably that is in practice almost all of the primitives, though?
>
> That's 200 gsubrs, vs. 873 "simple" subrs.

Thanks, interesting.  That's more gsubrs than I expected.

>> Not so bad, IMO.
>
> It breaks cases like primitive procedures with more than 16 arguments
> (because I arbitrarily decided that `snarf-gsubr.h' would contain
> definitions up to 16 req/opt args), and situations like:
>
>   SCM_DEFINE (scm_foo, "foo", 0001, 0002, 0003, ...)
>
> This is probably acceptable in practice.

Agreed.  (In future maybe we might stop relying only on the C
preprocessor for snarfing.)

>> This part is quite dirty, as you say.  I'm not sure what's the
>> advantage of the generation at make time.  Wouldn't it be simpler, and
>> have the same function, just to hardcode all these definitions
>> directly in snarf.h?
>
> Given the size of `snarf-gsubr.h' (there are 16 * 16 * 2 = 512
> combinations), I'd rather keep it separated.  The makefile rule is an
> efficient way to compress it.  ;-)

OK.  In that case, can you add a comment in the Makefile.am to say
this?  Simply to avoid someone wondering in future if there is some
other reason why the code is auto-generated.

>> I see there's no NEWS in the commit; is that because there's no impact
>> on the API?  Even if so, I imagine it might merit a line in the 2.0
>> release notes.  If you agree, I'd encourage you to write the NEWS now,
>> rather than adding it later.
>
> Right.  It's just that I have not maintained any NEWS file for
> BDW-GC-related changes, initially.

I guess it's OK to add the NEWS later when this is merged; probably
your memory is better than mine!

>> Why does the macro code sometimes use scm_i_paste, and sometimes ##
>> directly?
>
> The `scm_i_paste ()' macro is needed so that macro-expansion of
> definitions like those of `srfi-4.i.c' work as expected.  There are a
> few cases where it isn't used (e.g., in `SCM_IMMUTABLE_DOUBLE_CELL ()'),
> but I guess it didn't cause any problem because `scm_i_paste ()' was
> properly used by callers.  We could unify that but `scm_i_paste ()' has
> the drawback of having a long name.

Ah, OK.  Thanks for explaining.

>> Finally SCM_SUBR_ARITY_TO_TYPE... The implementation feels a bit
>> messy, but I don't have any alternative to suggest, so I guess that's
>> OK.
>
> The problem is that this information is shared among 3 places:
> `SCM_SUBR_ARITY_TO_TYPE ()', `create_gsubr ()', and
> `SCM_DEFINE_SUBR_reqX_optY_rstZ ()'.  Ideally, all 3 would be generated
> from a single source.
>
> Besides, I think we need to review the use of subr/gsubr tag in detail
> to see whether we can make better use of them.

OK.  Nothing more needed straightaway, then.

>> But what about the fact that it's added to the libguile API?  I
>> realize that this is necessary to some extent so that snarf.h can be
>> used by application code - but can we somehow restrict
>> SCM_SUBR_ARITY_TO_TYPE to being used in that context, so that it
>> doesn't become on ongoing constraint for us?
>
> I share your concern, but I have no idea of how to avoid it.  We could
> add `_I_' in its name, perhaps.  Hopefully, it's too low-level for
> anyone to try it.

I don't have an idea either.  I think having _I_ would be good, though.

Regards,
      Neil

Re: [BDW-GC] Static allocation of subrs

[Ludovic Courtès]

Hi,

ludo@gnu.org (Ludovic Courtès) writes:

> Neil Jerram <neil@ossau.uklinux.net> writes:
>
>> ludo@gnu.org (Ludovic Courtès) writes:
>
>>>      For these reasons, we may want to merge this patch in `master' as
>>>      well.
>>
>> Yes, I think so.
>
> Noted, will do.

Done.  Note that the patch is slightly different in `master' than in
`bdw-gc-static-alloc' because there is/was still
`scm_free_subr_entry ()' and `scm_mark_subr_table ()' in the former.

http://git.savannah.gnu.org/gitweb/?p=guile.git;a=commit;h=ac51e74b9533cc3df8fe9656b97a6385a6e71b80

Will investigate the subr tags...

Thanks,
Ludo'.

Re: [BDW-GC] Static allocation of subrs

[Ludovic Courtès]

Hello!

Following the simplification of gsubrs and removal of cclos, I
implemented static allocation of gsubrs in `bdw-gc-static-alloc':

  http://git.savannah.gnu.org/gitweb/?p=guile.git;a=commitdiff;h=f0eb5ae6c173aed35965b0561897fda1d8ff0db1

This removes the nastiness with `snarf-gsubr.h' et al., which is good!

Thanks,
Ludo'.