Third Teaser: Practical Multithreading

Guys, my future post on practical multithreading is going to be of epic scale (previous teaser). I wish I could split it up into multiple posts, but that would be too risky: I don’t want readers stumbling on a later part without having first read the earlier caveats.

So here is another teaser in the meantime. Suppose you have this code that works in a synchronous fashion:

//
//  ObjectCache.swift
//  AsyncObjectCache
//
//  Created by Pierre Lebeaupin on 10/02/2021.
//

import Foundation

class ObjectCache {
    class Slot {
        var data: Double?;
        
        init() {
            data = nil;
        }
        
        func getData(_ basePath: String,
                     _ index: UInt32) -> Double {
            if let solidData = data {
                return solidData; // our work here is done.
            }
            
            // Do the dirty work.
            let path = basePath.appendingFormat("/%lu.sprite", index);
            
            path.utf8CString.withUnsafeBufferPointer { ptr in
                let fd = open(ptr.baseAddress!, O_RDONLY);
                
                guard fd >= 0 else {
                    fatalError();
                }
                
                lseek(fd, off_t(8), SEEK_SET);
                
                var accum = ContiguousArray();
                accum.reserveCapacity(8);
                
                accum.withUnsafeMutableBufferPointer { mPtr in
                    guard read(fd, mPtr.baseAddress!, 8) == 8 else {
                        fatalError();
                    }
                };
                
                close(fd);
                
                var intermediate = UInt64(0);
                
                for byte in accum {
                    // decode from big-endian format
                    intermediate = (intermediate << 8) + UInt64(byte);
                }
                
                // Alleluia!
                data = Double(bitPattern: intermediate);
            };
            
            return data!;
        }
    }

    
    let base: String;
    let slots: Array;
    
    init(base inbase: String, count: UInt32) {
        base = inbase;
        var protoslots = Array();
        protoslots.reserveCapacity(Int(count));
        
        for _ in 0 .. Double {
        return slots[Int(index)].getData(base, index);
    }
}

Except for the use of Unix filesystem APIs, seems straightforward enough. But what if I want to make that work asynchronously so as to be safely callable from Grand Central Dispatch tasks? Here’s what you need to do:

//
//  AsyncObjectCache.swift
//  AsyncObjectCache
//
//  Created by Pierre Lebeaupin on 10/02/2021.
//

import Foundation

class AsyncObjectCache {
    class Slot {
        struct Functor {
            // silly struct just so I can make a
            // recursive function definition
            var invoke: (_ data: Double) -> Functor?;
        }

        var data: Double?;
        var insertNext: ((_ functor: Functor) -> Void)?;
        let q: DispatchQueue;
        var initialFunctor: Functor?;
        var launched: Bool;
        
        init() {
            q = DispatchQueue(label: "AsyncObjectCache slot protection");
            launched = false;

            insertNext = { [self] functor in
                initialFunctor = functor;
            }
            // Note that at this point there is a strong reference cycle
            // between the class instance and the closure; I see no way
            // around that.
            // The manual cleanup of the line, through initialFunctor,
            // ought to be enough to solve the situation.
        }
        
        func asyncGetData(_ basePath: String,
                          _ index: UInt32,
                          _ continuationQueue: DispatchQueue,
                          _ continuation: @escaping (_ data: Double) -> Void) {
            q.async { [self] in
                if let solidData = data {
                    continuationQueue.async {
                        continuation(solidData);
                    };
                    return; // our work here is done.
                }

                // TODO: move allocation of closures off of the
                // critical section to improve scalability?
                var next: Functor?

                insertNext!(Functor(invoke: { incomingData in
                    continuationQueue.async {
                        continuation(incomingData);
                    };

                    return next;
                }));
                
                insertNext = { functor in
                    next = functor;
                };
                
                guard !launched else {
                    return;
                }
                launched = true;
                
                // Do the dirty work.
                let path = basePath.appendingFormat("/%lu.sprite", index);
                
                path.utf8CString.withUnsafeBufferPointer { ptr in
                    let querier = DispatchIO(type: .random,
                                             path: ptr.baseAddress!,
                                             oflag: O_RDONLY,
                                             mode: 0,
                                             queue: q,
                                             cleanupHandler: {
                                                error in guard error == 0 else {
                                                    fatalError();
                                                }
                                             });
                    
                    var accum = DispatchData.empty;
                    
                    // At this point, launched is true, so newly
                    // launched tasks on our queue that are not the
                    // following one will not enter this clause:
                    // our state is consistent at this point, which
                    // is necessary for us to safely relinquish q.
                    querier!.read(offset: 8, length: 8, queue: q) {
                        (done, rawData, error)
                        in
                        guard error == 0 else {
                            fatalError();
                        }
                        
                        accum.append(rawData!);
                        
                        guard done else {
                            return;
                        }
                        
                        var intermediate = UInt64(0);
                        
                        for byte in accum {
                            // decode from big-endian format
                            intermediate = (intermediate << 8) + UInt64(byte);
                        }
                        
                        // Alleluia!
                        let incomingData = Double(bitPattern: intermediate);
                        var current = initialFunctor;
                        while let solidCurrent = current {
                            current = solidCurrent.invoke(incomingData);
                        }
                        
                        // clean up after ourselves
                        data = incomingData;
                        insertNext = nil;
                        initialFunctor = nil;
                    };
                };
            };
        }
    }

    
    let base: String;
    let slots: Array;
    
