select is not blocking

[Ambrevar]

The current implementation of the select statement is not blocking, which means that if no channel is ready it will loop actively until a channel unlocks, which hogs a CPU for the duration of the wait. I believe this makes select rarely useful in practice.

The select definition has this comment:

  ;; TODO true blocking select. a plan:
  ;; you basically have another channel behind each select clause
  ;; the process executing the select blocks on receiving from that channel,
  ;; and possible select clauses send some indication when they're ready

Has anyone got the chance to work on it?

Besides, would it be possible to have select return a value? This would be more Lispy in my opinion.

[adlai]

The current implementation of the select statement is not blocking, which means that if no channel is ready it will loop actively until a channel unlocks, which hogs a CPU for the duration of the wait. I believe this makes select rarely useful in practice.

The select definition has this comment:

  ;; TODO true blocking select. a plan:
  ;; you basically have another channel behind each select clause
  ;; the process executing the select blocks on receiving from that channel,
  ;; and possible select clauses send some indication when they're ready

Has anyone got the chance to work on it?

What I recall from ten years ago, is that when @zkat and I wanted to implement the non-blocking version, it was not obvious how do to to do without introducing additional complexity to the send and recv methods, which to my taste are already tanged enough. I do, however, have time available these days, although I am no further along in this specific issue than I was ten years ago.

Besides, would it be possible to have select return a value? This would be more Lispy in my opinion.

Any specific value, or just whatever values the last form in the executed clause returned?

[Ambrevar]

What I recall from ten years ago, is that when @zkat and I wanted to implement the non-blocking version, it was not obvious how do to to do without introducing additional complexity to the `send` and `recv` methods, which to my taste are already tanged enough. I do, however, have time available these days, although I am no further along in this specific issue than I was ten years ago.

That's fantastic!

Any specific value, or just whatever values the last form in the executed clause returned?

I think the most intuitive return value is that of the last form.

[adlai]

That's fantastic!

No, it isn't. Do you have any idea of the product of how much time it'll take to implement, multiplied by a reasonably inoffensive salary?

hint: one is nearly infinite, and the other is quite low, since my current salary is zero

[Ambrevar]

I'm confused, I didn't mean to offend, sorry if I did.
I'm happy to help if there is anything I can do.

[adlai]

I'm confused, I didn't mean to offend, sorry if I did.

None taken! However, the repository is not under active development, and I am hesitant to leave open GitHub Issues that are already referenced in the code itself.

I'm happy to help if there is anything I can do.

OK, definitely... you do seem to have a bit of experience, with Lisp specifically and programming in general!

What algorithm(s) do you suggest for a blocking implementation?

[Ambrevar]

I haven't looked at the ChanL code (yet) and I have never implemented CSP, so I'll give it my best guess for now and read about it later: - Add a "select-listeners" slot to channels. - When SELECT is run and no channel is read, add a listener (e.g. a message queue) to all channels it wraps. Finally wait on the listener. - Modify RECV and SEND to wake up the first listener from the "select-listeners" channel slot right before/after receiving/sending. The awake SELECT receives the channel object from the listener and thus knows which branch to execute. If there is nothing to read/send (e.g. channel was consumed by another party in the meantime), wait on the listener again. Maybe we can look at Clojure's core.async. Maybe Racket has an implementation? If you have resources on CSP implementations, please share them I'll give it a read. Cheers!

[adlai]

Your hypothetical algorithm has a circularity!

In other undeterminism, I will respond inline to your
comments, with no specific preorder to replies.
Narrow columns make it easier to prioritize these
responses according to the highest resolution, and
I will thus adopt a similar absence of width; however,
please avoid splitting paragraphs and sentences.

To demonstrate this, I have edited your suggestion,
replacing imprecisions with synonyms and code:

When SELECT is run and no message is received, add a task (e.g. a
(pexec (noise) (recv noise :blockp t))) to all queues it wraps.

Thank you for your curiosity, admission, guess, and most importantly,

I haven't looked at the ChanL code (yet) and I have never implemented
CSP, so I'll give it my best guess for now and read about it later:

