Re: [PATCH] c++/modules: optimize tree flag streaming
On Sat, 13 Apr 2024, Iain Sandoe wrote:
> Hi Patrick,
>
> > On 10 Apr 2024, at 17:33, Jason Merrill wrote:
> >
> > On 4/10/24 11:26, Patrick Palka wrote:
> >> On Wed, 10 Apr 2024, Patrick Palka wrote:
> >>>
> >>> On Tue, 9 Apr 2024, Jason Merrill wrote:
> >>>
> On 2/16/24 10:06, Patrick Palka wrote:
> > On Thu, 15 Feb 2024, Patrick Palka wrote:
> >
>
>
>
> > Let's keep documenting the inheritance relationship here, i.e.
> >
> > bytes_in : data
> >
> >> @@ -694,13 +656,132 @@ protected:
> >>/* Instrumentation. */
> >>static unsigned spans[4];
> >>static unsigned lengths[4];
> >> - static int is_set;
> >> + friend struct bits_out;
> >
> > It might be a little more elegant for bits_in/out to be nested classes of
> > bytes_in/out, returned from member functions, rather than friends
> > constructed directly? OK either way, with the above comment tweak.
>
> Unfortunately, this seems to break x86_64 Darwin bootstrap with fails as
> below - I did not yet have a chance to look in any morre detail, so this is a
> head’s up - unless you have any immediate ideas?
>
> thanks
> Iain
>
>
> /src-local/gcc-master/gcc/cp/module.cc: In member function
> ‘{anonymous}::bytes_in::bits_in {anonymous}::bytes_in::stream_bits()’:
> /src-local/gcc-master/gcc/cp/module.cc:735:24: error: use of deleted function
> ‘{anonymous}::bytes_in::bits_in::bits_in(const
> {anonymous}::bytes_in::bits_in&)’
> 735 | return bits_in (*this);
> |^
> /src-local/gcc-master/gcc/cp/module.cc:709:3: note: declared here
> 709 | bits_in(const bits_in&) = delete;
> | ^~~
> /src-local/gcc-master/gcc/cp/module.cc: In member function
> ‘{anonymous}::bytes_out::bits_out {anonymous}::bytes_out::stream_bits()’:
> /src-local/gcc-master/gcc/cp/module.cc:796:25: error: use of deleted function
> ‘{anonymous}::bytes_out::bits_out::bits_out(const
> {anonymous}::bytes_out::bits_out&)’
> 796 | return bits_out (*this);
> | ^
> /src-local/gcc-master/gcc/cp/module.cc:755:3: note: declared here
> 755 | bits_out(const bits_out&) = delete;
> | ^~~~
Drat, sorry for the breakage. We need to define defaulted move ctors
for these classes I think. I'll take care of it ASAP.
Re: [PATCH] c++/modules: optimize tree flag streaming
Hi Patrick,
> On 10 Apr 2024, at 17:33, Jason Merrill wrote:
>
> On 4/10/24 11:26, Patrick Palka wrote:
>> On Wed, 10 Apr 2024, Patrick Palka wrote:
>>>
>>> On Tue, 9 Apr 2024, Jason Merrill wrote:
>>>
On 2/16/24 10:06, Patrick Palka wrote:
> On Thu, 15 Feb 2024, Patrick Palka wrote:
>
> Let's keep documenting the inheritance relationship here, i.e.
>
> bytes_in : data
>
>> @@ -694,13 +656,132 @@ protected:
>>/* Instrumentation. */
>>static unsigned spans[4];
>>static unsigned lengths[4];
>> - static int is_set;
>> + friend struct bits_out;
>
> It might be a little more elegant for bits_in/out to be nested classes of
> bytes_in/out, returned from member functions, rather than friends constructed
> directly? OK either way, with the above comment tweak.
Unfortunately, this seems to break x86_64 Darwin bootstrap with fails as below
- I did not yet have a chance to look in any morre detail, so this is a head’s
up - unless you have any immediate ideas?
thanks
Iain
/src-local/gcc-master/gcc/cp/module.cc: In member function
‘{anonymous}::bytes_in::bits_in {anonymous}::bytes_in::stream_bits()’:
/src-local/gcc-master/gcc/cp/module.cc:735:24: error: use of deleted function
‘{anonymous}::bytes_in::bits_in::bits_in(const {anonymous}::bytes_in::bits_in&)’
735 | return bits_in (*this);
|^
/src-local/gcc-master/gcc/cp/module.cc:709:3: note: declared here
709 | bits_in(const bits_in&) = delete;
| ^~~
/src-local/gcc-master/gcc/cp/module.cc: In member function
‘{anonymous}::bytes_out::bits_out {anonymous}::bytes_out::stream_bits()’:
/src-local/gcc-master/gcc/cp/module.cc:796:25: error: use of deleted function
‘{anonymous}::bytes_out::bits_out::bits_out(const
{anonymous}::bytes_out::bits_out&)’
796 | return bits_out (*this);
| ^
/src-local/gcc-master/gcc/cp/module.cc:755:3: note: declared here
755 | bits_out(const bits_out&) = delete;
| ^~~~
Re: [PATCH] c++/modules: optimize tree flag streaming
On 4/10/24 11:26, Patrick Palka wrote:
On Wed, 10 Apr 2024, Patrick Palka wrote:
On Tue, 9 Apr 2024, Jason Merrill wrote:
On 2/16/24 10:06, Patrick Palka wrote:
On Thu, 15 Feb 2024, Patrick Palka wrote:
One would expect consecutive calls to bytes_in/out::b for streaming
adjacent bits, as we do for tree flag streaming, to at least be
optimized by the compiler into individual bit operations using
statically known bit positions (and ideally merged into larger sized
reads/writes).
Did you have any thoughts about how feasible it would be to use
data-streamer.h? I didn't see a response to richi's mail.
IIUC the workhorses of data-streamer.h are
for streaming out: bitpack_create / bp_pack_value / streamer_write_bitpack
for streaming in: streamer_read_bitpack / bp_unpack_value
which use a locally constructed bitpack_d struct for state management,
much like what this patch proposes, which is a sign that this is a good
approach I suppose.
The bit twiddling code is unsurprisingly pretty similar except
data-streamer.h can stream more than one bit at a time whereas
bits_in/out::b from this patch can only handle one bit at a time
(which is by far the common case). Another difference is that the
data-streamer.h buffer is a HOST_WIDE_INT while the modules bit buffer
is uint32_t (this patch doesn't change that).
Unfortunately it seems data-streamer.h is currently hardcoded for
LTO streaming since bitpack_d::stream must be an lto_input_block and it
uses streamer_write_uhwi_stream and streamer_read_uhwi under the hood.
So we can't use it for modules streaming currently without abstracting
away this hardcoding AFAICT.
Unfortunately this doesn't happen because the compiler has trouble
tracking the values of this->bit_pos and this->bit_val across such
calls, likely because the compiler doesn't know 'this' and so it's
treated as global memory. This means for each consecutive bit stream
operation, bit_pos and bit_val are loaded from memory, checked if
buffering is needed, and finally the bit is extracted from bit_val
according to the (unknown) bit_pos, even though relative to the previous
operation (if we didn't need to buffer) bit_val is unchanged and bit_pos
is just 1 larger. This ends up being quite slow, with tree_node_bools
taking 10% of time when streaming in parts of the std module.
This patch optimizes this by making tracking of bit_pos and bit_val
easier for the compiler. Rather than bit_pos and bit_val being members
of the (effectively global) bytes_in/out objects, this patch factors out
the bit streaming code/state into separate classes bits_in/out that get
constructed locally as needed for bit streaming. Since these objects
are now clearly local, the compiler can more easily track their values.
Please add this rationale to the bits_in comment.
Will do.
And since bit streaming is intended to be batched it's natural for these
new classes to be RAII-enabled such that the bit stream is flushed upon
destruction.
In order to make the most of this improved tracking of bit position,
this patch changes parts where we conditionally stream a tree flag
to unconditionally stream (the flag or a dummy value). That way
the number of bits streamed and the respective bit positions are as
statically known as reasonably possible. In lang_decl_bools and
lang_type_bools we flush the current bit buffer at the start so that
subsequent bit positions are statically known. And in core bools, we
can add explicit early exits utilizing invariants that the compiler
can't figure out itself (e.g. a tree code can't have both TS_TYPE_COMMON
and TS_DECL_COMMON, and if a tree code doesn't have TS_DECL_COMMON then
it doesn't have TS_DECL_WITH_VIS). Finally if we're streaming fewer
than 4 bits, it's more space efficient to stream them as individual
bytes rather than as packed bits (due to the 32-bit buffer).
Oops, this last sentence is wrong. Although the size of the bit buffer
is 32 bits, upon flushing we rewind unused bytes within the buffer,
which means streaming 2-8 bits ends up using only one byte not all four.
So v2 below undoes this pessimization.
This patch also moves the definitions of the relevant streaming classes
into anonymous namespaces so that the compiler can make more informed
decisions about inlining their member functions.
I'm curious why you decided to put namespace { } around each class rather than
a larger part of the file? Not asking for a change, just curious.
I don't feel strongly about i, but to me using a separate namespace { }
for each class is consistent with how we use 'static' instead of
namespace { } to give (consecutively defined) free functions internal
linkage, i.e. instead of
namespace {
void f() { }
void g() { }
}
we do
static void f() { }
static void g() { }
Using a separate namespace { } for each class is the closest thing to
'static' for types. And it makes it obvious whether a class is TU-local
or not.
I'm also
Re: [PATCH] c++/modules: optimize tree flag streaming
On Wed, 10 Apr 2024, Patrick Palka wrote:
>
> On Tue, 9 Apr 2024, Jason Merrill wrote:
>
> > On 2/16/24 10:06, Patrick Palka wrote:
> > > On Thu, 15 Feb 2024, Patrick Palka wrote:
> > >
> > > > One would expect consecutive calls to bytes_in/out::b for streaming
> > > > adjacent bits, as we do for tree flag streaming, to at least be
> > > > optimized by the compiler into individual bit operations using
> > > > statically known bit positions (and ideally merged into larger sized
> > > > reads/writes).
> >
> > Did you have any thoughts about how feasible it would be to use
> > data-streamer.h? I didn't see a response to richi's mail.
>
> IIUC the workhorses of data-streamer.h are
>
> for streaming out: bitpack_create / bp_pack_value / streamer_write_bitpack
> for streaming in: streamer_read_bitpack / bp_unpack_value
>
> which use a locally constructed bitpack_d struct for state management,
> much like what this patch proposes, which is a sign that this is a good
> approach I suppose.
>
> The bit twiddling code is unsurprisingly pretty similar except
> data-streamer.h can stream more than one bit at a time whereas
> bits_in/out::b from this patch can only handle one bit at a time
> (which is by far the common case). Another difference is that the
> data-streamer.h buffer is a HOST_WIDE_INT while the modules bit buffer
> is uint32_t (this patch doesn't change that).
>
> Unfortunately it seems data-streamer.h is currently hardcoded for
> LTO streaming since bitpack_d::stream must be an lto_input_block and it
> uses streamer_write_uhwi_stream and streamer_read_uhwi under the hood.
> So we can't use it for modules streaming currently without abstracting
> away this hardcoding AFAICT.
>
> >
> > > > Unfortunately this doesn't happen because the compiler has trouble
> > > > tracking the values of this->bit_pos and this->bit_val across such
> > > > calls, likely because the compiler doesn't know 'this' and so it's
> > > > treated as global memory. This means for each consecutive bit stream
> > > > operation, bit_pos and bit_val are loaded from memory, checked if
> > > > buffering is needed, and finally the bit is extracted from bit_val
> > > > according to the (unknown) bit_pos, even though relative to the previous
> > > > operation (if we didn't need to buffer) bit_val is unchanged and bit_pos
> > > > is just 1 larger. This ends up being quite slow, with tree_node_bools
> > > > taking 10% of time when streaming in parts of the std module.
> > > >
> > > > This patch optimizes this by making tracking of bit_pos and bit_val
> > > > easier for the compiler. Rather than bit_pos and bit_val being members
> > > > of the (effectively global) bytes_in/out objects, this patch factors out
> > > > the bit streaming code/state into separate classes bits_in/out that get
> > > > constructed locally as needed for bit streaming. Since these objects
> > > > are now clearly local, the compiler can more easily track their values.
> >
> > Please add this rationale to the bits_in comment.
>
> Will do.
>
> >
> > > > And since bit streaming is intended to be batched it's natural for these
> > > > new classes to be RAII-enabled such that the bit stream is flushed upon
> > > > destruction.
> > > >
> > > > In order to make the most of this improved tracking of bit position,
> > > > this patch changes parts where we conditionally stream a tree flag
> > > > to unconditionally stream (the flag or a dummy value). That way
> > > > the number of bits streamed and the respective bit positions are as
> > > > statically known as reasonably possible. In lang_decl_bools and
> > > > lang_type_bools we flush the current bit buffer at the start so that
> > > > subsequent bit positions are statically known. And in core bools, we
> > > > can add explicit early exits utilizing invariants that the compiler
> > > > can't figure out itself (e.g. a tree code can't have both TS_TYPE_COMMON
> > > > and TS_DECL_COMMON, and if a tree code doesn't have TS_DECL_COMMON then
> > > > it doesn't have TS_DECL_WITH_VIS). Finally if we're streaming fewer
> > > > than 4 bits, it's more space efficient to stream them as individual
> > > > bytes rather than as packed bits (due to the 32-bit buffer).
> > >
> > > Oops, this last sentence is wrong. Although the size of the bit buffer
> > > is 32 bits, upon flushing we rewind unused bytes within the buffer,
> > > which means streaming 2-8 bits ends up using only one byte not all four.
> > > So v2 below undoes this pessimization.
> > >
> > > > This patch also moves the definitions of the relevant streaming classes
> > > > into anonymous namespaces so that the compiler can make more informed
> > > > decisions about inlining their member functions.
> >
> > I'm curious why you decided to put namespace { } around each class rather
> > than
> > a larger part of the file? Not asking for a change, just curious.
>
> I don't feel strongly about i, but to me using a separate namespace { }
> for each
Re: [PATCH] c++/modules: optimize tree flag streaming
On Tue, 9 Apr 2024, Jason Merrill wrote:
> On 2/16/24 10:06, Patrick Palka wrote:
> > On Thu, 15 Feb 2024, Patrick Palka wrote:
> >
> > > One would expect consecutive calls to bytes_in/out::b for streaming
> > > adjacent bits, as we do for tree flag streaming, to at least be
> > > optimized by the compiler into individual bit operations using
> > > statically known bit positions (and ideally merged into larger sized
> > > reads/writes).
>
> Did you have any thoughts about how feasible it would be to use
> data-streamer.h? I didn't see a response to richi's mail.
IIUC the workhorses of data-streamer.h are
for streaming out: bitpack_create / bp_pack_value / streamer_write_bitpack
for streaming in: streamer_read_bitpack / bp_unpack_value
which use a locally constructed bitpack_d struct for state management,
much like what this patch proposes, which is a sign that this is a good
approach I suppose.
The bit twiddling code is unsurprisingly pretty similar except
data-streamer.h can stream more than one bit at a time whereas
bits_in/out::b from this patch can only handle one bit at a time
(which is by far the common case). Another difference is that the
data-streamer.h buffer is a HOST_WIDE_INT while the modules bit buffer
is uint32_t (this patch doesn't change that).
Unfortunately it seems data-streamer.h is currently hardcoded for
LTO streaming since bitpack_d::stream must be an lto_input_block and it
uses streamer_write_uhwi_stream and streamer_read_uhwi under the hood.
So we can't use it for modules streaming currently without abstracting
away this hardcoding AFAICT.
>
> > > Unfortunately this doesn't happen because the compiler has trouble
> > > tracking the values of this->bit_pos and this->bit_val across such
> > > calls, likely because the compiler doesn't know 'this' and so it's
> > > treated as global memory. This means for each consecutive bit stream
> > > operation, bit_pos and bit_val are loaded from memory, checked if
> > > buffering is needed, and finally the bit is extracted from bit_val
> > > according to the (unknown) bit_pos, even though relative to the previous
> > > operation (if we didn't need to buffer) bit_val is unchanged and bit_pos
> > > is just 1 larger. This ends up being quite slow, with tree_node_bools
> > > taking 10% of time when streaming in parts of the std module.
> > >
> > > This patch optimizes this by making tracking of bit_pos and bit_val
> > > easier for the compiler. Rather than bit_pos and bit_val being members
> > > of the (effectively global) bytes_in/out objects, this patch factors out
> > > the bit streaming code/state into separate classes bits_in/out that get
> > > constructed locally as needed for bit streaming. Since these objects
> > > are now clearly local, the compiler can more easily track their values.
>
> Please add this rationale to the bits_in comment.
Will do.
>
> > > And since bit streaming is intended to be batched it's natural for these
> > > new classes to be RAII-enabled such that the bit stream is flushed upon
> > > destruction.
> > >
> > > In order to make the most of this improved tracking of bit position,
> > > this patch changes parts where we conditionally stream a tree flag
> > > to unconditionally stream (the flag or a dummy value). That way
> > > the number of bits streamed and the respective bit positions are as
> > > statically known as reasonably possible. In lang_decl_bools and
> > > lang_type_bools we flush the current bit buffer at the start so that
> > > subsequent bit positions are statically known. And in core bools, we
> > > can add explicit early exits utilizing invariants that the compiler
> > > can't figure out itself (e.g. a tree code can't have both TS_TYPE_COMMON
> > > and TS_DECL_COMMON, and if a tree code doesn't have TS_DECL_COMMON then
> > > it doesn't have TS_DECL_WITH_VIS). Finally if we're streaming fewer
> > > than 4 bits, it's more space efficient to stream them as individual
> > > bytes rather than as packed bits (due to the 32-bit buffer).
> >
> > Oops, this last sentence is wrong. Although the size of the bit buffer
> > is 32 bits, upon flushing we rewind unused bytes within the buffer,
> > which means streaming 2-8 bits ends up using only one byte not all four.
> > So v2 below undoes this pessimization.
> >
> > > This patch also moves the definitions of the relevant streaming classes
> > > into anonymous namespaces so that the compiler can make more informed
> > > decisions about inlining their member functions.
>
> I'm curious why you decided to put namespace { } around each class rather than
> a larger part of the file? Not asking for a change, just curious.
I don't feel strongly about i, but to me using a separate namespace { }
for each class is consistent with how we use 'static' instead of
namespace { } to give (consecutively defined) free functions internal
linkage, i.e. instead of
namespace {
void f() { }
void g() { }
}
we do
static void
Re: [PATCH] c++/modules: optimize tree flag streaming
On 2/16/24 10:06, Patrick Palka wrote:
On Thu, 15 Feb 2024, Patrick Palka wrote:
One would expect consecutive calls to bytes_in/out::b for streaming
adjacent bits, as we do for tree flag streaming, to at least be
optimized by the compiler into individual bit operations using
statically known bit positions (and ideally merged into larger sized
reads/writes).
Did you have any thoughts about how feasible it would be to use
data-streamer.h? I didn't see a response to richi's mail.
Unfortunately this doesn't happen because the compiler has trouble
tracking the values of this->bit_pos and this->bit_val across such
calls, likely because the compiler doesn't know 'this' and so it's
treated as global memory. This means for each consecutive bit stream
operation, bit_pos and bit_val are loaded from memory, checked if
buffering is needed, and finally the bit is extracted from bit_val
according to the (unknown) bit_pos, even though relative to the previous
operation (if we didn't need to buffer) bit_val is unchanged and bit_pos
is just 1 larger. This ends up being quite slow, with tree_node_bools
taking 10% of time when streaming in parts of the std module.
This patch optimizes this by making tracking of bit_pos and bit_val
easier for the compiler. Rather than bit_pos and bit_val being members
of the (effectively global) bytes_in/out objects, this patch factors out
the bit streaming code/state into separate classes bits_in/out that get
constructed locally as needed for bit streaming. Since these objects
are now clearly local, the compiler can more easily track their values.
Please add this rationale to the bits_in comment.
And since bit streaming is intended to be batched it's natural for these
new classes to be RAII-enabled such that the bit stream is flushed upon
destruction.
In order to make the most of this improved tracking of bit position,
this patch changes parts where we conditionally stream a tree flag
to unconditionally stream (the flag or a dummy value). That way
the number of bits streamed and the respective bit positions are as
statically known as reasonably possible. In lang_decl_bools and
lang_type_bools we flush the current bit buffer at the start so that
subsequent bit positions are statically known. And in core bools, we
can add explicit early exits utilizing invariants that the compiler
can't figure out itself (e.g. a tree code can't have both TS_TYPE_COMMON
and TS_DECL_COMMON, and if a tree code doesn't have TS_DECL_COMMON then
it doesn't have TS_DECL_WITH_VIS). Finally if we're streaming fewer
than 4 bits, it's more space efficient to stream them as individual
bytes rather than as packed bits (due to the 32-bit buffer).
Oops, this last sentence is wrong. Although the size of the bit buffer
is 32 bits, upon flushing we rewind unused bytes within the buffer,
which means streaming 2-8 bits ends up using only one byte not all four.
So v2 below undoes this pessimization.
This patch also moves the definitions of the relevant streaming classes
into anonymous namespaces so that the compiler can make more informed
decisions about inlining their member functions.
I'm curious why you decided to put namespace { } around each class
rather than a larger part of the file? Not asking for a change, just
curious.
I'm also surprised that this would make a difference for inline
functions? Is this just to allow the compiler to inline member
functions defined outside the class body without marking them inline?
In any case, please add a rationale comment to the (first) anonymous
namespace.
After this patch, compile time for a simple Hello World using the std
module is reduced by 7% with a release compiler. The on-disk size of
the std module increases by 0.7% (presumably due to the extra flushing
done in lang_decl_bools and lang_type_bools).
The on-disk std module now only grows 0.4% instead of 0.7%.
The bit stream out performance isn't improved as much as the stream in
due to the spans/lengths instrumentation performed on stream out (which
probably should be e.g. removed for release builds?)
Based on CHECKING_P, sure.
diff --git a/gcc/cp/module.cc b/gcc/cp/module.cc
index 0291d456ff5..2ecee007e8a 100644
--- a/gcc/cp/module.cc
+++ b/gcc/cp/module.cc
@@ -694,13 +656,126 @@ protected:
/* Instrumentation. */
static unsigned spans[4];
static unsigned lengths[4];
- static int is_set;
+ friend struct bits_out;
};
+} // anon namespace
+
+/* Finish bit packet. Rewind the bytes not used. */
Missing blank line.
+static unsigned
+bit_flush (data& bits, uint32_t& bit_val, unsigned& bit_pos)
+{
+ gcc_assert (bit_pos);
+ unsigned bytes = (bit_pos + 7) / 8;
+ bits.unuse (4 - bytes);
+ bit_pos = 0;
+ bit_val = 0;
+ return bytes;
+}
+
@@ -5314,6 +5326,8 @@ trees_out::core_bools (tree t)
if (TREE_CODE_CLASS (code) != tcc_type)
/* This is TYPE_CACHED_VALUES_P for types. */
WB (t->base.public_flag);
+ else
+WB (false);
Can we simplify
Re: [PATCH] c++/modules: optimize tree flag streaming
On Tue, 26 Mar 2024, Patrick Palka wrote: > On Tue, 27 Feb 2024, Patrick Palka wrote: > > > On Fri, 16 Feb 2024, Patrick Palka wrote: > > > > > On Thu, 15 Feb 2024, Patrick Palka wrote: > > > > > > > Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look > > > > OK for trunk? > > > > > > > > -- >8 -- > > > > > > > > One would expect consecutive calls to bytes_in/out::b for streaming > > > > adjacent bits, as we do for tree flag streaming, to at least be > > > > optimized by the compiler into individual bit operations using > > > > statically known bit positions (and ideally merged into larger sized > > > > reads/writes). > > > > > > > > Unfortunately this doesn't happen because the compiler has trouble > > > > tracking the values of this->bit_pos and this->bit_val across such > > > > calls, likely because the compiler doesn't know 'this' and so it's > > > > treated as global memory. This means for each consecutive bit stream > > > > operation, bit_pos and bit_val are loaded from memory, checked if > > > > buffering is needed, and finally the bit is extracted from bit_val > > > > according to the (unknown) bit_pos, even though relative to the previous > > > > operation (if we didn't need to buffer) bit_val is unchanged and bit_pos > > > > is just 1 larger. This ends up being quite slow, with tree_node_bools > > > > taking 10% of time when streaming in parts of the std module. > > > > > > > > This patch optimizes this by making tracking of bit_pos and bit_val > > > > easier for the compiler. Rather than bit_pos and bit_val being members > > > > of the (effectively global) bytes_in/out objects, this patch factors out > > > > the bit streaming code/state into separate classes bits_in/out that get > > > > constructed locally as needed for bit streaming. Since these objects > > > > are now clearly local, the compiler can more easily track their values. > > > > > > > > And since bit streaming is intended to be batched it's natural for these > > > > new classes to be RAII-enabled such that the bit stream is flushed upon > > > > destruction. > > > > > > > > In order to make the most of this improved tracking of bit position, > > > > this patch changes parts where we conditionally stream a tree flag > > > > to unconditionally stream (the flag or a dummy value). That way > > > > the number of bits streamed and the respective bit positions are as > > > > statically known as reasonably possible. In lang_decl_bools and > > > > lang_type_bools we flush the current bit buffer at the start so that > > > > subsequent bit positions are statically known. And in core bools, we > > > > can add explicit early exits utilizing invariants that the compiler > > > > can't figure out itself (e.g. a tree code can't have both TS_TYPE_COMMON > > > > and TS_DECL_COMMON, and if a tree code doesn't have TS_DECL_COMMON then > > > > it doesn't have TS_DECL_WITH_VIS). Finally if we're streaming fewer > > > > than 4 bits, it's more space efficient to stream them as individual > > > > bytes rather than as packed bits (due to the 32-bit buffer). > > > > > > Oops, this last sentence is wrong. Although the size of the bit buffer > > > is 32 bits, upon flushing we rewind unused bytes within the buffer, > > > which means streaming 2-8 bits ends up using only one byte not all four. > > > So v2 below undoes this pessimization. > > > > > > > This patch also moves the definitions of the relevant streaming classes > > > > into anonymous namespaces so that the compiler can make more informed > > > > decisions about inlining their member functions. > > > > > > > > After this patch, compile time for a simple Hello World using the std > > > > module is reduced by 7% with a release compiler. The on-disk size of > > > > the std module increases by 0.7% (presumably due to the extra flushing > > > > done in lang_decl_bools and lang_type_bools). > > > > > > The on-disk std module now only grows 0.4% instead of 0.7%. > > > > > > > > > > > The bit stream out performance isn't improved as much as the stream in > > > > due to the spans/lengths instrumentation performed on stream out (which > > > > probably should be e.g. removed for release builds?) > > > > > > -- >8 -- > > > > > > gcc/cp/ChangeLog: > > > > > > * module.cc: Update comment about classes defined. > > > (class data): Enclose in an anonymous namespace. > > > (data::calc_crc): Moved from bytes::calc_crc. > > > (class bytes): Remove. Move bit_flush to namespace scope. > > > (class bytes_in): Enclose in an anonymous namespace. Inherit > > > directly from data and adjust accordingly. Move b and bflush > > > members to bits_in. > > > (class bytes_out): As above. Remove is_set static data member. > > > (bit_flush): Moved from class bytes. > > > (struct bits_in): Define. > > > (struct bits_out): Define. > > > (bytes_out::bflush): Moved to bits_out/in. > > > (bytes_in::bflush): Likewise > > > (bytes_in::bfill): Removed. > > >
Re: [PATCH] c++/modules: optimize tree flag streaming
On Tue, 27 Feb 2024, Patrick Palka wrote: > On Fri, 16 Feb 2024, Patrick Palka wrote: > > > On Thu, 15 Feb 2024, Patrick Palka wrote: > > > > > Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look > > > OK for trunk? > > > > > > -- >8 -- > > > > > > One would expect consecutive calls to bytes_in/out::b for streaming > > > adjacent bits, as we do for tree flag streaming, to at least be > > > optimized by the compiler into individual bit operations using > > > statically known bit positions (and ideally merged into larger sized > > > reads/writes). > > > > > > Unfortunately this doesn't happen because the compiler has trouble > > > tracking the values of this->bit_pos and this->bit_val across such > > > calls, likely because the compiler doesn't know 'this' and so it's > > > treated as global memory. This means for each consecutive bit stream > > > operation, bit_pos and bit_val are loaded from memory, checked if > > > buffering is needed, and finally the bit is extracted from bit_val > > > according to the (unknown) bit_pos, even though relative to the previous > > > operation (if we didn't need to buffer) bit_val is unchanged and bit_pos > > > is just 1 larger. This ends up being quite slow, with tree_node_bools > > > taking 10% of time when streaming in parts of the std module. > > > > > > This patch optimizes this by making tracking of bit_pos and bit_val > > > easier for the compiler. Rather than bit_pos and bit_val being members > > > of the (effectively global) bytes_in/out objects, this patch factors out > > > the bit streaming code/state into separate classes bits_in/out that get > > > constructed locally as needed for bit streaming. Since these objects > > > are now clearly local, the compiler can more easily track their values. > > > > > > And since bit streaming is intended to be batched it's natural for these > > > new classes to be RAII-enabled such that the bit stream is flushed upon > > > destruction. > > > > > > In order to make the most of this improved tracking of bit position, > > > this patch changes parts where we conditionally stream a tree flag > > > to unconditionally stream (the flag or a dummy value). That way > > > the number of bits streamed and the respective bit positions are as > > > statically known as reasonably possible. In lang_decl_bools and > > > lang_type_bools we flush the current bit buffer at the start so that > > > subsequent bit positions are statically known. And in core bools, we > > > can add explicit early exits utilizing invariants that the compiler > > > can't figure out itself (e.g. a tree code can't have both TS_TYPE_COMMON > > > and TS_DECL_COMMON, and if a tree code doesn't have TS_DECL_COMMON then > > > it doesn't have TS_DECL_WITH_VIS). Finally if we're streaming fewer > > > than 4 bits, it's more space efficient to stream them as individual > > > bytes rather than as packed bits (due to the 32-bit buffer). > > > > Oops, this last sentence is wrong. Although the size of the bit buffer > > is 32 bits, upon flushing we rewind unused bytes within the buffer, > > which means streaming 2-8 bits ends up using only one byte not all four. > > So v2 below undoes this pessimization. > > > > > This patch also moves the definitions of the relevant streaming classes > > > into anonymous namespaces so that the compiler can make more informed > > > decisions about inlining their member functions. > > > > > > After this patch, compile time for a simple Hello World using the std > > > module is reduced by 7% with a release compiler. The on-disk size of > > > the std module increases by 0.7% (presumably due to the extra flushing > > > done in lang_decl_bools and lang_type_bools). > > > > The on-disk std module now only grows 0.4% instead of 0.7%. > > > > > > > > The bit stream out performance isn't improved as much as the stream in > > > due to the spans/lengths instrumentation performed on stream out (which > > > probably should be e.g. removed for release builds?) > > > > -- >8 -- > > > > gcc/cp/ChangeLog: > > > > * module.cc: Update comment about classes defined. > > (class data): Enclose in an anonymous namespace. > > (data::calc_crc): Moved from bytes::calc_crc. > > (class bytes): Remove. Move bit_flush to namespace scope. > > (class bytes_in): Enclose in an anonymous namespace. Inherit > > directly from data and adjust accordingly. Move b and bflush > > members to bits_in. > > (class bytes_out): As above. Remove is_set static data member. > > (bit_flush): Moved from class bytes. > > (struct bits_in): Define. > > (struct bits_out): Define. > > (bytes_out::bflush): Moved to bits_out/in. > > (bytes_in::bflush): Likewise > > (bytes_in::bfill): Removed. > > (bytes_out::b): Moved to bits_out/in. > > (bytes_in::b): Likewise. > > (class trees_in): Enclose in an anonymous namespace. > > (class trees_out): Enclose in an anonymous namespace. > >
Re: [PATCH] c++/modules: optimize tree flag streaming
On Fri, 16 Feb 2024, Patrick Palka wrote: > On Thu, 15 Feb 2024, Patrick Palka wrote: > > > Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look > > OK for trunk? > > > > -- >8 -- > > > > One would expect consecutive calls to bytes_in/out::b for streaming > > adjacent bits, as we do for tree flag streaming, to at least be > > optimized by the compiler into individual bit operations using > > statically known bit positions (and ideally merged into larger sized > > reads/writes). > > > > Unfortunately this doesn't happen because the compiler has trouble > > tracking the values of this->bit_pos and this->bit_val across such > > calls, likely because the compiler doesn't know 'this' and so it's > > treated as global memory. This means for each consecutive bit stream > > operation, bit_pos and bit_val are loaded from memory, checked if > > buffering is needed, and finally the bit is extracted from bit_val > > according to the (unknown) bit_pos, even though relative to the previous > > operation (if we didn't need to buffer) bit_val is unchanged and bit_pos > > is just 1 larger. This ends up being quite slow, with tree_node_bools > > taking 10% of time when streaming in parts of the std module. > > > > This patch optimizes this by making tracking of bit_pos and bit_val > > easier for the compiler. Rather than bit_pos and bit_val being members > > of the (effectively global) bytes_in/out objects, this patch factors out > > the bit streaming code/state into separate classes bits_in/out that get > > constructed locally as needed for bit streaming. Since these objects > > are now clearly local, the compiler can more easily track their values. > > > > And since bit streaming is intended to be batched it's natural for these > > new classes to be RAII-enabled such that the bit stream is flushed upon > > destruction. > > > > In order to make the most of this improved tracking of bit position, > > this patch changes parts where we conditionally stream a tree flag > > to unconditionally stream (the flag or a dummy value). That way > > the number of bits streamed and the respective bit positions are as > > statically known as reasonably possible. In lang_decl_bools and > > lang_type_bools we flush the current bit buffer at the start so that > > subsequent bit positions are statically known. And in core bools, we > > can add explicit early exits utilizing invariants that the compiler > > can't figure out itself (e.g. a tree code can't have both TS_TYPE_COMMON > > and TS_DECL_COMMON, and if a tree code doesn't have TS_DECL_COMMON then > > it doesn't have TS_DECL_WITH_VIS). Finally if we're streaming fewer > > than 4 bits, it's more space efficient to stream them as individual > > bytes rather than as packed bits (due to the 32-bit buffer). > > Oops, this last sentence is wrong. Although the size of the bit buffer > is 32 bits, upon flushing we rewind unused bytes within the buffer, > which means streaming 2-8 bits ends up using only one byte not all four. > So v2 below undoes this pessimization. > > > This patch also moves the definitions of the relevant streaming classes > > into anonymous namespaces so that the compiler can make more informed > > decisions about inlining their member functions. > > > > After this patch, compile time for a simple Hello World using the std > > module is reduced by 7% with a release compiler. The on-disk size of > > the std module increases by 0.7% (presumably due to the extra flushing > > done in lang_decl_bools and lang_type_bools). > > The on-disk std module now only grows 0.4% instead of 0.7%. > > > > > The bit stream out performance isn't improved as much as the stream in > > due to the spans/lengths instrumentation performed on stream out (which > > probably should be e.g. removed for release builds?) > > -- >8 -- > > gcc/cp/ChangeLog: > > * module.cc: Update comment about classes defined. > (class data): Enclose in an anonymous namespace. > (data::calc_crc): Moved from bytes::calc_crc. > (class bytes): Remove. Move bit_flush to namespace scope. > (class bytes_in): Enclose in an anonymous namespace. Inherit > directly from data and adjust accordingly. Move b and bflush > members to bits_in. > (class bytes_out): As above. Remove is_set static data member. > (bit_flush): Moved from class bytes. > (struct bits_in): Define. > (struct bits_out): Define. > (bytes_out::bflush): Moved to bits_out/in. > (bytes_in::bflush): Likewise > (bytes_in::bfill): Removed. > (bytes_out::b): Moved to bits_out/in. > (bytes_in::b): Likewise. > (class trees_in): Enclose in an anonymous namespace. > (class trees_out): Enclose in an anonymous namespace. > (trees_out::core_bools): Add bits_out/in parameter and use it. > Unconditionally stream a bit for public_flag. Add early exits > as appropriate. > (trees_out::core_bools): Likewise. >
Re: [PATCH] c++/modules: optimize tree flag streaming
On Thu, 15 Feb 2024, Patrick Palka wrote: > Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look > OK for trunk? > > -- >8 -- > > One would expect consecutive calls to bytes_in/out::b for streaming > adjacent bits, as we do for tree flag streaming, to at least be > optimized by the compiler into individual bit operations using > statically known bit positions (and ideally merged into larger sized > reads/writes). > > Unfortunately this doesn't happen because the compiler has trouble > tracking the values of this->bit_pos and this->bit_val across such > calls, likely because the compiler doesn't know 'this' and so it's > treated as global memory. This means for each consecutive bit stream > operation, bit_pos and bit_val are loaded from memory, checked if > buffering is needed, and finally the bit is extracted from bit_val > according to the (unknown) bit_pos, even though relative to the previous > operation (if we didn't need to buffer) bit_val is unchanged and bit_pos > is just 1 larger. This ends up being quite slow, with tree_node_bools > taking 10% of time when streaming in parts of the std module. > > This patch optimizes this by making tracking of bit_pos and bit_val > easier for the compiler. Rather than bit_pos and bit_val being members > of the (effectively global) bytes_in/out objects, this patch factors out > the bit streaming code/state into separate classes bits_in/out that get > constructed locally as needed for bit streaming. Since these objects > are now clearly local, the compiler can more easily track their values. > > And since bit streaming is intended to be batched it's natural for these > new classes to be RAII-enabled such that the bit stream is flushed upon > destruction. > > In order to make the most of this improved tracking of bit position, > this patch changes parts where we conditionally stream a tree flag > to unconditionally stream (the flag or a dummy value). That way > the number of bits streamed and the respective bit positions are as > statically known as reasonably possible. In lang_decl_bools and > lang_type_bools we flush the current bit buffer at the start so that > subsequent bit positions are statically known. And in core bools, we > can add explicit early exits utilizing invariants that the compiler > can't figure out itself (e.g. a tree code can't have both TS_TYPE_COMMON > and TS_DECL_COMMON, and if a tree code doesn't have TS_DECL_COMMON then > it doesn't have TS_DECL_WITH_VIS). Finally if we're streaming fewer > than 4 bits, it's more space efficient to stream them as individual > bytes rather than as packed bits (due to the 32-bit buffer). Oops, this last sentence is wrong. Although the size of the bit buffer is 32 bits, upon flushing we rewind unused bytes within the buffer, which means streaming 2-8 bits ends up using only one byte not all four. So v2 below undoes this pessimization. > This patch also moves the definitions of the relevant streaming classes > into anonymous namespaces so that the compiler can make more informed > decisions about inlining their member functions. > > After this patch, compile time for a simple Hello World using the std > module is reduced by 7% with a release compiler. The on-disk size of > the std module increases by 0.7% (presumably due to the extra flushing > done in lang_decl_bools and lang_type_bools). The on-disk std module now only grows 0.4% instead of 0.7%. > > The bit stream out performance isn't improved as much as the stream in > due to the spans/lengths instrumentation performed on stream out (which > probably should be e.g. removed for release builds?) -- >8 -- gcc/cp/ChangeLog: * module.cc: Update comment about classes defined. (class data): Enclose in an anonymous namespace. (data::calc_crc): Moved from bytes::calc_crc. (class bytes): Remove. Move bit_flush to namespace scope. (class bytes_in): Enclose in an anonymous namespace. Inherit directly from data and adjust accordingly. Move b and bflush members to bits_in. (class bytes_out): As above. Remove is_set static data member. (bit_flush): Moved from class bytes. (struct bits_in): Define. (struct bits_out): Define. (bytes_out::bflush): Moved to bits_out/in. (bytes_in::bflush): Likewise (bytes_in::bfill): Removed. (bytes_out::b): Moved to bits_out/in. (bytes_in::b): Likewise. (class trees_in): Enclose in an anonymous namespace. (class trees_out): Enclose in an anonymous namespace. (trees_out::core_bools): Add bits_out/in parameter and use it. Unconditionally stream a bit for public_flag. Add early exits as appropriate. (trees_out::core_bools): Likewise. (trees_out::lang_decl_bools): Add bits_out/in parameter and use it. Flush the current bit buffer at the start. Unconditionally stream a bit for module_keyed_decls_p.
Re: [PATCH] c++/modules: optimize tree flag streaming
On Thu, Feb 15, 2024 at 7:38 PM Patrick Palka wrote: > > Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look > OK for trunk? Btw, there's the "bitpack" streaming support in data-streamer.h also added for exactly the same reason, it's likely not easily re-usable but this kind of approach is indeed important for performance. The whole "data-streamer" was supposed to be re-usable though. Richard. > -- >8 -- > > One would expect consecutive calls to bytes_in/out::b for streaming > adjacent bits, as we do for tree flag streaming, to at least be > optimized by the compiler into individual bit operations using > statically known bit positions (and ideally merged into larger sized > reads/writes). > > Unfortunately this doesn't happen because the compiler has trouble > tracking the values of this->bit_pos and this->bit_val across such > calls, likely because the compiler doesn't know 'this' and so it's > treated as global memory. This means for each consecutive bit stream > operation, bit_pos and bit_val are loaded from memory, checked if > buffering is needed, and finally the bit is extracted from bit_val > according to the (unknown) bit_pos, even though relative to the previous > operation (if we didn't need to buffer) bit_val is unchanged and bit_pos > is just 1 larger. This ends up being quite slow, with tree_node_bools > taking 10% of time when streaming in parts of the std module. > > This patch optimizes this by making tracking of bit_pos and bit_val > easier for the compiler. Rather than bit_pos and bit_val being members > of the (effectively global) bytes_in/out objects, this patch factors out > the bit streaming code/state into separate classes bits_in/out that get > constructed locally as needed for bit streaming. Since these objects > are now clearly local, the compiler can more easily track their values. > > And since bit streaming is intended to be batched it's natural for these > new classes to be RAII-enabled such that the bit stream is flushed upon > destruction. > > In order to make the most of this improved tracking of bit position, > this patch changes parts where we conditionally stream a tree flag > to unconditionally stream (the flag or a dummy value). That way > the number of bits streamed and the respective bit positions are as > statically known as reasonably possible. In lang_decl_bools and > lang_type_bools we flush the current bit buffer at the start so that > subsequent bit positions are statically known. And in core bools, we > can add explicit early exits utilizing invariants that the compiler > can't figure out itself (e.g. a tree code can't have both TS_TYPE_COMMON > and TS_DECL_COMMON, and if a tree code doesn't have TS_DECL_COMMON then > it doesn't have TS_DECL_WITH_VIS). Finally if we're streaming fewer > than 4 bits, it's more space efficient to stream them as individual > bytes rather than as packed bits (due to the 32-bit buffer). > > This patch also moves the definitions of the relevant streaming classes > into anonymous namespaces so that the compiler can make more informed > decisions about inlining their member functions. > > After this patch, compile time for a simple Hello World using the std > module is reduced by 7% with a release compiler. The on-disk size of > the std module increases by 0.7% (presumably due to the extra flushing > done in lang_decl_bools and lang_type_bools). > > The bit stream out performance isn't improved as much as the stream in > due to the spans/lengths instrumentation performed on stream out (which > probably should be e.g. removed for release builds?) > > gcc/cp/ChangeLog: > > * module.cc > (class data): Enclose in an anonymous namespace. > (data::calc_crc): Moved from bytes::calc_crc. > (class bytes): Remove. Move bit_flush to namespace scope. > (class bytes_in): Enclose in an anonymous namespace. Inherit > directly from data and adjust accordingly. Move b and bflush > members to bits_in. > (class bytes_out): As above. Remove is_set static data member. > (bit_flush): Moved from class bytes. > (struct bits_in): Define. > (struct bits_out): Define. > (bytes_out::bflush): Moved to bits_out/in. > (bytes_in::bflush): Likewise > (bytes_in::bfill): Removed. > (bytes_out::b): Moved to bits_out/in. > (bytes_in::b): Likewise. > (class trees_in): Enclose in an anonymous namespace. > (class trees_out): Enclose in an anonymous namespace. > (trees_out::core_bools): Add bits_out/in parameter and use it. > Unconditionally stream a bit for public_flag. Add early exits > as appropriate. > (trees_out::core_bools): Likewise. > (trees_out::lang_decl_bools): Add bits_out/in parameter and use > it. Flush the current bit buffer at the start. Unconditionally > stream a bit for module_keyed_decls_p. >
