Recent

Author Topic: STAX: Single Threaded Asynchronous Execution Framework  (Read 5703 times)

Warfley

  • Hero Member
  • *****
  • Posts: 554
STAX: Single Threaded Asynchronous Execution Framework
« on: August 30, 2021, 10:52:13 pm »
Hi,

for the past few weeks I was working on my new project, the Single Threaded Asynchronous EXecution framework (STAX for short), which enables async/await style co-routines for FreePascal.
Today I am pretty satisfied with the feature set and the stability of this project, so I wanted to share it with you.

It is available on GitHub: https://github.com/Warfley/STAX

The basic idea behind STAX is to enable asynchronous execution flows without the use of multithreading. The idea is to split the control flow up into small tasks, which all run on the same thread. Tasks will run until they voluntarily give up their execution time, and another can be scheduled. This introduces two guarantees: 1. there will never be two tasks running simultaniously (i.e. on different CPUs), 2. Tasks will only be interrupted when they are allowing it, i.e. never during any critical section. This completely eliminates the possibility for race conditions, and therefore allows for writing asynchronous code without the requirement for locks or synchronization mechanisms.
This is a major advantage over classical threading, as locking and synchronization mechanisms create a lot of maintainance overhead and can easily introduce bugs like deadlocks.

To guarantee a high degree of concurrency, it must be ensured that tasks yield often to the scheduler. To archive this, the programs need to be designed to consist of multiple small tasks. Rather than one task including a lot of functionality, the functionality must be seperated into multiple smaller tasks, which will depend on one another. When one task requires the functionality of another task, it will schedule that task and then yield to the scheduler until that new task finished, also giving other waiting tasks the chance to be scheduled.
If all tasks are small and often wait for other tasks, a high degree of concurrency can be archived.

Another opportunity for tasks to yield to the scheduler is when waiting for events. This includes the simple sleeping for a certain amount of time, but also waiting for the system. A prime example is the waiting for blocking I/O. In networking applications receiving and sending is usally blocking, meaning when a system call to receive data is made, the system will block that thread until data is available. In STAX this waiting time, until data is available, can be used to schedule other tasks.
An example for this can be seen in the examples/tcptest folder, which implements a TCP echo server which can serve multiple clients on a single thread

Besides not requiring locks another advantage by having all tasks run on the same thread is, that this can be directly incorporated int LCL GUI applications. A very simple approach on how to use STAX in LCL applications can be seen in "examples/pong", where STAX is used to implement a two player Pong game using TCP, where the TCP connection is handled on the same thread as the GUI, being able to directly access the GUI without any form of synchronization mechanism.

To give a small example on how such a STAX program would look, here is the tcp server example:
Code: Pascal  [Select][+][-]
  1. program server;
  2.  
  3. {$mode objfpc}{$H+}
  4.  
  5. uses
  6.   stax, stax.asynctcp, stax.functional;
  7.  
  8. // simple tcp echo server
  9. procedure HandleConnection(AExecutor: TExecutor; AConnection: TSocket);
  10. var
  11.   c: Char;
  12. begin
  13.   while True do
  14.   begin
  15.     // wait until a char was received
  16.     c := specialize Await<Char>(specialize AsyncReceive<Char>(AConnection));
  17.     Write(c);
  18.     // asynchronously send the response
  19.     AExecutor.RunAsync(specialize AsyncSend<Char>(AConnection, c));
  20.   end;
  21. end;
  22.  
  23. procedure RunServer(AExecutor: TExecutor; AHost: string; APort: Integer);
  24. var
  25.   Sock: Tsocket;
  26.   Conn: TSocket;
  27. begin
  28.   Sock := TCPServerSocket(AHost, APort);
  29.   TCPServerListen(Sock, 10);
  30.   while True do
  31.   begin
  32.     Conn := specialize Await<TSocket>(AsyncAccept(Sock));
  33.     // Asynchronously handle the communication to have this task continue to accept new clients
  34.     AExecutor.RunAsync(specialize AsyncProcedure<Tsocket>(@HandleConnection, Conn));
  35.   end;
  36. end;
  37.  
  38. var
  39.   exec: TExecutor;
  40. begin
  41.   exec := TExecutor.Create;
  42.   exec.RunAsync(specialize AsyncProcedure<String, Integer>(@RunServer, '0.0.0.0', 1337));
  43.   try
  44.     exec.Run;
  45.   except on E: EUnhandledError do
  46.     WriteLn('Unhandled error: ', E.Message);
  47.   end;
  48.   exec.Free;
  49.   ReadLn;
  50. end.

