Bug 7450 – elementAtPoint is expensive and should return a smart dictionary

• Component: WebKit API
• Status: RESOLVED FIXED

[Timothy Hatcher]

The elementAtPoint method returns a dictionary of 12 objects, this is a very hot method that is called during mouse moves. When hovering over an image, an NSImage is allocated and inserted into the returned dictionary, even though it is hardly used. We should return a smart dictionary that requests objects from the DOM as they are requested.

[Timothy Hatcher]

Created attachment 6706 [details]
Implementation using a smart dictionary

[Darin Adler]

Comment on attachment 6706 [details]
Implementation using a smart dictionary

titleDisplayString and other similar methods should get the backslashAsCurrencySymbol from the Frame rather than the renderer. This doesn't depend on rendering at all.

absoluteImageURL and similar functions need to make the NSURL using KURL, since that code path uses the appropriate NSURL/CFURL method. URLWithString: won't always work.

I suggest getNodesAtPoint: as the beginning of the method name. I think I've noticed AppKit/Foundation methods that return multiple values using pointers with a get prefix. In fact, you might want to pass the point last so it's "get these things, given this thing" (ForPoint: or AtPoint:).

No need for all those nil checks in nodesAtPoint.

Please split innerNode, innerNonSharedNode, and URLElement into separate lines, and set all 3 to nil -- if bridge is nil you want to get nil for all 3, so please do set all 3 to nil.

nodesAtPoint and init for WebElementDictionary should do the nodes in the same order. Currently they don't.

WebElementDictionary was not included with the patch -- please add it.

[Timothy Hatcher]

Created attachment 6708 [details]
Implementation using a smart dictionary (round 2)

Addresses Darin's comments.

[Darin Adler]

Comment on attachment 6708 [details]
Implementation using a smart dictionary (round 2)

If you look at Frame::backslashAsCurrencySymbol, you'll see that it's all done through the document. So this code can be written so that it works even when there's no Frame. Sorry I didn't notice that before. Please do that. Perhaps you could put the function in DocumentImpl, or you could just do the document()->decoder()->codec() thing yourself.

Identifiers like _WebElementSelf should not start with an underscore. First of all, there's no need to worry about conflict with end-user stuff since they are internal to the framework and the source file. Second, underscore followed by capital letter is reserved for the system and library.

In WebElementMethodMap, the "object" should be the enumeration type, not unsigned. I also suggest naming that structure WebElementMethod, since it's not a map.

I think NSMapTable is deprecated -- they encourage using CFDictionary instead, and that seems pretty easy to do. Or you could use an NSDictionary with NSValue for the values. But I could be wrong on this.

Inside WebKit files, #import "" is fine for WebKit headers. Some older files do #import <WebKit/>, but that's overkill.

All those checks after calling malloc on each node in initializeLookupTable aren't needed. When you're doing a small malloc during initialization checking the return value of malloc isn't really helpful. I don't think that function needs to have a return value.

Since the pattern malloc, set up, insert into map is repeated over and over again, I suggest making a function to do it, or putting the values into an array and then looping through the array to insert into the map.

The dealloc method doesn't have to nil things out, probably best not to.

+    else if(mapItem->object == _WebElementInnerNonSharedNode)

Needs a space after the if.

Also, the different mapItem->object values should be a switch statement.

Why the check for object == _WebElementSelf before checking respondsToSelector:? It seems fine to call respondsToSelector: on self.

+    if (!_URLElement) return nil;

Should be broken up over two lines.

I'm concerned that the nodes are released in dealloc and returned from methods. They might need to be autoreleased by the methods or by dealloc in case the caller gets the node then releases the dictionary. Not sure about this one.

Why doesn't this patch remove all the WebCoreXXXKey constants from WebCoreFrameBridge?

[Timothy Hatcher]

Created attachment 6735 [details]
Implementation using a smart dictionary (round 3)

Taking into account Darin's comments.

[Timothy Hatcher]

To be safe about returning the DOM node I did this:

- (DOMNode *)_domNode
{
    return [[_innerNonSharedNode retain] autorelease];
}

This is the only place we return a DOM node directly.

[Darin Adler]

Comment on attachment 6735 [details]
Implementation using a smart dictionary (round 3)

Looks great! I almost want to do review+, but I have so many comments (although each one is minor) that I'm going to review- this one more time:

It's a bit unfortunate introducing all these uses of QString -- we're trying to remove all use of QString. Ideally all these displayString methods would share a single function. But in any case, WebCore::String has a perfectly good replace function, which we would use and can convert itself to NSString without a function, so we could write:

+    return [self _HTMLElementImpl]->title().replace(QChar('\\'), [self _elementImpl]->getDocument()->backslashAsCurrencySymbol());

