修订版 | b181a1b05a4ea79f273d3606aeafa2d69f4ba561 (tree) |
---|---|
时间 | 2024-03-28 04:20:34 |
作者 | Albert Mietus < albert AT mietus DOT nl > |
Commiter | Albert Mietus < albert AT mietus DOT nl > |
CCastle-4.blog: Updated theSieve & Heisenbug -- keep in simple. Move (upcomming) variants to other blog
@@ -0,0 +1,174 @@ | ||
1 | +.. (C) 2023,2024 Albert Mietus. Part of CCastle project | |
2 | + | |
3 | +.. _Castle-TheSieve: | |
4 | + | |
5 | +========================= | |
6 | +The Sieve (basic variant) | |
7 | +========================= | |
8 | + | |
9 | +.. post:: 2024/03/25 | |
10 | + :category: CastleBlogs, Demo | |
11 | + :tags: Castle | |
12 | + | |
13 | + | |
14 | + To show some features of CCastle, I use *‘the Sieve’*, short for the `Sieve of Eratosthenes | |
15 | + <https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes>`__. An old, well-known, algorithm to find prime numbers; with | |
16 | + implicit concurrency. | |
17 | + | |
18 | + With an almost trivial implementation, many “CC concepts” can be shown; in only a handful of lines.... | |
19 | + | |
20 | +Several variants of ‘the Sieve’ will be presented to introduce various concepts. This is the most basic one. As we will | |
21 | +see, it does contain a :ref:`Heisenbug <Castle-Heisenbug>`, which will only be solved in another variant. | |
22 | +|BR| | |
23 | +Aside from demonstrating some CCastle concepts, ‘the Sieve’ (in all its variants) is used also to demo the compiler (see | |
24 | +:ref:`Castle-WorkshopTools`). | |
25 | + | |
26 | + | |
27 | + | |
28 | +The design | |
29 | +********** | |
30 | + | |
31 | +We only need three simple components as shown below, and a main component (not shown). We also use two protocols, which | |
32 | +are given below. | |
33 | + | |
34 | +.. include:: ./sieve-design.irst | |
35 | + | |
36 | +The elements of the sieve | |
37 | +========================= | |
38 | + | |
39 | +CCastle uses “components” [#not-package]_ as the main decomposition. Each kind of component can be instantiated multiple | |
40 | +times; sometimes called an *element*, or also just a *component*. This is very alike the difference between *“classes” | |
41 | +and “objects”* in OO [#active-class]_. | |
42 | + | |
43 | +Let’s introduce those components | |
44 | + | |
45 | +Generator | |
46 | +--------- | |
47 | + | |
48 | +This component generates just numbers, which will be tested for prime (see below). As primes are always integers bigger | |
49 | +than one; the output is the stream stream of numbers: 2,3,4, … | |
50 | + | |
51 | +Sieve (on prime) | |
52 | +---------------- | |
53 | + | |
54 | +We use a (growing) chain of sieve elements. Each one is the same; except for the sieving constant --an already found | |
55 | +prime. That number is set when instantiating the element. | |
56 | + | |
57 | + | |
58 | +Each Sieve tries to divide each incoming number by its own, sieve-constant. When the modulo isn’t zero, we call it a | |
59 | +*coprime* (relative to the already tested primes) and send it downstream. When it can be divided, the number is not | |
60 | +prime and ignored. | |
61 | + | |
62 | +Finder | |
63 | +------ | |
64 | + | |
65 | +Each number that comes out of the chain of sieves is a prime (that is the algorithm; see Wikipedia for details). It is | |
66 | +collected by the finder. For each found prime, an extra sieve (element) is created and added to the chain. This kind | |
67 | +of shifts the finder to the right (aka downstream) | |
68 | + | |
69 | +In some implementations that is the responsibility of the finder (therefore sometimes called “head”). In a variant, the | |
70 | +‘main’ component is carrying that load. | |
71 | + | |
72 | +Communication | |
73 | +============= | |
74 | +.. include:: ./sieve-protocols-sidebar.irst | |
75 | + | |
76 | +CCastle uses “protocols” to communicate between components. There are several kinds of protocols; we use the ‘event’ kind | |
77 | +here. Two ports can be connected when both use the same protocol. | |
78 | + | |
79 | +Notice, that a *protocol* is not the same as an API in most languages; it is a fundamental concept of the :ref:`CC` | |
80 | +concept of CCastle. And enforced the strict separation between “outside” and “inside” of a component. No implementation detail of a | |
81 | +component can call the interface of another component -- it has to be routed by ports and protocols. | |
82 | + | |
83 | +StartSieve | |
84 | +---------- | |
85 | + | |
86 | +With the StartSieve protocol, the sieving (so generating numbers) is started. The passed parameter is the maximum number to check for | |
87 | +“primeness”, and so forces a halt. In this (dumb) demo, there is no direct way to specify the number of primes to find. | |
88 | + | |
89 | +There is however an option to change that maximum number, with the ``newMax(int:max)`` event. | |
90 | +|BR| | |
91 | +In this demo, that event has no effect when the (old) max is already reached -- it is trivial to improve, but that is | |
92 | +outside the scope of this demo. | |
93 | + | |
94 | +SimpleSieve | |
95 | +----------- | |
96 | + | |
97 | +In this variant, we use an event-based protocol, that just holds one event (read: a message), that | |
98 | +carries the integer to be tried. | |
99 | + | |
100 | +The ``input(int:try)`` event gives *input* to the (next) sieve, carrying the number to *try*. | |
101 | + | |
102 | + | |
103 | +Heisenbug | |
104 | +--------- | |
105 | + | |
106 | +As we will see in :ref:`Castle-Heisenbug`, this design has a flaw. Depending on :ref:`TheMachinery`, the algorithm may | |
107 | +work, or terminate early. To manage the (variability in) concurrent communication, the protocol(s) have to be enriched. | |
108 | +|BR| | |
109 | +As it does work with the simple (:ref:`Machinery-DirectCall`) machinery, and as it is just a “Hello World” demo, we | |
110 | +prefer this imperfect version for the demo, as a kind of reference. | |
111 | + | |
112 | +.. attention:: Do not use this example in real (generic, production) code. | |
113 | + | |
114 | + See the variant(s) for an improved version. For example: :ref:`SlowStart-Sieve` details.) | |
115 | + | |
116 | +The Code | |
117 | +******** | |
118 | + | |
119 | +Below, we show all Castle-code for the components. With some comments to explain some typical castle concepts. | |
120 | +|BR| | |
121 | +Some parts (like import-lines) are not shown. See the code examples for full examples. | |
122 | + | |
123 | +Moat (*interfaces*) | |
124 | +=================== | |
125 | + | |
126 | +“Moat files” are like the interfaces, or *contracts*, to the components. The above-shown protocols are also part of | |
127 | +those *Moat files* -- but as they are already shown, we will not repeat them. | |
128 | + | |
129 | + | |
130 | +.. include:: ./sieve-moat.irst | |
131 | + | |
132 | +Castle (*implementation*) | |
133 | +========================= | |
134 | + | |
135 | +The “Castle files” contain the implementation of all components. | |
136 | + | |
137 | +.. include:: ./sieve-castle.irst | |
138 | + | |
139 | +Main | |
140 | +==== | |
141 | + | |
142 | +Components have to be created (statically or dynamically) into “elements”. This is typically done by a component that | |
143 | +‘holds’ the “sub-components” -- look for the ``sub`` [#subalias]_ keyword. This applies to all levels. | |
144 | + | |
145 | +At the very top, there is one element --usually called “main” -- that holds the major elements. In this example, that are | |
146 | +the `Generator`, the `Finder` and the `Sieve`\s themself. | |
147 | + | |
148 | +Note that “main” isn’t special. Unlike in C/C++ there is no need for a (single) main. The name *main* is more of a | |
149 | +convention (like in Python). | |
150 | +|BR| | |
151 | +Any component with a ``powerOn()`` method will act as (a) main component. | |
152 | + | |
153 | + | |
154 | +.. include:: ./sieve-main.irst | |
155 | + | |
156 | +---------- | |
157 | + | |
158 | +.. rubric:: Footnotes | |
159 | + | |
160 | +.. [#not-package] | |
161 | + A CCastle **component** is unrelated to a *UML component*. It is **not** a package, as many people use for the UML variant. | |
162 | + | |
163 | +.. [#active-class] | |
164 | + A (CCastle) **component** (or actually, an element) is sometimes described as an “active class (aka object)” -- a | |
165 | + class with a thread inside. This is not completely correct, but gives a good, first impression. | |
166 | + |BR| | |
167 | + Notice however there a no threads in CCastle -- just concurrency and parallelism. | |
168 | + | |
169 | +.. [#subalias] | |
170 | + You will encounter both ``sub`` and ``alias`` in this example. Both refer to a (sub)component inside the element, | |
171 | + with a small difference. A `sub` is part of the current element, whereas an `alias` is more a (temporally) reference to | |
172 | + *sub* -- for example, the last (most right) sieve element in the chain. | |
173 | + | |
174 | +.. LocalWords: coprime Heisenbug |
@@ -0,0 +1,213 @@ | ||
1 | +.. (C) 2023,2024 Albert Mietus. Part of CCastle project | |
2 | + | |
3 | +.. _Castle-Heisenbug: | |
4 | + | |
5 | +======================== | |
6 | +A Heisenbug in the Sieve | |
7 | +======================== | |
8 | + | |
9 | +.. post:: 2024/03/27 | |
10 | + :category: CastleBlogs, Castle, DesignStudy | |
11 | + :tags: Castle, DRAFT | |
12 | + | |
13 | + In Castle, one can dynamically connect components and send *events* over those connections. Typically, this is an | |
14 | + action on an incoming message (see: :ref:`CCC-Actors`). And depending on ‘:ref:`TheMachinery`’, those events can be | |
15 | + queued. It is this combination that *can result* in a **beautiful Heisenbug**. | |
16 | + | |
17 | + First, let’s explain the Heisenbug, before we give an example. Then we analyze it, show how to improve the code, and | |
18 | + finally formulate a *requirement* to prevent & detect this kind of bug in Castle. | |
19 | + | |
20 | +What is a Heisenbug? | |
21 | +==================== | |
22 | + | |
23 | +The `heisenbug <https://en.wikipedia.org/wiki/Heisenbug>`__ is named after the theoretical physics *Werner Heisenberg*, who | |
24 | +described the *“observer effect”*: when you look closely, the behaviour changes. The same can happen to software | |
25 | +(bugs). The behaviour apparently changes when you study -or slightly adjust- that code. Often, this is due to small | |
26 | +changes in timing, possibly even in generated code. Therefore old (old-fashioned) sequential code on slow CPUs is less | |
27 | +likely to have heisenbugs than concurrent code on fast multi-core systems. It’s also common in threaded programs. | |
28 | + | |
29 | +.. include:: ./Heisenbug-sidebar-Sequence.irst | |
30 | + | |
31 | +The Sieve goes wrong | |
32 | +==================== | |
33 | + | |
34 | +My standard example, :ref:`Castle-TheSieve`, suffered from this issue. The initial version did work for years | |
35 | +but failed horribly when another “machinery” was used. After studying this, the bug is simple and easy to fix. | |
36 | + | |
37 | +There are two related timing issues that together result in the Heisenbug. First, we introduce them and then | |
38 | +show how the combination may fail. | |
39 | + | |
40 | + | |
41 | +Event-order | |
42 | +----------- | |
43 | + | |
44 | +Conceptually, the `Generator` sends (events with) integers to `Sieve(2)`, which may forward them to `Sieve(3)`, then to | |
45 | +`Sieve(5)`, etc. As shown in the **Conceptual sidebar**, we probably assume that each integer is sieved before the next | |
46 | +*’int’* *starts*: the classic “sequential view” we are used to. | |
47 | + | |
48 | +However, that isn’t how it works. In Castle, *only* the order of events on a single connection is defined (*one by one, | |
49 | +sequential*). And given the code, the integer sent by a `Sieve` is always later than the incoming one. That is all we | |
50 | +may assume. | |
51 | +|BR| | |
52 | +The timing of unrelated events on multiple connections is not defined. That order may depend on :ref:`TheMachinery` and | |
53 | +many other factors. Do not assume any order -- as I did! | |
54 | + | |
55 | + | |
56 | +The diagram in the **One-by-One** sidebar shows another (allowed) order. The Generator outputs all events first before | |
57 | +Sieve(2) starts filtering. Then, the odd integers are passed to Sieve(3), which processes all its input, then Sieve(5), | |
58 | +etc. | |
59 | +|BR| | |
60 | +Although we aren’t using concurrency, and it needs tremendous buffers when finding big primes, it does conceptually | |
61 | +work. And so, it is an allowed execution [#ButImprove]_. | |
62 | + | |
63 | +As that order is “possible” we should have a design (and code) that handles it. But it doesn't ... (in the basic variant). | |
64 | + | |
65 | +Reconnecting | |
66 | +------------ | |
67 | + | |
68 | +The chain of `Sieve`\s will grow as we find more primes. Whenever an *int* isn’t filtered out and reaches the `Finder` a | |
69 | +*new prime* is found. Then, a new Sieve element is created and inserted into the chain. | |
70 | +|BR| | |
71 | +Building the chain is done by the Main component (which is signalled by the Finder) [#orVariant]_. | |
72 | + | |
73 | +Therefore, `Main` remembers the ``last_sieve`` and reconnects that output to the newly created `Sieve`. | |
74 | +Which output is temporally connected to the `Finder` | |
75 | +|BR| | |
76 | +For every newly found prime, this is repeated. | |
77 | + | |
78 | +This detail is shown in the “**with Details**” sidebar diagram; where the `Finder` and `Main` and all its messages | |
79 | +are shown too. | |
80 | + | |
81 | +Assuming the initial “conceptual” order, you will see the same Sieve(s) become alive (“new” message), and are added to | |
82 | +the end of the sieve chain. The integers still flow (now, shown as “try(`int`)” messages) by this sieve. | |
83 | +|BR| | |
84 | +You will also notice the `Finder` does indeed find all primes. | |
85 | + | |
86 | + | |
87 | +The combination | |
88 | +=============== | |
89 | + | |
90 | +Now let us study how the sieve chain will grow with a “fast generator”, and the one-by-one order of events is used. This | |
91 | +diagram is shown below. | |
92 | + | |
93 | +As we can see in the picture, it goes dreadfully wrong. No proper chain is created, and we will find integers like **4** | |
94 | +and **6**. This is wrong, they are not prime. | |
95 | +|BR| | |
96 | +With a (very) *fast Generator*, **all** integers are sent to the `Finder` --before any `Sieve` is created, and so any | |
97 | +int is reported as prime. besides, too many elements are added to the chain as a Sieve component is created for each found | |
98 | +“prime”. On top of that, no integer is ever sieved... | |
99 | + | |
100 | +This is just **an** example. As we can’t predict (or assume) any order, we can find other results too. And, when we add | |
101 | +“debugging print statement” (and *look closer*), we change the timing and will find other results. We found the | |
102 | +*observer effect*! | |
103 | + | |
104 | +.. uml:: ./sieve-Sequence-Wrong.puml | |
105 | + | |
106 | + | |
107 | +.. warning:: | |
108 | + | |
109 | + It is not *“the timing”* that is wrong! | |
110 | + |BR| | |
111 | + A concurrent program is only correct when it goes right for **any** possible timing. | |
112 | + | |
113 | + As in all software engineering, we can prove it is buggy when it goes wrong at least once. That is what we have | |
114 | + shown. And so, the original code is *wrong*. | |
115 | + | |
116 | + | |
117 | +How to improve? | |
118 | +=============== | |
119 | + | |
120 | +Finding this heisenbug triggered an investigation to improve Castle as well as ‘:ref:`Castle-TheSieve`’. Where our goal | |
121 | +is not just to improve the sieve code, but all programs. And give the programmer options to prevent heisenbugs. | |
122 | + | |
123 | +As we will see fixing ‘:ref:`the sieve <Castle-TheSieve>` is simple: use the **SLowStart** (base) protocol. It changes | |
124 | +only three lines! | |
125 | +|BR| | |
126 | +But we start with a new requirement, for a new tool in the :ref:`Castle Workshop <Workshop-Design>`. | |
127 | + | |
128 | + | |
129 | +Simulation | |
130 | +---------- | |
131 | + | |
132 | +As we will see below the `SlowStart` protocol will *remove* our Heisenbug. But it does not abolish the Heisenbug! | |
133 | + | |
134 | +The feature does by no means prevent a developer from using other solutions, with a comparable flaw. Besides, it’s | |
135 | +hopeless to use testing to prove the absence of a Heisenbug. As we have seen above, all variants of all possible | |
136 | +concurrent execution orders should be correct. Where we have very limited control over which variant is used. | |
137 | + | |
138 | +This led to a new requirement: :need:`U_Tools_EventOrder.` To assist the developer the Castle Workshop will come | |
139 | +with tools to detect such bugs. See :ref:`simulation` for more on this. | |
140 | + | |
141 | + | |
142 | +.. include:: ./sieve-protocols2-sidebar.irst | |
143 | +SlowStart | |
144 | +--------- | |
145 | + | |
146 | +Castle (now) comes [#KipEi]_ with the parametric *base* protocol :ref:`SlowStart <doc-SlowStart>`, which is based on | |
147 | +`TCP Slow start <https://en.wikipedia.org/wiki/TCP_congestion_control#Slow_start>`__ and contains a queueing model | |
148 | +[#ModelOnly]_ to control the speed of an (event) connection. As the name suggests, initially the connections with be | |
149 | +slow. Roughly, the parameter set the maximal number of unhandled events on a connection. | |
150 | +|BR| | |
151 | +The (improved) version of :ref:`Castle-TheSieve` uses a SlowStart of **1**. And `Main` will remove (or increase) that | |
152 | +limit after reconnecting. | |
153 | + | |
154 | +Initially, the `Generator` is only *allowed* to send one event, which is received by the `Finder`. Then, `Main` will create | |
155 | +the first Sieve (`Sieve(2)`), reconnect the Generator to that component, and increase the “speed” of the | |
156 | +connection. As the connection **Generator->Sieve(2)** is stable, the is no need to limit the “queue”. | |
157 | + | |
158 | +The `Generator` acts as before: it sends (events with) integers over its output. But now, the SimpleSieve protocol can | |
159 | +slow down the `Generator` --no code changes are needed for this. This may happen when the second event is sent before | |
160 | +it is received (or “handled”) by the Finder, and the limit is set to **1**. | |
161 | +|BR| | |
162 | +As this limit is removed when a Sieve-component is inserted into the chain, only the start is slow... | |
163 | + | |
164 | +The same happens to every Sieve: initially (when it is connected to the Finder) there is a limit of 1 event in the | |
165 | +queue. But when that connection is reconnected --and the potential Heisenbug is gone-- the limit is removed. | |
166 | + | |
167 | +.. tip:: Unlimited or better? | |
168 | + | |
169 | + In this blog, we remove the limit of the ``SlowStart protocol`` completely, for simplicity. Then the Heisenbug is | |
170 | + solved. | |
171 | + | |
172 | + That is not the only option. | |
173 | + |BR| | |
174 | + Given the `Generator` is a simple loop it can produce many integers fast. And so causes huge piles of queued | |
175 | + events. That can be done better, by the same concept: a maximal queue size. (again: just model). | |
176 | + | |
177 | + It’s up to the developer to optimize this. Some prefer the maximum queue length equal to the number of | |
178 | + Sieve-components, others relate the maximum queue length to the number of available cores. Some use static values, | |
179 | + others will adjust them over the run-time of the application. | |
180 | + |BR| | |
181 | + That is all possible with a few lines in the `Main` component. But also the Sieve component can set this | |
182 | + limit, both for incoming ports as well for outgoing ports. | |
183 | + | |
184 | + | |
185 | + | |
186 | +----- | |
187 | + | |
188 | +.. rubric:: Footnotes | |
189 | + | |
190 | +.. [#orVariant] | |
191 | + Again, there are many variants of :ref:`Castle-TheSieve`. In some adding a `Sieve` to the chain is done by the `Finder`, | |
192 | + in others by `Main`. In both alternatives, the same reconnect is needed. There is no real difference -- but the name | |
193 | + of the component initiating the change. | |
194 | + |BR| | |
195 | + The Heisenbug will not (trivially) disappear when switching between hose variants | |
196 | + | |
197 | +.. [#ButImprove] | |
198 | + Still, as language designers, we need to give the programmer more options to hint at a more optimal implementation. | |
199 | + | |
200 | +.. [#KipEi] | |
201 | + This *SlowStart* base protocol is part of Castle; see :ref:`Protocol-SlowStart`. But the need for it follows | |
202 | + --like this blog-- from the discovery of these :ref:`Castle-Heisenbug` in :ref:`Castle-TheSieve`. | |
203 | + | |
204 | + | |
205 | +.. [#ModelOnly] | |
206 | + Remember, this queue exists as a *model* **only** (like everything in Castle-code)! | |
207 | + |BR| | |
208 | + Depending on ‘:ref:`TheMachinery`, there may be no need to implement the queue (e.g.with DirectCall) at all; or there may | |
209 | + only be a queue length and -maximum, or ... | |
210 | + | |
211 | + | |
212 | + | |
213 | +.. LocalWords: heisenbug heisenbugs |
@@ -1,27 +1,29 @@ | ||
1 | -.. -*- rst -*- | |
2 | - included in `a.Heisenbug.rst` | |
1 | +.. -*- rst -*- (C) 2023,2024 Albert Mietus. Part of CCastle project | |
2 | + included in `2.Heisenbug.rst` | |
3 | 3 | |
4 | -.. sidebar:: | |
4 | +.. Sidebar:: | |
5 | 5 | |
6 | 6 | .. tabs:: |
7 | 7 | |
8 | 8 | .. tab:: Conceptual |
9 | 9 | |
10 | - This diagram shows the order of messages in a logical order. As we show only the integers that are tested for | |
11 | - (relative) prime, it looks simple and error-free. | |
10 | + This diagram shows the order of messages in a logical order. Hence, we show the “sieving sequence” per | |
11 | + integer. The following number starts only after finding a prime. | |
12 | + |BR| | |
13 | + It looks simple and error-free. | |
12 | 14 | |
13 | 15 | .. uml:: ./sieve-Sequence-concept.puml |
14 | 16 | |
15 | 17 | .. tab:: One-by-One |
16 | 18 | |
17 | - But there is no guarantee for that the simple, conceptual order. For example, the Generator can be *“fast”* and | |
19 | + But there is no guarantee for that simple, conceptual order. For example, the Generator can be *“fast”* and | |
18 | 20 | produce the to-be-sieved integers faster than the Sieves handle. |
19 | 21 | |
20 | 22 | .. uml:: ./sieve-Sequence-1b1.puml |
21 | 23 | |
22 | - .. tab:: With Details | |
24 | + .. tab:: with Details | |
23 | 25 | |
24 | - Adding components-creation (with reconnects) shows a lot more details. We added the event/port names, for | |
26 | + Adding components-creation (with reconnects) shows a lot more details. Also, we added the event/port names for | |
25 | 27 | clarity. When studying carefully, we can already see there might be a problem when the order changes |
26 | 28 | |
27 | 29 | .. uml:: ./sieve-Sequence-details.puml |
@@ -1,210 +0,0 @@ | ||
1 | -.. include:: /std/localtoc.irst | |
2 | - | |
3 | -.. _Castle-Heisenbug: | |
4 | - | |
5 | -========== | |
6 | -Heisenbugs | |
7 | -========== | |
8 | - | |
9 | -.. post:: 2023/04/08 | |
10 | - :category: CastleBlogs, Castle, DesignStudy | |
11 | - :tags: Castle, DRAFT | |
12 | - | |
13 | - In Castle, one can dynamically connect components and send “events” over those connections. Typically this is done as | |
14 | - an action on an incoming message (see: :ref:`CCC-Actors`). And depending on ‘:ref:`TheMachinery`’, those events can be | |
15 | - queued. It is this combination that *can result* in a **beautiful Heisenbug**. | |
16 | - | |
17 | - First, let’s explain the Heisenbug, before we give an example. Then we analyze it, show how to improve the code, and | |
18 | - finally formulate a *requirement* to prevent & detect this kind of bug in Castle. | |
19 | - | |
20 | -What is a Heisenbug? | |
21 | -==================== | |
22 | - | |
23 | -The `heisenbug <https://en.wikipedia.org/wiki/Heisenbug>`__ is named after the theoretical physics *Werner Heisenberg*, who | |
24 | -described the *“observer effect”*: when you look closely, the behavior changes. The same can happen to software | |
25 | -(bugs). The behavior apparently changes when you study -or slightly adjust- that code. Often this is due to (small) | |
26 | -changes in timing; possibly even in generated code. Therefore old (old-fashioned) sequential code on slow CPUs is less | |
27 | -likely to have heisenbugs than concurrent code on fast multi-core systems. It’s also common in threaded programs. | |
28 | - | |
29 | -.. include:: ./Heisenbug-sidebar-Sequence.irst | |
30 | - | |
31 | -The Sieve goes wrong | |
32 | -==================== | |
33 | - | |
34 | -My standard example, :ref:`Castle-TheSieve`, suffered from this issue. The initial version did work for years | |
35 | -but failed horribly when another “machinery” was used. After studying this, the bug is simple and easy to fix. | |
36 | - | |
37 | -There are two related timing issues that together result in the Heisenbug. First, we introduce them and then | |
38 | -show how the combination may fail. | |
39 | - | |
40 | - | |
41 | -Event-order | |
42 | ------------ | |
43 | - | |
44 | -Conceptually, the `Generator` sends (events with) integers to `Sieve(2)`, which may forward them to `Sieve(3)`, then | |
45 | -to `Sieve(5)`, etc. As shown in the **Conceptual sidebar**, we probably like to assume that each integer is sieved | |
46 | -before the next *’int’* *starts*: the classic “sequential view” we are used to. | |
47 | - | |
48 | -However, that isn’t how it works. In Castle, the order of events on a connection is defined (*one by one, | |
49 | -sequential*). And given the code, the integer sent by a `Sieve` is always later than the incoming one. That is all we | |
50 | -may assume. | |
51 | -|BR| | |
52 | -The timing of unrelated events on multiple connections is not defined. That order may depend on :ref:`TheMachinery` and | |
53 | -many other factors. Do not, as a developer, assume any order --as I did! | |
54 | - | |
55 | -As shown in the **One-by-One sidebar** diagram, this can result that the Generator is outputting all events first. Next, | |
56 | -Sieve(2) filters out the even integers, then Sieve(3) processes all its input, then Sieve(5), etc. | |
57 | -|BR| | |
58 | -Although we aren’t using concurrency, and it needs tremendous buffers when finding big primes, it does | |
59 | -conceptually work. And so, it is an allowed execution [#ButImprove]_. | |
60 | - | |
61 | - | |
62 | -Reconnecting | |
63 | ------------- | |
64 | - | |
65 | -The chain of `Sieve`\s will grow as we find more primes. Whenever an *int* isn’t filtered-out and reaches the `Finder` a | |
66 | -*new prime* is found. Then, a new Sieve element is created and inserted into the chain. | |
67 | -|BR| | |
68 | -Building the chain is done by the Main component (which is signaled by the Finder) [#orVariant]_. | |
69 | - | |
70 | -Therefore, `Main` remembers the ``last_sieve`` and reconnects that output to the newly creates `Sieve`. | |
71 | -Which output is temporally connected to the `Finder` | |
72 | -|BR| | |
73 | -For every newly found prime, this is repeated. | |
74 | - | |
75 | -This detail is shown in the **With Details** sidebar diagram; where the `Finder` and `Main` and all its messages | |
76 | -are shown too. | |
77 | - | |
78 | -Assuming the initial “conceptual” order, you will see the same Sieve(s) become alive (“new” message), and are added to | |
79 | -the end of the sieve chain. The integers still flow (now, shown as “try(`int`)” messages) by this sieve. | |
80 | -|BR| | |
81 | -You will also notice the `Finder` does indeed find all primes. | |
82 | - | |
83 | - | |
84 | -The combination | |
85 | -=============== | |
86 | - | |
87 | -Now let us study how the sieve chain will grow with a “fast generator”, and the one-by-one order of events is used. This | |
88 | -diagram is shown below. | |
89 | - | |
90 | -As we can see in the picture, it goes dreadfully wrong. No proper chain is created, and we will find integers like **4** | |
91 | -and **6**. This is wrong, they are not prime. | |
92 | -|BR| | |
93 | -With a (very) *fast Generator*, **all** integers are sent to the `Finder` --before any `Sieve` is created, and so any | |
94 | -int is reported as prime. besides, too many elements are added to the chain as a Sieve component is created for each found | |
95 | -“prime”. On top of that, no integer is ever sieved... | |
96 | - | |
97 | -This is just **an** example. As we can’t predict (or assume) any order, we can find other results too. And, when we add | |
98 | -“debugging print statement” (and *look closer*), we change the timing and will find other results. We found the | |
99 | -*observer effect*! | |
100 | - | |
101 | -.. uml:: ./sieve-Sequence-Wrong.puml | |
102 | - | |
103 | - | |
104 | -.. warning:: | |
105 | - | |
106 | - It is not *“the timing”* that is wrong! | |
107 | - |BR| | |
108 | - A concurrent program is only correct when it goes right for **any** possible timing. | |
109 | - | |
110 | - As in all software engineering, we can prove it is buggy when it goes wrong at least once. That is what we have | |
111 | - shown. And so, the original code is *wrong*. | |
112 | - | |
113 | - | |
114 | -How to improve? | |
115 | -=============== | |
116 | - | |
117 | -Finding this heisenbug triggered an investigation to improve Castle as well as ‘:ref:`Castle-TheSieve`’. Where our goal | |
118 | -is not just to improve the sieve code, but all programs. And give the programmer options to prevent heisenbugs. | |
119 | - | |
120 | -As we will see fixing ‘:ref:`the sieve <Castle-TheSieve>` is simple: use the **SLowStart** (base) protocol. It changes | |
121 | -only three lines! | |
122 | -|BR| | |
123 | -But we start with a new requirement, for a new tool in the :ref:`Castle Workshop <Workshop-Design>`. | |
124 | - | |
125 | - | |
126 | -Simulation | |
127 | ----------- | |
128 | - | |
129 | -As we will see below the `SlowStart` protocol will *remove* our Heisenbug. But it does not abolish the Heisenbug! | |
130 | - | |
131 | -The feature does by no means prevent a developer from using other solutions, with a comparable flaw. Besides, it’s | |
132 | -hopeless to use testing to prove the absence of a Heisenbug. As we have seen above, all variants of all possible | |
133 | -concurrent execution orders should be correct. Where we have very limited control over which variant is used. | |
134 | - | |
135 | -This led to a new requirement: :need:`U_Tools_EventOrder.` To assist the developer the Castle Workshop will come | |
136 | -with tools to detect such bugs. See :ref:`simulation` for more on this. | |
137 | - | |
138 | - | |
139 | -.. include:: ./sieve-protocols-sidebar.irst | |
140 | -SlowStart | |
141 | ---------- | |
142 | - | |
143 | -Castle (now) comes [#KipEi]_ with the parametric *base* protocol :ref:`SlowStart <doc-SlowStart>`, which is based on | |
144 | -`TCP Slow start <https://en.wikipedia.org/wiki/TCP_congestion_control#Slow_start>`__ and contains a queueing model | |
145 | -[#ModelOnly]_ to control the speed of an (event) connection. As the name suggests, initially the connections with be | |
146 | -slow. Roughly, the parameter set the maximal number of unhandled events on a connection. | |
147 | -|BR| | |
148 | -The (improved) version of :ref:`Castle-TheSieve` uses a SlowStart of **1**. And `Main` will remove (or increase) that | |
149 | -limit after reconnecting. | |
150 | - | |
151 | -Initially, the `Generator` is only *allowed* to send one event, which is received by the `Finder`. Then, `Main` will create | |
152 | -the first Sieve (`Sieve(2)`), reconnects the Generator to that component, and increases the “speed” of the | |
153 | -connection. As the connection **Generator->Sieve(2)** is stable, the is no need to limit the “queue”. | |
154 | - | |
155 | -The `Generator` acts as before: it sends (events with) integers over its output. But now, the SimpleSieve protocol can | |
156 | -slow down the `Generator` --no code changes are needed for this. This may happen when the second event is sent before | |
157 | -it is received (or “handled”) by the Finder, and the limit is set to **1**. | |
158 | -|BR| | |
159 | -As this limit is removed when a Sieve-component is inserted into the chain, only the start is slow... | |
160 | - | |
161 | -The same happens to every Sieve: initially (when it is connected to the Finder) there is a limit of 1 event in the | |
162 | -queue. But when that connection is reconnected --and the potential Heisenbug is gone-- the limit is removed. | |
163 | - | |
164 | -.. tip:: Unlimited or better? | |
165 | - | |
166 | - In this blog, we remove the limit of the ``SlowStart protocol`` completely, for simplicity. Then the Heisenbug is | |
167 | - solved. | |
168 | - | |
169 | - That is not the only option. | |
170 | - |BR| | |
171 | - Given the `Generator` is a simple loop it can produce many integers fast. And so cause huge piles of queued | |
172 | - events. That can be done better, by the same concept: a maximal queue size. (again: just model). | |
173 | - | |
174 | - It’s up to de developer to optimize this. Some prefer the maximum queue length equal to the number of | |
175 | - Sieve-components, others relate the maximum queue length to the number of available cores. Some use static values, | |
176 | - others will adjust them over the run-time of the application. | |
177 | - |BR| | |
178 | - That is all possible with a few lines in the `Main` component. But also the Sieve component can set this | |
179 | - limit, both for incoming-ports as well for outgoing ports. | |
180 | - | |
181 | - | |
182 | - | |
183 | ------ | |
184 | - | |
185 | -.. rubric:: Footnotes | |
186 | - | |
187 | -.. [#orVariant] | |
188 | - Again, there are many variants of :ref:`Castle-TheSieve`. In some adding a `Sieve` to the chain is done by the `Finder`, | |
189 | - in others by `Main`. In both alternatives, the same reconnect is needed. There is no real difference -- but the name | |
190 | - of the component initiating the change. | |
191 | - |BR| | |
192 | - The Heisenbug will not (trivially) disappear when switching between hose variants | |
193 | - | |
194 | -.. [#ButImprove] | |
195 | - Still, as language-designer, we need to give the programmer more options to hint at a more optimal implementation. | |
196 | - | |
197 | -.. [#KipEi] | |
198 | - This *SlowStart* base protocol is part of Castle; see :ref:`Protocol-SlowStart`. But the need for it --follows like | |
199 | - this blog-- follows from the discovery of these :ref:`Castle-Heisenbug` in :ref:`Castle-TheSieve`. | |
200 | - | |
201 | - | |
202 | -.. [#ModelOnly] | |
203 | - Remember, this queue exists as a *model* **only** (like everything in Castle-code)! | |
204 | - |BR| | |
205 | - Depending on ‘:ref:`TheMachinery`, there may be no need to implement the queue (e.g.with DirectCall) at all; or they may | |
206 | - only be a queue length and -maximum, or ... | |
207 | - | |
208 | - | |
209 | - | |
210 | -.. LocalWords: heisenbug heisenbugs |
@@ -1,148 +0,0 @@ | ||
1 | -.. .. include:: /std/localtoc.irst | |
2 | - | |
3 | -.. _Castle-TheSieve: | |
4 | - | |
5 | -============================ | |
6 | -The Sieve demo (start/DRAFT) | |
7 | -============================ | |
8 | - | |
9 | -.. post:: | |
10 | - :category: CastleBlogs, Demo | |
11 | - :tags: Castle, DRAFT | |
12 | - | |
13 | - | |
14 | - To show some features of CCastle, I use *‘the sieve’*, short for the `Sieve of Eratosthenes | |
15 | - <https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes>`__. An old, well known, algorithm to find prime numbers; with | |
16 | - impliciet concurrency. | |
17 | - | |
18 | - With an almost trivial implementation, many “CC concepts” can be shown. In only a handful of lines.... | |
19 | - | |
20 | -The design | |
21 | -********** | |
22 | - | |
23 | -We only need tree simple components as shown below, and a main component (not shown). We also use two protocols, that | |
24 | -are given below. | |
25 | - | |
26 | -.. include:: ./sieve-design.irst | |
27 | - | |
28 | -The elements of the sieve | |
29 | -========================= | |
30 | - | |
31 | -CCastle use “components” [#not-package]_ as main decomposition. Each kind of component can be instantiated multiple | |
32 | -times; sometimes called a *element*, or also just *component*. This is very like *“classes” and “objects”* in OO | |
33 | -[#active-class]_. | |
34 | - | |
35 | -Let’s introduce the those components | |
36 | - | |
37 | -Generator | |
38 | ---------- | |
39 | - | |
40 | -This component generates just numbers, which will be tested for prime (see below). As primes are always integer bigger | |
41 | -then one; it output is the stream stream of numbers: 2,3,4, … | |
42 | - | |
43 | -Sieve (on prime) | |
44 | ----------------- | |
45 | - | |
46 | -We use a (growing) chain of sieve-elements. Each one is the same; except for the sieving-constant --a already found | |
47 | -prime. That number is set when instantiating the element. | |
48 | - | |
49 | - | |
50 | -Each Sieve tries to divide each incoming number to its own, sieve-constant. When the modulo isn’t zero, we call it | |
51 | -a *coprime* (relative to the already tested primes) and send downstream. When it can be divided, the number is clearly | |
52 | -not prime and ignored | |
53 | - | |
54 | -Finder | |
55 | ------- | |
56 | - | |
57 | -Each number that comes out of the chain of sieves is a prime (that is the algorithm; see Wikipedia for details). It is | |
58 | -collected by the finder. For each found prime, an extra sieve (element) is created and added to the chain. This kind | |
59 | -of shifts the finder to the right (aka downstream) | |
60 | - | |
61 | -In some implementations that is the responsibility of the finder (therefore sometimes calls “head”). In a variant, the | |
62 | -‘main’ component is caring that load. | |
63 | - | |
64 | -Communication | |
65 | -============= | |
66 | -.. include:: ./sieve-protocols-sidebar.irst | |
67 | - | |
68 | -CCastle uses “protocols” to communicate between components. There are several kind of protocols; we use the ‘event’ kind | |
69 | -here. Two ports can be connected when both use the same protocol. | |
70 | - | |
71 | -Notice, that a *protocol* is not the same as an API in most language’s. A fundamenta concept of :ref:`CC`/CCastle is the | |
72 | -strict seperation between outside and inside | |
73 | - | |
74 | -StartSieve | |
75 | ----------- | |
76 | - | |
77 | -The StartSieve protocol signals to start sieving (so generating numbers), and when to stop. This “max” number is the | |
78 | -maximal number to be tried, and does not need to be a prime. | |
79 | - | |
80 | -Currently, the is no way to specify the number of primes to be found. | |
81 | - | |
82 | - | |
83 | -SimpleSieve | |
84 | ------------ | |
85 | - | |
86 | -In this variant [#sieve-variants]_, we use an event-based protocol, that just hold one event (read: a message), that | |
87 | -carries the integer to be tried. | |
88 | - | |
89 | -In the *Original* version, it was a basic `Protocol`. Which worked fine until we studied the another :ref:`machinery | |
90 | -<TheMachinery>`: :ref:`Machinery-LibDispatch`, and it become clear we had a :ref:`Castle-Heisenbug`! (See there for | |
91 | -details.) | |
92 | -|BR| | |
93 | -Now, we use an improved version, where we use a simple push-back algorithm by inheriting from ``SlowStart``. This adds a | |
94 | -queue to the model, that limits (slows down) the sender to a maximum number of (unhandled) events; in this case that is | |
95 | -initially: only one event ``SlowStart(1)``. | |
96 | - | |
97 | -.. note:: | |
98 | - | |
99 | - Without going into details, it important to realize the *queue* is only added in the model! Depending on the | |
100 | - :ref:`TheMachinery` it will probably **not** exist in the computer-code. | |
101 | - |BR| | |
102 | - For example, the :ref:`Machinery-DirectCall` machinery will never need, not use this queue | |
103 | - | |
104 | - It also shows normal Castle-programmer can focus on the functional aspect of the protocol. The SimpleSieve doesn't | |
105 | - need any extra message to controll this SlowStart (or sliding windows, as is also know) algorithm. That is fully | |
106 | - handled in a generic base-protocol. | |
107 | - |BR| | |
108 | - Additionally, the even more technical aspect of how to send events between (CC) components are completely hidden. As | |
109 | - long as both components use the same protocol it will work. ref:`TheMachinery` will make sure that both components | |
110 | - use the same technical details on both ends. | |
111 | - | |
112 | - | |
113 | - | |
114 | -Main | |
115 | -**** | |
116 | - | |
117 | -All the components (or elements) above have to created (statically or dynamically) by an top-level component, which is | |
118 | -usually called “main”. However the name is not special (like in C/C++), it’s more a convention (like in Python). | |
119 | - | |
120 | - | |
121 | - | |
122 | - | |
123 | -XXXX | |
124 | - | |
125 | -The Code | |
126 | -******** | |
127 | - | |
128 | -.. include:: ./sieve-code.irst | |
129 | - | |
130 | ----------- | |
131 | - | |
132 | -.. rubric:: Footnotes | |
133 | - | |
134 | -.. [#not-package] | |
135 | - A CCastle **component** is unrelated to an *UML-component*. It is **not** a package, as many people use for the UML variant. | |
136 | - | |
137 | -.. [#active-class] | |
138 | - A (CCastle) **component** (or actually, an element) is sometimes described as an “active class (aka object)” -- a | |
139 | - class with a thread inside. This is not completely correct, but gives a good, first impression. | |
140 | - |BR| | |
141 | - Notice however, there a no threads in CCastle -- just concurrency and parallelism. | |
142 | - | |
143 | -.. [#sieve-variants] | |
144 | - There are multiple variants of ‘the Sieve’; all showing other (CC/Castle) aspects. In this one event-bases protocols | |
145 | - are used. There is also a variant with data-based protocol, variants with, and without :ref:`Castle-Heisenbug`, etc. | |
146 | - | |
147 | - | |
148 | -.. LocalWords: coprime |
@@ -1,3 +1,4 @@ | ||
1 | +.. (C) 2023,2024 Albert Mietus. Part of CCastle project | |
1 | 2 | ============================== |
2 | 3 | Blog on various CCastle topics |
3 | 4 | ============================== |
@@ -1,3 +1,4 @@ | ||
1 | +' (C) 2023,2024 Albert Mietus. Part of CCastle project | |
1 | 2 | @startuml |
2 | 3 | hide footbox |
3 | 4 | title OutOfOrder (Fast generator) |
@@ -1,3 +1,4 @@ | ||
1 | +' (C) 2023,2024 Albert Mietus. Part of CCastle project | |
1 | 2 | @startuml |
2 | 3 | 'hide footbox |
3 | 4 | title Wrong (Generate fast & Slow creation) |
@@ -1,3 +1,4 @@ | ||
1 | +' (C) 2023,2024 Albert Mietus. Part of CCastle project | |
1 | 2 | @startuml |
2 | 3 | hide footbox |
3 | 4 | title Concept (sequential order) |
@@ -1,3 +1,4 @@ | ||
1 | +' (C) 2023,2024 Albert Mietus. Part of CCastle project | |
1 | 2 | @startuml |
2 | 3 | hide footbox |
3 | 4 | title Sieve creation details (sequantial order) |
@@ -0,0 +1,70 @@ | ||
1 | +.. -*-rst-*- (C) 2023,2024 Albert Mietus. Part of CCastle project | |
2 | + included in `1.TheSieve.rst` | |
3 | +.. NOTE the code-tabs use ReasonML , but it is Castle-code!! | |
4 | + | |
5 | +.. tabs:: | |
6 | + .. code-tab:: ReasonML Generator | |
7 | + | |
8 | + implement Generator { | |
9 | + int maxValue; | |
10 | + | |
11 | + StartSieve.newMax(max) on .controll | |
12 | + { | |
13 | + .maxValue := max; | |
14 | + } | |
15 | + | |
16 | + StartSieve.runTo(max) on .controll | |
17 | + { | |
18 | + int i; | |
19 | + | |
20 | + .maxValue := max; | |
21 | + i:=0; | |
22 | + while (i < .maxValue) { | |
23 | + .outlet.input(i); | |
24 | + } | |
25 | + } | |
26 | + | |
27 | + } //@end Generator | |
28 | + | |
29 | + | |
30 | + .. code-tab:: ReasonML Sieve | |
31 | + | |
32 | + implement Sieve { | |
33 | + int myPrime; | |
34 | + | |
35 | + init(int:onPrime) // `init` is (typically) part of the construction of a element. | |
36 | + { | |
37 | + super.init(); // `super` acts as port to the base-class | |
38 | + .myPrime := onPrime; | |
39 | + } | |
40 | + | |
41 | + SimpleSieve.input(try) on .try | |
42 | + { | |
43 | + if ( (try % .myPrime) !=0 ) { | |
44 | + .coprime.input(try); | |
45 | + } | |
46 | + } | |
47 | + | |
48 | + } //@end Sieve | |
49 | + | |
50 | + | |
51 | + .. code-tab:: ReasonML Finder | |
52 | + | |
53 | + implement Finder { | |
54 | + int count; | |
55 | + | |
56 | + SimpleSieve.input(foundPrime) on .newPrime | |
57 | + { | |
58 | + .found.input(foundPrime); // Forward to “main” | |
59 | + report() | |
60 | + } | |
61 | + | |
62 | + report() // This is a local function -- as it is not connected (to a port) it is “private” | |
63 | + { | |
64 | + printf("Finder: Found prime (no %s): %8i\n", .count, foundPrime); | |
65 | + .count +=1 | |
66 | + } | |
67 | + | |
68 | + } //@end Finder | |
69 | + | |
70 | + |
@@ -1,143 +0,0 @@ | ||
1 | -.. -*-rst-*- | |
2 | - included in `b.TheSieve.rst` | |
3 | - | |
4 | -.. NOTE the code-tabs use ReasonML , but it is Castle-code!! | |
5 | - | |
6 | -.. The "No Heisenbug" variant is used as base: ``.../SIEVE/3.NoHeisenbug/CC-event-sieve.Castle`` | |
7 | - | |
8 | -Moat (*interfaces*) | |
9 | -=================== | |
10 | - | |
11 | - | |
12 | -.. tabs:: | |
13 | - | |
14 | - .. code-tab:: ReasonML Generator | |
15 | - | |
16 | - component Generator : Component { | |
17 | - port StartSieve<in>:controll; | |
18 | - port SimpleSieve<out>:outlet; | |
19 | - port SimpleSieve<in>:collect; | |
20 | - } | |
21 | - | |
22 | - .. code-tab:: ReasonML Sieve | |
23 | - | |
24 | - component Sieve(onPrime:int) : Component { | |
25 | - port SimpleSieve<in>:try; | |
26 | - port SimpleSieve<out>:coprime; | |
27 | - } | |
28 | - | |
29 | - .. code-tab:: ReasonML Finder | |
30 | - | |
31 | - component Finder : Component { | |
32 | - port SimpleSieve<in>:newPrime; | |
33 | - port SimpleSieve<out>:found; | |
34 | - } | |
35 | - | |
36 | -Castle (*implementation*) | |
37 | -========================= | |
38 | - | |
39 | -.. tabs:: | |
40 | - .. code-tab:: ReasonML Generator | |
41 | - | |
42 | - implement Generator { | |
43 | - int maxValue; | |
44 | - | |
45 | - StartSieve.newMax(max) on self.controll | |
46 | - { | |
47 | - self.maxValue := max; | |
48 | - } | |
49 | - | |
50 | - StartSieve.runTo(max) on self.controll | |
51 | - { | |
52 | - int i; | |
53 | - | |
54 | - self.maxValue := max; | |
55 | - i:=0; | |
56 | - while (i < self.maxValue) { | |
57 | - self.outlet.input(i); | |
58 | - } | |
59 | - } | |
60 | - | |
61 | - SimpleSieve.input(foundPrime) on .collect | |
62 | - { | |
63 | - static int count:=0; | |
64 | - count :+= 1; | |
65 | - printf("Generator: Collected prime (no %s): %8i\n", count, foundPrime); | |
66 | - } | |
67 | - } //@end Generator | |
68 | - | |
69 | - .. code-tab:: ReasonML Sieve | |
70 | - | |
71 | - implement Sieve { | |
72 | - int myPrime; | |
73 | - | |
74 | - -init(onPrime:int) | |
75 | - { | |
76 | - super.init(); //note 'super' acts as a port | |
77 | - self.myPrime := onPrime; | |
78 | - } | |
79 | - | |
80 | - SimpleSieve.input(try) on .try | |
81 | - { | |
82 | - if ( (try % self.myPrime) !=0 ) { | |
83 | - self.coprime.input(try); | |
84 | - } | |
85 | - } | |
86 | - } //@end Sieve | |
87 | - | |
88 | - .. code-tab:: ReasonML Finder | |
89 | - | |
90 | - implement Finder { | |
91 | - | |
92 | - SimpleSieve.input(foundPrime) on self.newPrime | |
93 | - { | |
94 | - // Send out the newPrime, | |
95 | - self.found.input(foundPrime); | |
96 | - } | |
97 | - } //@end Finder | |
98 | - | |
99 | - .. code-tab:: ReasonML Main | |
100 | - | |
101 | - implement Main { | |
102 | - sub generator; | |
103 | - sub finder; | |
104 | - alias lastSieve; // The list of Sieve's grow dynamicly!; keep track of the last one | |
105 | - | |
106 | - -init() | |
107 | - { | |
108 | - self := super.init(); | |
109 | - | |
110 | - .generator := Generator.new(); | |
111 | - .finder := Finder.new(); | |
112 | - | |
113 | - .generator.outlet = .finder.newPrime; // Initially, there aren't any Sieves | |
114 | - self.lastSieve := Ground; // Not needed, as it is default. But is clearifies the code below | |
115 | - } | |
116 | - | |
117 | - // We have build the sievelist (and reconnect) on a newly found prime .. | |
118 | - SimpleSieve.try(newPrime) on self.generator.found | |
119 | - { | |
120 | - alias s; | |
121 | - | |
122 | - // Extent the sieve-list ... | |
123 | - s:= Sieve.new(newPrime); | |
124 | - s.coprime = self.finder.newPrime; | |
125 | - if (not self.lastSieve == Ground) { // .lastSieve == Ground, so not connected, so we have the first Sieve to connect to .generator | |
126 | - self.generator.outlet = s.try; | |
127 | - self.generator.outlet.queue.removeLimit(); | |
128 | - } else { | |
129 | - self.lastSieve.coprime = s.try; | |
130 | - self.lastSieve.coprime.queue.removeLimit(); | |
131 | - } | |
132 | - .lastSieve := s; | |
133 | - | |
134 | - self.generator.collect.input(newPrime); // forward the prime to the Generator | |
135 | - } | |
136 | - | |
137 | - powerOn() on self.power | |
138 | - { | |
139 | - int max := 10; | |
140 | - | |
141 | - self.generator.runTo(max); | |
142 | - } | |
143 | - } //@end Main |
@@ -1,5 +1,5 @@ | ||
1 | 1 | .. -*- rst -*- |
2 | - USED in b.TheSieve.rst | |
2 | + USED in 1.TheSieve.rst | |
3 | 3 | |
4 | 4 | .. uml:: |
5 | 5 |
@@ -14,7 +14,7 @@ | ||
14 | 14 | +-----------/ \-----------/ \-----------/ \-----------/ \-----------/ \---------*-+ |
15 | 15 | | |
16 | 16 | 0 The shown (horizontal) connections all use the SimpleSieve protocol V Primes |
17 | - 0 The Generator has an (in-)port for the StartSieve protocol | |
18 | - 0 The Finder has an optional (out-) port for SimpleSieve protocol | |
17 | + 0 The Generator has an (in‒) port for the StartSieve protocol | |
18 | + 0 The Finder has an optional (out‒) port for SimpleSieve protocol | |
19 | 19 | |
20 | 20 | @endditaa |
@@ -0,0 +1,66 @@ | ||
1 | +.. -*-rst-*- (C) 2023,2024 Albert Mietus. Part of CCastle project | |
2 | + included in `1.TheSieve.rst` | |
3 | +.. NOTE the code-tabs use ReasonML , but it is Castle-code!! | |
4 | + | |
5 | +.. tabs:: | |
6 | + | |
7 | + .. code-tab:: ReasonML Main | |
8 | + | |
9 | + implement Main { | |
10 | + sub generator; | |
11 | + sub finder; | |
12 | + alias lastSieve; // The list of Sieve's grow dynamically!; keep track of the last one | |
13 | + ... | |
14 | + | |
15 | + | |
16 | + .. code-tab:: ReasonML init() | |
17 | + | |
18 | + init() | |
19 | + { | |
20 | + super.init(); | |
21 | + | |
22 | + .generator := Generator(); | |
23 | + .finder := Finder(); | |
24 | + | |
25 | + // Initially, there aren't any Sieves, so ... | |
26 | + .generator.outlet = .finder.newPrime; // ... connect the generator to the finder | |
27 | + .lastSieve := Ground; // Not needed (as default); but it clarifies the code below | |
28 | + } | |
29 | + | |
30 | + | |
31 | + .. code-tab:: ReasonML try() on found | |
32 | + | |
33 | + // We have build the sievelist (and reconnect) on a newly found prime .. | |
34 | + SimpleSieve.try(newPrime) on .generator.found | |
35 | + { | |
36 | + alias s; | |
37 | + | |
38 | + // Extent the sieve-list ... | |
39 | + s:= Sieve(newPrime); | |
40 | + insert_sieve(s); | |
41 | + .generator.collect.input(newPrime); // forward the prime to the Generator | |
42 | + } | |
43 | + | |
44 | + | |
45 | + insert_sieve(alias:s) | |
46 | + { | |
47 | + // Connect s to the lastSieve, or the Generator | |
48 | + if (.lastSieve == Ground) { // .lastSieve == Ground, so not connected, so we have the first Sieve to connect to .generator | |
49 | + .generator.outlet = s.try; | |
50 | + } else { | |
51 | + .lastSieve.coprime = s.try; | |
52 | + } | |
53 | + | |
54 | + // And to the Finder, that is self | |
55 | + s.coprime = .finder.newPrime; | |
56 | + } | |
57 | + | |
58 | + .. code-tab:: ReasonML powerOn() | |
59 | + | |
60 | + powerOn() // this kick-starts “every main” | |
61 | + { | |
62 | + int max := 10; | |
63 | + | |
64 | + .generator.runTo(max); | |
65 | + } | |
66 | + |
@@ -0,0 +1,28 @@ | ||
1 | +.. -*-rst-*- (C) 2023,2024 Albert Mietus. Part of CCastle project | |
2 | + included in `1.TheSieve.rst` | |
3 | +.. NOTE the code-tabs use ReasonML , but it is Castle-code!! | |
4 | + | |
5 | +.. tabs:: | |
6 | + | |
7 | + .. code-tab:: ReasonML Generator | |
8 | + | |
9 | + component Generator : Component { | |
10 | + port StartSieve<in>:controll; | |
11 | + port SimpleSieve<out>:outlet; | |
12 | + port SimpleSieve<in>:collect; | |
13 | + } | |
14 | + | |
15 | + .. code-tab:: ReasonML Sieve | |
16 | + | |
17 | + component Sieve(onPrime:int) : Component { | |
18 | + port SimpleSieve<in>:try; | |
19 | + port SimpleSieve<out>:coprime; | |
20 | + } | |
21 | + | |
22 | + .. code-tab:: ReasonML Finder | |
23 | + | |
24 | + component Finder : Component { | |
25 | + port SimpleSieve<in>:newPrime; | |
26 | + port SimpleSieve<out>:found; | |
27 | + } | |
28 | + |
@@ -1,55 +1,28 @@ | ||
1 | -.. -*-rst-*- | |
1 | +.. -*-rst-*- (C) 2023,2024 Albert Mietus. Part of CCastle project | |
2 | 2 | included in `b.TheSieve.rst` |
3 | 3 | |
4 | -.. note: the code-tabs use ReasonML , but it Castle-code!! | |
4 | +.. note The code-tabs use ReasonML , but it is Castle-code!! | |
5 | 5 | |
6 | 6 | .. sidebar:: Sieve Protocols |
7 | 7 | |
8 | 8 | .. tabs:: |
9 | 9 | |
10 | - .. code-tab:: ReasonML Original | |
10 | + .. code-tab:: ReasonML StartSieve | |
11 | 11 | |
12 | - protocol StartSieve : Protocol { | |
13 | - kind: event; | |
12 | + protocol StartSieve : EventProtocol { | |
14 | 13 | runTo(int:max); |
14 | + newMax(int:max); | |
15 | 15 | } |
16 | 16 | |
17 | - protocol SimpleSieve : Protocol { | |
18 | - kind: event; | |
17 | + .. code-tab:: ReasonML SimpleSieve | |
18 | + | |
19 | + protocol SimpleSieve : EventProtocol { | |
19 | 20 | input(int:try); |
20 | 21 | } |
21 | 22 | |
22 | - .. tab:: Improved | |
23 | - | |
24 | - This version has one main change: the SimpleSieve now inherits from **SlowStart** | |
25 | - | |
26 | - .. code-block:: ReasonML | |
27 | - | |
28 | - protocol StartSieve : Protocol { | |
29 | - kind: event; | |
30 | - runTo(int:max); | |
31 | - } | |
32 | - | |
33 | - protocol SimpleSieve : SlowStart(1) { | |
34 | - input(int:try); | |
35 | - } | |
36 | - | |
37 | - Aside of that, the ``kind: event`` line is gone, as it *inherited* from ``SlowStart`` | |
23 | + .. tab:: Syntax notes | |
38 | 24 | |
39 | - .. tab:: Demo of use | |
40 | - | |
41 | - .. code-block:: ReasonML | |
42 | - :emphasize-lines: 6,10 | |
25 | + As the Castle syntax isn’t fully stable, a few notes: | |
43 | 26 | |
44 | - SimpleSieve.try(newPrime) on self.generator.found | |
45 | - { | |
46 | - ... | |
47 | - // When ``Sieve(2)`` is made (alias: s) | |
48 | - self.generator.outlet = s2.try; | |
49 | - self.generator.outlet.queue.removeLimit(); | |
50 | - ... | |
51 | - // Simular for other ``Sieve’s`` | |
52 | - self.lastSieve.coprime = s.try; | |
53 | - self.lastSieve.coprime.queue.removeLimit(); | |
54 | - ... | |
55 | - } | |
27 | + - Parmeters are in ``type:name`` order, which may change. | |
28 | + - The protocol-kind is inherited, not the (older) explicit ``kind: event`` variant. |
@@ -0,0 +1,49 @@ | ||
1 | +.. -*-rst-*- (C) 2023,2024 Albert Mietus. Part of CCastle project | |
2 | + included in `b.TheSieve.rst` | |
3 | + | |
4 | +.. note The code-tabs use ReasonML , but it is Castle-code!! | |
5 | + | |
6 | +.. sidebar:: SimpleSieve Protocols | |
7 | + | |
8 | + .. tabs:: | |
9 | + | |
10 | + .. tab:: Original | |
11 | + | |
12 | + The original SimpleSieve protocol is (sic) simple ... too simple. | |
13 | + | |
14 | + .. code-block:: ReasonML | |
15 | + | |
16 | + protocol SimpleSieve : EventProtocol { | |
17 | + input(int:try); | |
18 | + } | |
19 | + | |
20 | + As there is no flow control “co-primes” can be *queued*, or arrive too soon. | |
21 | + | |
22 | + .. tab:: SlowStart | |
23 | + | |
24 | + In this version, SimpleSieve inherits from **SlowStart** | |
25 | + | |
26 | + .. code-block:: ReasonML | |
27 | + | |
28 | + protocol SimpleSieve : SlowStart(1) { | |
29 | + input(int:try); | |
30 | + } | |
31 | + | |
32 | + .. tab:: Demo of use | |
33 | + | |
34 | + .. code-block:: ReasonML | |
35 | + :emphasize-lines: 6,10 | |
36 | + | |
37 | + SimpleSieve.try(newPrime) on self.generator.found | |
38 | + { | |
39 | + ... | |
40 | + // When ``Sieve(2)`` is made (alias: s) | |
41 | + self.generator.outlet = s2.try; | |
42 | + self.generator.outlet.queue.removeLimit(); | |
43 | + ... | |
44 | + // Simular for other ``Sieve’s`` | |
45 | + self.lastSieve.coprime = s.try; | |
46 | + self.lastSieve.coprime.queue.removeLimit(); | |
47 | + ... | |
48 | + } | |
49 | + |
@@ -0,0 +1,60 @@ | ||
1 | +:orphan: | |
2 | +.. (C) 2024 Albert Mietus. Part of CCastle project | |
3 | + | |
4 | +.. _SLowStart-Sieve: | |
5 | + | |
6 | +====================== | |
7 | +SlowStart Sieve (ToDo) | |
8 | +====================== | |
9 | + | |
10 | +* variants [#sieve-variants]_, | |
11 | + | |
12 | +Now, we use an improved version, where we use a simple push-back algorithm by inheriting from ``SlowStart``. This adds a | |
13 | +queue to the model, that limits (slows down) the sender to a maximum number of (unhandled) events; in this case that is | |
14 | +initially: only one event ``SlowStart(1)``. | |
15 | + | |
16 | +.. note:: | |
17 | + | |
18 | + Without going into details, it important to realize the *queue* is only added in the model! Depending on the | |
19 | + :ref:`TheMachinery` it will probably **not** exist in the computer-code. | |
20 | + |BR| | |
21 | + For example, the :ref:`Machinery-DirectCall` machinery will never need, not use this queue | |
22 | + | |
23 | + It also shows normal Castle-programmer can focus on the functional aspect of the protocol. The SimpleSieve doesn't | |
24 | + need any extra message to controll this SlowStart (or sliding windows, as is also know) algorithm. That is fully | |
25 | + handled in a generic base-protocol. | |
26 | + |BR| | |
27 | + Additionally, the even more technical aspect of how to send events between (CC) components are completely hidden. As | |
28 | + long as both components use the same protocol it will work. ref:`TheMachinery` will make sure that both components | |
29 | + use the same technical details on both ends. | |
30 | + | |
31 | + | |
32 | +.. [#sieve-variants] | |
33 | + There are multiple variants of ‘the Sieve’; all showing other (CC/Castle) aspects. In this one event-bases protocols | |
34 | + are used. There is also a variant with data-based protocol, variants with, and without :ref:`Castle-Heisenbug`, etc. | |
35 | + | |
36 | + | |
37 | +.. tabs:: | |
38 | + | |
39 | + .. code-tab:: ReasonML try() on found -- with puhback | |
40 | + | |
41 | + // We have build the sievelist (and reconnect) on a newly found prime .. | |
42 | + SimpleSieve.try(newPrime) on self.generator.found | |
43 | + { | |
44 | + alias s; | |
45 | + | |
46 | + // Extent the sieve-list ... | |
47 | + s:= Sieve.new(newPrime); | |
48 | + s.coprime = self.finder.newPrime; | |
49 | + if (not self.lastSieve == Ground) { // .lastSieve == Ground, so not connected, so we have the first Sieve to connect to .generator | |
50 | + self.generator.outlet = s.try; | |
51 | + self.generator.outlet.queue.removeLimit(); | |
52 | + } else { | |
53 | + self.lastSieve.coprime = s.try; | |
54 | + self.lastSieve.coprime.queue.removeLimit(); | |
55 | + } | |
56 | + .lastSieve := s; | |
57 | + | |
58 | + self.generator.collect.input(newPrime); // forward the prime to the Generator | |
59 | + } | |
60 | + |
@@ -0,0 +1,48 @@ | ||
1 | +.. (C) 2023,2024 Albert Mietus. Part of CCastle project | |
2 | + | |
3 | +.. -*-rst-*- | |
4 | + These where used in a draft, overcomplicated version of “the Sieve” blog. And saved here when that blog was clean-up | |
5 | +.. note: the code-tabs use ReasonML , but it Castle-code!! | |
6 | + | |
7 | +.. sidebar:: SAVED | |
8 | + | |
9 | + .. tabs:: | |
10 | + | |
11 | + .. tab:: SlowStart(1) | |
12 | + | |
13 | + This version has one main change: the SimpleSieve now inherits from **SlowStart** | |
14 | + | |
15 | + .. code-block:: ReasonML | |
16 | + | |
17 | + protocol StartSieve : Protocol { | |
18 | + kind: event; | |
19 | + runTo(int:max); | |
20 | + } | |
21 | + | |
22 | + protocol SimpleSieve : SlowStart(1) { | |
23 | + input(int:try); | |
24 | + } | |
25 | + | |
26 | + Aside of that, the ``kind: event`` line is gone, as it *inherited* from ``SlowStart`` | |
27 | + | |
28 | + .. tab:: Demo of use | |
29 | + | |
30 | + .. code-block:: ReasonML | |
31 | + :emphasize-lines: 6,10 | |
32 | + | |
33 | + SimpleSieve.try(newPrime) on self.generator.found | |
34 | + { | |
35 | + ... | |
36 | + // When ``Sieve(2)`` is made (alias: s) | |
37 | + self.generator.outlet = s2.try; | |
38 | + self.generator.outlet.queue.removeLimit(); | |
39 | + ... | |
40 | + // Simular for other ``Sieve’s`` | |
41 | + self.lastSieve.coprime = s.try; | |
42 | + self.lastSieve.coprime.queue.removeLimit(); | |
43 | + ... | |
44 | + } | |
45 | + | |
46 | + The Castle syntax isn’t fully stable, Here we use an old/provisionally version | |
47 | + | |
48 | + |