(Concept patch) Simplify WTF::HashTable::add() return value for size and performance

(Concept patch)
WTF::HashTable::add() returns a full-blown iterator object
that is never used as an iterator which makes it a bit
wasteful both in clock cycles and in code size.

This patch changes the iterator object to a clean
ValueType pointer. That change shaves ~95 KB off the
x64 content_shell binary.

The shaving is half that callers of add() and set() becomes
smaller (example: eventNameForAttributeName shrinks from
8.5 KB to 7 KB) and half that the add() method
instantiations shrink by 50-150 bytes each (and there are
about 500 different add() methods)

[Daniel Bratell, 2014-02-04 09:35:41]

Adam, Eric, this i fallout patch from me looking into inlines and collection
templates. HashTable::add's return value causes some bloat that is unnecessary.
Replacing the Iterator object with a ValueType pointer shaves 100 KB of an x64
clang binary so it seems worth doing.

[pfeldman, 2014-02-04 09:48:34]

Adam, Eric, it is your call. 100 KB is a lot, but I don't like the way suggested
inspector code reads.

[Mikhail, 2014-02-04 09:57:40]

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

https://codereview.chromium.org/152883002/diff/1/Source/wtf/ListHashSet.h#new...
Source/wtf/ListHashSet.h:764: Node* node = result.iterator;
IMO the semantic is incorrect: iterator should not be the same thing as pointer.

[Daniel Bratell, 2014-02-04 10:05:04]

On 2014/02/04 09:57:40, mikhail.pozdnyakov wrote:
> https://codereview.chromium.org/152883002/diff/1/Source/wtf/ListHashSet.h
> File Source/wtf/ListHashSet.h (right):
> 
>
https://codereview.chromium.org/152883002/diff/1/Source/wtf/ListHashSet.h#new...
> Source/wtf/ListHashSet.h:764: Node* node = result.iterator;
> IMO the semantic is incorrect: iterator should not be the same thing as
pointer.

It's just to keep the size of the patch down. If I had changed the name the
patch would have been huge and dozens of people would have started demanding
small tuning of the code around the places where the code changed. I have a
version locally where it's named valuePtr, but the interesting thing here is
whether you would even accept a change to HashTable::add() at all or if it has
to have a heavy return value.

[Daniel Bratell, 2014-02-04 10:06:32]

On 2014/02/04 09:48:34, pfeldman wrote:
> Adam, Eric, it is your call. 100 KB is a lot, but I don't like the way
suggested
> inspector code reads.

If you're thinking about mapPtr that was the most messy place out of hundreds
(thousands) of call sites. I really just went for a minimal change where any
typo would be caught by the compiler. Everywhere else it's more or less a
trivial s/Iterator/ValueType/ substitution.

[Inactive, 2014-02-04 14:21:33]

I am not a wtf/ OWNER but as a wtf user, I am not a huge fan of the resulting
code. This is a bit less flexible and leads to some code duplication.

https://codereview.chromium.org/152883002/diff/1/Source/core/css/CSSSegmented...
File Source/core/css/CSSSegmentedFontFace.cpp (right):

https://codereview.chromium.org/152883002/diff/1/Source/core/css/CSSSegmented...
Source/core/css/CSSSegmentedFontFace.cpp:97: m_firstNonCssConnectedFace =
m_fontFaces.find(fontFace);
So for the cases where the caller of add() expects an iterator, we have to do an
additional call to find() and thus an extra lookup? This seems unfortunate.

https://codereview.chromium.org/152883002/diff/1/Source/core/dom/custom/Custo...
File Source/core/dom/custom/CustomElementUpgradeCandidateMap.cpp (right):

https://codereview.chromium.org/152883002/diff/1/Source/core/dom/custom/Custo...
Source/core/dom/custom/CustomElementUpgradeCandidateMap.cpp:54:
m_unresolvedDefinitions.add(descriptor,
ElementSet()).iterator->value.add(element);
This sort of change leads to some code duplication.

[Erik Corry, 2014-02-04 14:27:14]

I like this change.  An iterator has always seemed like a heavy thing to return
to a caller that doesn't use it.

The disadvantage of the pointer is that you have to use it immediately.  If you
do something that could cause a rehash of the collection then your pointer will
be invalid.  The iterator has the same issue, but at least it checks in debug
mode that the collection has not been changed.

So I like this change, but I would also support forking add into two functions,
only one of which returned an iterator.

https://codereview.chromium.org/152883002/diff/1/Source/core/animation/Keyfra...
File Source/core/animation/KeyframeEffectModel.cpp (right):