    init(base inbase: String, count: UInt32) {
        base = inbase;
        var protoslots = Array();
        protoslots.reserveCapacity(Int(count));
        
        for _ in 0 .. Void) {
        slots[Int(index)].asyncGetData(base, index, continuationQueue, continuation);
    }
}

Much less straightforward now, unfortunately.

Second Teaser: Practical Multithreading

My future practical multithreading post (previous teaser) is going to be a doozy. Let’s just say it will have diagrams. So here is another teaser to keep you waiting.

In the previous teaser, I showed you how I think you should be able to transform a long-lived function in the future in order to parallelize it. Now, it turns out such a transformation is already possible using non-experimental APIs or Swift features, but the result is clearly less elegant and less generalizable:

//
//  Created by Pierre Lebeaupin on 13/12/2020.
//  Copyright © 2020 Pierre Lebeaupin. All rights reserved.
//
// Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
//
// 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
//
// 3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//

import Foundation;

enum Op: String {
    case additive = "+", multiplicative = "*";
    
    func neutralValue() -> UInt32 {
        return ((self == .additive) ? 0 : 1);
    }
    
    func combine(_ a: UInt32, _ b: UInt32) -> UInt32 {
        return ((self == .additive) ? (a + b) : (a * b));
    }

    func uncombine(_ a: UInt32, _ b: UInt32) -> UInt32 {
        return ((self == .additive) ? (a - b) : (a / b));
    }
}


struct ReadyValue {
    let value: UInt32;
    let op: Op?;
    let description: () -> String;
    // Note that as a closure, it can depend on more than the stored properties, contrary to a
    // computed property.

    init(_ inValue: UInt32) {
        value = inValue;
        op = nil;
        description = { return inValue.description;};
    }
    
    init(value inValue: UInt32, op inOp: Op, description indescription: @escaping () -> String) {
        value = inValue;
        op = inOp;
        description = indescription;
    }
}

class ResolveObject {
    let semaphoreWaitingHost: Thread;
    // Using a thread, as the function is going to spend its time blocked in a semaphore,
    // so better directly use a thread than gum up the libdispatch machinery.
    
