Bug 170579 – Add a PriorityQueue class

• Status: RESOLVED
• Resolution: FIXED
• Component: New Bugs

[Keith Miller]

Add PriorityQueue class

[Keith Miller]

Created attachment 306450 [details]
Patch

[Yusuke Suzuki]

Comment on attachment 306450 [details]
Patch

I think we can use std::push_heap & std::pop_heap to simplify the implementation. What do you think of?

[Keith Miller]

Created attachment 306453 [details]
Patch

[Keith Miller]

(In reply to Yusuke Suzuki from comment #2)
> Comment on attachment 306450 [details]
> Patch
> 
> I think we can use std::push_heap & std::pop_heap to simplify the
> implementation. What do you think of?

I'm not sure that really helps since we need to have a siftUp and siftDown for the increaseKey/decreaseKey methods.

[Yusuke Suzuki]

(In reply to Keith Miller from comment #4)
> (In reply to Yusuke Suzuki from comment #2)
> > Comment on attachment 306450 [details]
> > Patch
> > 
> > I think we can use std::push_heap & std::pop_heap to simplify the
> > implementation. What do you think of?
> 
> I'm not sure that really helps since we need to have a siftUp and siftDown
> for the increaseKey/decreaseKey methods.

Seems right. While increaseKey can be implemented in push_heap, decreaseKey requires siftDown which is not directly offered by stl.

[Saam Barati]

Comment on attachment 306453 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=306453&action=review

PriorityQueue LGTM, just one thing looks weird to me about how you're using this in Plan. Comments below.

> Source/WTF/ChangeLog:19
> +        The only way to update the location of an entry is to do a hash
> +        table lookup with the entry's hash but this is probably more
> +        expensive than just doing a linear search.

This seems unlikely to be true if the heap gets large. Perhaps it's worth filing a bug to investigate this if it ever becomes an issue?

> Source/JavaScriptCore/wasm/WasmWorklist.cpp:112
> +            worklist.m_queue.enqueue(WTFMove(element));
>              worklist.m_planEnqueued->notifyAll(locker);
> +            element = worklist.m_queue.peek();

I'm confused as to what this is doing? What if you get back a different element when you do this?

Actually, this also looks like a potential problem in the old queue as well, except that it'd naturally handle it since it never WTFMove() the element, so in the worst case, you'd notify all your threads and they'd grab a bunch of new plans and validate them, instead of compiling the element's plan in parallel.

> Source/WTF/wtf/PriorityQueue.h:39
> +//

Style: remove empty "//"

> Source/WTF/wtf/PriorityQueue.h:54
> +    void enqueue(T&& element)
> +    {
> +        size_t location = m_buffer.size();
> +        m_buffer.append(WTFMove(element));
> +        siftUp(location);
> +    }

You should use forwarding semantics here.

> Source/WTF/wtf/PriorityQueue.h:106
> +    size_t parentOf(size_t location) const { ASSERT(location); return (location - 1) / 2; }
> +    size_t leftChildOf(size_t location) const { return location * 2 + 1; }
> +    size_t rightChildOf(size_t location) const { return leftChildOf(location) + 1; }

Style nit: I'd make these static constexpr

> Source/WTF/wtf/PriorityQueue.h:138
> +    IsHigherPriority isHigherPriority;

It's questionable that you need to instantiate a value here. Why not just have an API here that requires some static function called isHigherPriority(a, b)?

> Tools/TestWebKitAPI/Tests/WTF/PriorityQueue.cpp:34
> +constexpr std::size_t operator "" _z ( unsigned long long n ) { return n; }

Is this needed? You only use it in 2 places.

> Tools/TestWebKitAPI/Tests/WTF/PriorityQueue.cpp:196
> +}

It might also be worth having a test based off randomness, but for values being enqueued/dequeued, and total length of the test.

[Keith Miller]

Comment on attachment 306453 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=306453&action=review

>> Source/WTF/ChangeLog:19
>> +        expensive than just doing a linear search.
> 
> This seems unlikely to be true if the heap gets large. Perhaps it's worth filing a bug to investigate this if it ever becomes an issue?

Sounds good. I didn't mention this but it's also pretty rare that we actually use the  increase/decreaseKey functions so the cost of a O(n) is pretty rare. Also, the hash cost applies to enqueue and dequeue as well so changing the value of the key would likely need to be very common to outweigh the cost of searching.

>> Source/JavaScriptCore/wasm/WasmWorklist.cpp:112
>> +            element = worklist.m_queue.peek();
> 
> I'm confused as to what this is doing? What if you get back a different element when you do this?
> 
> Actually, this also looks like a potential problem in the old queue as well, except that it'd naturally handle it since it never WTFMove() the element, so in the worst case, you'd notify all your threads and they'd grab a bunch of new plans and validate them, instead of compiling the element's plan in parallel.

I think this works but only because compilation is strictly higher priority than validation. It might be conceptually simpler to poll again instead, however. I'll make that change.

>> Source/WTF/wtf/PriorityQueue.h:39
>> +//
> 
> Style: remove empty "//"

Fixed.

>> Source/WTF/wtf/PriorityQueue.h:54
>> +    }
> 
> You should use forwarding semantics here.

Fixed.

>> Source/WTF/wtf/PriorityQueue.h:106
>> +    size_t rightChildOf(size_t location) const { return leftChildOf(location) + 1; }
> 
> Style nit: I'd make these static constexpr

Changed.

>> Source/WTF/wtf/PriorityQueue.h:138
>> +    IsHigherPriority isHigherPriority;
> 
> It's questionable that you need to instantiate a value here. Why not just have an API here that requires some static function called isHigherPriority(a, b)?

Otherwise, you can't use std::less and friends as the comparator. If you think it's worth it we could implement our own template isLess, isGreater, etc.

>> Tools/TestWebKitAPI/Tests/WTF/PriorityQueue.cpp:34
>> +constexpr std::size_t operator "" _z ( unsigned long long n ) { return n; }
> 
> Is this needed? You only use it in 2 places.

Either way. I can replace it with a const size_t zero.

>> Tools/TestWebKitAPI/Tests/WTF/PriorityQueue.cpp:196
>> +}
> 
> It might also be worth having a test based off randomness, but for values being enqueued/dequeued, and total length of the test.

