diff mbox series

[RFC] Add vec::ordered_remove_if

Message ID 86f69704-0721-a81b-96d9-d98a3bbd53ac@mentor.com
State New
Headers show
Series [RFC] Add vec::ordered_remove_if | expand

Commit Message

Tom de Vries Dec. 29, 2017, 1:55 p.m. UTC 
[ was: Re: [libgomp, openacc, openmp, PR83046] Prune removed funcs from 
offload table ]

On 12/28/2017 05:06 PM, Jakub Jelinek wrote:
> On Thu, Dec 28, 2017 at 04:53:29PM +0100, Tom de Vries wrote:
>> --- a/gcc/lto-cgraph.c
>> +++ b/gcc/lto-cgraph.c
>> @@ -1111,6 +1111,16 @@ output_offload_tables (void)
>>     struct lto_simple_output_block *ob
>>       = lto_create_simple_output_block (LTO_section_offload_table);
>>   
>> +  for (unsigned i = 0; i < vec_safe_length (offload_funcs);)
>> +    {
>> +      if (!cgraph_node::get ((*offload_funcs)[i]))
>> +	{
>> +	  offload_funcs->ordered_remove (i);
>> +	  continue;
>> +	}
>> +      i++;
>> +    }

> This has O(n^2) complexity for n == vec_safe_length (offload_funcs).
> Can't you instead just have 2 IVs, one for where we read the vector elt and
> one for where we write it if the 2 are different, then truncate the vector
> if needed at the end?

I wonder if it makes sense to add this function to the vec interface.

Any comments?

Thanks,
- Tom

Comments

Richard Biener Jan. 2, 2018, 2:08 p.m. UTC | #1 
On Fri, Dec 29, 2017 at 2:55 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
> [ was: Re: [libgomp, openacc, openmp, PR83046] Prune removed funcs from
> offload table ]
>
> On 12/28/2017 05:06 PM, Jakub Jelinek wrote:
>>
>> On Thu, Dec 28, 2017 at 04:53:29PM +0100, Tom de Vries wrote:
>>>
>>> --- a/gcc/lto-cgraph.c
>>> +++ b/gcc/lto-cgraph.c
>>> @@ -1111,6 +1111,16 @@ output_offload_tables (void)
>>>     struct lto_simple_output_block *ob
>>>       = lto_create_simple_output_block (LTO_section_offload_table);
>>>   +  for (unsigned i = 0; i < vec_safe_length (offload_funcs);)
>>> +    {
>>> +      if (!cgraph_node::get ((*offload_funcs)[i]))
>>> +       {
>>> +         offload_funcs->ordered_remove (i);
>>> +         continue;
>>> +       }
>>> +      i++;
>>> +    }
>
>
>> This has O(n^2) complexity for n == vec_safe_length (offload_funcs).
>> Can't you instead just have 2 IVs, one for where we read the vector elt
>> and
>> one for where we write it if the 2 are different, then truncate the vector
>> if needed at the end?
>
>
> I wonder if it makes sense to add this function to the vec interface.
>
> Any comments?

Hmm.  We do have quite some cases in the tree doing this kind of
operation - can you try finding one or two and see if it fits?

If we only could use lambdas here...

Oh, and I somehow miss a start/end index for operating on a vector part?

Richard.

> Thanks,
> - Tom
diff mbox series

Patch

Add vec::ordered_remove_if

---
 gcc/vec.c | 21 +++++++++++++++++++++
 gcc/vec.h | 39 +++++++++++++++++++++++++++++++++++++++
 2 files changed, 60 insertions(+)

diff --git a/gcc/vec.c b/gcc/vec.c
index 9a80f34..91e2464 100644
--- a/gcc/vec.c
+++ b/gcc/vec.c
@@ -403,6 +403,26 @@  test_ordered_remove ()
   ASSERT_EQ (9, v.length ());
 }
 
+static bool
+remove_5_7_p (const int &a)
+{
+  return a == 5 || a == 7;
+}
+
+/* Verify that vec::ordered_remove_if works correctly.  */
+
+static void
+test_ordered_remove_if (void)
+{
+  auto_vec <int> v;
+  safe_push_range (v, 0, 10);
+  v.ordered_remove_if (remove_5_7_p);
+  ASSERT_EQ (4, v[4]);
+  ASSERT_EQ (6, v[5]);
+  ASSERT_EQ (8, v[6]);
+  ASSERT_EQ (8, v.length ());
+}
+
 /* Verify that vec::unordered_remove works correctly.  */
 
 static void
@@ -464,6 +484,7 @@  vec_c_tests ()
   test_pop ();
   test_safe_insert ();
   test_ordered_remove ();
+  test_ordered_remove_if ();
   test_unordered_remove ();
   test_block_remove ();
   test_qsort ();
diff --git a/gcc/vec.h b/gcc/vec.h
index f55a41f..857e4f4 100644
--- a/gcc/vec.h
+++ b/gcc/vec.h
@@ -571,6 +571,7 @@  public:
   void truncate (unsigned);
   void quick_insert (unsigned, const T &);
   void ordered_remove (unsigned);
+  void ordered_remove_if (bool (*) (const T &));
   void unordered_remove (unsigned);
   void block_remove (unsigned, unsigned);
   void qsort (int (*) (const void *, const void *));
@@ -1013,6 +1014,31 @@  vec<T, A, vl_embed>::ordered_remove (unsigned ix)
 }
 
 
+/* Remove all elements from this vector for which REMOVE_ELEM_P (elem) holds.
+   Ordering of remaining elements is preserved.  This is an an O(N)
+   operation.  */
+
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::ordered_remove_if (bool (*remove_elem_p) (const T &))
+{
+  unsigned int n = length ();
+  unsigned int write_index = 0;
+  for (unsigned int read_index = 0; read_index < n; ++read_index)
+    {
+      bool remove_p = remove_elem_p (read_index);
+      if (remove_p)
+	continue;
+
+      if (read_index != write_index)
+	m_vecdata[write_index] = m_vecdata[read_index];
+
+      write_index++;
+    }
+  truncate (write_index);
+}
+
+
 /* Remove an element from the IXth position of this vector.  Ordering of
    remaining elements is destroyed.  This is an O(1) operation.  */
 
@@ -1334,6 +1360,7 @@  public:
   void quick_insert (unsigned, const T &);
   void safe_insert (unsigned, const T & CXX_MEM_STAT_INFO);
   void ordered_remove (unsigned);
+  void ordered_remove_if (bool (*) (const T &));
   void unordered_remove (unsigned);
   void block_remove (unsigned, unsigned);
   void qsort (int (*) (const void *, const void *));
@@ -1779,6 +1806,18 @@  vec<T, va_heap, vl_ptr>::ordered_remove (unsigned ix)
 }
 
 
+/* Remove all elements from this vector for which REMOVE_ELEM_P (elem) holds.
+   Ordering of remaining elements is preserved.  This is an an O(N)
+   operation.  */
+
+template<typename T>
+inline void
+vec<T, va_heap, vl_ptr>::ordered_remove_if (bool (*remove_elem_p) (const T &))
+{
+  m_vec->ordered_remove_if (remove_elem_p);
+}
+
+
 /* Remove an element from the IXth position of this vector.  Ordering
    of remaining elements is destroyed.  This is an O(1) operation.  */