Besides tasks, STAX also support generators, which allow to write code that produces multiple results sequentially. Unlike tasks, where memory management can simply be done after finishing, generators can contain potentially infinite code, and might be shared between tasks. For this reason rather than manual memory management (as used for Tasks), they are implemented with reference counted COM interfaces to ease usage. As long as generators are only referenced via the IGenrator interface, no manual considerations for memory manamgement is required.

An example to iterate the filesystem recursively can be found in examples/generators/generatoriterationtest.pas:
Code: Pascal  [Select][+][-]
  1. program generatoriterationtest;
  2.  
  3. {$mode objfpc}{$H+}
  4.  
  5. uses
  6.   SysUtils, stax, stax.functional;
  7.  
  8. procedure IterateDirectory(Yield: specialize TYieldFunction<String>; ADirectory: String);
  9. var
  10.   SearchRec: TSearchRec;
  11.   Entry, SubEntry: string;
  12. begin
  13.   if FindFirst(ADirectory + PathDelim + '*', faAnyFile, SearchRec) = 0 then
  14.   try
  15.     repeat
  16.       if (SearchRec.Name = '.') or (SearchRec.Name = '..') then
  17.         Continue;
  18.       Entry := ADirectory + PathDelim + SearchRec.Name;
  19.       Yield(Entry);
  20.       // recursive descent into directories
  21.       if (SearchRec.Attr and faDirectory) = faDirectory then
  22.         for SubEntry in specialize AsyncGenerator<String, String>(@IterateDirectory, Entry) do
  23.           Yield(SubEntry);
  24.     until FindNext(SearchRec) <> 0;
  25.   finally
  26.     FindClose(SearchRec);
  27.   end;
  28. end;
  29.  
  30. procedure GeneratorIteratorTest(AExecutor: TExecutor);
  31. var
  32.   dir: String;
  33. begin
  34.   for dir in specialize AsyncGenerator<String, String>(@IterateDirectory, '.') do
  35.     WriteLn(dir);
  36. end;
  37.  
  38. var
  39.   exec: TExecutor;
  40. begin
  41.   exec := TExecutor.Create;
  42.   try
  43.     exec.RunAsync(AsyncProcedure(@GeneratorIteratorTest));
  44.     exec.Run;
  45.   finally
  46.     exec.Free;
  47.   end;
  48.   ReadLn;
  49. end.
  50.  
  51.  

More technical information can be found in the repositories README.md


I've developed and tested STAX under Windows 10 and Linux, both x86_64 systems. On Windows it works right out of the box. On linux it requires a small change to the RTL i.e. requires a custom FPC build. The required changes are stored as a diff in the fpc.patch of the FPCFiber repository (which is referenced as a submodule in the externals directory of the STAX repository). It can be applied with "git apply" in the local fpc-sources git repository.

For using STAX I am also developing some asynchronous libraries.

For now I am working on an networking lib AsyncNet, which shall provide the functionality of FCL-Net but for asynchronous use: Link. It is also provides with the asyncnet.sockets unit a replacement for the stax.asynctcp unit, now supporting also IPv6 as well as UDP. Besides this, it also includes DNS resolution functionality.
« Last Edit: October 11, 2021, 06:58:51 pm by Warfley »

Alextp

  • Hero Member
  • *****
  • Posts: 1405
    • UVviewsoft
Re: STAX: Single Threaded Asynchronous Execution Framework
« Reply #1 on: August 31, 2021, 01:47:21 am »
I posted this intro-text to wiki:
https://wiki.freepascal.org/STAX

PierceNg

  • Full Member
  • ***
  • Posts: 139
Re: STAX: Single Threaded Asynchronous Execution Framework
« Reply #2 on: August 31, 2021, 03:52:24 am »
Great stuff!

But existing web frameworks probably need to be modified or new ones written?