+    QChar DocumentImpl::backslashAsCurrencySymbol() const;

The above is wrong. Should not include the class name DocumentImpl there.

Maybe we should change URLElement to actually be an ElementImpl instead of a NodeImpl. It's annoying to have the code here know that it's always an element, but not have the code it's bridging know. (Probably not something you have to fix in this patch though; just cleanup for later.)

WebElementDictionary.h should have a copyright date of 2006, not 2003, and WebElementDictionary.m have 2006 instead of 2005 unless there is code in those files published earlier which requires more than one year to be listed.

We should probably import <Foundation/Foundation.h> rather than individual Foundation headers in WebKit code.

I prefer a blank line after:

+#import "WebElementDictionary.h"

and before the other includes.

I don't think addLookupKey needs an "if (!lookupTable)" at the start of it; there's no practical case where that can be nil and if it's nil a crash is probably the best we can do.

There's no reason that addLookupKey needs to use CFAllocatorAllocate instead of malloc, is there?

Since we never plan to delete any values out of the lookup table, nor delete the table itself, we can pass NULL for the value callbacks instead of &vcb.

I think it's a little fragile to have the hardcoded constant 12 and then 12 calls to addLookupKey below. It seems highly likely that someone would add a new call without noticing the number 12 they should be updating. I'm not sure what the best fix is for this. Passing 0 is probably OK, even though we will give up a tiny bit of efficiency by doing so.

Since all callers check _cacheComplete before calling _fillCache, I think it should not also check _cacheComplete. An assert perhaps, but not an if ... return.

_fillCache does not need to initialize the key to nil.

I think that _fillCache should use CFDictionaryApplyFunction instead of casting to NSDictionary and using keyEnumerator. It would be pretty easy to do that, passing self through as the context, and then we would not be relying on toll-free bridging at all for the lookup table.

+    id value = [_cache objectForKey:key];
+    if (value || _cacheComplete || (_nilValues && [_nilValues containsObject:key]))
+        return value;

It's a little inconsistent here to just use _cache without checking it for nil and then checking _nilValues for nil before calling containsObject:. I think you should check either both or neither.

I think you should do:

    typedef struct { ... } WebElementMethod;

and then refer to it as WebElementMethod everywhere instead of struct WebElementMethod.

Since CFDictionaryGetCount is used no matter what in objectForKey: I suggest putting it into a local variable. The local variable can be an unsigned type, which will obviate the need for the (unsigned long) cast in the _cacheComplete check.

This:

    _cacheComplete = ([_cache count] + [_nilValues count]) == lookupTableCount

will generate slightly better code than if (x) y = YES, so I suggest using that form.

[Timothy Hatcher]

Created attachment 6747 [details]
Implementation using a smart dictionary (round 4)

> We should probably import <Foundation/Foundation.h> rather than individual Foundation headers in WebKit code.

I am under the impression it is better to include the specific header when you subclass, and add @class ... for any other classes you need. This speeds up compile time.

I was using CFAllocatorAllocate so we could safely use CFAllocatorDeallocate. No longer needed if we pass NULL for the value callbacks.

I falsely assumed what capacity meant to CFDictionary based on what NSMutableDictionary mean by dictionaryWithCapacity (as the initial size, not a hard maximum). Corrected.

[Darin Adler]

Comment on attachment 6747 [details]
Implementation using a smart dictionary (round 4)

The _targetWebFrame method assumes that URLElement is a DOMHTMLAnchorElement, but that's not right. If you look at the code in WebCore you can see that a URLElement can be an HTMLAreaElement, an HTMLImageElement with a usemap attribute, an HTMLAnchorElement with an href attribute, or an SVGAElement with an XLink::href attribute. So we can get method-not-found if we just call target without checking the type.

I'm setting this review- just for the _targetWebFrame issue. If you fix that it's fine to land it with "Reviewed by Darin" without an additional round of review.

Here are a few other minor nitpicks:

In all those replace calls, it can just be '\\', doesn't have to be QChar('\\').

In getInnerNonSharedNode:, when there's no renderer, it should probably set the results to nil instead of leaving them untouched. The single caller is initializing all of them to nil anyway, so it won't matter in practice for us.

You apparently didn't heed my complaint about the inconsistency between _nilValues and _cache in objectForKey: -- there's still a nil check for _nilValues and no nil check for _cache. I suggest checking neither for nil or checking both for nil.

I preferred the old version of objectForKey: that would only look at the _nilValues set if [_cache objectForKey:] returned nil.

[Timothy Hatcher]

A tweaked version based on Darin's last comments was landed as r13070.