CS343 - Concurrent and Parallel Programming

https://student.cs.uwaterloo.ca/~cs343/W23/

Notes: https://student.cs.uwaterloo.ca/~cs343/W23/notes.pdf

Apparently, we use uC++ in this course:

https://plg.uwaterloo.ca/~usystem/pub/uSystem/uC++.pdf

Concepts

Understand how multiple stacks operate with a single thread.

You can have multiple stacks in a single thread

I actually don’t know why my program works on q1, it just magically worked when I tried

I think my Q1 is buggy? just why am I using a catch(…) in one of the cases, and catchresume in the other??

10 5 3 6 7 8 9 10

Notes

Only started taking notes seriously in the second part of the course. If I don’t take it seriously, I’m going to fail.

1. Advanced Control Flow

p.1

Multi-exit loop (mid-test loop)

This is when your loop has one or more exit locations occurring within the body, of the loop, not just top (while) or bottom (do-while).

i.e. if you have a break statement

for (;;) { // infinite loop, while ( true )
    if (...) break; // middle exit
}

A loop exit NEVER needs an else clause. i.e.:

This is BAD

for ( ;; ) {
    if ( C1 ) {S2}
    else {
        break;
    }
    ...
}

Other way applies too (if (C1) {break} else { S2}; is BAD)

This is GOOD

for ( ;; ) {
    if ( !C1 ) break;
    S2;
    ...
}

Remove S2 from the if statement

Why is it bad?

Because should be S2 logically part of the loop, not part of an IF. It’s about the scope of the statement.

Though I feel like this is a personal preference

p.2

In theory, flag variables can achieve the same multi-exit functionality. However, very cumbersome

Flag variables are the variable equivalent to a goto because they can be set/reset/tested at arbitrary locations in a program.

bool flag1 = false, flag2 = false;
while ( ! flag1 && ! flag2 ) {
    S1
    if ( C1 ) flag1 = true;
    } else {
        S2
        if ( C2 ) flag2 = true;
        } else {
            S3
        }
    }
}
if ( flag1 ) E1;
else E2;

disgusting code..

Clean version

for ( ;; ) {
    S1
    if ( C1 ) { E1; break; }
    S2
    if ( C2 ) { E2; break; }
    S3
}

Static muti-level exit

Static multi-level exit exits multiple control structures where exit point is known at compile time.

This is the notion of being able to exit to various levels, not just to the level right above the current loop

{
    switch (...) {
        for ( . . . ) {
            ...goto BK; ...
            ...goto SW; ...
            ...goto FR; ... // or break
        } FR: ;
    ...
    } SW: ; // bad eye-candy
} BK:

p.4 Dynamic Memory Allocation Stack allocation eliminates explicit storage-management and is more efficient than heap allocation—“

Why is stack allocation faster than heap allocation?

Managing heap memory requires maintaing a data structure (like a free list) to keep track of used and free blocks.

requires searching for a suitable block, which takes more time.

In contrast, stack memory simply follows a LIFO structure, and we know ahead of time how much memory is needed.

Some cases where heap alllocation is ABSOLUTE needed:

When storage must outlive the block in which it is allocated (ownership change)
When the amount of data read is unknown. (i.e C++ Vector)
When an array of objects must be initialized via the object’s constructor and each element has a different value.
When large local variables are allocated on a small stack.

For 3., look at this exmample

// need to initialize each array element
Obj obj[10]; // no default constructor! declaration fails
for ( int id = 0; id < 10; id += 1 )
obj[id].id = id; // Obj::id is const! assignment fails

We are forced to use pointers and dynamic allocation.

Obj * objs[size];
for ( int id = 0; id < size; id += 1 )
    objs[id] = new Obj{ id };
for ( int id = 0; id < size; id += 1 )
    delete objs[id];

HOWEVER, there is a way to achieve stack allocation in uC++ through the concept of a uArray

{ // GOOD, use stack
    cin >> size;
    uArray( Obj, objs, size ); // macro
    for ( int id = 0; id < size; id += 1 )
    objs[id]( id ); // constructor call
    . . .
    } // implicit array deallocate

2. Nonlocal Transfer

One thing we’d like to achieve is non-local transfer.

I guess isn’t multi-level exit that??

Consider this example

routine h calls g calls f

cannot return from f to h, terminating g’s activation

2.3 Exception Handling

3. Coroutine

A coroutine is a routine that can also be suspended at some point and resumed from that point when control returns.

The state of a coroutine consists of:

an execution location, starting at the beginning of the coroutine and remembered at each suspend.
an execution state holding the data created by the code the coroutine is executing. ⇒ each coroutine has its own stack, containing its local variables and those of any routines it calls.
an execution status—active or inactive or terminated—which changes as control resumes and suspends in a coroutine.

