1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
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.
|
