Brad,
The domain resizing may represent a substantial performance hit. I
looked into using a fixed array and const domain with an internal index
on the heap size (see below); very pleasantly, this version is
comparable in speed to similar examples in C++ (and about 10-20 times
faster than my previous version). This suggests that an alternative
domain map could be very beneficial.
I have also provided a small discrete event simulation class and example
below.
Kindly, Mark.
/**
Mark Clements
2015-08-10
Apache v2.0
**/
class Heap {
type eltType;
const D : domain(1) = {0..1000}; // const
var heap : [D] eltType;
const FIRST : int = 0;
var LAST : int = -1; // that is, empty
proc left(pos : int) : int { return pos*2 + 1; }
proc right(pos : int) : int { return (pos+1)*2; }
proc parent(pos : int) : int { return (pos-1)/2; }
proc head() : eltType { return heap.head(); }
proc clear() { LAST = -1; } // current does _not_ clear values:
heap.clear() changes D
proc isEmpty() : bool { return LAST == -1; }
proc insert(x : eltType) {
// ASSERT( LAST < D.high )
LAST += 1;
heap[LAST] = x;
var k = LAST;
var k_parent : int;
while(k > FIRST) {
k_parent = parent(k);
if (heap[k] < heap[k_parent]) {
heap[k] <=> heap[k_parent];
k = k_parent;
} else {
return;
}
}
}
proc pop_first() : eltType {
// ASSERT( !isEmpty() )
var res : eltType = heap[FIRST];
if (FIRST == LAST) {
LAST -= 1;
return res;
}
heap[FIRST] = heap[LAST];
LAST -= 1;
var k = FIRST;
var k_next : int;
while(true) {
k_next = left(k);
if (k_next > LAST) {
break;
}
if (right(k) <= LAST && heap[right(k)] < heap[k_next]) {
k_next = right(k);
}
if (heap[k_next] < heap[k]) {
heap[k] <=> heap[k_next];
k = k_next;
} else {
break;
}
}
return res;
}
}
class cEvent {
var sendingTime : real;
var time : real;
proc action() { }
}
inline proc <(ev1 : cEvent, ev2 : cEvent) {
return ev1.time < ev2.time;
}
class Simulation {
var eq : Heap(cEvent) = new Heap(cEvent);
var simulationTime : real = 0.0;
var running : bool = false;
proc now() : real { return simulationTime; }
proc scheduleAt(time : real, ev : cEvent) {
ev.sendingTime = now();
ev.time = time;
eq.insert(ev);
}
proc run() {
simulationTime = 0.0;
running = true;
init();
while(!eq.isEmpty() && running) {
var ev : cEvent = eq.pop_first();
simulationTime = ev.time;
ev.action();
}
}
proc stop_simulation() { eq.clear(); running = false; }
proc init() { }
}
class Example : Simulation {
var show : bool = true;
class Tick : cEvent {
proc action() {
if (simulationTime < 5.0) {
if (show) then write("tick..");
scheduleAt(now()+1,new Tock());
} else {
if (show) then writeln("ring!");
stop_simulation();
}
}
}
class Tock : cEvent {
proc action() {
if (show) then write("tock..");
scheduleAt(now()+1,new Tick());
}
}
proc init() {
scheduleAt(1,new Tick());
}
}
var sim = new Example();
sim.run();
sim.show=false;
for i in 1..100000 {
sim.run();
}
On 07/29/2015 06:03 PM, Brad Chamberlain wrote:
> Hi Mark --
>
> I held off a day in responding because I didn't have any particularly
> insightful information and didn't want to preclude other responses by
> being the first to answer. But since nobody else has picked this up yet,
> I'll say that I'm not aware of other implementations of a heap/priority
> queue in Chapel at present. I don't believe that we ever received any code
> contributions back from the Kassel work that you mention. If you end up
> with code that you're happy with and would like to contribute back to the
> project (as part of the standard libraries, say, or even just a
> test/example code), please consider it.
>
> I think using Chapel's arrays are a reasonable way to express heaps in
> Chapel and, at a glance, like the approach you've taken below. I wanted
> to make one performance-oriented note on the use of the array's push/pop
> routines that you're using below (though you may already be aware of it),
> to note that the current default implementation of arrays doesn't amortize
> domain/array resizing as one would want/expect in cases like this. We
> have plans to provide an alternative domain map that supports amortized
> resizing for the next release to address this (and I'm sorry that we don't
> already have that ready -- I believe it's very low-hanging fruit. If it
> was of great short-term interest to you, we could look at whether it would
> be possible to bump its priority in short order).
>
> I'll note that one could also work around the lack of such a domain map by
> doing the recursive doubling/halving within your Heap class itself, but
> the amount of effort required is probably similar to (if not greater than)
> doing the work of the previous paragraph, so I'm not sure I'd suggest it
> unless you're really anxious to proceed on your own.
>
> One other note which may or may not matter for your work: At present, the
> push/pop-style operators are not task-safe, so if you were to parallelize
> operations on your heap class, you'd want to use some sort of coordination
> to avoid unsafe races.
>
> Hope this is helpful, and thanks for your interest in Chapel,
> -Brad
>
>
>
> On Tue, 28 Jul 2015, Mark Clements wrote:
>
>> Is there a standard implementation for a min-heap (or priority queue)
>> data structure in Chapel? (I want to implement simple discrete event
>> simulations in Chapel.) I noticed the interesting treatise from Kassel
>> by Marco Postigo Perez on "Distributed Priority Queue in Chapel" but
>> found no code.
>>
>> I have given a simple array-based implementation below, but I am
>> uncertain whether arrays are the best way to implement this.
>>
>> Kindly, Mark.
>>
>> // heap.chpl
>> // Mark Clements <[email protected]> 2015-07-28
>> // Apache v2.0
>>
>> class Heap {
>>
>> type eltType;
>> var D : domain(1) = {0..-1};
>> var heap : [D] eltType;
>> const FIRST : int = 0;
>>
>> proc last() : int { return heap.numElements-1; }
>> proc left(pos : int) : int { return pos*2 + 1; }
>> proc right(pos : int) : int { return (pos+1)*2; }
>> proc parent(pos : int) : int { return (pos-1)/2; }
>>
>> proc head() : eltType { return heap.head(); }
>> proc clear() { heap.clear(); }
>> proc isEmpty() : bool { return heap.isEmpty(); }
>>
>> proc insert(x : eltType) {
>> heap.push_back(x);
>> var k = last();
>> var k_parent : int;
>> while(k > FIRST) {
>> k_parent = parent(k);
>> if (heap[k] < heap[k_parent]) {
>> heap[k] <=> heap[k_parent];
>> k = k_parent;
>> } else {
>> return;
>> }
>> }
>> }
>>
>> proc pop() : eltType {
>> // assert( !heap.isEmpty())
>> var res : eltType = heap[FIRST];
>> if (FIRST == last()) {
>> heap.pop_back();
>> return res;
>> }
>> heap[FIRST] = heap[last()];
>> heap.pop_back();
>> var k = FIRST;
>> var k_next : int;
>> while(true) {
>> k_next = left(k);
>> if (k_next > last()) {
>> break;
>> }
>> if (right(k) <= last() && heap[right(k)] < heap[k_next]) {
>> k_next = right(k);
>> }
>> if (heap[k_next] < heap[k]) {
>> heap[k] <=> heap[k_next];
>> k = k_next;
>> } else {
>> break;
>> }
>> }
>> return res;
>> }
>> }
>>
>> var X = new Heap(int);
>> X.insert(2);
>> X.insert(3);
>> X.insert(1);
>> for i in 1..3 do writeln(X.pop());
>>
>> ------------------------------------------------------------------------------
>> _______________________________________________
>> Chapel-users mailing list
>> [email protected]
>> https://lists.sourceforge.net/lists/listinfo/chapel-users
>>
------------------------------------------------------------------------------
_______________________________________________
Chapel-users mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/chapel-users
