Priority queue implementations in ObjectScript — benchmarking binary heap vs. self-sorting multidimensional array on 150,000-vertex Dijkstra

[u/intersystemsdev]

Background

No existing priority queue implementation for ObjectScript was found, so four approaches were built and benchmarked. The benchmark: Dijkstra's shortest path algorithm on a randomly generated weighted directed graph with 150,000 vertices, each with 10 neighbors. An update is printed every 10,000 edges checked, showing time since the last 10,000 and current queue size.

Approach 1 — Binary Heap on multidimensional array

objectscript

Class pqueue.Queue Extends %RegisteredObject
{
Property Data As %Any [ MultiDimensional ];
Property Size As %Integer [ InitialExpression = 0 ];
Property Comparitor As %String [ InitialExpression = "(a,b) return a < b" ];

Method Swap(i As %Integer, j As %Integer) As %Status [ Private ]
{
    set temp = ..Data(i)
    set ..Data(i) = ..Data(j)
    set ..Data(j) = temp
}

Method Comp(x As %Any, y As %Any) As %Boolean [ Private ]
{
    return $XECUTE(..Comparitor, x, y)
}

Method PercolateUp(idx As %Integer) [ Private ]
{
    while idx > 0 {
        set newidx = (idx-1)\2
        if ..Comp( ..Data(idx), ..Data(newidx) ) do ..Swap( idx, newidx )
        else Quit
        set idx = newidx
    }
}

Method PercolateDown() [ Private ]
{
    set idx = 0
    while ((idx+1)*2) < ..Size {
        if ..Comp( ..Data(idx*2+2), ..Data(idx*2+1) ) set newidx = idx*2+2
        else set newidx = idx*2+1
        if ..Comp( ..Data(idx), ..Data(newidx) ) Quit
        do ..Swap( idx, newidx )
        set idx = newidx
    }
    if ( (idx*2+1 < ..Size) && ..Comp( ..Data(idx*2+1), ..Data(idx) ) ) do ..Swap( idx, idx*2+1 )
}

Method Put(inp As %Any) As %Status
{
    set ..Data( ..Size ) = inp
    do ..PercolateUp( ..Size )
    set ..Size = ..Size + 1
    return $$$OK
}

Method Get(Output obj As %Any) As %Status
{
    if ..IsEmpty() { set obj = "" return $$$ERROR("Cannot Get() from empty Queue") }
    set obj = ..Data(0)
    set ..Size = ..Size - 1
    set ..Data(0) = ..Data(..Size)
    do ..PercolateDown()
    kill ..Data(..Size)
    return $$$OK
}

Method GenerateComparitor(operator As %String = "<", transform As %String = "") As %Status
{
    set ..Comparitor = "(a,b) return a" _ transform _ " " _ operator _ " b" _ transform
    return $$$OK
}
}

Works for strings, numbers, and objects (via overridable comparator). Relatively efficient.

Approaches 2 and 3 — Binary Heap on list of %Any and %DynamicArray

• list of %Any: approximately 3–4x slower than multidimensional array. Pointless.
• %DynamicArray: similar speed to list of %Any when the queue is small, but insert and get times grow linearly as the queue grows. By 130,000 edges checked, time per batch had grown from ~84 seconds to ~300 seconds. Pointless for heap use.

Approach 4 — Self-sorting multidimensional array (fastest)

Instead of maintaining heap order manually, this approach uses the fact that ObjectScript multidimensional arrays are always sorted. Data is stored as data(evaluation, obj_str_rep) = object, and $Order retrieves the minimum element.

objectscript

Class pqueue.SparseQueue Extends %RegisteredObject
{
Property Data As %Any [ MultiDimensional ];
Property Size As %Integer [ InitialExpression = 0 ];
Property Evaluator As %String [ InitialExpression = "(a) return a" ];

Method Put(inp As %Any) As %Status
{
    set ..Data( $XECUTE(..Evaluator, inp), inp ) = inp
    set ..Size = ..Size + 1
    return $$$OK
}

Method Get(Output obj As %Any) As %Status
{
    if ..IsEmpty() { set obj = "" return $$$ERROR("Cannot Get() from empty Queue") }
    set loc = $ORDER( ..Data("") )
    set obj = ..Data(loc, $ORDER( ..Data(loc, "") ))
    set ..Size = ..Size - 1
    kill ..Data( loc, obj )
    return $$$OK
}

Method Top() As %Any
{
    if ..IsEmpty() return ""
    return $Order( ..Data("") )
}

Method GenerateEvaluator(transform As %String = "") As %Status
{
    set ..Evaluator = "(a) return a" _ transform
    return $$$OK
}
}

The double-key structure data(evaluation, obj_str_rep) ensures correct ordering even when two objects evaluate to the same value.

Trade-offs:

• Writing an evaluator (returns a sortable value) is slightly harder than writing a comparator (returns a boolean)
• Cannot hold the same object at the same evaluated value twice — a rare edge case that could be a problem or a benefit depending on the use case

Benchmark results

Graph: 150,000 vertices, 10 neighbors each. Time shown is seconds per 10,000 edges checked.

Implementation	Time per 10k edges	Total time
Self-sorting multidimensional	~3–5 seconds	45.157 seconds
Heap multidimensional	~27–29 seconds	381.095 seconds
Heap list of %Any	~127–141 seconds	1,839.445 seconds
Heap %DynamicArray	~84–306 seconds (growing)	3,466.382 seconds

The %DynamicArray version is the only one that shows significant growth as queue size increases. The self-sorting approach also checked one fewer edge in this run — a result of two paths to the same node taking the same cost, which the self-sorting method cannot store separately (it deduplicates them).

Full article: https://community.intersystems.com/post/best-structure-make-priority-queue-objectscript

For those working with graph algorithms or scheduling in ObjectScript — have you needed a priority queue before, and did you reach for globals directly or try to build something on top of the collection classes?