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();
}
}