Bug 101861 – Check for assignment to self in WTF containers' operator=()

• Component: Web Template Framework
• Status: RESOLVED FIXED

[Chris Dumez]

Several WTF container classes do not check for assignment to self in their operator=().

I think it is a good idea to check for assignment to self in operator=() for 2 reasons:
1. Efficiency: If we detect assignment to self at the top of the assignment operator, we can return right away, possibly saving some work we would have to go through otherwise to implement assignment.
2. Correctness: There is a risk the assignment implementation frees old resources before it allocates the new resources corresponding to its new value. In a "assignment to self" case, this can have non-desirable effect as the old and new resources are the same.

Note that this approach is advised by the "Effective C++" book and already implemented in WTF::Vector::operator=(). A few containers do not implement this check though:
* BitVector
* Deque
* FastBitVector
* HashTable
* ListHashSet

[Chris Dumez]

Created attachment 173506 [details]
Patch

[Maciej Stachowiak]

Comment on attachment 173506 [details]
Patch

The best way to make an assignment operator that is safe against self-assignment is to use the copy-and-swap idiom: http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Copy-and-swap

In fact, it looks like many of these classes already use the copy-and-swap idiom, which makes this change unnecessary for correctness. At best it would matter for efficiency. But we should not make changes solely for performance without some evidence that they help performance.

Therefore please provide evidence that explicit self-assignment checks give a performance benefit.

[Chris Dumez]

(In reply to comment #2)
> (From update of attachment 173506 [details])
> The best way to make an assignment operator that is safe against self-assignment is to use the copy-and-swap idiom: http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Copy-and-swap
> 
> In fact, it looks like many of these classes already use the copy-and-swap idiom, which makes this change unnecessary for correctness. At best it would matter for efficiency. But we should not make changes solely for performance without some evidence that they help performance.
> 
> Therefore please provide evidence that explicit self-assignment checks give a performance benefit.

Sure, I'll produce provide some evidence.

[Chris Dumez]

Created attachment 173516 [details]
Test app to check performance

I'm attaching a test app I wrote to check performance with and without the assignment to self check.

What the test app does:
- Create a Deque containing 100000000 CString objects
- Do an assignment to self and measure how long the assignment operation took (Repeats this 100 times and compute the average durations).

Here are the results I got on my machine:
- With assignment to self check:
  * 5.85937e-05 ms (debug) / 5.37109e-05 ms (release)

Without the check (without my patch):
  * 4904.65 ms (debug) / 559.326 ms (release)

As you can see the performance seems much better when assigning to self. The assigning to self check is just a pointer comparison so it is fairly inexpensive.

[Chris Dumez]

Created attachment 173517 [details]
Patch

Remove comment about correctness from the Changelog since this is not an issue with the current implementation.

[Maciej Stachowiak]

(In reply to comment #4)
> Created an attachment (id=173516) [details]
> Test app to check performance
> 
> I'm attaching a test app I wrote to check performance with and without the assignment to self check.
> 
> What the test app does:
> - Create a Deque containing 100000000 CString objects
> - Do an assignment to self and measure how long the assignment operation took (Repeats this 100 times and compute the average durations).
> 
> Here are the results I got on my machine:
> - With assignment to self check:
>   * 5.85937e-05 ms (debug) / 5.37109e-05 ms (release)
> 
> Without the check (without my patch):
>   * 4904.65 ms (debug) / 559.326 ms (release)
> 
> As you can see the performance seems much better when assigning to self. The assigning to self check is just a pointer comparison so it is fairly inexpensive.

OK, but, does this affect any real-world test cases? I expect that in actual use of WebKit, self-assignment is  very rare, and therefore this patch won't make a difference (might even be a slowdown due to the extra branch).

[Chris Dumez]

Created attachment 173650 [details]
Improved test app to check performance

Results on my machine:

With "assignment to self" check (release):
Average assignment to self duration: 0.000732422 ms (100000000 values)
Average assignment to other duration: 591.353 ms (100000000 values)
Average assignment to other duration: 0.000559082 ms (100 values)
Average assignment to other duration: 9.0332e-05 ms (10 values)

Without "assignment to self" check (release):
Average assignment to self duration: 561.441 ms (100000000 values)
Average assignment to other duration: 544.214 ms (100000000 values)
Average assignment to other duration: 0.000559082 ms (100 values)
Average assignment to other duration: 0.000148926 ms (10 values)

[Chris Dumez]

(In reply to comment #7)
> Created an attachment (id=173650) [details]
> Improved test app to check performance
> 
> Results on my machine:
> 
> With "assignment to self" check (release):
> Average assignment to self duration: 0.000732422 ms (100000000 values)
> Average assignment to other duration: 591.353 ms (100000000 values)
> Average assignment to other duration: 0.000559082 ms (100 values)
> Average assignment to other duration: 9.0332e-05 ms (10 values)
> 
> Without "assignment to self" check (release):
> Average assignment to self duration: 561.441 ms (100000000 values)
> Average assignment to other duration: 544.214 ms (100000000 values)
> Average assignment to other duration: 0.000559082 ms (100 values)
> Average assignment to other duration: 0.000148926 ms (10 values)

I added to tests for the regular assignment case. I added tests with smaller containers. My results don't show any real impact of the "assign to self" check for regular assignment cases.

[Benjamin Poulain]

Branches are fairly costly on ARM, a lot more than on modern x86.

Please instrument WebKit first to find how common are these cases. Your performance test is a good indicator of the gain, but you should find how often the self-assignment case arises.

[Benjamin Poulain]

Comment on attachment 173517 [details]
Patch

Let's remove this from the review queue. The patch looks good, but we first need data proving this added branch actually adds value.

[Radar WebKit Bug Importer]

<rdar://problem/165278957>

[Fady Farag]

Pull request: https://github.com/WebKit/WebKit/pull/54373

[EWS]

Committed 303557@main (a94531bb17ad): <https://commits.webkit.org/303557@main>

Reviewed commits have been landed. Closing PR #54373 and removing active labels.