https://codereview.chromium.org/152883002/diff/1/Source/core/animation/Keyfra...
Source/core/animation/KeyframeEffectModel.cpp:249: KeyframeGroupMap::iterator
groupIter = m_keyframeGroups->find(property);
This might be more elegant if there were a version of find that did not return
an iterator, but rather a pointer-or-null.  Then you can say if (!ptr) ptr =
...add(...);

https://codereview.chromium.org/152883002/diff/1/Source/core/animation/Keyfra...
Source/core/animation/KeyframeEffectModel.cpp:254: new
PropertySpecificKeyframe(keyframe->offset(), keyframe->propertyValue(property),
keyframe->composite())));
Funny indentation, and there's a chunk of repeated code between here and the
else clause.

https://codereview.chromium.org/152883002/diff/1/Source/core/dom/Presentation...
File Source/core/dom/PresentationAttributeStyle.cpp (right):

https://codereview.chromium.org/152883002/diff/1/Source/core/dom/Presentation...
Source/core/dom/PresentationAttributeStyle.cpp:166:
PresentationAttributeCache::ValueType* cacheIterator;
It seems wrong to call this 'iterator'.

https://codereview.chromium.org/152883002/diff/1/Source/core/dom/custom/Custo...
File Source/core/dom/custom/CustomElementScheduler.cpp (right):

https://codereview.chromium.org/152883002/diff/1/Source/core/dom/custom/Custo...
Source/core/dom/custom/CustomElementScheduler.cpp:110:
ElementCallbackQueueMap::iterator it = m_elementCallbackQueueMap.find(key);
Also here with the find that insists on returning an iterator.

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

https://codereview.chromium.org/152883002/diff/1/Source/wtf/HashTable.h#newco...
Source/wtf/HashTable.h:210: HashTableAddResult(ValueType* iterator, bool
isNewEntry) : iterator(iterator), isNewEntry(isNewEntry) { }
If this is no longer an iterator, should it be called 'iterator'?

[adamk, 2014-02-04 16:29:32]

Like Chris, I'm not a WTF reviewer, but I don't much like this change (see my
comments below). It also moves us even further away from the behavior of STL.

https://codereview.chromium.org/152883002/diff/1/Source/core/css/CSSSegmented...
File Source/core/css/CSSSegmentedFontFace.cpp (right):

https://codereview.chromium.org/152883002/diff/1/Source/core/css/CSSSegmented...
Source/core/css/CSSSegmentedFontFace.cpp:97: m_firstNonCssConnectedFace =
m_fontFaces.find(fontFace);
On 2014/02/04 14:21:33, Chris Dumez wrote:
> So for the cases where the caller of add() expects an iterator, we have to do
an
> additional call to find() and thus an extra lookup? This seems unfortunate.

This is my objection, too. Many uses of add() are intentionally trying to avoid
extra hash lookups, so while this change might save on binary size it's trading
runtime for that.

