Store HValue uses in a custom small list structure.

Store HValue uses in a custom small list structure.

This saves about 700K of zone allocation when compiling the V8
benchmark suite.

Committed: http://code.google.com/p/v8/source/detail?r=7330

[fschneider, 2011-03-22 10:15:52]

Added Kevin.

It seems to be a good idea to have a compact data structure for one-element
use-lists. Did you see any difference in compile-time?

Kevin and me were discussing representing uses not just as HValue*, but as a
pair (HValue*, operand_index) instead. This would allow us to simplify the code
dealing with the case where one value is used multiple times in an instructions.
I think we can use your approach also if we represent uses as pairs in the
future (e.g. SmallPointerList<HUse> where HUse is a pair <HValue*, int>.

Otherwise this change LGTM.

http://codereview.chromium.org/6707001/diff/1/src/small-pointer-list.h
File src/small-pointer-list.h (right):

http://codereview.chromium.org/6707001/diff/1/src/small-pointer-list.h#newcode28
src/small-pointer-list.h:28: #ifndef V8_SMALL_POINTER_LIST_H_
You need to update the project files (gyp, visual studio, etc.) with the new
file.

http://codereview.chromium.org/6707001/diff/1/src/small-pointer-list.h#newcode89
src/small-pointer-list.h:89: if (pointer == single_value()) {
I rather like less nested if-statements:

if ((data_ & kTagMask) == kSingletonTag &&
    pointer == single_value()) {

http://codereview.chromium.org/6707001/diff/1/src/small-pointer-list.h#newcod...
src/small-pointer-list.h:125: if (start == 0 && start <= end) {
Maybe a matter of taste - I prefer

if (start == 0 && end >= 0) {

here.

[Vitaly Repeshko, 2011-03-22 17:07:49]

Florian, thanks for having a look!

When testing locally I see no differences in compilation time on average (as
reported by --hydrogen-stats).


Thanks,
Vitaly

http://codereview.chromium.org/6707001/diff/1/src/small-pointer-list.h
File src/small-pointer-list.h (right):

http://codereview.chromium.org/6707001/diff/1/src/small-pointer-list.h#newcode28
src/small-pointer-list.h:28: #ifndef V8_SMALL_POINTER_LIST_H_
On 2011/03/22 10:15:52, fschneider wrote:
> You need to update the project files (gyp, visual studio, etc.) with the new
> file.

Updated.

http://codereview.chromium.org/6707001/diff/1/src/small-pointer-list.h#newcode89
src/small-pointer-list.h:89: if (pointer == single_value()) {
On 2011/03/22 10:15:52, fschneider wrote:
> I rather like less nested if-statements:
> 
> if ((data_ & kTagMask) == kSingletonTag &&
>     pointer == single_value()) {

Can't combine them, because we need to return.

http://codereview.chromium.org/6707001/diff/1/src/small-pointer-list.h#newcod...
src/small-pointer-list.h:125: if (start == 0 && start <= end) {
On 2011/03/22 10:15:52, fschneider wrote:
> Maybe a matter of taste - I prefer
> 
> if (start == 0 && end >= 0) {
> 
> here.

Done.

[Kevin Millikin (Chromium), 2011-03-23 07:38:43]

LGTM!

http://codereview.chromium.org/6707001/diff/4001/src/small-pointer-list.h
File src/small-pointer-list.h (right):

http://codereview.chromium.org/6707001/diff/4001/src/small-pointer-list.h#new...
src/small-pointer-list.h:62: PointerList* list = new PointerList(2);
We should count the lengths of use lists that are >= 2.  This backing store will
be resized as soon as we add a another use.  

If this is frequent, we should avoid the doubling and wasted 2-element list and
preallocate it a bit bigger.

http://codereview.chromium.org/6707001/diff/4001/src/small-pointer-list.h#new...
src/small-pointer-list.h:86: void RemoveElement(T* pointer) {
Maybe a short comment that the intended semantics is to remove if present (like
List::RemoveElement).

[Vitaly Repeshko, 2011-03-23 14:42:32]

Kevin, thanks for your comments!


-- Vitaly

http://codereview.chromium.org/6707001/diff/4001/src/small-pointer-list.h
File src/small-pointer-list.h (right):

http://codereview.chromium.org/6707001/diff/4001/src/small-pointer-list.h#new...
src/small-pointer-list.h:62: PointerList* list = new PointerList(2);
On 2011/03/23 07:38:44, Kevin Millikin wrote:
> We should count the lengths of use lists that are >= 2.  This backing store
will
> be resized as soon as we add a another use.  
> 
> If this is frequent, we should avoid the doubling and wasted 2-element list
and
> preallocate it a bit bigger.

When compiling the V8 benchmark the number of values with 2 uses is
approximately equal to the number of values with strictly more than 2 uses. So I
think it makes sense to keep 2 here.

http://codereview.chromium.org/6707001/diff/4001/src/small-pointer-list.h#new...
src/small-pointer-list.h:86: void RemoveElement(T* pointer) {
On 2011/03/23 07:38:44, Kevin Millikin wrote:
> Maybe a short comment that the intended semantics is to remove if present
(like
> List::RemoveElement).

Done.