Add method Vector::shrinkToReasonableCapacity()

Add method Vector::shrinkToReasonableCapacity()

Shrinks vector capacity to the vector size if capacity is excessivly big.

BUG=

Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=173420

[ostap, 2014-04-15 22:16:42]

By the discussion from here: https://codereview.chromium.org/183663030/

[danakj, 2014-04-15 22:21:40]

https://codereview.chromium.org/239603005/diff/1/Source/wtf/Vector.h
File Source/wtf/Vector.h (right):

https://codereview.chromium.org/239603005/diff/1/Source/wtf/Vector.h#newcode681
Source/wtf/Vector.h:681: shrinkToFit();
How about: shrinkCapacity(size() * 2)?

So a series of
for i to 1000 {
  insert()
  shrinkToReasonableCapacity()
}
don't cause some crazy behaviour?

Also, do you need to check for integer overflow here?

[ostap, 2014-04-15 22:46:34]

https://codereview.chromium.org/239603005/diff/1/Source/wtf/Vector.h
File Source/wtf/Vector.h (right):

https://codereview.chromium.org/239603005/diff/1/Source/wtf/Vector.h#newcode681
Source/wtf/Vector.h:681: shrinkToFit();
On 2014/04/15 22:21:40, danakj wrote:
> How about: shrinkCapacity(size() * 2)?

I thought that shrinkToFit() would be better for memory saving.
May be use value from ::expandCapacity():

shrinkCapacity(size() + size() / 4 + 1)

?

> So a series of
> for i to 1000 {
>   insert()
>   shrinkToReasonableCapacity()
> }
> don't cause some crazy behaviour?

Why it would? In this cycle capacity will be always less than size * 2.

> Also, do you need to check for integer overflow here?

There is comment in ::expandCapacity() that allocations can't be more than (2^31
- 1) on 32 bit systems and more than 2^32 on 64 bit, so size() * 2 normally
cannot produce integer overflow.

[danakj, 2014-04-15 22:53:25]

https://codereview.chromium.org/239603005/diff/1/Source/wtf/Vector.h
File Source/wtf/Vector.h (right):

https://codereview.chromium.org/239603005/diff/1/Source/wtf/Vector.h#newcode681
Source/wtf/Vector.h:681: shrinkToFit();
On 2014/04/15 22:46:34, ostap wrote:
> On 2014/04/15 22:21:40, danakj wrote:
> > How about: shrinkCapacity(size() * 2)?
> 
> I thought that shrinkToFit() would be better for memory saving.
> May be use value from ::expandCapacity():
> 
> shrinkCapacity(size() + size() / 4 + 1)
> 
> ?

Oh, yes I agree. I didn't read the method far enough, stopped at the *= 2;

> 
> > So a series of
> > for i to 1000 {
> >   insert()
> >   shrinkToReasonableCapacity()
> > }
> > don't cause some crazy behaviour?
> 
> Why it would? In this cycle capacity will be always less than size * 2.

shrinkToFit() does shrinkCapacity(size()), so the next insert would mean that we
have to expandCapacity() each time, right?

> > Also, do you need to check for integer overflow here?
> 
> There is comment in ::expandCapacity() that allocations can't be more than
(2^31
> - 1) on 32 bit systems and more than 2^32 on 64 bit, so size() * 2 normally
> cannot produce integer overflow.

[ostap, 2014-04-15 23:17:15]

On 2014/04/15 22:53:25, danakj wrote:
> https://codereview.chromium.org/239603005/diff/1/Source/wtf/Vector.h
> File Source/wtf/Vector.h (right):
> 
>
https://codereview.chromium.org/239603005/diff/1/Source/wtf/Vector.h#newcode681
> Source/wtf/Vector.h:681: shrinkToFit();
> On 2014/04/15 22:46:34, ostap wrote:
> > On 2014/04/15 22:21:40, danakj wrote:
> > > How about: shrinkCapacity(size() * 2)?
> > 
> > I thought that shrinkToFit() would be better for memory saving.
> > May be use value from ::expandCapacity():
> > 
> > shrinkCapacity(size() + size() / 4 + 1)
> > 
> > ?
> 
> Oh, yes I agree. I didn't read the method far enough, stopped at the *= 2;

Done

