<html>
<head>
<base href="https://bugs.webkit.org/" />
</head>
<body><table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Bug ID</th>
<td><a class="bz_bug_link
bz_status_NEW "
title="NEW - Speed up Heap::isMarkedConcurrently"
href="https://bugs.webkit.org/show_bug.cgi?id=162095">162095</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>Speed up Heap::isMarkedConcurrently
</td>
</tr>
<tr>
<th>Classification</th>
<td>Unclassified
</td>
</tr>
<tr>
<th>Product</th>
<td>WebKit
</td>
</tr>
<tr>
<th>Version</th>
<td>WebKit Nightly Build
</td>
</tr>
<tr>
<th>Hardware</th>
<td>Unspecified
</td>
</tr>
<tr>
<th>OS</th>
<td>Unspecified
</td>
</tr>
<tr>
<th>Status</th>
<td>NEW
</td>
</tr>
<tr>
<th>Severity</th>
<td>Normal
</td>
</tr>
<tr>
<th>Priority</th>
<td>P2
</td>
</tr>
<tr>
<th>Component</th>
<td>JavaScriptCore
</td>
</tr>
<tr>
<th>Assignee</th>
<td>webkit-unassigned@lists.webkit.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>jfbastien@apple.com
</td>
</tr></table>
<p>
<div>
<pre>Heap::isMarkedConcurrently has a fairly expensive load-load fence.
This fence is there because:
1. If the read of m_version in MarkedBlock::needsFlip isn't what's expected then;
2. The read of m_marks in MarkedBlock::isMarked needs to observe the value that was stored *before* m_version was stored.
This ordering isn't guaranteed on ARM, which has a weak memory model.
There are 3 ways to guarantee this ordering:
A. Use a barrier instruction.
B. Use a load-acquire (new in ARMv8).
C. use ARM's address dependency rule, which C++ calls memory_order_consume.
In general:
A. is slow but orders all of memory in an intuitive manner.
B. is faster-ish and has the same property-ish.
C. should be faster still, but *only orders dependent loads*. This last part is critical! Consume isn't an all-out replacement for acquire (acquire is rather a superset of consume).
ARM explains the address dependency rule in their document "barrier litmus tests and cookbook":
<span class="quote">> *Resolving by the use of barriers and address dependency*</span >
>
<span class="quote">> There is a rule within the ARM architecture that:</span >
>
<span class="quote">> Where the value returned by a read is used to compute the virtual address of a subsequent read or write (this is known as an address dependency), then these two memory accesses will be observed in program order. An address dependency exists even if the value read by the first read has no effect in changing the virtual address (as might be the case if the value returned is masked off before it is used, or if it had no effect on changing a predicted address value).
>
> This restriction applies only when the data value returned from one read is used as a data value to calculate the address of a subsequent read or write. This does not apply if the data value returned from</span >
one read is used to determine the condition code flags, and the values of the flags are used for condition code evaluation to determine the address of a subsequent reads, either through conditional execution or
the evaluation of a branch. This is known as a control dependency.
>
<span class="quote">> Where both a control and address dependency exist, the ordering behaviour is consistent with the address dependency. </span >
C++'s memory_order_consume is unfortunately unimplemented by C++ compilers, and maybe unimplementable as spec'd. I'm working with interested folks in the committee to fix this situation: <a href="http://wg21.link/p0190r2">http://wg21.link/p0190r2</a>
You'll note that this paper has a bunch of proposed solutions, no C++ implementation of any of them, and that Linux uses consume ordering in RCU successfully. I therefore intend to:
1. implement our own special-purpose dependency + consume in WebKit's Atomics.h;
2. Benchmark and use it in this location;
3. If that works out, commit and slowly start using it in other locations (which may require improving the hacky API I have in mind).
4. Feed this information back to the C++ standards committee so that C++Next has a proper way to use consume ordering.</pre>
</div>
</p>
<hr>
<span>You are receiving this mail because:</span>
<ul>
<li>You are the assignee for the bug.</li>
</ul>
</body>
</html>