Comments (3)
Shared Queue As a Serialization Mechanism
Basically each solution we can get will be serialization for connections with shared receivers. To do so, we need to get rid of concurrency for them.
The most simple way to do is this:
- Get rid of goroutine-per connection
- Implement queue and share it across all senders
- When sender sends to a queue, there is a (one) goroutine that reads from it and does broadcasting
connect() {
for msg := range q {
broadcast(msg)
}
}
However, there's a couple of problems with this solution...
Problems
- It's a bottleneck, each sender sends to the same queue. Slow receiver will slow down fast senders and other receivers.
- Much bigger problem (not performance, but correctness) - how to handle intermediate connections?
Performance Problem (Making the bottleneck wider)
There's basically 3 ways to improve performance of this solution
- Add buffer to queue
- Add buffers to receiver channels
- Use several queues instead of one
It's easy to do first two but last is a bit tricky. The idea is to have queue for each fan-in pattern. I.e. each time we have N senders sharing the same receiver - they need a shared queue. Their messages needs to be serialized.
Intermediate Connections Handling (Fixing Correctness)
As soon as we got rid of "goroutine per connection" we created a problem. Let's look at broadcast()
function
broadcast(msg) {
for r := range receivers {
r <- msg
}
}
The problem is with this line r <- msg
- who gonna receive it?
It's not a problem if we have some runtime function that reads from this port but what if this it's intermediate connection_?
By "intermediate" connection I mean connection that is exist because there was a user-defined component.
Let's take a look at these 2 versions:
component Main(start) (stop) {
:start -> printer -> :stop
}
component Printer(data) (sig) {
nodes { Println }
:data -> println -> :sig
}
// VS
component Main(start) (stop) {
nodes { Println }
:start -> println -> :stop
}
They are equal by functionality but the first one gonna have more ports and connections (channels and gorotuines) - more message passing (more synchronization). Which is bad BTW.
This could be solved by Optimization step (whether that source-code lvl optimizer or IR optimizer, doesn't matter). However, we don't have optimizer how and it's not clear whether any program could be optimized up to the point where it doesn't have "intermediate connections".
So, the thing is after rewriting runtime will handle later but not the first. Because we don't have goroutine that could transfer our message from printer:data -> println:data
more. So nobody reads from printer/in:data[0]
these days. We gonna block. And no buffer will help us.
Solution
There's 2 ways to solve it
- implement optimizer that would get rid of all intermediate connections
- support intermediate connections at the level of runtime
The answer is... We need both! And we need to start from the second one.
The reason is that optimisation should be optimisation_. We should not (probably) think of slow programs as of incorrect ones (even tho I personally would love to).
Second, it's not clear whether we can optimize any program, as been said, this way. Is any program could be 100% inlined into one giant Main
? I'm not sure (even tho I personally would love to!).
So we need to support this. How?
connect(prog) {
for item := range q {
broadcast(item, prog)
}
}
broadcast(item, prog) {
finalReceivers := getFinalReceivers(item, prog)
for finalReceiver := range finalReceivers {
finalReceiver <- item.Msg
}
}
I didn't describe getFinalReceivers
but you get the idea. We need to traverse the graph until the leaf. Which is a runtime function.
As an optimisation for this instead of could make runtime remember addr of the leaf once it found so we don't have to do it all the time on each msg.
That... feels like that optimization we talked about before right? I know it's weird. But I feel like runtime should be able to work with this. We should not just push it fully onto compiler's shoulders. Why? Debugging
A note on -debug
(and tracing)
I think we should log events each time we "unwrap" intermediate step. Ofc it's weird to log all 3 levels sequentially but what can we do? Yep it's gonna be sent, pending, received
even tho nothing actually happened.
This also related to #347 and #94
Other option could ofc not to log them and be ready that you won't see the whole picture in logs. This feels bad and especially for message traces that going to be implemented someday.
Other Option
Other option would be to append message back to the queue (to the tail) but with different receiver. That could be either final one (leaf/runtimeFunc) or just one next level. However there's not much sense in that. We gonna do >=1 extra sending to queue ->chan
and that's less performant.
Log/trace thing feels like more sense if we send to q chan but why? I don't know.
from neva.
IRGen
generates intermediate-step-less programs
This is improvement of #644 (comment)
- We wanna do as less as possible at runtime
- We ready to do as much as possible at compiler
- We need be able to easily debug our programs
How can we have all three? Ok look
Do not find leafs at Runtime
Find them at compile time. Probably that would be irgen
but I'm not sure. IR Connection gonna me smt like
type Connection struct {
Sender PortAddr
Receiver []Receiver
}
type ReceiverSide struct {
PortAddr PortAddr // final
Transit []PortAddr // intermediate (just to log)
}
This way we don't have to traverse the graph at runtime (even at first sending to remember it for later) but still have metadata we need to do the even listener calls we need
from neva.
Maybe this could be simpler if IR would have hierarchy (runtime can still work with flat struct tho)
{
ports: {
in: {
start: { slots: 1, buf: 0 },
},
out: {
stop: { slots: 1, buf: 0 },
},
},
connections: [":start -> printer:data", "printer:data -> :stop"],
nodes: {
printer: {
ports: {
in: { data: { slots: 1, buf: 0 } },
out: { sig: { slots: 1, buf: 0 } },
},
connections: [":start -> println:data", "println:data -> :stop"],
nodes: {
println: {
ports: {
in: { start: 1 },
out: { stop: 1 },
},
func: {
ref: "println",
cfgMsg: null,
},
connections: null,
},
},
},
},
}
from neva.
Related Issues (20)
- Inconsistent output inside `For` with branching HOT 7
- Match allows array-port overwrite HOT 1
- Consistent naming for boolean components
- Alternative syntax for outports (network nesting) HOT 4
- `Zip` component HOT 2
- Iter should support strings HOT 3
- Force Outport Operator HOT 3
- Data processing components out of the box
- `Find` component HOT 1
- `Has` component HOT 2
- `Collate` component
- Reduce noise when using ports by replacing `:` with `.` HOT 1
- HTTP Client
- Improve struct field selectors syntax
- Move println to io HOT 6
- Reduce as higher order component for binary handlers HOT 1
- Move Lock to sync
- Alternative `nodes` syntax HOT 1
- `os.Args` has no inports
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from neva.