Additionally, given the above, it seems your claim in the CL description, that
the returned iterator "is never used as an iterator" is incorrect (in this case,
and in other cases where add() is used to avoid a double hash lookup, the fact
that it's an iterator is used).

[Daniel Bratell, 2014-02-04 17:07:54]

On 2014/02/04 16:29:32, adamk wrote:
> Like Chris, I'm not a WTF reviewer, but I don't much like this change (see my
> comments below). It also moves us even further away from the behavior of STL.
> 
>
https://codereview.chromium.org/152883002/diff/1/Source/core/css/CSSSegmented...
> File Source/core/css/CSSSegmentedFontFace.cpp (right):
> 
>
https://codereview.chromium.org/152883002/diff/1/Source/core/css/CSSSegmented...
> Source/core/css/CSSSegmentedFontFace.cpp:97: m_firstNonCssConnectedFace =
> m_fontFaces.find(fontFace);
> On 2014/02/04 14:21:33, Chris Dumez wrote:
> > So for the cases where the caller of add() expects an iterator, we have to
do
> an
> > additional call to find() and thus an extra lookup? This seems unfortunate.
> 
> This is my objection, too. Many uses of add() are intentionally trying to
avoid
> extra hash lookups, so while this change might save on binary size it's
trading
> runtime for that.

Not at all. You have misunderstood the patch. At ~2 places (out of hundreds and
hundreds and hundreds of adds) I choose to replace an add with an add+find to
minimize the number of lines of code I had to change to make it compile (they
wanted to store the return value from add in the same variable as the return
value from find). The code at those ~2 places can certainly be written in a
better way but that would involve modifying more lines of code and more
discussions that is rather uninteresting when the main question is if this is
the best way of making Blink less fat.

> Additionally, given the above, it seems your claim in the CL description, that
> the returned iterator "is never used as an iterator" is incorrect (in this
case,
> and in other cases where add() is used to avoid a double hash lookup, the fact
> that it's an iterator is used).

What I should have said is that the return value is never used as anything but a
pointer to a single object (roughly "input iterator"). It's never compared to
other iterators and the only operation that is used is ->. What I wanted to
convey was that we don't need the full functionality of the existing Iterator
object, that the Iterator object has a cost for functionality we don't need and
a pointer is all the callers need.

[adamk, 2014-02-04 17:25:49]

On 2014/02/04 17:07:54, Daniel Bratell wrote:
> On 2014/02/04 16:29:32, adamk wrote:
> > Like Chris, I'm not a WTF reviewer, but I don't much like this change (see
my
> > comments below). It also moves us even further away from the behavior of
STL.
> > 
> >
>
https://codereview.chromium.org/152883002/diff/1/Source/core/css/CSSSegmented...
> > File Source/core/css/CSSSegmentedFontFace.cpp (right):
> > 
> >
>
https://codereview.chromium.org/152883002/diff/1/Source/core/css/CSSSegmented...
> > Source/core/css/CSSSegmentedFontFace.cpp:97: m_firstNonCssConnectedFace =
> > m_fontFaces.find(fontFace);
> > On 2014/02/04 14:21:33, Chris Dumez wrote:
> > > So for the cases where the caller of add() expects an iterator, we have to
> do
> > an
> > > additional call to find() and thus an extra lookup? This seems
unfortunate.
> > 
> > This is my objection, too. Many uses of add() are intentionally trying to
> avoid
> > extra hash lookups, so while this change might save on binary size it's
> trading
> > runtime for that.
> 
> Not at all. You have misunderstood the patch. At ~2 places (out of hundreds
and
> hundreds and hundreds of adds) I choose to replace an add with an add+find to
> minimize the number of lines of code I had to change to make it compile (they
> wanted to store the return value from add in the same variable as the return
> value from find). The code at those ~2 places can certainly be written in a
> better way but that would involve modifying more lines of code and more
> discussions that is rather uninteresting when the main question is if this is
> the best way of making Blink less fat.
>
> > Additionally, given the above, it seems your claim in the CL description,
that
> > the returned iterator "is never used as an iterator" is incorrect (in this
> case,
> > and in other cases where add() is used to avoid a double hash lookup, the
fact
> > that it's an iterator is used).
> 
> What I should have said is that the return value is never used as anything but
a
> pointer to a single object (roughly "input iterator"). It's never compared to
> other iterators and the only operation that is used is ->. What I wanted to
> convey was that we don't need the full functionality of the existing Iterator
> object, that the Iterator object has a cost for functionality we don't need
and
> a pointer is all the callers need.

Ah, sorry, I hadn't had my coffee yet and forgot what "ValueType" means for a
Map. My apologies for the misunderstanding.

I'm now mostly neutral on this change (though I don't think I'm the only one
who's going to be confused by the name "ValueType" being used regularly outside
of HashMap's implementation, since "value" also means something for maps).

[Daniel Bratell, 2014-02-04 19:17:37]

On 2014/02/04 17:25:49, adamk wrote:
> Ah, sorry, I hadn't had my coffee yet and forgot what "ValueType" means for a
> Map. My apologies for the misunderstanding.
> 
> I'm now mostly neutral on this change (though I don't think I'm the only one
> who's going to be confused by the name "ValueType" being used regularly
outside
> of HashMap's implementation, since "value" also means something for maps).

Don't consider it gospel. Even after such a change you can write code in (too?)
many ways.

For instance:
HashMap<string, MyValue> map;
MyValue& inMapValue = map.add("foo", MyValue()).iterator->value;
inMapValue = theValueIWantToInsert;

I used ValueType because I needed something that compiled and I didn't want to
spend too much time figuring out the local conventions and type names for
something that at the time was just a hunch.

[eseidel, 2014-02-05 21:59:30]

lgtm

We can always add it back.  I strongly support more people taking interest in
improving our core collection classes.  100k isn't a particularly huge slice of
binary, but removing dead code is always A Good Thing™ in my mind.

[eseidel, 2014-02-05 21:59:38]

The CQ bit was unchecked by eseidel@chromium.org

[eseidel, 2014-02-05 22:04:08]

Actually, looking through the change again I'm less sure.   I have to head to
the office atm, but I will look again this morning.  Looks like you have some
objections from others as well, calling into question the 100k trade.

If the goal is binary size, we have very low hanging fruit in other places. ;) 
But our core collection classes are also pretty bloaty.

[eseidel, 2014-02-05 22:17:19]

OK, I've read it again more carefully.  The idea still seems fine.  The
iterator/value naming on the addedValue result needs fixing to reduce confusion.

Mostly we need an owner for this code, or we need to move to STL types.  The
owner for this code was Darin or Maciej in WebKit, neither of which is involved
in the Blink project.  We've had a couple people hack on these, but I don't feel
like we have someone who's really claimed ownership of them yet to help set the
long-term technical direction for these classes.

My understanding is that we can't (yet) move to stl core collection classes yet
due to OilPan possibly needing to customize them further.  It also doens't
surprise me that a project of our size might need its own custom core
datastructurs, but I'd like to to continue to reduce Blink's code and re-use
others good ideas when possible.

So I guess in short, please update to fix the naming and address any other's
concerns I missed, but I'm overall fine with the idea.

Thanks for working on binary size!

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

https://codereview.chromium.org/152883002/diff/1/Source/wtf/HashTable.h#newco...
Source/wtf/HashTable.h:210: HashTableAddResult(ValueType* iterator, bool
isNewEntry) : iterator(iterator), isNewEntry(isNewEntry) { }
On 2014/02/04 14:27:15, Erik Corry wrote:
> If this is no longer an iterator, should it be called 'iterator'?

No. :)  But presumably Daniel did this to minimize changes?  I would call this
value or addedValue or something.

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

https://codereview.chromium.org/152883002/diff/1/Source/wtf/ListHashSet.h#new...
Source/wtf/ListHashSet.h:764: Node* node = result.iterator;
On 2014/02/04 09:57:41, mikhail.pozdnyakov wrote:
> IMO the semantic is incorrect: iterator should not be the same thing as
pointer.

It's just the naming which is wrong.  If this was result.value it seems it would
read fine.

[Mikhail, 2014-02-07 14:22:03]

On 2014/02/05 22:17:19, eseidel wrote:
> OK, I've read it again more carefully.  The idea still seems fine.  The
> iterator/value naming on the addedValue result needs fixing to reduce
confusion.
> 
> Mostly we need an owner for this code, or we need to move to STL types.  The
> owner for this code was Darin or Maciej in WebKit, neither of which is
involved
> in the Blink project.  We've had a couple people hack on these, but I don't
feel
> like we have someone who's really claimed ownership of them yet to help set
the
> long-term technical direction for these classes.
> 
> My understanding is that we can't (yet) move to stl core collection classes
yet
> due to OilPan possibly needing to customize them further.  It also doens't
> surprise me that a project of our size might need its own custom core
> datastructurs, but I'd like to to continue to reduce Blink's code and re-use
> others good ideas when possible.
> 
> So I guess in short, please update to fix the naming and address any other's
> concerns I missed, but I'm overall fine with the idea.
> 
> Thanks for working on binary size!
> 
> https://codereview.chromium.org/152883002/diff/1/Source/wtf/HashTable.h
> File Source/wtf/HashTable.h (right):
> 
>
https://codereview.chromium.org/152883002/diff/1/Source/wtf/HashTable.h#newco...
> Source/wtf/HashTable.h:210: HashTableAddResult(ValueType* iterator, bool
> isNewEntry) : iterator(iterator), isNewEntry(isNewEntry) { }
> On 2014/02/04 14:27:15, Erik Corry wrote:
> > If this is no longer an iterator, should it be called 'iterator'?
> 
> No. :)  But presumably Daniel did this to minimize changes?  I would call this
> value or addedValue or something.
> 
> https://codereview.chromium.org/152883002/diff/1/Source/wtf/ListHashSet.h
> File Source/wtf/ListHashSet.h (right):
> 
>
https://codereview.chromium.org/152883002/diff/1/Source/wtf/ListHashSet.h#new...
> Source/wtf/ListHashSet.h:764: Node* node = result.iterator;
> On 2014/02/04 09:57:41, mikhail.pozdnyakov wrote:
> > IMO the semantic is incorrect: iterator should not be the same thing as
> pointer.
> 
> It's just the naming which is wrong.  If this was result.value it seems it
would
> read fine.

I agree, the idea is good but the naming makes it a bit confusing.

[Daniel Bratell, 2014-02-10 11:05:59]

I am closing this concept patch. The new fresh patch with the conclusions
reached here can be found in https://codereview.chromium.org/138643003/

Thanks everyone for your feedback. See you in the other issue!