good intentions; please feel free to ask questions, and when necessary,
consult the modification history and the associated comments.

As for happy help:

Maybe we can look at Clojure's core.async.
Maybe Racket has an implementation?

I am less familiar with the internals of the JVM,
so am hesitant to plunge headfirst into Clojure's
implementation under the bold assumption that
its multiprocessing primitives behave identically
to those synthesized by Bordeaux Threads,
rather than merely equivalently; as for Racket's:
a much more likely target for patent poaching.

If you have resources on CSP implementations,

I have no specific recommendations of any text
describing the precise semantics targeted by the
original authors; the current artifact is orphanwa
re, no more maintained than suffices for the des

please share them I'll give it a read.

The current maintainer recommends that you,
instead of fixing compliance to an incomplete
specification, consult the standards document
linked from the comment introducing "actors",
the file of undocumented code.

[adlai]

If you feel up to floating a contracting proposal,
either personally or on behalf of your consultancy:

I am unlikely to fund pure research, although am
mildly likely to compensate implementation of a
specific algorithm, and am highly likely to pay for
only documentation of rationale for its choice.

[Ambrevar]

**Your hypothetical algorithm has a circularity!**

Do you mean because SELECT would invoke recv / send, which would again send a message to the listeners? If so, this limitation can be easily overcome by having a lower-level recv / send that does not send messages to the listeners.

I am less familiar with the internals of the JVM, so am hesitant to plunge headfirst into Clojure's implementation under the bold assumption that its multiprocessing primitives behave identically to those synthesized by Bordeaux Threads, rather than merely equivalently;

