11:10 a.m.
I had trouble understanding the alignment code, especially
align_table. Ideas:
Use ALIGNOF maybe?
The maximum alignment required should be perhaps (from opaque.h)
typedef union
{
struct { Lisp_Object obj; } obj;
struct { void *p; } p;
struct { double d; } d;
} max_align_t;
We could move max_align_t to lisp.h, and have
size_t max_alignment = ALIGNOF (max_align_t);
Wouldn't we get a tremendous performance boost by having the
lrecord_implementations_table indices be constant? We would lose a
level of indirection on every FOOP, because it would not have to
examine lrecord_implementations_table itself.
11:42 a.m.
Martin Buchholz writes:
Wouldn't we get a tremendous performance boost by having the
lrecord_implementations_table indices be constant? We would lose a
level of indirection on every FOOP, because it would not have to
examine lrecord_implementations_table itself.
Yes, this is a great idea. I think the reason the changeover to
minimal tagbits was a wash speedwise was because of increased
time spent type checking. We got rid of the pointer masking and
unmasking, but almost all the type checks got more expensive.
9:27 p.m.
On Wed, Feb 16, 2000 at 03:42:25AM -0800, Kyle Jones wrote:
Martin Buchholz writes:
> Wouldn't we get a tremendous performance boost by having the
> lrecord_implementations_table indices be constant? We would lose a
> level of indirection on every FOOP, because it would not have to
> examine lrecord_implementations_table itself.
Yes, this is a great idea. I think the reason the changeover to
minimal tagbits was a wash speedwise was because of increased
time spent type checking. We got rid of the pointer masking and
unmasking, but almost all the type checks got more expensive.
We need a game plan.
One one hand, we have the possibility of implementing the paginated
allocator. Type testing will become "*(blah **)(ptr & MASK) ==
constant)"[1]. This is mostly equivalent (one instruction difference)
to the "*(byte *)(ptr) == constant" you'd like to have. A good thing
with such a paginated allocator is that fixed block types will go, and
lrecord-lists will probably become useless. Bad thing is that it will
be a huge change in the portable dumper. Also, I'm not sure how much
the overhead will be, but I'm afraid it may overweight the space gain
we would have. Also, we will have to kill all the flags.
On the other hand, we can decide not to implement the allocator. I
can hack a way to get the data sharing back which will cost only
~40Kbytes of memory at run time without, I hope, changing the speed of
marking/unmarking in a noticeable manner. We can also add a small
program to lib-src that will look at all the
DEFINE_*_LRECORD_*_IMPLEMENTATION and generate a big enum in a file
out of them.
Also, what would you think of:
- killing basic_p and free
- splitting the symbol_value_magic type in multiple types, separating
in particular forwarders to C from the rest
OG.
[1] MASK=~((1<<PAGESIZE)-1), blah = lrecord_implementation *, constant =
&lrecord_<type>
5:21 a.m.
>>>> "OG" == Olivier Galibert
<galibert(a)pobox.com> writes:
OG> On Wed, Feb 16, 2000 at 03:42:25AM -0800, Kyle Jones wrote:
> Martin Buchholz writes:
> > Wouldn't we get a tremendous performance boost by having the
> > lrecord_implementations_table indices be constant? We would lose a
> > level of indirection on every FOOP, because it would not have to
> > examine lrecord_implementations_table itself.
>
> Yes, this is a great idea. I think the reason the changeover to
> minimal tagbits was a wash speedwise was because of increased
> time spent type checking. We got rid of the pointer masking and
> unmasking, but almost all the type checks got more expensive.
OG> We need a game plan.
OG> One one hand, we have the possibility of implementing the paginated
OG> allocator. Type testing will become "*(blah **)(ptr & MASK) ==
OG> constant)"[1]. This is mostly equivalent (one instruction difference)
OG> to the "*(byte *)(ptr) == constant" you'd like to have. A good
thing
OG> with such a paginated allocator is that fixed block types will go, and
OG> lrecord-lists will probably become useless. Bad thing is that it will
OG> be a huge change in the portable dumper. Also, I'm not sure how much
OG> the overhead will be, but I'm afraid it may overweight the space gain
OG> we would have. Also, we will have to kill all the flags.
No, the flags can also be placed at the beginning of the block.
We make a, say, 8k aligned block. At the beginning of the block, we
put a lisp object type identifier. Then we can have an array of
per-object flags. We can decide how many flags per object, but 8 is
probably good. We could choose to have the mark bits for all objects
together in a special mark-bit area, or all the per-object flags could
be put together into one byte. Since the mark-bits are only used at a
special time, it is more cache-friendly to isolate the mark-bits in
their own ghetto.
OG> On the other hand, we can decide not to implement the allocator. I
OG> can hack a way to get the data sharing back which will cost only
OG> ~40Kbytes of memory at run time without, I hope, changing the speed of
OG> marking/unmarking in a noticeable manner. We can also add a small
OG> program to lib-src that will look at all the
OG> DEFINE_*_LRECORD_*_IMPLEMENTATION and generate a big enum in a file
OG> out of them.
We should continue to think about the best way to do this, _BUT_ we
should delay making any such major changes until after 21.2 is
released. Let's try to get our current xemacs releasable. It's been
too long since the last release. I suggest we do the constant type
optimization for 21.2 since it's quite safe and relatively easy to
implement, and delay rewriting the allocation system yet again till
later.
OG> Also, what would you think of:
OG> - killing basic_p and free
I don't really understand the `free' bit yet.
`basic_p' certainly is confusing. I imagine the `c' in lcrecord
stands for `chained', so we should have `chained_p' instead of
`basic_p'.
OG> - splitting the symbol_value_magic type in multiple types, separating
OG> in particular forwarders to C from the rest
Be careful here. The key piece of code you want to be fast is this in
bytecode.c:
do_varref:
{
Lisp_Object symbol = constants_data[n];
Lisp_Object value = XSYMBOL (symbol)->value;
if (SYMBOL_VALUE_MAGIC_P (value))
value = Fsymbol_value (symbol);
PUSH (value);
break;
}
Make sure that SYMBOL_VALUE_MAGIC_P is as fast as possible, which
might be hard if magic values are multiple types. As I said before, I
think setting a bit in the symbol object itself is the way to go here
(and demoting magic values from Lisp_Object status). Allocated memory
that is never visible to the user, and always logically part of some
other object, should not be subject to gc. You want to keep the
objects examined by gc as small as possible. ... but after 21.2....
OG> [1] MASK=~((1<<PAGESIZE)-1), blah = lrecord_implementation *, constant =
&lrecord_<type>
7:11 p.m.
On Wed, Feb 16, 2000 at 09:21:18PM -0800, Martin Buchholz wrote:
I don't really understand the `free' bit yet.
The free bit is here for lrecord-lists sake. The idea is that some of
the of the lcrecords in the global all_lcrecord list are in practice
free and on a lrecord-list free list. The lrecord-lists have no quick
way to remove these records from the list when free_managed_lcrecord
is called, so they don't.
Actually, since the marker for the lcrecord-lists marks
(non-recursively) all the elements of its free list, the flag isn't
useful at sweep time. The only time when it is useful is when calling
disksave_object_finalization_1. And frankly, I'm not sure we really
need this finalization.
`basic_p' certainly is confusing. I imagine the `c' in
lcrecord
stands for `chained', so we should have `chained_p' instead of
`basic_p'.
Nothing actually _uses_ basic_p.
Make sure that SYMBOL_VALUE_MAGIC_P is as fast as possible, which
might be hard if magic values are multiple types. As I said before, I
think setting a bit in the symbol object itself is the way to go here
(and demoting magic values from Lisp_Object status). Allocated memory
that is never visible to the user, and always logically part of some
other object, should not be subject to gc. You want to keep the
objects examined by gc as small as possible. ... but after 21.2....
Beware, you're giving me ideas ;-)
OG.
11:28 p.m.
>>>> "OG" == Olivier Galibert
<galibert(a)pobox.com> writes:
OG> On Wed, Feb 16, 2000 at 09:21:18PM -0800, Martin Buchholz wrote:
> I don't really understand the `free' bit yet.
OG> The free bit is here for lrecord-lists sake. The idea is that some of
OG> the of the lcrecords in the global all_lcrecord list are in practice
OG> free and on a lrecord-list free list. The lrecord-lists have no quick
OG> way to remove these records from the list when free_managed_lcrecord
OG> is called, so they don't.
If a particular lcrecord isn't to be collected using all_lcrecords, it
shouldn't be put on that list in the first place, i.e. we shouldn't
use alloc_lcrecord().
OG> Actually, since the marker for the lcrecord-lists marks
OG> (non-recursively) all the elements of its free list, the flag isn't
OG> useful at sweep time. The only time when it is useful is when calling
OG> disksave_object_finalization_1. And frankly, I'm not sure we really
OG> need this finalization.
> Make sure that SYMBOL_VALUE_MAGIC_P is as fast as possible,
which
> might be hard if magic values are multiple types. As I said before, I
> think setting a bit in the symbol object itself is the way to go here
> (and demoting magic values from Lisp_Object status). Allocated memory
> that is never visible to the user, and always logically part of some
> other object, should not be subject to gc. You want to keep the
> objects examined by gc as small as possible. ... but after 21.2....
OG> Beware, you're giving me ideas ;-)
After the next release...
(of course, I keep breaking that rule myself...)
11:31 p.m.
On Thu, Feb 17, 2000 at 03:28:13PM -0800, Martin Buchholz wrote:
>>>>> "OG" == Olivier Galibert
<galibert(a)pobox.com> writes:
OG> On Wed, Feb 16, 2000 at 09:21:18PM -0800, Martin Buchholz wrote:
>> I don't really understand the `free' bit yet.
OG> The free bit is here for lrecord-lists sake. The idea is that some of
OG> the of the lcrecords in the global all_lcrecord list are in practice
OG> free and on a lrecord-list free list. The lrecord-lists have no quick
OG> way to remove these records from the list when free_managed_lcrecord
OG> is called, so they don't.
If a particular lcrecord isn't to be collected using all_lcrecords, it
shouldn't be put on that list in the first place, i.e. we shouldn't
use alloc_lcrecord().
That's extremely reasonable, you know ?
OG, jumping in the code.
7:16 p.m.
On Wed, Feb 16, 2000 at 03:10:26AM -0800, Martin Buchholz wrote:
I had trouble understanding the alignment code, especially
align_table. Ideas:
Use ALIGNOF maybe?
#ifndef ALIGNOF
# if defined (__GNUC__) && (__GNUC__ >= 2)
# define ALIGNOF(x) __alignof__ (x)
# else
# define ALIGNOF(x) sizeof (x)
# endif
#endif
Nope, won't do. I don't want to align conses on a 12 bytes boundary
when 4 bytes is enough.
The maximum alignment required should be perhaps (from opaque.h)
typedef union
{
struct { Lisp_Object obj; } obj;
struct { void *p; } p;
struct { double d; } d;
} max_align_t;
We could move max_align_t to lisp.h, and have
size_t max_alignment = ALIGNOF (max_align_t);
Maybe. I know 256 as a max is overkill, but it doesn't cost us
anything, since we enumerate objects in reverse alignment order and
we're only using powers of two.
Yes, I know, that's perverted code, but it does a perverted thing.
OG.
11:40 p.m.
>>>> "OG" == Olivier Galibert
<galibert(a)pobox.com> writes:
OG> On Wed, Feb 16, 2000 at 03:10:26AM -0800, Martin Buchholz wrote:
> I had trouble understanding the alignment code, especially
> align_table. Ideas:
>
> Use ALIGNOF maybe?
OG> #ifndef ALIGNOF
OG> # if defined (__GNUC__) && (__GNUC__ >= 2)
OG> # define ALIGNOF(x) __alignof__ (x)
OG> # else
OG> # define ALIGNOF(x) sizeof (x)
OG> # endif
OG> #endif
OG> Nope, won't do. I don't want to align conses on a 12 bytes boundary
OG> when 4 bytes is enough.
In practice, all objects to be dumped can use ALIGNOF this:
union
{
struct { Lisp_Object obj; } obj;
struct { void *p; } p;
};
unless they contain a double, in which case ALIGNOF this:
union
{
struct { Lisp_Object obj; } obj;
struct { void *p; } p;
struct { double d; } d;
};
will do.
> The maximum alignment required should be perhaps (from opaque.h)
>
> typedef union
> {
> struct { Lisp_Object obj; } obj;
> struct { void *p; } p;
> struct { double d; } d;
> } max_align_t;
>
>
> We could move max_align_t to lisp.h, and have
>
> size_t max_alignment = ALIGNOF (max_align_t);
OG> Maybe. I know 256 as a max is overkill, but it doesn't cost us
OG> anything, since we enumerate objects in reverse alignment order and
OG> we're only using powers of two.
OG> Yes, I know, that's perverted code, but it does a perverted thing.
The only thing I know it costs us currently is the head-scratching I
do whenever I look at that code.
If it doesn't cost us anything to use oversized alignments, why not
just always use ALIGNOF (max_align_t) to align everything we dump?
Are we likely to actually dump anything that is going to have 1-byte
alignment? We might be able to do this for some opaque's, but since
the dumping code doesn't know how the opaques will be used, we can't.
And opaques have memory returned from malloc(), so it will also be
max_align_t-aligned.
Martin
12:20 a.m.
On Thu, Feb 17, 2000 at 03:40:59PM -0800, Martin Buchholz wrote:
If it doesn't cost us anything to use oversized alignments, why
not
just always use ALIGNOF (max_align_t) to align everything we dump?
Then you'll lose space.
All real-world alignments are powers of two. As a consequence, most
of the time[1], you can know the alignment requirement of a bunch of
data by looking at the biggest power of two which divides its size.
That's what the align_table does.
Now, let's take a cons. 12 bytes. So the alignment is 4. If you put
a cons at a 4-bytes aligned address, the next address is still 4-bytes
aligned. That means you can pack conses next to each other without
losing space. In fact, you can pack anything 4-bytes aligned without
losing space.
The last thing the see is that a (say) 8-bytes alignement is also a 4,
2, and 1-byte one.
So if you dump the data biggest alignement first, without putting any
padding between elements, you actually are respecting alignements
without losing space. You also don't need to make any assumptions on
the maximum possible alignment (expect that I put a 256-bytes max
alignement assumption for simplicity).
Are we likely to actually dump anything that is going to have 1-byte
alignment?
Strings' data.
We might be able to do this for some opaque's, but since
the dumping code doesn't know how the opaques will be used, we can't.
And opaques have memory returned from malloc(), so it will also be
max_align_t-aligned.
Opaques are lrecords, all lrecords have an hardcoded 4-byte minimal
alignment (because of opaques, actually :-). Actually, that should be
8 on computers with 64 bits pointers, now that I think of it.
OG.
[1] Opaques are the only exception in our case. I hardcoded a minimal
4 bytes alignment for all lrecords because of them.
1:14 a.m.
>>>> "OG" == Olivier Galibert
<galibert(a)pobox.com> writes:
OG> On Thu, Feb 17, 2000 at 03:40:59PM -0800, Martin Buchholz wrote:
> If it doesn't cost us anything to use oversized alignments,
why not
> just always use ALIGNOF (max_align_t) to align everything we dump?
OG> Then you'll lose space.
OG> All real-world alignments are powers of two. As a consequence, most
OG> of the time[1], you can know the alignment requirement of a bunch of
OG> data by looking at the biggest power of two which divides its size.
OG> That's what the align_table does.
OG> Now, let's take a cons. 12 bytes. So the alignment is 4. If you put
OG> a cons at a 4-bytes aligned address, the next address is still 4-bytes
OG> aligned. That means you can pack conses next to each other without
OG> losing space. In fact, you can pack anything 4-bytes aligned without
OG> losing space.
Oh. Finalement je compris. Light bulb.
Hmmmm
The packing works if the size of our C structures is the same as the C
sizeof (structtype), but not in general for flexible arrays that
have arbitrary data hanging off the end.
For example,
struct foo
{
double d;
size_t obj_count;
Lisp_Object obj[1];
}
If there are a variable number of obj's, and the size method returns
offsetof (foo, obj[obj_count]), then we cannot portably pack foo's
using the size method.
If you want to save the space, then you must either do this
non-portably, or perhaps add alignment information to the
lrecord_description, or add an `align' method to struct lrecord_description.
Most lrecords would use ALIGNOF (union { Lisp_Object obj; void *p; }).
But some, like Lips_Opaque, would use ALIGNOF (max_align_t)
I think we should try to get this right, else we'll again have weird
platform-dependent crashes or platform-dependent inefficiency on
unaligned accesses, which might be very difficult to diagnose if the
maintainers never get access to such a system.
OG> The last thing the see is that a (say) 8-bytes alignement is also a 4,
OG> 2, and 1-byte one.
OG> So if you dump the data biggest alignement first, without putting any
OG> padding between elements, you actually are respecting alignements
OG> without losing space. You also don't need to make any assumptions on
OG> the maximum possible alignment (expect that I put a 256-bytes max
OG> alignement assumption for simplicity).
> Are we likely to actually dump anything that is going to have
1-byte
> alignment?
OG> Strings' data.
But strings data is either in a string_chars_block (it would be nice
to just copy all the string_chars_blocks into the dumped data,
preferably after compacting), or malloc()ed for big strings, in which
case the extra padding space will be insignificant.
OG> Opaques are lrecords, all lrecords have an hardcoded 4-byte minimal
OG> alignment (because of opaques, actually :-). Actually, that should be
OG> 8 on computers with 64 bits pointers, now that I think of it.
I was wondering about that hardcoded 4. Use ALIGNOF (max_align_t) instead?
OG> [1] Opaques are the only exception in our case. I hardcoded a minimal
OG> 4 bytes alignment for all lrecords because of them.
Martin
1:27 a.m.
On Thu, Feb 17, 2000 at 05:14:24PM -0800, Martin Buchholz wrote:
If there are a variable number of obj's, and the size method
returns
offsetof (foo, obj[obj_count]), then we cannot portably pack foo's
using the size method.
True. OTOH, it's in the "it doesn't happen... yet" list.
If you want to save the space, then you must either do this
non-portably, or perhaps add alignment information to the
lrecord_description, or add an `align' method to struct lrecord_description.
A special XD_ALIGN tag? Hmmm, that's perverted. I like it. Except
that none of our structures would use it for now, which makes it far
less interesting...
But some, like Lips_Opaque, would use ALIGNOF (max_align_t)
OTOH we could use it for opaques. Good thinking Martin. I'll do it.
But strings data is either in a string_chars_block (it would be nice
to just copy all the string_chars_blocks into the dumped data,
preferably after compacting), or malloc()ed for big strings, in which
case the extra padding space will be insignificant.
I think it's nicer to have all the strings concatenated like we have
now (think docstrings, it'd love to have the DOC file in preloaded and
ending in the .dmp file) and going back to using string_char_blocks
only when we change the size of the string. I think that's the more
efficient way, both spacewise and sharing-wise.
I was wondering about that hardcoded 4. Use ALIGNOF (max_align_t)
instead?
Yup.
OG.
8871
days inactive
8873
days old
11 comments
3 participants
participants (3)
-
Kyle Jones -
Martin Buchholz -
Olivier Galibert