2,684 karma · joined June 16, 2013
I've been using a compiler fence to force reloads from memory to prevent -O3 from optimising away my variables/structs changing by other threads and keeping data in registers rather than reloading from memory each time. I saw the volatile recommended against from the Linux kernel programmers.
such as my thread->running == 1 in my event loops for my threads.
https://www.kernel.org/doc/html/latest/process/volatile-cons...
rather than just a plain load.
My understanding of that syntax is that it is a compiler memory barrier, not a CPU memory barrier because the asm block is empty (no sfence or mfence).
they're all on https://github.com/samsquire/assembly, i tried to write multiple disruptor with multiple consumers, then one with multiple producers then one with multiple consumers AND multiple producers, inspired by LMAX Disruptor. (There's files for each of them and table in the repo. it's not proven yet!)
the contention on the same memory address (the read/write index) is the thing that seems difficult to address.
One thing I've learned about thread safety:
I think if you have thread-owned values then you can be thread safe with a simple semaphore, providing that you have unique, DISTINCT values for each thread.
If you have two threads that have this in a hot loop in parallel:
// thread 0
if buffer[x].available == 1:
// do stuff
buffer[x].available = 0
// thread 1
if buffer[x].available == 0:
// do stuff
buffer[x].available = 1
The CMP is a cheap mutex with distinct valued memory locations.
Even though thread 1 is writing to buffer[x].available and thread 0 is writing to buffer[x].available it doesn't matter because the causality is mutually exclusive. There is no interleaving of buffer[x].available = x because of the if statement.
The buffer[x].available = 0 will never run while buffer[x].available is equal to 0 overwriting or causing a data race when setting buffer[x].available to 1. So the second line cannot happen in parallel.
I need to write a TLA model to assert its safety.
If you have more than 2 threads, then you need different tokens to provide admissability to the if statement.
Remember to use compiler memory barrier
asm volatile ("" ::: "memory");
I submitted my personal homepage.
Those GitHub conventions are helpful. I was hoping people would create entire repositories in a standard convention too. Similar to Rails conventions.
I have my own animation here - if you scroll down. You can see the parsing I do for an async syntax (scroll to the hearing named Definition) - you can edit the syntax and it reparses and displays the parsed output. Sorry for the mess it's kind of a place I work on ideas. Further down is my graph renderer.
https://processes3.replit.app/
I want to auto parallelize async tasks.
I am working on a multithreaded runtime in C which is incomplete but can communicate between threads in roughly 60 nanoseconds at 6 million requests per second or closer to LMAX throughout of 20 million requests per second at a latency of 90-120 nanoseconds.
In my learnings Mutexes do not scale.
I am inspired by bulk synchronous parallel which means threads synchronize in a rhythm without Mutexes and a lock free algorithm to do with semaphores and observation rather than mutability.
I run two io_urings in different threads - one thread does send and another thread does recv. One ioring is talking to an epoll instance for network buffer readiness with EPOLLOUT.This means sending and receiving is full duplex - you can send and receive to different clients in parallel. I call it split IO.
I plan to write up all my learnings soon.
My adapted HTTP server from the loti examples gets a throughout that scales with the number of connections I am at 7000 requests per second. I am not nginx.
I use mailboxes and double buffering for thread safe communication. Each thread can communicate with another thread through its mailbox. This is like Erlang.
I plan to add coroutines based on Marce Colls coroutines. I can deschedule a coroutine when there is an await.
I'm encouraged by the same ideas.
Sometimes you just want something that stays running and doesn't go down and can scale to zero and scale upwards, ideally with revenue.
I kind of want a special mega HTTP form endpoint which I can define a pipeline from, that can go to database and cause background jobs and goes into a mega API automatically.
My homepage is a small introduction and a table of projects with links to those projects, which are also github repositories with a blog underneath.
This community standardisation I really like /about /now /ideas, I would like people to create github repositories with this format:
"wants" -> things that this person wants
"perspectives" -> technical perspectives on different subjects
"work" -> work that someone thinks need doing
"collaboration" -> what someone would be willing to work with others on
"commissions" -> what you'll pay someone for
"ideas" -> ideas
"blog" -> if your blog is hosted on github
"dotfiles" -> if you have them
It might be interesting to someone but I used A* to do code generation to go from one state to target state. I'm not experienced with the planning community or solvers except for playing around naively with ortools.
I generate assembly instructions to move between states.
start_state = {
"memory": [0, 0, 0, 0],
"rax": 0,
"rbx": 1,
"rcx": 2,
"rdx": 3,
"rsp": -1,
"rdi": -1,
"rbp": -1
}
end_state = {
"memory": [3, 1, 2, -1],
"rax": 3,
"rbx": 2,
"rcx": 1,
"rdx": 0,
"rsp": 6,
"rdi": -1,
"rbp": -1
}
[start, mov %rax, (%rdx), mov %rbx, (%rbx), mov %rcx, (%rcx), mov %rdx, (%rsp), mov %rax, %rsp, mov %rdx, %rax, mov %rsp, %rdx, mov %rcx, %rsp, mov %rbx, %rcx, mov %rsp, %rbx, call minus1(rdi=-1) -> rsp=4, call fourtofive(rsp=4) -> rsp=5, call fivetosix(rsp=5) -> rsp=6]
I also run it in parallel to speed up search using python multiprocessing and do dynamic neighbour generation because neighbour generation is different between threads and I couldn't parallelise A* with my original attempts without sharding this.
The dream of my experimentation is that you tell the computer what you have and what you want it works out the correct traversals for you.
For my personal intuition programming is logistics like factorio or a factory. This is why it's called "sliding puzzle", it's a puzzle where you have to move things around to see the correct picture.
Github repo with some notes: https://github.com/samsquire/sliding-puzzle-codegen-memory
Multithreading and parallelism is my hobby, so I'm curious how emacs implements this. I imagine it would be really difficult to migrate the entire ecosystem from code that is not designed to be accelerated by multicore.
I feel that if you just add a mutex, the code will fall very short of expectations of Amdahls law because:
* you cannot accelerate any single memory address mutability rates/performance by adding threads * to accelerate write/read performance (to get up to theoretical memory bandwidth) you need no-locks and multiple threads with DIFFERENT memory addresses
You need a different model to programming that is efficient.
One thing I can think of is that each thread owns a few buffers and you load balance that way.
Did you regex engine support commutative events? (Happen in either order?)
Would you like to talk more about this subject?
What do you find extremely satisfying working on in programming?
Do you write all the time? It works for me! I keep journalling my ideas in a markdown README.md file publicly on GitHub since 2013. While I was writing I felt inspired by an idea and actually felt I desired to try write some code to implement this idea.
I encourage you! You can write your thoughts down and do small achievable things repeatedly.
I recommend using replit to get an environment quick and ready for programming in. When I was a child I wanted to be an inventor because I liked the idea of creating things.
My interest is low level things such as JIT compilers, database internals and distributed systems.
see my profile for what I've done with this strategy and my programming side projects.
Your package manager knows your operating system's current state and the state space of all the control flow graph through the program and configuration together can go to, it can verify that everything lines up and there will be no error when executed a bit like a compiler but without causing the Halting problem.
In TLA+ you can dump a state graph as a dot file, which I turn into a SVG and run with TLA+ graph visualiser.
Types verify possible control flow is valid at every point. We just need to add types to the operating system and file system and represent state space for deterministic verification.
You could hide packages that won't work.
The package manager would have to lookup precached state spaces or download them as part of the verification process.
I am an absolute beginner at TLA+ but I really like this possible design space.
I have an idea for a package manager that combines type system with this style of deterministic testing and state space exploration.
Imagine knowing that your invocation of
package-manager install <tool name>
or an next gen Helm with type system and state space exploration is tested:
kubectl apply <yaml>
* lots of screenshots
* a README.md that is extremely long and detailed
* tutorials, reference, design documents, architecture diagrams
* mental model documents to explain how things are thought of by the authors
state1a state1b state1c | state2a state2b state2c | state3a state3b state3c
In a multithreaded server or multimachine distributed system, there are global states you want to wait for and then trigger behaviour. The communication can be inferred and optimised and scheduled.
It's BNF syntax - inspired by parsing technology for parsing sequences of tokens but tokens represent events.
If you use printf debugging a lot, you know the progression of what you see is what happened and that helps you understand what went wrong. So why not write or generate the log of sequence of actions you want directly not worry about details?
But wait! There's more. You can define movements between things.
So take an async/await thread pool, this syntax defines an async/await thread pool:
next_free_thread(thread:2);
task(task:A) thread(thread:1) assignment(task:A, thread:1) = running_on(task:A, thread:1) | paused(task:A, thread:1);
running_on(task:A, thread:1)
thread(thread:1)
assignment(task:A, thread:1)
thread_free(thread:next_free_thread) = fork(task:A, task:B)
| send_task_to_thread(task:B, thread:next_free_thread)
| running_on(task:B, thread:2)
paused(task:A, thread:1)
running_on(task:A, thread:1)
assignment(task:B, thread:2)
| { yield(task:B, returnvalue) | paused(task:B, thread:2) }
{ await(task:A, task:B, returnvalue) | paused(task:A, thread:1) }
| send_returnvalue(task:B, task:A, returnvalue);
I think iteration/looping and state persistence and closures are all related.
I have a parser for this syntax and a multithreaded barrier runtime which I'm working on, I use liburing. I want to get to 500 million requests per second of the and ~50ish nanosecond latency of LMAX Disruptor.
The notation could be used for business programming and low level server programming I think.
Regarding the article which talks about multicore. Multicore and distributed systems are hard. Behaviour implementation, and transforming event sequences across multicore and multimachine consistently is the hard part of computing for me (distributed systems). And understanding large existing systems such as Chromium, Firefox or GCC. Any enterprise K8s cluster with operators everywhere. That's a lot of code.
This is just my thoughts, I find it easier to write code than read large code bases because like trying to understand a very large mathematical formulae in one go. You cannot even get the entire system into a screenful to understand it, like you could potentially a small formulae. I have to break it out into ordered steps to understand mathematics. They're like an object in the mind that you interact with intuitively. My mental model is the key driver to the act of programming. I sometimes get the mental model right and serialise it into code. Writing is an expression of thoughts and there is a thought that gets turned into notation. Do either of them (thought,notation) represent the other losslessly?
I once used OpenGrok, a web based sourcecode repository viewer to tell myself I would try reading and understanding a large code base.
The semantics of programming languages have an impedance mismatch to how my mental model works.... I have mental models about relational databases and what is fast on a computer. And then there is behaviour, state and IO to work with.
I could change my mental model to match the programming language semantics on the computer but I would probably be less happy that way.
I feel programming languages such as C++ and Rust and Haskell introduce abstractions that work with a certain mental model of solving problems, but not everyone has the same mental model. They work great for the compiler codegen writer, but not for implementing behaviours.
If you've ever worked in a enterprise Java codebase or a frontend software React codebase, from my perspective they're a mess because of the imposed semantics of the language and false problems of trying to get the computer to have the right sequence of actions or behaviour sequence.
I am in early stages of writing a low latency barrier which provides low latency lock free communication between thread pairs ( 1 thread bidirectionally with 1 other thread ) but wiring up to other barriers is proving difficult.
The number of sent messages doesn't match the number of received messages I think I need a mutex unfortunately
So it's interesting that there is options in this space in Rust.
I think you see this in programming languages themselves. I am not criticising C++ or Rust (they do good work, which I admire) but from my perspective the languages have many features that all interact in tricky ways. An example would be coroutines, threads, async, memory management.
There's also social interactions that multiply complexity: see the Python 2 to 3 migration pain that splintered the language for a while. Or Red Hat and its source.
I really enjoy this blog post about writing accidentally writing a compiler and handling the permutations of AST Nodes.
https://rachit.pl/post/you-have-built-a-compiler/
A billing or invoice system, that should be simple? But it isn't because everything interacts: failed jobs, holidays, daylight saving time, timezones, time, business processes, procedures, edge cases.
This is actually a subject that I am investigating as a hobby which is how do you handle interactions between arbitrary behaviours: such as you want a system that is Windows, Linux and Mac and platforms have different semantics that make writing your software tricky.
I think type systems get some of the way there but TLA+ and other formal verification tools help us get another part of the way there. But I am still learning.
The future I am trying to design is a language where traversal order is arbitrarily repetitive and arbitrary and corecursive and has term rewriting traversals.
I think algorithms are just reified traversal evaluation orders and joins - of algebra and mathematics.
The semantics of C really fit how what I think about what computers do: that we move around things between boxes of memory and between registers. That computers is largely logistics between "places". Edit: It's a bit like a factory as in factorio
I didn't write it in Rust because I find the semantics of C++, Rust, Haskell and other functional languages to be much more abstract and harder than this simple idea of stateful movement.
Since there's no requirement to credit a zero clause licenced BSD code, someone who receives the BSD code compiled might not know it's included but that's the risk I'm taking.
I think (please correct my understanding) zero clause BSD can be embedded in a GPL project too, it just becomes one-way included, subsumed into the GPL project and then under the GPL licence. (Relicenced)
Could the author of HTMX explain their reasoning for changing the licence? I am curious?
Every thread has its own unique tag.
long original = me->realend;
int tag = (original & TAG_MASK);
changed = (((original & END_MASK) >> 32)) % me->size;
long new = (data->thread_tag) | (((changed + 1) % me->size) << 32);
I am still learning TLA+ to write a model.
I kind of think of the interactions with the OS as the "effects" of the application like the IO Monad.
It's like a protocol too, function application in a certain order causes the effects of the software. The syscalls is a stream.
There is also a inner protocol between the buffers of binary protocols inside the syscalls such as a network buffer.
There's instruction stream streams into L3, L2, L1 caches from DRAM, PCIE, DMA
then there's multiple cores and they each have register files, they shuffle numbers between registers and the caches.
There's reordering going on, there's parallelisation going on, lots of conveyor belts.
It's all so complicated factory.
objdump -b binary -Matt,x86-64 -D main.bin -m i386 ;
You can work that the assembly implements the semantics of C's virtual machine model and it is this that I find easier to understand than some algebraic systems. I kind of think of struct->ptrarray[indx]->struct.something corresponds to the calculation of ultimately a single memory address even if there is various shift lefts or adds or ors.
Java has its template interpreter which is interesting to read about and there is copy and patch JIT compilers.
I find C easier to understand than the algebra of other languages such as Haskell, Ocaml, Rust because of how C statements correspond to assembly.
Memory is just a big grid of numbered locations and computing is logistics between grid locations. Execution is transition between memory locations.
LEAQ or "&" (C addressof) is an address calculation or LEAQ for one of those grid locations.