core.async being in Java (isn't it?) it makes it less interesting to study indeed.

as for Racket's: a much more likely target for patent poaching.

Why? Racket is free software, why would it be different here?

The current maintainer recommends that you, instead of fixing compliance to an incomplete specification, consult the standards document linked from the [comment introducing "actors", the file of undocumented code](https://github.com/adlai/chanl/blob/master/src/actors.lisp#L5-L8).

This seems interesting, but are you saying that SELECT need not be fixed then?

[Ambrevar]

If you feel up to floating a contracting proposal, either personally or on behalf of your consultancy: I am unlikely to fund pure research, although am mildly likely to compensate implementation of a specific algorithm, and am highly likely to pay for only documentation of rationale for its choice.

Thanks for the offer. Why not! Do you want to discuss this here publicly or do you prefer to move this to a private discussion?

[adlai]

Thanks for the offer. Why not! Do you want to discuss this here
publicly or do you prefer to move this to a private discussion?

Discussion of the technical issue, including your estimate of how much work it requires, should be public. Discussion of payment can be private, and my email address can be found in the metadata file for the git-shortlog command.

[adlai]

Your hypothetical algorithm has a circularity!

Do you mean because SELECT would invoke recv / send, which would again send a message to the listeners? If so, this limitation can be easily overcome by having a lower-level recv / send that does not send messages to the listeners.

Yes; and the recursion should probably be resolved as you suggested, although my preference is to retain the same generic functions, and rely on method specifiers to recognize the base case. I'd appreciate confirmation from @zkat that this is a good solution, although that is not necessary.

I am less familiar with the internals of the JVM, so am hesitant to plunge headfirst into Clojure's implementation under the bold assumption that its multiprocessing primitives behave identically to those synthesized by Bordeaux Threads, rather than merely equivalently;

core.async being in Java (isn't it?) it makes it less interesting to study indeed.

as for Racket's: a much more likely target for patent poaching.

Why? Racket is free software, why would it be different here?

Free software can still be covered by defensive patents, precisely because of parallelism between patent infrastructures and innovators!

The current maintainer recommends that you, instead of fixing compliance to an incomplete specification, consult the standards document linked from the comment introducing "actors", the file of undocumented code.

This seems interesting, but are you saying that SELECT need not be fixed then?

Not at all! This is an important enhancement, and arguably even a critical issue.

[Ambrevar]

Adlai <[email protected]> writes:

> Why? Racket is free software, why would it be different here? Free software can still be covered by defensive patents, precisely because of parallelism between patent infrastructures and innovators!

Have you heard of any patents around Racket? I haven't, and as far as I know Racket is a very "free" community (as in freedom, and patent-free). I'm not sure where to look for this kind of information.

[adlai]

In response to adlai's:

Why? Racket is free software, why would it be different here? Free software can still be covered by defensive patents, precisely because of parallelism between patent infrastructures and innovators!

Ambrevar wrote:

Have you heard of any patents around Racket? I haven't, and as far as I know Racket is a very "free" community (as in freedom, and patent-free). I'm not sure where to look for this kind of information.

Neither have I. If you wish to study Racket's implementation as part of working on a commissionned task, then I suggest you focus primarily on the source code, and I will look over their licenses myself.

[Ambrevar]

Today I tested Calispel: http://www.thoughtcrime.us/software/calispel/
Turns out it has a blocking SELECT statement (called fair-alt).

@adlai Have you tried this package? Pros and cons between ChanL and Calispel?

[mdbergmann]

Just my 2 cents.

Turns out it has a blocking SELECT statement

Depending on how it is implemented a blocking thing can be more resource intensive.
(I had to find that out here: https://github.com/mdbergmann/cl-gserver)
Because when you put something to be computed into a queue, and don't care about returning a result to the caller, then that is very cheap. If you have to wait for a result you have to implement locking and need condition variables for sleep and wake-up.
If it should be asynchronous but still should return a result, then that is even more resource intensive.

[adlai]

Ambrevar asked:

@adlai Have you tried this package?

Calispel predates my involvement with Common Lisp in general, and this library in particular. I do not recall having studied Calispel in any level of detail, although I do remember it as being one of the existing libraries when this one was being written.

Pros and cons between ChanL and Calispel?

The original vision was for this library to be a single multiprocessing library. As you can see from Calispel's documentation, it does not attempt to offer threading, whereas this library does; however, this library never progressed to the point of implementing its own threading primitives, and currently just punts to the portability layer.

edit: Yes, I did not list pros and cons... how about: the other library has more dependencies than this one; whereas this one has more bugs

mdbergmann wrote:

Depending on how it is implemented a blocking thing can be more resource intensive.
[...]
If it should be asynchronous but still should return a result, then that is even more resource intensive.

Indeed, Calispel's documentation page reveals a rather significant design difference: it uses a global lock. This is a slight inefficiency on machines with few cores, although scales terribly, and I do have terribly ambitious goals for this library.

[Ambrevar]

Understood, thanks for your feedback!

[adlai]

Keeping this issue alive by documenting my thoughts, a few years down the road...

select is ChanL's Swiss Army Knife, and can be used in many different conformations. If the users need some call to block, then this should be doable without requiring extra machinery in the calling code.

The current implementation is difficult to read, due to it being a macro that builds code by reusing much of the original list structure, however the generated code is "in userspace"; i.e. select is implemented in terms of send and recv without calling any of the internal machinery directly. Several approaches are possible...

The simplest strategy can be implemented with a trivial layer on top of the current macro: accept a keyword argument :blockp <boolean> in the first form of each clause, like with the underlying send/recv functions; limit this to appearing in at most one clause, and not allowing both a blocking clause and a default clause. The implementation is then quite simple: the blocking clause is the default clause, after all others have failed.

More sophisticated approaches would allow blocking on multiple operations, using one or more helpers thread that monitor channel states and notify the blocked threads when there is a match between sender and receiver; and/or spawning threads that block for completing operations that optimistically went through simultaneously when multiple channels blocked together in one clause. The latter approach changes semantics slightly, as there could now be a situation where some sender thinks the receiving thread has begun work on the sent object, when all that happened is the object moved to some delivery handler; however, a well-designed application should not processing of a sent object to have completed, but only to have begun.

[adlai]

relevant to the idea described in my previous comment as "one or more helpers thread [sic]", is the following old comment lifted from zkat/memento-mori@acf7cf0 todo.org#work-stealing-task-queue

general idea of work stealing is good, but a bit more effort needs to be put into balancing the load across the scheduler threads. See https://groups.google.com/forum/?fromgroups#!topic/erlang-programming/0axWwyWq8Aw