Difference between Routine and Coroutine?

A coroutine can suspend its execution and return to the caller without terminating, a routine cannot.

Cortouine

A coroutine is activated at the point of last suspension.

Routine

A routine always starts execution at the beginning and its local variables only persist for a single activation.

Coroutines are designed to be able to pass execution control back and forth between themselves.

It looks something like this

I guess it looks something like preemption, and being able to resume that! So you context switch between routines and are able to get back!

A coroutine executes synchronously with other coroutines; hence, no concurrency among coroutines.

Why learn about coroutines?

Coroutines are the precursor to concurrent tasks, and introduce the complex concept of suspending and resuming on separate stacks.

coroutines.

There are 2 different approaches:

Semi-Coroutine
Full Coroutine

Semi-Coroutine

A semi-coroutine acts asymmetrically, like non-recursive routines, by implicitly reactivating the coroutine that previously activated it.

Full Coroutine

A full coroutine acts symmetrically, like recursive routines, by explicitly activating a member of another coroutine, which directly or indirectly reactivates the original coroutine (activation cycle).

3.1 Semi-Coroutine

Fibonacci Sequence

So the teacher’s motivation for this is first, let’s consider using global variables. But then that isn’t extendible super well to multiple instances.

You want to encapsulate global variables into structure variables, and then pass these into each coroutine