MarkMLl

  • Hero Member
  • *****
  • Posts: 3253
Re: STAX: Single Threaded Asynchronous Execution Framework
« Reply #3 on: August 31, 2021, 08:22:28 am »
Well done, and hopefully it will spur the introduction of coroutines as a standard feature in FPC.

But existing web frameworks probably need to be modified or new ones written?

I hate to tell you this but there's more to software than web stuff.

MarkMLl
Turbo Pascal v1 on CCP/M-86, multitasking with LAN and graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

engkin

  • Hero Member
  • *****
  • Posts: 2958
Re: STAX: Single Threaded Asynchronous Execution Framework
« Reply #4 on: August 31, 2021, 09:40:13 am »
Thank you for sharing. Bookmarked!

Warfley

  • Hero Member
  • *****
  • Posts: 554
Re: STAX: Single Threaded Asynchronous Execution Framework
« Reply #5 on: August 31, 2021, 05:21:31 pm »
Great stuff!

But existing web frameworks probably need to be modified or new ones written?

Do you mean fpweb? You can use it to write a webserver, but you need to write one from scratch. I only provide basic TCP functionality. I don't see any easy way of porting existing libraries to the async/await paradigm. It requires a completely new approach to developing components.

Leledumbo

  • Hero Member
  • *****
  • Posts: 8386
  • Programming + Glam Metal + Tae Kwon Do = Me
Re: STAX: Single Threaded Asynchronous Execution Framework
« Reply #6 on: September 17, 2021, 07:25:10 am »
This sounds like cooperative multitasking, doesn't it?

MarkMLl

  • Hero Member
  • *****
  • Posts: 3253
Re: STAX: Single Threaded Asynchronous Execution Framework
« Reply #7 on: September 17, 2021, 08:45:44 am »
This sounds like cooperative multitasking, doesn't it?

Yes, but in the context of a single process/program. Coroutines, broadly as implemented in Modula-2.

MarkMLl
Turbo Pascal v1 on CCP/M-86, multitasking with LAN and graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

devEric69

  • Hero Member
  • *****
  • Posts: 614
Re: STAX: Single Threaded Asynchronous Execution Framework
« Reply #8 on: September 17, 2021, 09:04:34 am »
Question from a newbie: it's close to parallel procedures (https://wiki.lazarus.freepascal.org/Parallel_procedures), or is this implemented completely differently, or inside a different paradigm, ...?

(Said differently) In fact, my question is: in a big loop that I call a resultt task (a for, let's say), can STAX easily transform each iteration of the for loop into a task (it's sometimes with this kind of simple transformation that I would like to consider, I would like to do a refactoring) and give the answer in the resulting task (i.e. the final for loop)?
« Last Edit: September 17, 2021, 09:22:40 am by devEric69 »
use: Linux 64 bits (Ubuntu 20.04 LTS).
Lazarus version: 2.0.4 (svn revision: 62502M) compiled with fpc 3.0.4 - fpDebug \ Dwarf3.

MarkMLl

  • Hero Member
  • *****
  • Posts: 3253
Re: STAX: Single Threaded Asynchronous Execution Framework
« Reply #9 on: September 17, 2021, 09:21:55 am »
Question from a newbie: it's close to parallel procedures (https://wiki.lazarus.freepascal.org/Parallel_procedures), or is this implemented completely differently, or inside a different paradigm, ...?

Distinct. The point of parallel procedures (or, in the slightly more general case, parallel blocks) is that you have a block of code which can usefully be farmed out to multiple CPUs (etc.) with a controlled rendezvous at the end.

The point of coroutines etc. is that control can enter a block, then that block's command sequence can yield the CPU to some other block, and when control returns it comes back to the same place. So you can have two or more blocks, each with their own state, with control shuttling between them depending on the availability of data etc.

***

https://en.wikipedia.org/wiki/Coroutine#Comparison_with_subroutines

An interrupt handler is a special case: it's a coroutine associated with a specific IRQ and sometimes is specified with a priority etc. On top of coroutines you can build threads, although in almost all cases these days those are handled at the OS level. On top of threads you can build processes which are basically threads with a distinct memory context, and a process can load and execute a binary program... hence all variants of multiprocessing.

