1

Hi Guys,

I was going through Operation.swift's code and I noticed an opportunity to improve the time complexity of operations like dequeue and remove.

The current implementation of OperationQueue uses an internal struct called _OperationList which contains 6 arrays of operations,

struct _OperationList {
    var veryLow = [Operation]()
    var low = [Operation]()
    var normal = [Operation]()
    var high = [Operation]()
    var veryHigh = [Operation]()
    var all = [Operation]()
}

When an operation is cancelled or finished, OperationQueue is calling _OperatonList.removing(_:Operation) method and when an operation is dequeued _OperationList.dequeue() is calling.

Now, given the nature of OperationQueue, which frequently adds, dequeues and removes operations from the queue, the program end up running at 0(n) runtime, for search and delete, as the operations are performed on Array data structure.

Im thinking this O(n) time can be reduced down to O(1) if we use LinkedList and HashTable together.

Heres the updated interface,

Double Linked List

internal class _IndexedOperationLinkedList {
    internal class Node {
        var operation: Operation
        var next: _IndexedOperationLinkedList.Node? = nil
        var previous: _IndexedOperationLinkedList.Node? = nil
    }
    
    private(set) var root: _IndexedOperationLinkedList.Node? = nil
    private(set) weak var tail: _IndexedOperationLinkedList.Node? = nil
    private(set) var count: Int = 0
    private var nodeForOperation: [Operation: _IndexedOperationLinkedList.Node] = [:]
    
    func insert(_ operation: Operation) { }
    func remove(_ operation: Operation) { }
    func removeFirst() -> Operation? { } 
    func map<T>(_ transform: (Operation) throws -> T) rethrows -> [T] { }
}

_OperationList

internal struct _OperationList {
    var veryLow = _IndexedOperationLinkedList()
    var low = _IndexedOperationLinkedList()
    var normal = _IndexedOperationLinkedList()
    var high = _IndexedOperationLinkedList()
    var veryHigh = _IndexedOperationLinkedList()
    var all = _IndexedOperationLinkedList()
    
    mutating func insert(_ operation: Operation) {
        all.insert(operation)
        
        switch operation.queuePriority {
        case .veryLow:
            veryLow.insert(operation)
        case .low:
            low.insert(operation)
        case .normal:
            normal.insert(operation)
        case .high:
            high.insert(operation)
        case .veryHigh:
            veryHigh.insert(operation)
        }
    }
    
    mutating func remove(_ operation: Operation) {
        all.remove(operation)
        
        switch operation.queuePriority {
        case .veryLow:
            veryLow.remove(operation)
        case .low:
            low.remove(operation)
        case .normal:
            normal.remove(operation)
        case .high:
            high.remove(operation)
        case .veryHigh:
            veryHigh.remove(operation)
        }
    }
    
    mutating func dequeue() -> Operation? {
        if let operation = veryHigh.removeFirst() {
            return operation
        }
        if let operation = high.removeFirst() {
            return operation
        }
        if let operation = normal.removeFirst() {
            return operation
        }
        if let operation = low.removeFirst() {
            return operation
        }
        if let operation = veryLow.removeFirst() {
            return operation
        }
        return nil
    }
    
    func map<T>(_ transform: (Operation) throws -> T) rethrows -> [T] {
        return try all.map(transform)
    }
}

Please give me your suggestions.

1 Like
2

Have you tested the performance of this? Array's theoretical O(n) performance often beats a linked list's O(1) in practice because of cache locality and avoiding memory allocations. Of course, I haven't looked at this, so maybe it is a win in this case.

3

@jrose thanks for the quick response.

Yes, I have performed measurement test using XCTest.measure { }, although I don't have the baseline for this measurement, the numbers I see for linked list based implementation is better than the array implementation.

Heres the test code snippet for the test,

    func test_OperationQueuePerformanceMeasurement() {
        let priorities: [Operation.QueuePriority] = [ .veryHigh, .high, .normal, .low, .veryLow ]
        
        let queue = OperationQueue()
        queue.maxConcurrentOperationCount = 1
        measure {
            var operations = [Operation]()
            for _ in 0...1000 {
                let operation = BlockOperation(block: { })
                operation.queuePriority = priorities.randomElement() ?? .normal
                operations.append(operation)
            }
            
            queue.addOperations(operations, waitUntilFinished: true)
        }
    }