Ahh i understand, so the state is stored. resume()transfers to the lastsuspend()`.

Example for fibonacci

Coroutine Fibonacci { // : public uBaseCoroutine
    int fn; // used for communication
    void main() { // distinguished member
        int fn1, fn2; // retained between resumes
        fn = 0; fn1 = fn;
        suspend(); // return to last resume
        fn = 1; fn2 = fn1; fn1 = fn;
        suspend(); // return to last resume
        for ( ;; ) {
            fn = fn1 + fn2; fn2 = fn1; fn1 = fn;
            suspend(); // return to last resume
        }
    }
    public:
        int operator()() { // functor
            resume(); // transfer to last suspend
            return fn;
        }
};

Some notes:

distinguished member main (coroutine main) can be suspended and resumed
no parameters or return value (supplied by public members and communication variables

The main program:

int main() {
    Fibonacci f1, f2; // multiple instances
    for ( int i = 1; i <= 10; i += 1 ) {
    cout << f1() << " " << f2() << endl;
    }
}

All coroutines are written like this for uC++

class uBaseCoroutine {
    protected:
        void resume(); // context switch to this
        void suspend(); // context switch to last resumer
        virtual void main() = 0; // starting routine for coroutine
    public:
        uBaseCoroutine();
        uBaseCoroutine( unsigned int stackSize ); // set stack size
        void verify(); // check stack
        const char *
        setName( const char *
        name ); // printed in error messages
        const char *
        getName() const;
        uBaseCoroutine & starter() const; // coroutine performing first resume
        uBaseCoroutine & resumer() const; // coroutine performing last resume
};

Warning

Warning, do not use catch(...) (catch any) in a coroutine, if it may be deleted before terminating, because a cleanup exception is raised to force stack unwinding (implementation issue).

p.30 Another example for reading characters

_Coroutine Format {
char ch; // used for communication
int g, b; // global because used in destructor
void main() {
for ( ;; ) { // for as many characters
for ( g = 0; g < 5; g += 1 ) { // groups of 5 blocks
for ( b = 0; b < 4; b += 1 ) { // blocks of 4 characters
for ( ;; ) { // for newline characters
suspend();
if ( ch != ’\n’ ) break; // ignore newline
}
cout << ch; // print character
}
cout << " "; // print block separator
}
cout << endl; // print group separator
}
}
public:
Format() { resume(); } // start coroutine
~Format() { if ( g != 0 | | b != 0 ) cout << endl; }
void prt( char ch ) { Format::ch = ch; resume(); }
};

int main() {
Format fmt;
char ch;
cin >> noskipws; // turn off white space skipping
for ( ;; ) {
cin >> ch; // read one character
if ( cin.fail() ) break; // eof ?
fmt.prt( ch );
}
}

3.1.3 Correct Coroutine Usage

Danger

Eliminate computation or flag variables retaining information about execution state.

This is because the variables might change (?) No, because its bad

In coroutine-based programming, you want to avoid such explicit logic and let the coroutine’s suspension and resumption naturally guide the flow of execution.

The purpose of coroutines is to simplify the flow, making it more linear and removing state-related logic.

It’s a way to think about the problem

for ( int i = 0; i < 10; i += 1 ) {
    if ( i % 2 == 0 ) // even ?
        even += digit;
    else
        odd += digit;
    suspend();
}

for (int i = 0; i < 5; i+=1) {
    even += digit;
    suspend();
    odd += digit;
    suspend();
}

When possible, simplest coroutine construction is to write a direct (stand-alone) program

Convert to coroutine by:

putting processing code into coroutine main,
converting reads if program is consuming or writes if program is producing to suspend,
Fibonacci consumes nothing and produces (generates) Fibonacci numbers ⇒ convert writes (cout) to suspends.
Formatter consumes characters and only indirectly produces output (as side-effect) ⇒ convert reads (cin) to suspends.
use interface members and communication variables to to transfer data in/out of coroutine

This approach is impossible for advanced coroutine problems.

3.2 EHM

Exception is the same as a class-object with respect to creation and destruction.

_Exception D {...};
D d; // local creation
_Resume d;
D *dp = new D; // dynamic creation
_Resume *dp;
delete dp;
_Throw D(); // temporary local creation

The tree traversal stuff

template <typename T>
class Btree {
  struct Node {
    ...
  };
  ...  // other members
      public : _Coroutine Iterator {
    Node* cursor;
    void walk(Node * node) {  // walk tree
      if (node == nullptr) return;
      if (node->left == nullptr && node->right == nullptr) {  // leaf?
        cursor = node;
        suspend();  // multiple stack frames
      } else {
        walk(node->left);   // recursion
        walk(node->right);  // recursion
      }
    }
    void main() {
      walk(cursor);
      cursor = nullptr;
    }
 
   public:
    Iterator(Btree<T> & btree) : cursor(&btree.root) {}
    T* next() {
      resume();
      return cursor;
    }
  };
  ...  // other members
};
 
template <class T>
bool sameFringe(BTree<T>& tree1, BTree<T>& tree2) {
  Btree<T>::Iterator iter1(btree1), iter2(btree2);  // iterator for each tree
  T *t1, *t2;
  for (;;) {
    t1 = iter1.next();
    t2 = iter2.next();
    if (t1 == nullptr | | t2 == nullptr) break;  // one traversal complete ?
    if (*t1 != *t2) return false;                // elements not equal ?
  }
  return t1 == nullptr && t2 == nullptr;  // both traversals completed ?
};

3.5 Raising

• There are two raising mechanisms: throwing and resuming.

_Throw [ exception-type ] ;
_Resume [ exception-type ] [ _At uBaseCoroutine-id ] ;

• If _Throw has no exception-type, it is a rethrow. • If _Resume has no exception-type, it is a reresume.

Resumption allows faulting execution greatest flexibility: it can process the exception as a resumption or rethrow the exception for termination.

3.6 Handler

uC++ has 2 kinds of handlers:

Termination
Resumption

For termination, uC++ uses try and catch, same as C++.

For Resumption, µC++ extends the try block to include resumption handlers. • Resumption handler is denoted by a _CatchResume clause after try body:

try {
    ...
} _CatchResume( E1 ) { . . . } // must appear before catch clauses
    // more _CatchResume clauses
    _CatchResume( . . . ) { . . . } // must be last _CatchResume clause
    catch( E2 ) { . . . } // must appear after _CatchResume clauses
    // more catch clauses
    catch( . . . ) { . . . } // must be last catch clause

• Any number of resumption handlers can be associated with a try block.

Tip

All _CatchResume handlers must precede any catch handlers, solely to make reading the two sets of clauses easier.

Like catch(...) (catch-any), _CatchResume(...) must appear at the end of the list of the resumption handlers.

p.38 Resumption handler cannot perform a break, continue, goto, or return.

This example program makes things make more sense for how _CatchResume works

#include <iostream>
using namespace std;
_Exception E {};
int main() {
    try {
        cout << "before throw" << endl;
        _Throw E{};
        cout << "after throw" << endl;
    } catch( E ) {
        cout << "catch" << endl;
    }
    cout << "after try1" << endl;
    try {
        cout << "before resume" << endl;
        _Resume E{};
        cout << "after resume" << endl;
    } _CatchResume( E ) {
        cout << "_CatchResume" << endl;
    }
    cout << "after try2" << endl;
}

output

before throw
catch
after try1
before resume
_CatchResume
after resume
after try2

There is a defaultResume (like if there is no resumption handler, the default behavior is to try and find a handler to catch it (generic catch)).

The raise dictates set of handlers examined during propagation: ◦ terminating propagation (_Throw) only examines termination handlers (catch), ◦ resuming propagation (_Resume) only examines resumption handlers (_CatchResume).

I'm confused about the interactions?

Like not sure if this is totally true. LIke i can _Throw, and have it handled by a catchResume??

Like in my A2, I threw using _Throw
Initially, I tried to handle it with a CatchResume, however that didn’t work. Or also trying with Resume_, but that didn’t work too. I still am not 100% sure about the mechanism#gap-in-knowledge

    _CatchResume(Sentinel & e) {
      // Node without value
      _Throw Sentinel();
    }

3.7 Nonlocal Exceptions

For nonlocal exceptions, you do something more advanced?

That’s where you do _Resume Exception() at C.

That syntax allows you to trigger resumption somewhere else

For nonlocal resumption, _Resume is a proxy for actual raise in the faulting coroutine ⇒ non-local resumption becomes local resumption.

While source delivers nonlocal exception immediately, propagation only occurs when faulting becomes active.

i.e. you must resume back to the coroutine for it to react properly (through calling their resume() in some way)

Multiple nonlocal exceptions are queued and delivered in FIFO order depending on the current enabled exceptions.

I'm confused on non-local exceptions and resumption

So I understand that when you call _Resume, that is essentially triggering an exception. After the exception is handled, we will resume here.

I also remember that

_CatchResume only handles _Resume

_Catch only handles _Throw

So after a _Resume is handled, the control will come back right?

And what happens the next time that coroutine is resumed, because we just jumped back? Does it just continue down?

And in these cases, is using catchresume correct? don’t you just want to throw at? No, because you don’t want termination

I guess you can ask, resume() vs. _Resume?

it makes sense resume() goes with suspend()
But do you need that for _Resume

Now, if there are

p.49 If a coroutine throws an exception but does not handle it, the system will raise a special exception called uBaseCoroutine::UnhandledException.

When an unhandled exception occurs:

The exception is propagated to the last resumer of the coroutine, not its original starter.
The coroutine terminates after this unhandled exception is raised

Take a look at this example

_Exception E {};
_Coroutine C {
  void main() { _Throw E(); }  // The coroutine throws exception E but doesn't handle it
public:
  void mem() { resume(); }     // Resuming the coroutine triggers the unhandled exception
};
 
int main() {
  C c;
  try {
    c.mem();                   // Resuming coroutine C
  } _CatchResume( uBaseCoroutine::UnhandledException & ) {
    // Option 1: Handle it after resume
  } catch( uBaseCoroutine::UnhandledException & ) {
    // Option 2: Handle it after the try block
  }
}

There are 2 ways to handle an unhandled exception:
What it does: The CatchResume handler catches the unhandled exception and allows the program to continue execution from the point of resumption—that is, after the coroutine has been resumed.

3.10 Full Coroutines

Semi-coroutine activates the member routine that activated it.
Full coroutine has a resume cycle; semi-coroutine does not form a resume cycle

I still don’t really understand the difference in full coroutine.

Ahh I think i get it

It's about the resume()

When a semi-coroutine calls a resume(), it will resume itself in main() the last point of suspension (last suspend()).

However, for a full-coroutine, we can have the case where we call resume() and have another coroutine resumed.

_Coroutine PingPong {
    const char * name;
    const unsigned int N;
    PingPong * part;
    void main() { // ping’s starter ::main, pong’s starter ping
        for ( unsigned int i = 0; i < N; i += 1 ) {
            cout << name << endl;
            part->cycle();
        }
    }
  public:
    PingPong( const char * name, unsigned int N, PingPong & part ) : name(name), N(N), part(&part) {}
    PingPong( const char* name, unsigned int N) : name( name), N(N) {}
    void partner(PingPong & part) { PingPong::part = &part; }
    void cycle() { resume(); }
};
 
int main() {
    enum { N = 20 };
    PingPong ping("ping", N + 1), pong( "pong", N, ping);
    ping.partner(pong);
    ping.cycle();
}

3.11 Coroutine Languages

Coroutine implementations have two forms:

stackless: use the caller’s stack and a fixed-sized local-state
stackful: separate stack and a fixed-sized (class) local-state

🛠️ Steven Gong

Table of Contents

CS343 - Concurrent and Parallel Programming

Notes

1. Advanced Control Flow

2. Nonlocal Transfer

2.3 Exception Handling

3. Coroutine

3.1 Semi-Coroutine

Fibonacci Sequence

3.1.3 Correct Coroutine Usage

3.2 EHM

3.5 Raising

3.6 Handler

3.7 Nonlocal Exceptions

What it does: The CatchResume handler catches the unhandled exception and allows the program to continue execution from the point of resumption—that is, after the coroutine has been resumed.

3.10 Full Coroutines

3.11 Coroutine Languages

Graph View

Backlinks