ideas4 VS preemptible-thread

https://github.com/samsquire/ideas4#334-knowledgegraph-progr...

How would you do control flow and scheduling and parallelism and async efficiently with this code?

`db.save()`, `download()` are IO intensive whereas `document.query("a")` and `parse` is CPU intensive.

I think its work diagram looks like this: https://github.com/samsquire/dream-programming-language/blob...

I've tried to design a multithreaded architecture that is scalable which combines lightweight threads + thread pools for work + control threads for IO epoll or liburing loops:

Here's the high level diagram:

https://github.com/samsquire/ideas5/blob/main/NonblockingRun...

The secret is modelling control flow as a data flow problem and having a simple but efficient scheduler.

I wrote about schedulers here and binpacking work into time:

https://github.com/samsquire/ideas4#196-binpacking-work-into...

I also have a 1:M:N lightweight thread scheduler/multiplexer:

https://github.com/samsquire/preemptible-thread

My blogging/journalling setup is simple.

I just use GitHub. I just rely on the default repository view on GitHub.com

I create a README.md and add markdown headings to the bottom or to the top (bottom if its a journal, top if it's a blog) and then when I get to 100-800 I create a new repository and repeat.

https://github.com/samsquire/ideas (2013)

https://github.com/samsquire/ideas4

https://github.com/samsquire/ideas3

https://github.com/samsquire/ideas2

Thanks for posting this Ask HN question.

I journal ideas and thoughts about computers and software. I am interested in software architecture, parallelism, async, coroutines, database internals, programming language implementation, software design and the web.

https://github.com/samsquire/ideas (2013)

https://github.com/samsquire/ideas2

https://github.com/samsquire/ideas3

https://github.com/samsquire/ideas4 <-- this is recent but needs editing

https://github.com/samsquire/ideas5 <-- this is what I'm working on now

https://github.com/samsquire/startups

https://github.com/samsquire/blog <-- thoughts I want to write about, but incomplete

I use README.md on GitHub and create a heading at the bottom for each entry. I use Typora on Windows or the GitHub web interface to edit.

My deep interest is multithreaded code. For a software engineer working on business software, I'm not sure if they should be spending too much time debugging multithreaded bugs because they are operating at the wrong level of abstraction from my perspective for business operations.

I'm looking for an approach to writing concurrent code with parallelism that is elegant and easy to understand and hard to introduce bugs. This requires alternative programming approaches and in my perspective, alternative notations.

One such design uses monotonic state machines which can only move in one direction. I've designed a syntax and written a parser and very toy runtime for the notation.

https://github.com/samsquire/ideas5#56-stateful-circle-progr...

https://github.com/samsquire/ideas4#558-state-machine-formul...

The idea is inspired by LMAX Disruptor and queuing systems.

This is really good. Thank you!

I've been studying how to create an asynchronous runtime that works across threads. My goal: neither CPU and IO bound work slow down event loops.

I've only written two Rust programs but in Rust you presumably you can use Rayon (CPU scheduling) and Tokio (IO scheduling)

I wrote about using the LMAX Disruptor ringbuffer pattern between threads.

https://github.com/samsquire/ideas4#51-rewrite-synchronous-c...

I am designing a state machine formulation syntax that is thread safe and parallelises effectively. It looks like EBNF syntax or a bash pipeline. Parallel steps go in curly brackets. There is an implied interthread ringbuffer between pipes.

  states = state1 | {state1a state1b state1c} {state2a state2b state2d} | state3

This is very interesting and could lead to some futuristic programming technology.

I kind of want to plot the state space of a program to see all available states.

In my exploration of distributed systems, microservices and multithreaded systems, it is extremely helpful to try and see what potential states the system can be in. Global and local reasoning of these kinds of software is rather difficult.

I've written about value tracing but I've not heard of treating values as types. I would love to be able to see the trajectory of a value through different states.

https://github.com/samsquire/ideas4#571-value-calculus-varia...

I've never written a TLA+ specification and I'm a complete beginner to this space but I've been trying to understand the dining philosophers one. TLA+ Toolbox is aware of discrete states in the state space, which is absolutely awesome. Types can inform us about future possible valid states.

I began writing a visualisation of memory and animated the movement of memory around to try reveal patterns.

https://replit.com/@Chronological/ProgrammingRTS#index.html

If we see types or values as positions, we can create animations of the state space unfolding in front of us. This is the dream.

Great comment!

>I think late architecture is orthogonal to functional, imperative

Absolutely. From a truly architectural view, procedural, functional, and method-oriented (current OO) are really only variations on the call/return architectural style. Good and sometimes important distinctions, but not really that far apart. They are very much about computing, results from inputs. That is an appropriate architecture for fewer and fewer programs.

See Why Architecture Oriented Programming matters

https://blog.metaobject.com/2019/02/why-architecture-oriente...

and

Can Programmers Escape the Gentle Tyranny of call/return?

https://2020.programming-conference.org/details/salon-2020-p...

> its solution is higher level than even functional programming

Yes. Well, functional actually gets most of its utility from being lower level as far as paradigms go (less powerful). But yes.

> and more abstract

No. Well, yes, if expressed with current programming languages. But that's part of the problem set, not part of the solution set. We should be able to express our architectures less abstractly, more concretely, but for that we need linguistic support. Which is why I am working on that:

http://objective.st

> I want software architecture to be cheap and easy to change without breaking any existing behaviours. I don't know much research on this subject.

There was quite a bit of research at CMU, for example on packaging mismatch. Famous paper Architectural Mismatch, Why Reuse is so hard, and the 10 year follow up in 2009: Architectural Mismatch: Why Reuse is Still So Hard

https://repository.upenn.edu/cgi/viewcontent.cgi?article=107...*

Not much has changed since.

> https://github.com/samsquire/ideas4

> https://devops-pipeline.com

Will check those out. Dataflow is definitely a big part of it, with the extension of dataflow constraints (make, spreadsheets, "FRP"/"Rx"). But so is in-process REST with Storage Combinators!

And breaking down barriers between scripting and "real" programming.

Thanks for this.

I have never deployed a server mesh or used one but I am designing something similar at the code layer. It is designed to route between server components. That is, at the architecture between threads in a multithreaded system.

The problem I want to solve is that I want architecture to be trivially easy to change with minimal code changes. This is the promise and allure of enterprise service buses and messaging queues.

I have managed RabbitMQ and I didn't enjoy it.

If I want a system that can scale up and down and that multiples of any system object can be introduced or removed without drastic rewrites.

I would like to decouple bottleneck from code and turn it into runtime configuration.

My understanding of things such as Traefik and istio is that they are frustrating to set up.

Specifically I am working on designing interthread communication patterns for multithreaded software.

How do you design an architecture that is easy to change, scales and is flexible?

I am thinking of a message routing definition format that is extremely flexible and allows any topology to be created.

https://github.com/samsquire/ideas4#526-multiplexing-setting...

I think there is application of the same pattern to the network layer too.

Each communication event has associated with it an environment of keyvalues that look similar to this:

  petsserver1

Thanks for remembering me :-)

