diff options
Diffstat (limited to 'notes/simple_to_parallel.txt')
-rw-r--r-- | notes/simple_to_parallel.txt | 83 |
1 files changed, 83 insertions, 0 deletions
diff --git a/notes/simple_to_parallel.txt b/notes/simple_to_parallel.txt new file mode 100644 index 0000000..c46bc59 --- /dev/null +++ b/notes/simple_to_parallel.txt @@ -0,0 +1,83 @@ +From simple to parallel +======================= + +Single-threaded code have some advantages: + +* Can modify data in place without issues +* Does not need synchronization +* Overall, it can be lightweight and simple + +Can code be made to be usable in both simple single-threaded code +as well as in multi-threaded code? + +(Note that single-threaded includes some forms of "shared nothing" +parallelism). + +In-place mutation vs. copy vs. specialized multi-threaded code +-------------------------------------------------------------- + +(The latter might be using some kind of multi-threading capable data structure) + +Let's say that there is a function that appends "=true" to a string if it does +not already end with "=true". + +This can be done in several ways: + +* In-place modification, if the string has sufficient capacity. +* Allocating a new string and writing the result string there. +* Using a thread-safe refcount to select the best strategy. +* Using some kind of data structure that allows this operation + to work without copying. E.g. a chain of delta encoded updates + to the string. This could be done in a lock-free/opportunistic way: + - Find the last delta entry of the string. + - Parse the string, check if it ends with "=true". + - Generate a "delta entry" to append. + - Atomically swap the pointer in the last delta entry + from null to the newly generated delta entry. + - If the swap operation fails, restart the process. + +The idea +-------- + +Can we generate "combined single/multi-threaded" code from the same source +code, and have the compiler (and/or runtime) select the appropriate code +variant? + +Related: Combined code for mutator methods: +1. pre-allocated result (with mandatory usage) +2. pre-allocated result (with optional usage, i.e. input lifetime is at least as long) +3. arena-allocated result +4. shallow-ref in-place modification (with existing refs) +5. deep-copy in-place modification (with copies of refs) + +For example, given source code like this: + + func String.append_if_absent(String suffix) -> String + { + if this.ends_with(suffix) { + return this + } else { + return .concat(this, suffix) + } + } + +It might be transformed into: + + func String.append_if_absent(arena, ref var String placement, String suffix) -> String + { + String result + transaction_start(arena, .[this]) + do { + if this.ends_with(suffix) { + result = .copy_if_needed(arena, placement, this) + } else { + # .concat selects the requested method 1-5 + result = .concat(arena, placement, this, suffix) + } + } while not transaction_commit(arena) + return result + } + +Apparently. something similar is done by Swift already and is called "value semantics". +- ...and apparently, it can still cause unintended behavior when a value + gets copied and then silently discarded. |