* [PATCH] Speed up qsort in IPA ICF
@ 2019-09-19 9:06 Martin Liška
2019-09-19 11:01 ` Richard Biener
0 siblings, 1 reply; 7+ messages in thread
From: Martin Liška @ 2019-09-19 9:06 UTC (permalink / raw)
To: gcc-patches; +Cc: Alexander Monakov
[-- Attachment #1: Type: text/plain, Size: 943 bytes --]
Hi.
As Alexander pointed out, the sort_congruence_class_groups_by_decl_uid is the most
expensive qsort operator in tramp3d compilation. It does unfortunate 7 pointer dereferences
via: DECL_UID (classes[i]->classes[0]->members[0]->decl). I'm suggesting to cache that
in congruence_class_group.
Patch can bootstrap on x86_64-linux-gnu and survives regression tests.
Ready to be installed?
Thanks,
Martin
gcc/ChangeLog:
2019-09-19 Martin Liska <mliska@suse.cz>
* ipa-icf.c (sort_sem_items_by_decl_uid): Simplify comparator.
(sort_congruence_classes_by_decl_uid): Likewise.
(sort_congruence_class_groups_by_decl_uid): Use
congruence_class_group::uid.
(sem_item_optimizer::merge_classes): Cache
DECL_UID (classes[i]->classes[0]->members[0]->decl).
* ipa-icf.h (struct congruence_class_group): New field.
---
gcc/ipa-icf.c | 29 +++++------------------------
gcc/ipa-icf.h | 1 +
2 files changed, 6 insertions(+), 24 deletions(-)
[-- Attachment #2: 0001-Speed-up-qsort-in-IPA-ICF.patch --]
[-- Type: text/x-patch, Size: 2044 bytes --]
diff --git a/gcc/ipa-icf.c b/gcc/ipa-icf.c
index c9c3cb4a331..d78635ad6b3 100644
--- a/gcc/ipa-icf.c
+++ b/gcc/ipa-icf.c
@@ -3350,13 +3350,7 @@ sort_sem_items_by_decl_uid (const void *a, const void *b)
int uid1 = DECL_UID (i1->decl);
int uid2 = DECL_UID (i2->decl);
-
- if (uid1 < uid2)
- return -1;
- else if (uid1 > uid2)
- return 1;
- else
- return 0;
+ return uid1 - uid2;
}
/* Sort pair of congruence_classes A and B by DECL_UID of the first member. */
@@ -3369,13 +3363,7 @@ sort_congruence_classes_by_decl_uid (const void *a, const void *b)
int uid1 = DECL_UID (c1->members[0]->decl);
int uid2 = DECL_UID (c2->members[0]->decl);
-
- if (uid1 < uid2)
- return -1;
- else if (uid1 > uid2)
- return 1;
- else
- return 0;
+ return uid1 - uid2;
}
/* Sort pair of congruence_class_groups A and B by
@@ -3388,16 +3376,7 @@ sort_congruence_class_groups_by_decl_uid (const void *a, const void *b)
= *(const congruence_class_group * const *)a;
const congruence_class_group *g2
= *(const congruence_class_group * const *)b;
-
- int uid1 = DECL_UID (g1->classes[0]->members[0]->decl);
- int uid2 = DECL_UID (g2->classes[0]->members[0]->decl);
-
- if (uid1 < uid2)
- return -1;
- else if (uid1 > uid2)
- return 1;
- else
- return 0;
+ return g1->uid - g2->uid;
}
/* After reduction is done, we can declare all items in a group
@@ -3450,6 +3429,8 @@ sem_item_optimizer::merge_classes (unsigned int prev_class_count)
it != m_classes.end (); ++it)
classes.quick_push (*it);
+ for (unsigned i = 0; i < classes.length (); i++)
+ classes[i]->uid = DECL_UID (classes[i]->classes[0]->members[0]->decl);
classes.qsort (sort_congruence_class_groups_by_decl_uid);
if (dump_file)
diff --git a/gcc/ipa-icf.h b/gcc/ipa-icf.h
index 2bf0f156ef6..e7bb4afcfee 100644
--- a/gcc/ipa-icf.h
+++ b/gcc/ipa-icf.h
@@ -461,6 +461,7 @@ struct congruence_class_group
{
hashval_t hash;
sem_item_type type;
+ int uid;
vec <congruence_class *> classes;
};
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] Speed up qsort in IPA ICF
2019-09-19 9:06 [PATCH] Speed up qsort in IPA ICF Martin Liška
@ 2019-09-19 11:01 ` Richard Biener
2019-09-19 13:02 ` Martin Liška
0 siblings, 1 reply; 7+ messages in thread
From: Richard Biener @ 2019-09-19 11:01 UTC (permalink / raw)
To: Martin Liška; +Cc: GCC Patches, Alexander Monakov
On Thu, Sep 19, 2019 at 11:06 AM Martin Liška <mliska@suse.cz> wrote:
>
> Hi.
>
> As Alexander pointed out, the sort_congruence_class_groups_by_decl_uid is the most
> expensive qsort operator in tramp3d compilation. It does unfortunate 7 pointer dereferences
> via: DECL_UID (classes[i]->classes[0]->members[0]->decl). I'm suggesting to cache that
> in congruence_class_group.
>
> Patch can bootstrap on x86_64-linux-gnu and survives regression tests.
>
> Ready to be installed?
Since we're populating the classes vector right before you could elide
the new field and do it in the same iteration by having
auto_vec <std::pair<congruence_class_group *, unsigned> > classes
and pushing *it, DECL_UID and then sorting by the readily available
UID in the data? That makes the sort use a linear memory region
w/o dereferences.
Richard.
> Thanks,
> Martin
>
> gcc/ChangeLog:
>
> 2019-09-19 Martin Liska <mliska@suse.cz>
>
> * ipa-icf.c (sort_sem_items_by_decl_uid): Simplify comparator.
> (sort_congruence_classes_by_decl_uid): Likewise.
> (sort_congruence_class_groups_by_decl_uid): Use
> congruence_class_group::uid.
> (sem_item_optimizer::merge_classes): Cache
> DECL_UID (classes[i]->classes[0]->members[0]->decl).
> * ipa-icf.h (struct congruence_class_group): New field.
> ---
> gcc/ipa-icf.c | 29 +++++------------------------
> gcc/ipa-icf.h | 1 +
> 2 files changed, 6 insertions(+), 24 deletions(-)
>
>
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] Speed up qsort in IPA ICF
2019-09-19 11:01 ` Richard Biener
@ 2019-09-19 13:02 ` Martin Liška
2019-09-19 13:09 ` Richard Biener
0 siblings, 1 reply; 7+ messages in thread
From: Martin Liška @ 2019-09-19 13:02 UTC (permalink / raw)
To: Richard Biener; +Cc: GCC Patches, Alexander Monakov
[-- Attachment #1: Type: text/plain, Size: 1623 bytes --]
On 9/19/19 1:01 PM, Richard Biener wrote:
> On Thu, Sep 19, 2019 at 11:06 AM Martin Liška <mliska@suse.cz> wrote:
>>
>> Hi.
>>
>> As Alexander pointed out, the sort_congruence_class_groups_by_decl_uid is the most
>> expensive qsort operator in tramp3d compilation. It does unfortunate 7 pointer dereferences
>> via: DECL_UID (classes[i]->classes[0]->members[0]->decl). I'm suggesting to cache that
>> in congruence_class_group.
>>
>> Patch can bootstrap on x86_64-linux-gnu and survives regression tests.
>>
>> Ready to be installed?
>
> Since we're populating the classes vector right before you could elide
> the new field and do it in the same iteration by having
>
> auto_vec <std::pair<congruence_class_group *, unsigned> > classes
>
> and pushing *it, DECL_UID and then sorting by the readily available
> UID in the data? That makes the sort use a linear memory region
> w/o dereferences.
Good point, there's a tested patch.
Martin
>
> Richard.
>
>> Thanks,
>> Martin
>>
>> gcc/ChangeLog:
>>
>> 2019-09-19 Martin Liska <mliska@suse.cz>
>>
>> * ipa-icf.c (sort_sem_items_by_decl_uid): Simplify comparator.
>> (sort_congruence_classes_by_decl_uid): Likewise.
>> (sort_congruence_class_groups_by_decl_uid): Use
>> congruence_class_group::uid.
>> (sem_item_optimizer::merge_classes): Cache
>> DECL_UID (classes[i]->classes[0]->members[0]->decl).
>> * ipa-icf.h (struct congruence_class_group): New field.
>> ---
>> gcc/ipa-icf.c | 29 +++++------------------------
>> gcc/ipa-icf.h | 1 +
>> 2 files changed, 6 insertions(+), 24 deletions(-)
>>
>>
[-- Attachment #2: 0001-Speed-up-qsort-in-IPA-ICF.patch --]
[-- Type: text/x-patch, Size: 3561 bytes --]
From 05a78667e932e554dfbd69433ad66242cbca6492 Mon Sep 17 00:00:00 2001
From: Martin Liska <mliska@suse.cz>
Date: Thu, 19 Sep 2019 09:41:39 +0200
Subject: [PATCH] Speed up qsort in IPA ICF.
gcc/ChangeLog:
2019-09-19 Martin Liska <mliska@suse.cz>
* ipa-icf.c (sort_sem_items_by_decl_uid): Simplify comparator.
(sort_congruence_classes_by_decl_uid): Likewise.
(sort_congruence_class_groups_by_decl_uid): Use std::pair for
easier sorting.
(sem_item_optimizer::merge_classes): Likewise.
---
gcc/ipa-icf.c | 49 ++++++++++++++++---------------------------------
1 file changed, 16 insertions(+), 33 deletions(-)
diff --git a/gcc/ipa-icf.c b/gcc/ipa-icf.c
index c9c3cb4a331..59b7f8b1b9d 100644
--- a/gcc/ipa-icf.c
+++ b/gcc/ipa-icf.c
@@ -3350,13 +3350,7 @@ sort_sem_items_by_decl_uid (const void *a, const void *b)
int uid1 = DECL_UID (i1->decl);
int uid2 = DECL_UID (i2->decl);
-
- if (uid1 < uid2)
- return -1;
- else if (uid1 > uid2)
- return 1;
- else
- return 0;
+ return uid1 - uid2;
}
/* Sort pair of congruence_classes A and B by DECL_UID of the first member. */
@@ -3369,13 +3363,7 @@ sort_congruence_classes_by_decl_uid (const void *a, const void *b)
int uid1 = DECL_UID (c1->members[0]->decl);
int uid2 = DECL_UID (c2->members[0]->decl);
-
- if (uid1 < uid2)
- return -1;
- else if (uid1 > uid2)
- return 1;
- else
- return 0;
+ return uid1 - uid2;
}
/* Sort pair of congruence_class_groups A and B by
@@ -3384,20 +3372,11 @@ sort_congruence_classes_by_decl_uid (const void *a, const void *b)
static int
sort_congruence_class_groups_by_decl_uid (const void *a, const void *b)
{
- const congruence_class_group *g1
- = *(const congruence_class_group * const *)a;
- const congruence_class_group *g2
- = *(const congruence_class_group * const *)b;
-
- int uid1 = DECL_UID (g1->classes[0]->members[0]->decl);
- int uid2 = DECL_UID (g2->classes[0]->members[0]->decl);
-
- if (uid1 < uid2)
- return -1;
- else if (uid1 > uid2)
- return 1;
- else
- return 0;
+ const std::pair<congruence_class_group *, int> *g1
+ = *(const std::pair<congruence_class_group *, int> *const *) a;
+ const std::pair<congruence_class_group *, int> *g2
+ = *(const std::pair<congruence_class_group *, int> *const *) b;
+ return g1->second - g2->second;
}
/* After reduction is done, we can declare all items in a group
@@ -3445,10 +3424,14 @@ sem_item_optimizer::merge_classes (unsigned int prev_class_count)
}
}
- auto_vec <congruence_class_group *> classes (m_classes.elements ());
+ auto_vec<std::pair<congruence_class_group *, int> > classes (
+ m_classes.elements ());
for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
it != m_classes.end (); ++it)
- classes.quick_push (*it);
+ {
+ int uid = DECL_UID ((*it)->classes[0]->members[0]->decl);
+ classes.quick_push (std::pair<congruence_class_group *, int> (*it, uid));
+ }
classes.qsort (sort_congruence_class_groups_by_decl_uid);
@@ -3470,11 +3453,11 @@ sem_item_optimizer::merge_classes (unsigned int prev_class_count)
}
unsigned int l;
- congruence_class_group *it;
+ std::pair<congruence_class_group *, int> *it;
FOR_EACH_VEC_ELT (classes, l, it)
- for (unsigned int i = 0; i < it->classes.length (); i++)
+ for (unsigned int i = 0; i < it->first->classes.length (); i++)
{
- congruence_class *c = it->classes[i];
+ congruence_class *c = it->first->classes[i];
if (c->members.length () == 1)
continue;
--
2.23.0
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] Speed up qsort in IPA ICF
2019-09-19 13:02 ` Martin Liška
@ 2019-09-19 13:09 ` Richard Biener
2019-09-19 13:15 ` Alexander Monakov
0 siblings, 1 reply; 7+ messages in thread
From: Richard Biener @ 2019-09-19 13:09 UTC (permalink / raw)
To: Martin Liška; +Cc: GCC Patches, Alexander Monakov
On Thu, Sep 19, 2019 at 3:02 PM Martin Liška <mliska@suse.cz> wrote:
>
> On 9/19/19 1:01 PM, Richard Biener wrote:
> > On Thu, Sep 19, 2019 at 11:06 AM Martin Liška <mliska@suse.cz> wrote:
> >>
> >> Hi.
> >>
> >> As Alexander pointed out, the sort_congruence_class_groups_by_decl_uid is the most
> >> expensive qsort operator in tramp3d compilation. It does unfortunate 7 pointer dereferences
> >> via: DECL_UID (classes[i]->classes[0]->members[0]->decl). I'm suggesting to cache that
> >> in congruence_class_group.
> >>
> >> Patch can bootstrap on x86_64-linux-gnu and survives regression tests.
> >>
> >> Ready to be installed?
> >
> > Since we're populating the classes vector right before you could elide
> > the new field and do it in the same iteration by having
> >
> > auto_vec <std::pair<congruence_class_group *, unsigned> > classes
> >
> > and pushing *it, DECL_UID and then sorting by the readily available
> > UID in the data? That makes the sort use a linear memory region
> > w/o dereferences.
>
> Good point, there's a tested patch.
OK.
Thanks,
Richard.
> Martin
>
> >
> > Richard.
> >
> >> Thanks,
> >> Martin
> >>
> >> gcc/ChangeLog:
> >>
> >> 2019-09-19 Martin Liska <mliska@suse.cz>
> >>
> >> * ipa-icf.c (sort_sem_items_by_decl_uid): Simplify comparator.
> >> (sort_congruence_classes_by_decl_uid): Likewise.
> >> (sort_congruence_class_groups_by_decl_uid): Use
> >> congruence_class_group::uid.
> >> (sem_item_optimizer::merge_classes): Cache
> >> DECL_UID (classes[i]->classes[0]->members[0]->decl).
> >> * ipa-icf.h (struct congruence_class_group): New field.
> >> ---
> >> gcc/ipa-icf.c | 29 +++++------------------------
> >> gcc/ipa-icf.h | 1 +
> >> 2 files changed, 6 insertions(+), 24 deletions(-)
> >>
> >>
>
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] Speed up qsort in IPA ICF
2019-09-19 13:09 ` Richard Biener
@ 2019-09-19 13:15 ` Alexander Monakov
2019-09-19 13:18 ` Richard Biener
0 siblings, 1 reply; 7+ messages in thread
From: Alexander Monakov @ 2019-09-19 13:15 UTC (permalink / raw)
To: Richard Biener; +Cc: Martin Liška, GCC Patches
On Thu, 19 Sep 2019, Richard Biener wrote:
> > Good point, there's a tested patch.
>
> OK.
Hold on, is the new comparator really correct?
@@ -3384,20 +3372,11 @@ sort_congruence_classes_by_decl_uid (const void *a, const void *b)
static int
sort_congruence_class_groups_by_decl_uid (const void *a, const void *b)
{
- const congruence_class_group *g1
- = *(const congruence_class_group * const *)a;
- const congruence_class_group *g2
- = *(const congruence_class_group * const *)b;
-
- int uid1 = DECL_UID (g1->classes[0]->members[0]->decl);
- int uid2 = DECL_UID (g2->classes[0]->members[0]->decl);
-
- if (uid1 < uid2)
- return -1;
- else if (uid1 > uid2)
- return 1;
- else
- return 0;
+ const std::pair<congruence_class_group *, int> *g1
+ = *(const std::pair<congruence_class_group *, int> *const *) a;
+ const std::pair<congruence_class_group *, int> *g2
+ = *(const std::pair<congruence_class_group *, int> *const *) b;
+ return g1->second - g2->second;
}
AFAICT the vec holds pairs, not pointers to pairs, so why does the comparator
cast to a pointer-to-pointer-to-pair? Shouldn't it read
const std::pair<congruence_class_group *, int> *g1
= (const std::pair<congruence_class_group *, int> *) a;
Thanks.
Alexander
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] Speed up qsort in IPA ICF
2019-09-19 13:15 ` Alexander Monakov
@ 2019-09-19 13:18 ` Richard Biener
2019-09-19 13:32 ` Martin Liška
0 siblings, 1 reply; 7+ messages in thread
From: Richard Biener @ 2019-09-19 13:18 UTC (permalink / raw)
To: Alexander Monakov; +Cc: Martin Liška, GCC Patches
On Thu, Sep 19, 2019 at 3:15 PM Alexander Monakov <amonakov@ispras.ru> wrote:
>
> On Thu, 19 Sep 2019, Richard Biener wrote:
>
> > > Good point, there's a tested patch.
> >
> > OK.
>
> Hold on, is the new comparator really correct?
>
>
> @@ -3384,20 +3372,11 @@ sort_congruence_classes_by_decl_uid (const void *a, const void *b)
> static int
> sort_congruence_class_groups_by_decl_uid (const void *a, const void *b)
> {
> - const congruence_class_group *g1
> - = *(const congruence_class_group * const *)a;
> - const congruence_class_group *g2
> - = *(const congruence_class_group * const *)b;
> -
> - int uid1 = DECL_UID (g1->classes[0]->members[0]->decl);
> - int uid2 = DECL_UID (g2->classes[0]->members[0]->decl);
> -
> - if (uid1 < uid2)
> - return -1;
> - else if (uid1 > uid2)
> - return 1;
> - else
> - return 0;
> + const std::pair<congruence_class_group *, int> *g1
> + = *(const std::pair<congruence_class_group *, int> *const *) a;
> + const std::pair<congruence_class_group *, int> *g2
> + = *(const std::pair<congruence_class_group *, int> *const *) b;
> + return g1->second - g2->second;
> }
>
>
> AFAICT the vec holds pairs, not pointers to pairs, so why does the comparator
> cast to a pointer-to-pointer-to-pair? Shouldn't it read
>
> const std::pair<congruence_class_group *, int> *g1
> = (const std::pair<congruence_class_group *, int> *) a;
Indeed. We need static type correctness for the comparator :/
Richard.
> Thanks.
> Alexander
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] Speed up qsort in IPA ICF
2019-09-19 13:18 ` Richard Biener
@ 2019-09-19 13:32 ` Martin Liška
0 siblings, 0 replies; 7+ messages in thread
From: Martin Liška @ 2019-09-19 13:32 UTC (permalink / raw)
To: Richard Biener, Alexander Monakov; +Cc: GCC Patches
[-- Attachment #1: Type: text/plain, Size: 1733 bytes --]
On 9/19/19 3:18 PM, Richard Biener wrote:
> On Thu, Sep 19, 2019 at 3:15 PM Alexander Monakov <amonakov@ispras.ru> wrote:
>>
>> On Thu, 19 Sep 2019, Richard Biener wrote:
>>
>>>> Good point, there's a tested patch.
>>>
>>> OK.
>>
>> Hold on, is the new comparator really correct?
>>
>>
>> @@ -3384,20 +3372,11 @@ sort_congruence_classes_by_decl_uid (const void *a, const void *b)
>> static int
>> sort_congruence_class_groups_by_decl_uid (const void *a, const void *b)
>> {
>> - const congruence_class_group *g1
>> - = *(const congruence_class_group * const *)a;
>> - const congruence_class_group *g2
>> - = *(const congruence_class_group * const *)b;
>> -
>> - int uid1 = DECL_UID (g1->classes[0]->members[0]->decl);
>> - int uid2 = DECL_UID (g2->classes[0]->members[0]->decl);
>> -
>> - if (uid1 < uid2)
>> - return -1;
>> - else if (uid1 > uid2)
>> - return 1;
>> - else
>> - return 0;
>> + const std::pair<congruence_class_group *, int> *g1
>> + = *(const std::pair<congruence_class_group *, int> *const *) a;
>> + const std::pair<congruence_class_group *, int> *g2
>> + = *(const std::pair<congruence_class_group *, int> *const *) b;
>> + return g1->second - g2->second;
>> }
>>
>>
>> AFAICT the vec holds pairs, not pointers to pairs, so why does the comparator
>> cast to a pointer-to-pointer-to-pair? Shouldn't it read
>>
>> const std::pair<congruence_class_group *, int> *g1
>> = (const std::pair<congruence_class_group *, int> *) a;
>
> Indeed. We need static type correctness for the comparator :/
Ooops, sorry for the mistake. I'm testing the following patch.
I checked in debugger that uids are valid for a simple test-case.
Martin
>
> Richard.
>
>> Thanks.
>> Alexander
[-- Attachment #2: 0001-Fix-cast-in-sort_congruence_class_groups_by_decl_uid.patch --]
[-- Type: text/x-patch, Size: 1083 bytes --]
From 5f94530ee52b254a1e3cdfc0f4db4222a6b77a14 Mon Sep 17 00:00:00 2001
From: Martin Liska <mliska@suse.cz>
Date: Thu, 19 Sep 2019 15:27:20 +0200
Subject: [PATCH] Fix cast in sort_congruence_class_groups_by_decl_uid.
gcc/ChangeLog:
2019-09-19 Martin Liska <mliska@suse.cz>
* ipa-icf.c (sort_congruence_class_groups_by_decl_uid):
Use proper casting.
---
gcc/ipa-icf.c | 4 ++--
1 file changed, 2 insertions(+), 2 deletions(-)
diff --git a/gcc/ipa-icf.c b/gcc/ipa-icf.c
index 59b7f8b1b9d..009aeb487dd 100644
--- a/gcc/ipa-icf.c
+++ b/gcc/ipa-icf.c
@@ -3373,9 +3373,9 @@ static int
sort_congruence_class_groups_by_decl_uid (const void *a, const void *b)
{
const std::pair<congruence_class_group *, int> *g1
- = *(const std::pair<congruence_class_group *, int> *const *) a;
+ = (const std::pair<congruence_class_group *, int> *) a;
const std::pair<congruence_class_group *, int> *g2
- = *(const std::pair<congruence_class_group *, int> *const *) b;
+ = (const std::pair<congruence_class_group *, int> *) b;
return g1->second - g2->second;
}
--
2.23.0
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2019-09-19 13:32 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-09-19 9:06 [PATCH] Speed up qsort in IPA ICF Martin Liška
2019-09-19 11:01 ` Richard Biener
2019-09-19 13:02 ` Martin Liška
2019-09-19 13:09 ` Richard Biener
2019-09-19 13:15 ` Alexander Monakov
2019-09-19 13:18 ` Richard Biener
2019-09-19 13:32 ` Martin Liška
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).