Re: changing a collision resolution strategy of the symbol table of identifiers

[Roman Gareev]

These are statistically significant differences: increasing by 0.23%
for the version 4.8.0, increasing by 0.21% for the version 4.8.1,
decreasing by 0.686% for trunk.


These are new row numbers:

2013-11-05 Roman Gareev gareevro...@gmail.com:
 2013/10/31 Florian Weimer fwei...@redhat.com:
 On 10/20/2013 02:55 PM, Roman Gareev wrote:

 During testing of the linux kernel (3.8.8) compilation time, the
 acquired results were the following: increasing by 0.17% for the
 version 4.8.0, increasing by 1.12% for the version 4.8.1, decreasing
 by 0.598% for trunk (this are average values).


 Can you share the raw numbers?  Are the differences statistically
 significant?

 --
 Florian Weimer / Red Hat Product Security Team

 These are the row numbers. I'll share results of checking for
 statistical significance as soon as more compilations are made.



-- 
   C уважением, Гареев Роман.


trunk_original
Description: Binary data


trunk
Description: Binary data


4.8.1_original
Description: Binary data


4.8.1_modified
Description: Binary data


4.8.0_original
Description: Binary data


4.8.0_modified
Description: Binary data

Re: changing a collision resolution strategy of the symbol table of identifiers

[Roman Gareev]