Sounds good.

[Keith Miller]

Created attachment 306530 [details]
Patch

[Saam Barati]

Comment on attachment 306530 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=306530&action=review

r=me

> Source/JavaScriptCore/wasm/WasmWorklist.cpp:184
> +    while (!m_queue.isEmpty()) {
> +        QueueElement element = m_queue.dequeue();
>          if (&element.plan->vm() == &vm) {
>              element.plan->cancel();
> -            return IterateResult::DropAndContinue;
> +            continue;
>          }

You need to rebase. This is no longer the code.

> Source/WTF/wtf/PriorityQueue.h:39
> +//

Please remove this.

> Source/WTF/wtf/PriorityQueue.h:138
> +    IsHigherPriority isHigherPriority;

I still don't quite understand why we need this, instead of something akin to HashTraits. Maybe file a bug to do this? It's unfortunate to make this class use more memory than needed. The only use of this class ATM will be a struct with no field members. It could just as easily be some abstract API.

[Keith Miller]

Created attachment 306536 [details]
Patch

[Keith Miller]

Created attachment 306537 [details]
Patch for landing

[WebKit Commit Bot]

Comment on attachment 306537 [details]
Patch for landing

Rejecting attachment 306537 [details] from commit-queue.

Failed to run "['/Volumes/Data/EWS/WebKit/Tools/Scripts/webkit-patch', '--status-host=webkit-queues.webkit.org', '--bot-id=webkit-cq-01', 'apply-attachment', '--no-update', '--non-interactive', 306537, '--port=mac']" exit_code: 2 cwd: /Volumes/Data/EWS/WebKit

Last 500 characters of output:
ScriptCore/wasm/WasmWorklist.h
patching file Source/WTF/WTF.xcodeproj/project.pbxproj
patching file Source/WTF/wtf/MathExtras.h
patching file Source/WTF/wtf/PriorityQueue.h
patching file Tools/ChangeLog
Hunk #1 succeeded at 1 with fuzz 3.
patching file Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj
patching file Tools/TestWebKitAPI/Tests/WTF/PriorityQueue.cpp

Failed to run "[u'/Volumes/Data/EWS/WebKit/Tools/Scripts/svn-apply', '--force']" exit_code: 1 cwd: /Volumes/Data/EWS/WebKit

Full output: http://webkit-queues.webkit.org/results/3492593

[Keith Miller]

Created attachment 306539 [details]
Patch for landing

[WebKit Commit Bot]

Comment on attachment 306539 [details]
Patch for landing

Rejecting attachment 306539 [details] from commit-queue.

Failed to run "['/Volumes/Data/EWS/WebKit/Tools/Scripts/webkit-patch', '--status-host=webkit-queues.webkit.org', '--bot-id=webkit-cq-01', 'build', '--no-clean', '--no-update', '--build-style=release', '--port=mac']" exit_code: 2 cwd: /Volumes/Data/EWS/WebKit

Last 500 characters of output:
athExtras.dia -c /Volumes/Data/EWS/WebKit/Source/JavaScriptCore/b3/B3MathExtras.cpp -o /Volumes/Data/EWS/WebKit/WebKitBuild/JavaScriptCore.build/Release/JavaScriptCore.build/Objects-normal/x86_64/B3MathExtras.o

** BUILD FAILED **


The following build commands failed:
	CompileC /Volumes/Data/EWS/WebKit/WebKitBuild/JavaScriptCore.build/Release/JavaScriptCore.build/Objects-normal/x86_64/WasmWorklist.o wasm/WasmWorklist.cpp normal x86_64 c++ com.apple.compilers.llvm.clang.1_0.compiler
(1 failure)

Full output: http://webkit-queues.webkit.org/results/3492675

[Keith Miller]

Created attachment 306554 [details]
Patch for landing

[WebKit Commit Bot]

Comment on attachment 306554 [details]
Patch for landing

Clearing flags on attachment: 306554

Committed r215135: <http://trac.webkit.org/changeset/215135>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Csaba Osztrogonác]

(In reply to WebKit Commit Bot from comment #16)
> Comment on attachment 306554 [details]
> Patch for landing
> 
> Clearing flags on attachment: 306554
> 
> Committed r215135: <http://trac.webkit.org/changeset/215135>

It broke the GTK build:
In file included from ../../Source/JavaScriptCore/wasm/WasmWorklist.h:35:0,
                 from ../../Source/JavaScriptCore/wasm/WasmWorklist.cpp:26:
../../Source/WTF/wtf/PriorityQueue.h: In instantiation of ‘static constexpr size_t WTF::PriorityQueue<T, isHigherPriority, inlineCapacity>::parentOf(size_t) [with T = JSC::Wasm::Worklist::QueueElement; bool (* isHigherPriority)(const T&, const T&) = JSC::Wasm::Worklist::isHigherPriority; long unsigned int inlineCapacity = 10ul; size_t = long unsigned int]’:
../../Source/WTF/wtf/PriorityQueue.h:110:44:   required from ‘void WTF::PriorityQueue<T, isHigherPriority, inlineCapacity>::siftUp(size_t) [with T = JSC::Wasm::Worklist::QueueElement; bool (* isHigherPriority)(const T&, const T&) = JSC::Wasm::Worklist::isHigherPriority; long unsigned int inlineCapacity = 10ul; size_t = long unsigned int]’
../../Source/WTF/wtf/PriorityQueue.h:52:24:   required from ‘void WTF::PriorityQueue<T, isHigherPriority, inlineCapacity>::enqueue(T) [with T = JSC::Wasm::Worklist::QueueElement; bool (* isHigherPriority)(const T&, const T&) = JSC::Wasm::Worklist::isHigherPriority; long unsigned int inlineCapacity = 10ul]’
../../Source/JavaScriptCore/wasm/WasmWorklist.cpp:112:81:   required from here
../../Source/WTF/wtf/PriorityQueue.h:103:95: error: body of constexpr function ‘static constexpr size_t WTF::PriorityQueue<T, isHigherPriority, inlineCapacity>::parentOf(size_t) [with T = JSC::Wasm::Worklist::QueueElement; bool (* isHigherPriority)(const T&, const T&) = JSC::Wasm::Worklist::isHigherPriority; long unsigned int inlineCapacity = 10ul; size_t = long unsigned int]’ not a return-statement
     static constexpr size_t parentOf(size_t location) { ASSERT(location); return (location - 1) / 2; }
                                                                                               ^

[Geoffrey Garen]

Comment on attachment 306554 [details]
Patch for landing

The std library has built-in heap functions. You should consider using those. (std has a priority queue as well. The only reason not to use it is that it will do the slow kind of allocation.)

[Darin Adler]

When I needed a priority queue in the Timer.cpp implementation, I used std::push_heap and std::pop_heap. RunLoopGeneric.cpp and LegacyTileGrid.mm also use this approach.

[Keith Miller]

(In reply to Geoffrey Garen from comment #19)
> The std library has built-in heap functions. You should consider using those.

(In reply to Darin Adler from comment #20)
> When I needed a priority queue in the Timer.cpp implementation, I used
> std::push_heap and std::pop_heap. RunLoopGeneric.cpp and LegacyTileGrid.mm
> also use this approach.

I considered using the std::push_heap and std::pop_heap methods but it's not possible to implement decreaseKey() with std::pop_heap and there is no officially supported std::sift_down method. Although, it is possible to implement increaseKey() with std::push_heap.

(In reply to Geoffrey Garen from comment #19)
> (std has a priority queue as well. The only reason not to use it is
> that it will do the slow kind of allocation.)

std::priority_queue does not support iterating the queue, which is important for the Wasm use case. Additionally, std::priority_queue does not support an increaseKey or decreaseKey method. While I could subclass std::priority_queue and implement those methods, if I'm going to go through that effort I might as well make a priority queue with all the bells and whistles I want.

[Geoffrey Garen]

Since increaseKey and decreaseKey are O(n) in their implementations here, you could get similar performance using std by just changing a key and then calling make_heap again.

I guess you've saved a little bit of performance since, after your O(n) search, you move the entry in O(log(n)) time, whereas make_heap would move the entry in O(n) time.