*** Added subsequently. Noting https://forum.lazarus.freepascal.org/index.php/topic,56439.msg419515.html#msg419515 from Marco, there are actually three interesting cases:

* Coroutines, where control can be transferred between blocks as discussed elsewhere in this thread,

* Parallelised blocks, where a block is implicitly distributed across multiple threads/processors (not supported by FPC or Delphi),

* Monitors, where if multiple threads arrive at a block only one of them is allowed to proceed (not supported by FPC).

MarkMLl
« Last Edit: September 28, 2021, 10:10:02 pm by MarkMLl »
Turbo Pascal v1 on CCP/M-86, multitasking with LAN and graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

Warfley

  • Hero Member
  • *****
  • Posts: 554
Re: STAX: Single Threaded Asynchronous Execution Framework
« Reply #10 on: September 28, 2021, 09:29:04 pm »
So over the past few weeks I was working on a more extended networking library for STAX, which now also includes functionality for UDP as well as IPv4  and IPv6 support. The goal is to provide all the fcl-net functionality for STAX (and make porting of existing applications using FCL-Net easier). Right now it only supports the basic networking functionality and the DNS resolution functionality. In the near future I will try to implement the ssockets unit as well as the socket handler and SSL support.

As this is basically a fork of FCL-Net (even though through heavy reworking and restructuring there is pretty much not a single line of original fcl-net code currently in this project) I published it under the same license as the FCL (Modified LGPL) and not under the BSD as STAX is.

For more information check out my original post, I've added  the link to AsyncNet into the post.

Besides this, I also fixed some bugs in STAX I discovered while working on AsyncNet, changed a lot of things under the hood and added some features. For example now there is a AwaitAll function which awaits one or more Tasks until either all finished or one threw an error.  All await functions (Await, Await<Result> and AwaitAll) now also have a timeout which can be used to kill these tasks if they don't finish in time (e.g. usefull for implementing timeout network connections).
I also added Fiber caching to improve performance. In my performance test example on my machine this makes the execution of tasks around 10-30 times faster under Windows, while there is not much difference under Linux (which is about as fast as Windows with caching in both configurations).
And LCL integration is massively improved. While it is still a hack, it works really reliable and one can make use of all features of the LCL. Further information can be found on the GitHub README

Also I layed the groundwork for adding a new feature, generators, which will allow the user to write iterative code sequentially. This can make writing custom iterators/enumerators (e.g. iterating over a directory) much easier than with conventional enumerators.
For example a generator that can generate the numbers 1, 2 and 3 could look like this:
Code: Pascal  [Select][+][-]
  1. TNumberGenerator.Execute;
  2. begin
  3.   Generate(1); // will wait until next is requested
  4.   Generate(2); // will wait until next is requested
  5.   Generate(3); // will wait until next is requested, then it will signal finish
  6. end;
and  used like this:
Code: Pascal  [Select][+][-]
  1. for number  in NumberGenerator do
  2.   WriteLn(Number);
  3. // or
  4. firstNum := GenerateNext<Integer>(NumberGenerator);
  5. secondNum := GenerateNext<Integer>(NumberGenerator);
  6. thirdNum := GenerateNext<Integer>(NumberGenerator);
  7. // or
  8. NumArray := GenerateArray<Integer>(NumberGenerator, 3);
But this is all still in the design phase
« Last Edit: September 28, 2021, 09:38:06 pm by Warfley »

MarkMLl

  • Hero Member
  • *****
  • Posts: 3253
Re: STAX: Single Threaded Asynchronous Execution Framework
« Reply #11 on: September 28, 2021, 09:53:11 pm »
Good work.

MarkMLl
Turbo Pascal v1 on CCP/M-86, multitasking with LAN and graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

Warfley

  • Hero Member
  • *****
  • Posts: 554
Re: STAX: Single Threaded Asynchronous Execution Framework
« Reply #12 on: October 11, 2021, 06:55:48 pm »
Generators are now implemented (example was edited into the first post of this Thread). And this now basically forms my version 2.0.

Sadly I now don't have as much free time as before, meaning progress will now slow down (significantly)

 

TinyPortal © 2005-2018