> > > So a series of
> > > for i to 1000 {
> > >   insert()
> > >   shrinkToReasonableCapacity()
> > > }
> > > don't cause some crazy behaviour?
> > 
> > Why it would? In this cycle capacity will be always less than size * 2.
> 
> shrinkToFit() does shrinkCapacity(size()), so the next insert would mean that
we
> have to expandCapacity() each time, right?

But shrinkToFit() will be never executed because vector capacity will be never
bigger than (size() * 2). Even if we do (size() * 2) expand of capacity, adding
element makes capacity() below (size() * 2).
Actually, I realized that in most cases there will be no shrinking, so I added
UNLIKELY() to the condition to help compiler with optimizations.

[abarth-chromium, 2014-04-16 00:58:38]

https://codereview.chromium.org/239603005/diff/20001/Source/wtf/Vector.h
File Source/wtf/Vector.h (right):

https://codereview.chromium.org/239603005/diff/20001/Source/wtf/Vector.h#newc...
Source/wtf/Vector.h:680: if (UNLIKELY(size() * 2 < capacity()))
Sorry to leave a drive-by comment, but please don't add UNLIKELY macros unless
you have a benchmark (even a microbenchmark) that shows the win.  These macros
rarely make any measurable difference.

[Mikhail, 2014-04-16 08:29:13]

https://codereview.chromium.org/239603005/diff/20001/Source/wtf/Vector.h
File Source/wtf/Vector.h (right):

https://codereview.chromium.org/239603005/diff/20001/Source/wtf/Vector.h#newc...
Source/wtf/Vector.h:678: void shrinkToReasonableCapacity()
Is this method supposed to be called so frequently that it's worth adding it to
Vector class? The client can always have it as a free function

void shrinkToReasonableCapacity(Vector& vector)
{
 ...
}

[danakj, 2014-04-16 15:55:06]

LGTM % abarth and/or OWNERS.

https://codereview.chromium.org/239603005/diff/20001/Source/wtf/Vector.h
File Source/wtf/Vector.h (right):

https://codereview.chromium.org/239603005/diff/20001/Source/wtf/Vector.h#newc...
Source/wtf/Vector.h:678: void shrinkToReasonableCapacity()
On 2014/04/16 08:29:14, mikhail.pozdnyakov wrote:
> Is this method supposed to be called so frequently that it's worth adding it
to
> Vector class? The client can always have it as a free function
> 
> void shrinkToReasonableCapacity(Vector& vector)
> {
>  ...
> }

shrinkCapacity() is currently private, so this needs to be added, or something
else needs to be made public.

[ostap, 2014-04-16 16:04:15]

On 2014/04/16 08:29:13, mikhail.pozdnyakov wrote:
> https://codereview.chromium.org/239603005/diff/20001/Source/wtf/Vector.h
> File Source/wtf/Vector.h (right):
> 
>
https://codereview.chromium.org/239603005/diff/20001/Source/wtf/Vector.h#newc...
> Source/wtf/Vector.h:678: void shrinkToReasonableCapacity()
> Is this method supposed to be called so frequently that it's worth adding it
to
> Vector class? The client can always have it as a free function
> 
> void shrinkToReasonableCapacity(Vector& vector)
> {
>  ...
> }

I think shrinkToReasonableCapacity is definitely good to have. Use of
shrinkToFit can cause too many reallocations. And shrinkToReasonableCapacity in
most cases will be no-op, but still save memory if there is a lot of unused
capacity.
Since shrinkCapacity is private, I had to add this method to Vector class.

[ostap, 2014-04-16 16:11:02]

https://codereview.chromium.org/239603005/diff/20001/Source/wtf/Vector.h
File Source/wtf/Vector.h (right):

https://codereview.chromium.org/239603005/diff/20001/Source/wtf/Vector.h#newc...
Source/wtf/Vector.h:680: if (UNLIKELY(size() * 2 < capacity()))
On 2014/04/16 00:58:38, abarth wrote:
> Sorry to leave a drive-by comment, but please don't add UNLIKELY macros unless
> you have a benchmark (even a microbenchmark) that shows the win.  These macros
> rarely make any measurable difference.

Thanks.
I tested. It really makes no difference.

[Mikhail, 2014-04-16 21:06:07]