2013/10/20 Ondřej Bílka nel...@seznam.cz:
 On Sun, Oct 20, 2013 at 06:55:40PM +0600, Roman Gareev wrote:
 Dear gcc contributors,

 Recently I came across the list of ideas for speeding up GCC
 (http://gcc.gnu.org/wiki/Speedup_areas). Among others, there was
 suggested to replace identifier hash table with other data structure.

 Please find attached a patch, that switches the resolution strategy of
 a hash table used in the symbol table of identifiers from open
 addressing to separate chaining with linked list. I would be very
 grateful for your comments, feedback and ideas about further
 enhancements to gcc, in which I could take a part. I am pursuing
 master of science and looking for thesis theme, that is compiler
 related.

 Below are results of testing and the patch.

 During testing of the linux kernel (3.8.8) compilation time, the
 acquired results were the following: increasing by 0.17% for the
 version 4.8.0, increasing by 1.12% for the version 4.8.1, decreasing
 by 0.598% for trunk (this are average values).


 Tested x86_64-unknown-linux-gnu, applying to 4.8.0, 4.8.1 and trunk.


 diff --git a/gcc/stringpool.c b/gcc/stringpool.c

 index f4d0dae..cc696f7 100644

 --- a/gcc/stringpool.c

 +++ b/gcc/stringpool.c

 @@ -241,12 +241,8 @@ gt_pch_nx (unsigned char *x, gt_pointer_operator
 op, void *cookie)

 /* SPD is saved in the PCH file and holds the information needed

 to restore the string pool. */

 -struct GTY(()) string_pool_data {

 - ht_identifier_ptr *

 - GTY((length (%h.nslots),

 Mail client broke it?
Sorry, an error occurred somewhere. Below is an attachment with the patch.


patch
Description: Binary data

Re: changing a collision resolution strategy of the symbol table of identifiers

[Roman Gareev]

2013/10/31 Florian Weimer fwei...@redhat.com:
 On 10/20/2013 02:55 PM, Roman Gareev wrote:

 During testing of the linux kernel (3.8.8) compilation time, the
 acquired results were the following: increasing by 0.17% for the
 version 4.8.0, increasing by 1.12% for the version 4.8.1, decreasing
 by 0.598% for trunk (this are average values).


 Can you share the raw numbers?  Are the differences statistically
 significant?

 --
 Florian Weimer / Red Hat Product Security Team

These are the row numbers. I'll share results of checking for
statistical significance as soon as more compilations are made.


results
Description: Binary data

Re: changing a collision resolution strategy of the symbol table of identifiers

[Florian Weimer]

On 10/20/2013 02:55 PM, Roman Gareev wrote:

During testing of the linux kernel (3.8.8) compilation time, the
acquired results were the following: increasing by 0.17% for the
version 4.8.0, increasing by 1.12% for the version 4.8.1, decreasing
by 0.598% for trunk (this are average values).


Can you share the raw numbers?  Are the differences statistically 
significant?


--
Florian Weimer / Red Hat Product Security Team

changing a collision resolution strategy of the symbol table of identifiers

[Roman Gareev]

Dear gcc contributors,

Recently I came across the list of ideas for speeding up GCC
(http://gcc.gnu.org/wiki/Speedup_areas). Among others, there was
suggested to replace identifier hash table with other data structure.

Please find attached a patch, that switches the resolution strategy of
a hash table used in the symbol table of identifiers from open
addressing to separate chaining with linked list. I would be very
grateful for your comments, feedback and ideas about further
enhancements to gcc, in which I could take a part. I am pursuing
master of science and looking for thesis theme, that is compiler
related.

Below are results of testing and the patch.

During testing of the linux kernel (3.8.8) compilation time, the
acquired results were the following: increasing by 0.17% for the
version 4.8.0, increasing by 1.12% for the version 4.8.1, decreasing
by 0.598% for trunk (this are average values).


Tested x86_64-unknown-linux-gnu, applying to 4.8.0, 4.8.1 and trunk.


diff --git a/gcc/stringpool.c b/gcc/stringpool.c

index f4d0dae..cc696f7 100644

--- a/gcc/stringpool.c

+++ b/gcc/stringpool.c

@@ -241,12 +241,8 @@ gt_pch_nx (unsigned char *x, gt_pointer_operator
op, void *cookie)

/* SPD is saved in the PCH file and holds the information needed

to restore the string pool. */

-struct GTY(()) string_pool_data {

- ht_identifier_ptr *

- GTY((length (%h.nslots),

- nested_ptr (union tree_node, %h ? GCC_IDENT_TO_HT_IDENT (%h) : NULL,

- %h ? HT_IDENT_TO_GCC_IDENT (%h) : NULL)))

- entries;

+struct GTY((user)) string_pool_data {

+ ht_identifier_ptr * entries;

unsigned int nslots;

unsigned int nelements;

};

@@ -284,4 +280,113 @@ gt_pch_restore_stringpool (void)

spd = NULL;

}

+/* User-provided GC marking routines for the struct ht_identifier.
They are using

+ only in GC marking routines for the struct string_pool_data. */

+

+extern void ht_identifier_ggc_mx (void *x_p);

+extern void ht_identifier_pch_nx (void *x_p);

+extern void ht_identifier_pch_nx (void *this_obj, void *x_p,
gt_pointer_operator op, void *cookie);

+

+void

+ht_identifier_ggc_mx (void *x_p)

+{

+ struct ht_identifier * x = (struct ht_identifier *)x_p;

+ struct ht_identifier * xlimit = x;

+ while (ggc_test_and_set_mark (xlimit))

+ xlimit = ((*xlimit).next);

+ while (x != xlimit)

+ {

+ union tree_node * const x0 = ((*x).next) ? HT_IDENT_TO_GCC_IDENT
(((*x).next)) : NULL;

+ gt_ggc_m_9tree_node (x0);

+ x = ((*x).next);

+ }

+}

+

+void

+ht_identifier_pch_nx (void *x_p)

+{

+ struct ht_identifier * x = (struct ht_identifier *)x_p;

+ struct ht_identifier * xlimit = x;

+ while (gt_pch_note_object (xlimit, xlimit, ht_identifier_pch_nx))

+ xlimit = ((*xlimit).next);

+ while (x != xlimit)

+ {

+ union tree_node * const x0 = ((*x).next) ? HT_IDENT_TO_GCC_IDENT
(((*x).next)) : NULL;

+ gt_pch_n_9tree_node (x0);

+ x = ((*x).next);

+ }

+}

+

+void

+ht_identifier_pch_nx (void *this_obj, void *x_p, gt_pointer_operator
op, void *cookie)

+{

+ struct ht_identifier * x = (struct ht_identifier *)x_p;

+ op (((*x).str), cookie);

+ union tree_node * x0 = ((*x).next) ? HT_IDENT_TO_GCC_IDENT
(((*x).next)) : NULL;

+ op ((x0), cookie);

+ (*x).next = (x0) ? (GCC_IDENT_TO_HT_IDENT ((x0))) : NULL;

+}

+

+/* A pointer walker for entries of the struct string_pool_data. */

+

+void

+string_pool_data_pch_entries_walker (void *this_obj, void *x_p,
gt_pointer_operator op, void *cookie)

+{

+ struct string_pool_data * x ATTRIBUTE_UNUSED = (struct string_pool_data *)x_p;

+ size_t l0 = (size_t)(((*x)).nslots);

+ if ((*x).entries != NULL)

+ {

+ size_t i0;

+ for (i0 = 0; i0 != (size_t)(l0); i0++)

+ {

+ union tree_node * x0 = ((*x).entries[i0]) ? HT_IDENT_TO_GCC_IDENT
(((*x).entries[i0])) : NULL;

+ op ((x0), cookie);

+ (*x).entries[i0] = (x0) ? (GCC_IDENT_TO_HT_IDENT ((x0))) : NULL;

+ }

+ }

+}

+

+/* User-provided GC marking routines for the struct string_pool_data. */

+

+void

+gt_ggc_mx (string_pool_data *x)

+{

+ size_t l0 = (size_t)(((*x)).nslots);

+ if ((*x).entries != NULL)

+ {

+ size_t i0;

+ for (i0 = 0; i0 != (size_t)(l0); i0++)

+ {

+ ht_identifier_ggc_mx ((*x).entries[i0]);

+ union tree_node * const x0 = ((*x).entries[i0]) ?
HT_IDENT_TO_GCC_IDENT (((*x).entries[i0])) : NULL;

+ gt_ggc_m_9tree_node (x0);

+ }

+ ggc_mark ((*x).entries);

+ }

+}

+

+void

+gt_pch_nx (string_pool_data *x)

+{

+ size_t l0 = (size_t)(((*x)).nslots);

+ if ((*x).entries != NULL)

+ {

+ size_t i0;

+ for (i0 = 0; i0 != (size_t)(l0); i0++)

+ {

+ union tree_node * const x1 = ((*x).entries[i0]) ?
HT_IDENT_TO_GCC_IDENT (((*x).entries[i0])) : NULL;

+ gt_pch_n_9tree_node (x1);

+ ht_identifier_pch_nx ((*x).entries[i0]);

+ }

+ gt_pch_note_object ((*x).entries, x, string_pool_data_pch_entries_walker);

+ }

+}

+

+void

+gt_pch_nx (string_pool_data *x, gt_pointer_operator op, void *cookie)

+{

+ if ((*x).entries != NULL)

+ op (((*x).entries), cookie);

+}

+

#include gt-stringpool.h

diff --git a/libcpp/include/symtab.h 

Re: changing a collision resolution strategy of the symbol table of identifiers

[Ondřej Bílka]

On Sun, Oct 20, 2013 at 06:55:40PM +0600, Roman Gareev wrote:
 Dear gcc contributors,
 
 Recently I came across the list of ideas for speeding up GCC
 (http://gcc.gnu.org/wiki/Speedup_areas). Among others, there was
 suggested to replace identifier hash table with other data structure.
 
 Please find attached a patch, that switches the resolution strategy of
 a hash table used in the symbol table of identifiers from open
 addressing to separate chaining with linked list. I would be very
 grateful for your comments, feedback and ideas about further
 enhancements to gcc, in which I could take a part. I am pursuing
 master of science and looking for thesis theme, that is compiler
 related.
 
 Below are results of testing and the patch.
 
 During testing of the linux kernel (3.8.8) compilation time, the
 acquired results were the following: increasing by 0.17% for the
 version 4.8.0, increasing by 1.12% for the version 4.8.1, decreasing
 by 0.598% for trunk (this are average values).
 
 
 Tested x86_64-unknown-linux-gnu, applying to 4.8.0, 4.8.1 and trunk.
 
 
 diff --git a/gcc/stringpool.c b/gcc/stringpool.c
 
 index f4d0dae..cc696f7 100644
 
 --- a/gcc/stringpool.c
 
 +++ b/gcc/stringpool.c
 
 @@ -241,12 +241,8 @@ gt_pch_nx (unsigned char *x, gt_pointer_operator
 op, void *cookie)
 
 /* SPD is saved in the PCH file and holds the information needed
 
 to restore the string pool. */
 
 -struct GTY(()) string_pool_data {
 
 - ht_identifier_ptr *
 
 - GTY((length (%h.nslots),
 
Mail client broke it?