    init(_ startGoal: UInt32, _ inqueue: DispatchQueue, _ incb: @escaping (_ result: String) -> Void, _ completionCb: @escaping () -> Void, _ primitives: UInt32...) {
        semaphoreWaitingHost = Thread(block:{
            let /* 's */ avoidOvercommitment = DispatchSemaphore(value: ProcessInfo.processInfo.activeProcessorCount - 1);
            // We take one from the get go
            
            let completion = DispatchGroup();
            completion.enter(); // Compensated when the thread exits
            completion.notify(queue: inqueue, execute: completionCb);

            {
                var referenceL = [ReadyValue]();
                var referenceComposedCount = 0;
                var referenceOtherComposedCount = 0;
            
            
                for element in primitives {
                    referenceL.append(ReadyValue(element));
                }
            
                exploreAdditionOfRightNode(&referenceL,
                                           &referenceComposedCount,
                                           &referenceOtherComposedCount,
                                           isParent: true,
                                           kind: .additive);
                exploreAdditionOfRightNode(&referenceL,
                                           &referenceComposedCount,
                                           &referenceOtherComposedCount,
                                           isParent: true,
                                           kind: .multiplicative);
            }(); // https://bugs.swift.org/browse/SR-12243

            
            func exploreAdditionOfRightNode(_ l: inout [ReadyValue],
                                            _ composedCount: inout Int,
                                            _ otherComposedCount: inout Int,
                                            isParent: Bool,
                                            kind: Op) {
                if (l.count != 0) && (l[l.count - 1].op != kind) {
                    guard otherComposedCount == 0 else {
                        return;
                    }
                    
                    otherComposedCount = composedCount;
                    composedCount = 0;
                }
                defer {
                    if (l.count != 0) && (l[l.count - 1].op != kind) {
                        composedCount = otherComposedCount;
                        otherComposedCount = 0;
                    }
                }
                
                var referenceDecomposedValue = [false: kind.neutralValue(), true: kind.neutralValue()];
                
                iteratePossibleLeftNodesDispatch(&l,
                                                 &composedCount,
                                                 &otherComposedCount,
                                                 &referenceDecomposedValue,
                                                 isParent: isParent,
                                                 kind: kind,
                                                 startingFrom: 0,
                                                 { _ in return;});
            }

            func iteratePossibleLeftNodesDispatch(_ l: inout [ReadyValue],
                                                  _ composedCount: inout Int,
                                                  _ otherComposedCount: inout Int,
                                                  _ decomposedValue: inout [Bool:UInt32],
                                                  isParent: Bool,
                                                  kind: Op,
                                                  startingFrom: Int,
                                                  _ walkOperands: @escaping (_ action: (_ value: ReadyValue, _ reverse: Bool) -> Void) -> Void) {
                guard isParent else {
                    return iteratePossibleLeftNodes(&l,
                                                    &composedCount,
                                                    &otherComposedCount,
                                                    &decomposedValue,
                                                    isParent: isParent,
                                                    kind: kind,
                                                    startingFrom: startingFrom,
                                                    walkOperands);
                }
                
                var imminentlyViableOrBetter = false;
                walkOperands({_,_ in imminentlyViableOrBetter = true;});
                
                let workloadEstimator = l.count + (imminentlyViableOrBetter ? 1 : 0);
                /* Among other properties, this estimator value is monotonic. */
                
                // 6 may be too many to fit in a tick (1/60th of a second)
                // 4 already means too few possibilities to explore
                // 3 is right out
                if workloadEstimator == 5 {
                    // reseat this divergence over a copy of the whole state
                    var childL = l;
                    var childComposedCount = composedCount;
                    var childOtherComposedCount = otherComposedCount;
                    var childDecomposedValue = decomposedValue;
                    
                    DispatchQueue.global(qos:.userInitiated).async(group: completion) {
                        iteratePossibleLeftNodes(&childL,
                                                 &childComposedCount,
                                                 &childOtherComposedCount,
                                                 &childDecomposedValue,
                                                 isParent: false,
                                                 kind: kind,
                                                 startingFrom: startingFrom,
                                                 walkOperands);
                        
                        avoidOvercommitment.signal();
                    }
                    
                    avoidOvercommitment.wait();
                } else {
                    return iteratePossibleLeftNodes(&l,
                                                    &composedCount,
                                                    &otherComposedCount,
                                                    &decomposedValue,
                                                    isParent: isParent,
                                                    kind: kind,
                                                    startingFrom: startingFrom,
                                                    walkOperands);
                }
            }

            func iteratePossibleLeftNodes(_ l: inout [ReadyValue],
                                          _ composedCount: inout Int,
                                          _ otherComposedCount: inout Int,
                                          _ decomposedValue: inout [Bool:UInt32],
                                          isParent: Bool,
                                          kind: Op,
                                          startingFrom: Int,
                                          _ walkOperands: @escaping (_ action: (_ value: ReadyValue, _ reverse: Bool) -> Void) -> Void) {
                for candidateOffset in startingFrom .. Void) -> Void in
                            action(rightChild, reverse);
                            walkOperands(action);
                        };
                        
                        iteratePossibleLeftNodesDispatch(&l,
                                                         &composedCount,
                                                         &otherComposedCount,
                                                         &decomposedValue,
                                                         isParent: isParent,
                                                         kind: kind,
                                                         startingFrom: candidateOffset,
                                                         selfNode);
                        
                        // close current composition
                        guard ({
                            var num = 0;
                            selfNode({_,_ in num += 1;});
                            return num;
                        }() > 1) && ( (kind == .additive) ? decomposedValue[false]! > decomposedValue[true]! :
                                        ((decomposedValue[false]! % decomposedValue[true]!) == 0) ) else {
                            continue;
                        }
                        
                        let realizedValue = kind.uncombine(decomposedValue[false]!, decomposedValue[true]!);
                        let description = { () -> String in
                            var current = "(";
                            selfNode({(_ value: ReadyValue, _ freverse: Bool) -> Void in
                                current += " ";
                                current += (freverse ? (kind == .additive ? "-" : "/") : kind.rawValue);
                                current += " ";
                                current += value.description();
                            });
                            current += ")";
                            
                            return current;
                        };
                        
                        guard l.count > 0 else {
                            if realizedValue == startGoal {
                                let solution = description();
                                inqueue.async { incb(solution); };
                            }
                            continue;
                        }
                        
                        composedCount += 1;
                        l.append(ReadyValue(value: realizedValue, op: kind, description: description));
                        defer {
                            l.remove(at: l.count - 1);
                            composedCount -= 1;
                        }
                        
                        exploreAdditionOfRightNode(&l,
                                                   &composedCount,
                                                   &otherComposedCount,
                                                   isParent: isParent,
                                                   kind: .additive);
                        exploreAdditionOfRightNode(&l,
                                                   &composedCount,
                                                   &otherComposedCount,
                                                   isParent: isParent,
                                                   kind: .multiplicative);
                    }
                }
            }
            
            completion.leave();
        });
    }
    
    func start() {
        semaphoreWaitingHost.start();
    }
}

April fools’ 2016

In case you missed it, for April fools’ day in 2016 I shuffled all my posts such that, at the URL for one post, you would find a completely different one: for instance, at the address http://wanderingcoder.net/2010/06/02/intro-neon/ you would find Apple’s Golden Path, at the address http://wanderingcoder.net/2010/06/21/golden-path/ you would find A few things iOS developers ought to know about the ARM architecture, etc. This mostly affected people visiting from search engines or who followed an external link, though it was not hard for them to then locate the post they were actually interested in; for people who visited from the front page, the only really visible effect is that my first post had rolled over and appeared as the latest.

I hope those of you who stumbled upon this appreciated it, and as always, thank you for reading Wandering Coder.