On 2014/04/16 16:04:15, ostap wrote:
> On 2014/04/16 08:29:13, mikhail.pozdnyakov wrote:
> > https://codereview.chromium.org/239603005/diff/20001/Source/wtf/Vector.h
> > File Source/wtf/Vector.h (right):
> > 
> >
>
https://codereview.chromium.org/239603005/diff/20001/Source/wtf/Vector.h#newc...
> > Source/wtf/Vector.h:678: void shrinkToReasonableCapacity()
> > Is this method supposed to be called so frequently that it's worth adding it
> to
> > Vector class? The client can always have it as a free function
> > 
> > void shrinkToReasonableCapacity(Vector& vector)
> > {
> >  ...
> > }
> 
> I think shrinkToReasonableCapacity is definitely good to have. Use of
> shrinkToFit can cause too many reallocations. And shrinkToReasonableCapacity
in
> most cases will be no-op, but still save memory if there is a lot of unused
> capacity.
> Since shrinkCapacity is private, I had to add this method to Vector class.

I see your point, but isn't it better to make 'shrinkCapacity' public?
(it used to be public before r157740 , and I did not realize it is private now)

[danakj, 2014-04-16 21:15:04]

On Wed, Apr 16, 2014 at 5:06 PM, <mikhail.pozdnyakov@intel.com> wrote:

> On 2014/04/16 16:04:15, ostap wrote:
>
>> On 2014/04/16 08:29:13, mikhail.pozdnyakov wrote:
>> > https://codereview.chromium.org/239603005/diff/20001/
>> Source/wtf/Vector.h
>> > File Source/wtf/Vector.h (right):
>> >
>> >
>>
>
> https://codereview.chromium.org/239603005/diff/20001/
> Source/wtf/Vector.h#newcode678
>
>> > Source/wtf/Vector.h:678: void shrinkToReasonableCapacity()
>> > Is this method supposed to be called so frequently that it's worth
>> adding it
>> to
>> > Vector class? The client can always have it as a free function
>> >
>> > void shrinkToReasonableCapacity(Vector& vector)
>> > {
>> >  ...
>> > }
>>
>
>  I think shrinkToReasonableCapacity is definitely good to have. Use of
>> shrinkToFit can cause too many reallocations. And
>> shrinkToReasonableCapacity
>>
> in
>
>> most cases will be no-op, but still save memory if there is a lot of
>> unused
>> capacity.
>> Since shrinkCapacity is private, I had to add this method to Vector class.
>>
>
> I see your point, but isn't it better to make 'shrinkCapacity' public?
> (it used to be public before r157740 , and I did not realize it is private
> now)
>

I don't think it is, because this method wants to use Vector-internal
knowledge, like break points for growing and how much it grows by.

To unsubscribe from this group and stop receiving emails from it, send an email
to blink-reviews+unsubscribe@chromium.org.

[abarth-chromium, 2014-04-17 19:21:35]

https://codereview.chromium.org/239603005/diff/40001/Source/wtf/Vector.h
File Source/wtf/Vector.h (right):

https://codereview.chromium.org/239603005/diff/40001/Source/wtf/Vector.h#newc...
Source/wtf/Vector.h:681: shrinkCapacity(size() + size() / 4 + 1);
Is there a problem with integer overflow in this code?

See void Vector<T, inlineCapacity, Allocator>::expandCapacity(size_t
newMinCapacity) for some worries about integer overflow in a similar codepath.

[ostap, 2014-04-17 21:34:43]

On 2014/04/17 19:21:35, abarth wrote:
> https://codereview.chromium.org/239603005/diff/40001/Source/wtf/Vector.h
> File Source/wtf/Vector.h (right):
> 
>
https://codereview.chromium.org/239603005/diff/40001/Source/wtf/Vector.h#newc...
> Source/wtf/Vector.h:681: shrinkCapacity(size() + size() / 4 + 1);
> Is there a problem with integer overflow in this code?
> 
> See void Vector<T, inlineCapacity, Allocator>::expandCapacity(size_t
> newMinCapacity) for some worries about integer overflow in a similar codepath.

There is comment in ::expandCapacity() that allocations can't be more than (2^31
- 1) on 32 bit systems and more than 2^32 on 64 bit, so size() * 2 normally
cannot produce integer overflow.

[abarth-chromium, 2014-05-06 18:50:47]

lgtm

[commit-bot: I haz the power, 2014-05-06 18:51:22]

CQ is trying da patch. Follow status at
 https://chromium-status.appspot.com/cq/sl.ostapenko@samsung.com/239603005/40001

[commit-bot: I haz the power, 2014-05-06 20:00:36]

Change committed as 173420