I would like things to run locally by default and then deployed to the cloud where they run.

Should be easier to debug problems if I can get the code to my machine and investigate issues with tools that my computer has such as "strace", "perf" and debug logging that I liberally apply to the build script.

In production we would have log aggregation and log search (such as ELK stack) and it is a good habit to get into the perspective of debugging production via tooling.

But CICD feels before that tooling in the pipeline. You could wire up your CICD to log to ELK but I would prefer local deployable software.

I think my focus on automating things means I want to be capable of seeing how the thing works without relying on a deployed black box in the cloud and using assumptions of how it works rather than direct investigation.

One of my journal entries is almost a lamentation of all the things that need to be done to release and use software.

This is that entry:

https://github.com/samsquire/ideas4#5-permanent-softwareplat...

I wonder if software could be deployed more like a URL that has all the information to configure a virtual machine. Docker over URL or something.

Thanks for this article.

I want to combine the benefits of kernel threads with coroutines or goroutines/green threads/lightweight threads. (If anybody knows anything specifically about fibers, I'd appreciate that because I'm not familiar with them.)

I have a lightweight thread scheduler https://github.com/samsquire/preemptible-thread which is a 1:M:N scheduler (1 scheduler thread, M kernel threads, N lightweight threads) with the lightweight threads being multiplexed on the kernel threads.

I am working on a multithreaded architecture which I all 3 tier multithreaded architecture. It combines request parallelism with IO and CPU parallelism and intra request parallelism.

We split kernel threads into three groups: app threads, which run lightweight threads, IO threads (liburing/epoll) and traditional CPU threadpool with work stealing.

* The IO threads have buffers that other threads can write to to queue up data for sockets.

How would you do control flow and scheduling and parallelism and async efficiently with this code?

`db.save()`, `download()` are IO intensive whereas `document.query("a")` and `parse` is CPU intensive.

I think its work diagram looks like this: https://github.com/samsquire/dream-programming-language/blob...

I've tried to design a multithreaded architecture that is scalable which combines lightweight threads + thread pools for work + control threads for IO epoll or liburing loops:

Here's the high level diagram:

https://github.com/samsquire/ideas5/blob/main/NonblockingRun...

The secret is modelling control flow as a data flow problem and having a simple but efficient scheduler.