I tried measurement for both, current and linked list implementation, with 1000, 500, 100, 10 number of operations. The results are below,

Current Implementation

1000 Operations
average: 4.059
relative standard deviation: 5.279%
values: [4.118417, 3.810524, 4.005855, 4.614813, 4.090776, 3.996997, 4.058232, 3.924490, 4.024753, 3.948501]
maxPercentRelativeStandardDeviation: 10.000%
maxStandardDeviation: 0.100

500 Operations
average: 1.162
relative standard deviation: 3.986%
values: [1.194851, 1.218860, 1.120588, 1.189215, 1.196692, 1.087050, 1.196618, 1.098075, 1.175428, 1.145848]
maxPercentRelativeStandardDeviation: 10.000%
maxStandardDeviation: 0.100

10 Operations
average: 0.003
relative standard deviation: 8.285%
values: [0.003790, 0.003167, 0.003243, 0.003103, 0.003118, 0.003006, 0.002971, 0.003039, 0.002859, 0.002953]
maxPercentRelativeStandardDeviation: 10.000%
maxStandardDeviation: 0.100

--

Linked List Implementation

1000 Operations
average: 0.173
relative standard deviation: 3.914%
values: [0.178822, 0.180436, 0.178626, 0.180535, 0.165167, 0.163331, 0.176456, 0.174253, 0.168144, 0.166332]
maxPercentRelativeStandardDeviation: 10.000%
maxStandardDeviation: 0.100

500 Operations
average: 0.102
relative standard deviation: 3.473%
values: [0.101013, 0.097204, 0.096554, 0.107769, 0.104321, 0.102416, 0.104235, 0.106209, 0.101869, 0.102254]
maxPercentRelativeStandardDeviation: 10.000%
maxStandardDeviation: 0.100

100 Operations
average: 0.018
relative standard deviation: 4.641%
values: [0.017459, 0.017175, 0.017106, 0.017388, 0.018774, 0.019306, 0.018784, 0.019071, 0.018116, 0.018749]
maxPercentRelativeStandardDeviation: 10.000%
maxStandardDeviation: 0.100

10 Operations
average: 0.002
relative standard deviation: 6.390%
values: [0.002861, 0.002572, 0.002399, 0.002386, 0.002376, 0.002443, 0.002455, 0.002348, 0.002348, 0.002376]
maxPercentRelativeStandardDeviation: 10.000%
maxStandardDeviation: 0.100

--

Looking at the numbers, the trend Im seeing is that, as the number of operations increases, the linked list based implementation's performance looks better than array based implementation.

Hope Im doing the measurement correct, please correct me if Im wrong.

1 Like
4

Okay, then maybe it is worth it! @millenomi, what do you think?

2 Likes
5

Speaking as someone with zero expertise nor experience here, from a purely theoretical perspective I would have rather expected to see a priority queue being used for this type of application.

6

Shouldn't this be weak or unowned?

2 Likes
7

Hi Nevin,

I thought about implementing Priority Queue, but following are the reasons I decided to go with linked list based approach,

  • Priority queue do insert and delete-next-prioritized-item in O(log N) time.
  • We need random access to the elements in queue, not just the first element. Finding that element is again is O(n) time
  • Besides, Im guessing, it is gonna be quite a challenge to keep the operations of same priority, in the same order as it was added in the queue.

In linked list based approach we could do insert, delete-next-prioritized in O(1) and with the use of hash map deleting a random item also comes down to O(1).

Hope I made a correct decision.

1 Like
8

Thanks @TellowKrinkle, good catch. I will update the property previous as a weak reference. You have saved a potential retain cycle.

1 Like
9

FYI NSOperationQueue (objc) uses a doubly linked list with the heads stored in the queue and next/prev stored in the NSOperations (all of these are stored as unsafe references balanced by a retain on add and a release on finish/cancel). It is worth noting there are a few caveats from a threading perspective: 1) all mutations to the list are done under the lock from the queue, and 2) the queue is strongly referenced by the operations and cleared after finished/cancelled.

1 Like
10

Hi @Philippe_Hausler

Sorry, Im unable to completely understand your reply. Are you suggesting any changes to my approach or a different approach altogether? Or Is this proposed solution of mine good to go?

11

I am saying that your approach is accurate to how the objc version is implemented. In short; I think it is a salient method of implementing it and is worthwhile to eek out some more perf here.

2 Likes
12

Thanks @Philippe_Hausler