I wrote about schedulers here and binpacking work into time:

https://github.com/samsquire/ideas4#196-binpacking-work-into...

I also have a 1:M:N lightweight thread scheduler/multiplexer:

https://github.com/samsquire/preemptible-thread

* I want to keep IO and CPU in flight at all times.

I think I want this schedule:

https://user-images.githubusercontent.com/1983701/254083968-...

I have a toy 1:M:L 1 scheduler thread:M kernel threads:N lightweight threads lightweight scheduler in C, Rust and Java

https://github.com/samsquire/preemptible-thread

This lets me switch between tasks and preempt them from user space without assistance at descheduling time.

I have a simplistic async/await state machine thread pool in Java. My scheduling algorithm is very simple.

I want things like backpressure, circuit breakers, rate limiting, load shedding, rate adjustment, queuing.

Thanks for this article and to ingve for submitting it.

Concurrency and async is my favourite topic. I wrote a very simple toy lightweight 1:M:N (1 scheduler:M kernel threads:N lightweight threads) thread scheduler in C, Rust and Java.

https://github.com/samsquire/preemptible-thread

It works on the principle that hot loops can be interrupted BY ANOTHER THREAD (the scheduler thread) on a timer, to give lightweight threads a chance to execute.

What I think I want today though is an extremely rich process/concurrency API that resembles a stream API but for processes. For example, we should be able to create pipelines that can be paused, resumed, forked, merged, drop_while, iterate_until and whatever else would be useful.

I really like this.

Thank you for your comment and sharing.

I have a lightweight 1:M:N runtime (1 scheduler thread, M kernel threads, N lightweight threads) which preempts by setting hot loops to the limit.

https://github.com/samsquire/preemptible-thread (Rust, Java and C)

How do you preempt code that is running?

https://github.com/samsquire/ideas5/blob/main/NonblockingRun...

The design is that we have three groupings of thread types. The application starts up some application threads which are not associated with a request, these service multiconsumer multiproducer thread safe ringbuffers in lightweight threads with a Go-erlang-like lightweight process runtime. (My simple lightweight thread runtime is https://github.com/samsquire/preemptible-thread) We also multiplex multiple network clients sockets across a set number of kernel threads which I call control threads. Their responsibility is to dispatch work to a work stealing thread pool ASAP which has its own group of threads. So we pay a thread synchronization cost ONCE per IO which is the dispatch from the control thread to a thread pool thread. (Presumably this is fast, because the thread pool threads are all looping on a submission queue)

We split all IO and CPU tasks into two halves: submit and handle reply. I assume you can use liburing or epoll in the control threads. The same with CPU tasks and use ringbuffers to communicate between threads. We can always serve client's requests because we're never blocked on handling someone else's request. The control thread is always unblocked.

I think this article is good regarding Python's asyncio story:

I am deeply interested in the multithreading, parallelism, async and coroutine design space and I journal about it everyday in my ideas journal.

I wrote a toy very simple 1:M kernel threads:N lightweight thread runtime in terrible Rust, C and Java.

Hot loops use a structure for its limit and looping variable. Then to cancel the loop, you set the looping variable to the limit from a scheduling thread, cancelling the loop. This is used for process switching and scheduling but it can also be used for cancellation.

Can create very responsive code this way, it's even possible to cancel while (true) loops by replacing them with while (!preempted) {}.

https://github.com/samsquire/preemptible-thread

There is potential for a race, but that can be detected and worked around.

I also have a M:N m kernel threads to N lightweight thread userspace preemptive scheduler at https://github.com/samsquire/preemptible-thread It would be nice to schedule lightweight threads in a JIT compiler. Imagine being capable of running processes similar to BEAM and Go but with JIT.

This is interesting, thank you.

I really should learn from BEAM and the OTP and learn Erlang. I get the feeling it's super robust and reliable and low maintenance. I wrote a userspace multithreaded scheduler which distributes N lightweight threads to M kernel threads.

https://github.com/samsquire/preemptible-thread

I recently wrote a JIT compiler and got lazy compilation of machine code working and I'm nowhere near beginning optimisation

https://github.com/samsquire/compiler

How do you write robust software, that doesn't crash when something unexpected goes on?

I looked at sozo https://github.com/sozu-proxy/sozu

and I'm thinking how to create something that just stays up and running regardless.

I wrote a preemptive 1:M:N scheduler in C, Rust and Java.

https://github.com/samsquire/preemptible-thread

It is a 1:M:N scheduler where there is one scheduler thread, M kernel threads and N lightweight threads. I take advantage that loop indexes can be structures and can be modified by other threads. So we can set the thread's looping variable to the limit to end the current loop and pause it and then schedule another thread.