Thanks for those answers, Henry.
With regards to point 3., I find it hard to see how the example on the T.
vocabulary page works, I don't understand it (also because there is a
sequence described, but no actual code). What I am currently missing is
having a way of using non-throw-away tasks, that can be supplied with new
data, can return data and continue working afterwards. An example I had in
mind when writing the remark you responded to, could be written like this
in Lua (note, coroutines are actually not parallel in Lua, but I don't
think that's a conceptual problem; yield transfers control to the function
calling resume, and allows passing results; resume does the opposite):
co = coroutine.create(
function(a,b)
print("co got initial arguments",a,b)
for k=1,3 do
local res = a+b
print("co sends",res)
a,b = coroutine.yield(res)
print("co received",a,b)
end
print"last iteration"
return 100*(a+b)
end
)
print"created coroutine"
print("first resume", coroutine.resume(co,1,2))
print("second resume", coroutine.resume(co,2,3))
print("third resume", coroutine.resume(co,3,4))
print("fourth resume", coroutine.resume(co,4,5))
print("fifth resume", coroutine.resume(co,5,6))
I think it's fairly readable without knowing the intricacies of Lua. It
would return the output below:
created coroutine
co got initial arguments 1 2
co sends 3
first resume true 3
co received 2 3
co sends 5
second resume true 5
co received 3 4
co sends 7
third resume true 7
co received 4 5
last iteration
fourth resume true 900
fifth resume false cannot resume dead coroutine
I tried imagining how to write it with the 5, 6 and 10-14 T. but couldn't
figure it out, and certainly not in a way that is user-friendly. At best it
would require locales, or updating random global variables, and it would be
far from user-friendly.
I could imagine an interface to behaviour as in Lua implemented in J as
follows (note, not an expert language implementer, just a user):
Coroutines in this J concept described below are just tasks running on
threads.
Tasks containing y. are coroutines (y. for yield).
y. takes its y argument, and puts those arguments in the pyx that is
returned when the verb resulting from u t. '' (referred to as
"corresponding verb" below) is called, and blocks the coroutine until
resumed.
A coroutine is resumed when its corresponding verb is called, which also
passes the new arguments to the coroutine as result of the call to y. .
t. could be extended to the following cases: add possibility to give t. an
array of gerund as left argument, starting a plurality of tasks and
returning a gerund of verbs for accessing them. n can be a literal for
options one might have in mind ('' for now). Boxes can be used if: options
are needed for multiple threads, or in case options and thread numbers are
combined. If u/m does not have the same length (#) as n, it should throw a
length error.
The corresponding verb for each task returns a pyx for each task, filled
with either results returned, or in case of coroutines resulting from a
call to y. . For instance, c0`c1`c2"0 i. 3 3 passes 0 1 2 to c0, 4 5 6 to
c1 and 7 8 9 to c2, returning 3 pyxes that will contain the results
yielded/returned by c0, c1 and c2.
Another adverb/conjunction could be used to check threads being resumable
based on their corresponding verb (e.g. t: ; if T. were a
conjunction/adverb it could as well be a case of T. when called with a verb
as left argument): e.g. 0 dead (task not running or not containing y.); 1
waiting for input (yielded) (perhaps to be extended to other statuses, e.g.
idle, running, which could be interesting for other purposes, I guess.
If implemented as such, it could provide for a lot of interesting patterns
I think:
- generators/iterators, especially if iterators would be allowed in e.g.
for/while loops instead of arrays, e.g. like
(gen =: genverb t '') initial_args
for_k. gen do. ... would continue calling the generated coroutine (e.g.
with default arg '') until it is dead, or only once when the verb did not
yield, and just returned normally. See also the last example below.
- scatter/gather operations where the verb's state could be kept from
previous iterations.
This would also render it easy to communicate in two directions with
running tasks, as well as allow easy translation from other languages
having these constructs. The Lua case points out coroutines can also be a
useful abstraction when running in a single thread (as in Lua is single
threaded, and coroutines are just an abstraction, see e.g.
https://www.lua.org/pil/9.3.html).
With the above interface, this Lua example above could as follows
0 T. '' NB. create thread 1
co_fun =: {{
'a b'=. y NB. received from the creating thread when first calling the
verb resulting from v t. ''
echo 'co got initial arguments ', ": a,b
for. i. 3 do.
res=. a + b
echo 'co sends ',":res
'a b' =. y. res NB. blocks, so no pyxes needed
echo 'co received ',": a,b
end.
echo 'last iteration'
100*a+b
}}
NB. the example here would print about the same as the Lua version:
co=: co_fun t. '' NB. create new task (in this case,coroutine, since it
calls y.), co is a the corresponding verb
echo 'created coroutine'
echo 'first resume ', > co 1 2 NB. corresponds to initially starting
co_fun, setting the y argument.
echo 'second resume ', > co 2 3
echo 'third resume ', > co 3 4
echo 'fourth resume ', > co 4 5
echo 'fifth resume ', > co 5 6 NB. opening pyx signals domain error?
resuming a dead coroutine is impossible.
NB. Another example using t: for checking coroutine c is still alive (1) or
dead (0):
co =. co_fun t. ''
NB. as long as co is alive, resume it
(1, >@co)^:(co t:)^:(_) 1 2
NB. would print:
NB. co got initial arguments 1 2
NB. co sends 3
NB. co received 1 3
NB. co sends 4
NB. co received 1 4
NB. co sends 5
NB. co received 1 6
NB. last iteration
NB. 1 700 NB. return value, not printed.
A last example loops over different permutations without having to
pre-calculate all (mildly adapted from section 9.3 of the Lua book linked
above):
permgen = {{ NB. takes a, n as inputs
'a nn'=.y
if. nn = 0 do. y. a else.
for_i. i. nn do.
a =. (a {~ i,nn) (nn,i)} a NB. swap index i and n
permgen a;<:nn NB. generate all permutations of the other
elements
a =. (a {~ i,nn) (nn,i)} a NB. swap back
end.
end.
}}
perm =: {{ NB. adverb creating a verb corresponding to the permgen
coroutine, created with initial arguments m and #m
co =. permgen t. ''
co (;#) m
co
}}
NB. now the following, with a for loop adapted to allow verbs being passed
to be called with '' until c t: is 0.
for_p. 'abc' perm do.
echo p
end.
NB. would, if I did everything correctly, print:
bca
cba
cab
acb
bac
abc
I hope that I didn't bore people to death and that I did not make any
reasoning errors, it's hard to verify if it's not executable. One thing
that could be an issue is that if the returned pyxes are not opened before
the coroutine is called again, you could have multiple pyxes waiting before
previous ones are opened. I don't know whether this could lead to
troubles...
Main advantage of the above proposal I see is that it would make it very
easy to translate generator/iterator patterns from other languages (e.g.
Python, Lua), thereby lowering the entry threshold for people acquainted
with such language. I think that as these multi-tasking primitives are
introduced now, providing low-level control is good, but it would be
beneficial if they were also general and easy to use in common cases.
Let me know what you think. Anyhow, I had fun with this little thought
experiment.
Jan-Pieter.
Op wo 27 apr. 2022 om 16:47 schreef Henry Rich <[email protected]>:
> 0. Space accounting is wrong in beta-b when memory is allocated in a
> task and freed in the master. This will be fixed in beta-c.
>
> 1. Yes, if you write > u t. '' y it will block immediately.
>
> 2. You started a task and then lost interest in the result. I guess we
> will need a way to terminate a task but I don't see that it needs to be
> automatic.
>
> 3. beta-c has new T.-verbs that allow you to create semaphores. This
> would do what you are describing. More verbs will certainly be needed
> (mutexes, for example) and we welcome suggestions.
>
> 4. Globals should 'work' in that when you read a global that is being
> modified in another thread you will get either the old or the new value;
> same for files and mapped files. wd may have problems. Without
> synchronization primitives that's not enough for useful work. There was
> a synchronization error in beta-b (that took several days to find), to
> be fixed in beta-c.
>
> Henry Rich
>
>
>
> On 4/27/2022 10:28 AM, Jan-Pieter Jacobs wrote:
> > Hi there,
> >
> > I finally managed to find an example where the parallel processing made a
> > measurable improvement (that is, previously, I did not find verbs where
> the
> > overhead was less than the computational improvement).
> > Doing so, I also wrote some cover verbs that some might find useful. Note
> > that these leave chunking up the input to the user, opposed to the verbs
> > Elijah Stone recently posted.
> >
> > startpool =: (0 T. ''"_)^:] NB. starts a thread pool of y threads
> > peach =: (t.'')(&>) NB. parallel version of each; still looking for
> an
> > apricot verb.
> > pevery =: (t.'')(&>)(>@:) NB. parallel version of every (note, @:, not @
> > for speed improvement)
> >
> > For instance:
> > startpool 8 NB. start 8 threads (note, I have a core i5 with 2
> physical
> > cores, 4 virtual ones).
> > 8
> > in =: <"2]30 300 300 ?@$100 NB. 30 boxed matrices
> > NB. calculating determinants
> > 10 timespacex 'outseq =: -/ .* every in' NB. normal every
> > 1.22102 3.14651e7
> > 10 timespacex 'outpar =: -/ .* pevery in' NB. parallel version
> > 0.578477 3.1583e6
> > outseq -: outpar
> > 1
> > 10 timespacex 'outseq =: -/ .* each in' NB. normal each
> > 1.21831 3.14669e7
> > 10 timespacex 'outpar =: -/ .* peach in' NB. cheating, due to
> > asynchronous threads.
> > 0.555217 4.20666e6
> > outseq -: outpar
> > 1
> > NB. inverting 30 matrices
> > 10 timespacex 'outseq =: %. every in'
> > 0.526015 3.90624e7
> > 10 timespacex 'outpar =: %. pevery in'
> > 0.30344 4.30001e7
> > outseq -: outpar
> > 1
> >
> > A few things I noted:
> > 0. Why does "-/ .* pevery" consume 10 times less memory than "-/ .*
> every"?
> > It is not the case with %. .
> >
> > 1. Note that in the definition of pevery, using @: instead of @ is
> > necessary for better performance. Otherwise, it appears that the created
> > pyxes are immediately opened: For instance "%. pevery" generates as verb
> >> @:(%. t.''&>), in which the part in parenthesis has verb rank 0 0 0.
> Using
> >> @ would execute > on each pyx individually, which apparently in the
> > current is immediately after its creation. This causes the master to
> block,
> > and effectively execute all calls sequentially (if I understood
> correctly).
> > I don't know whether this is considered an implementation detail not
> > specified in the specification of the parsing, but it's important to know
> > in this case.
> >
> > 2. What happens with busy threads whose pyxes are no longer accessible?
> > Should they be terminated, i.e. in the spirit of garbage collection of
> > unreachable values? Perhaps they could, only if they can be assured not
> to
> > have side effects (e.g. do not have explicit components in the verb
> that's
> > being executed that could cause side effects, or perhaps some foreigns,
> > e.g. file operations, or perhaps there could be an option to t. letting
> the
> > user "promise" the supplied verb does not have side-effects).
> >
> > 3. Would it make sense to have threads that can return values multiple
> > times? I'd think of generators and iterators that could be more easily
> > written, or perhaps used as in Lua's coroutines (
> > https://www.lua.org/manual/5.3/manual.html#2.6) which, albeit not being
> > parallel, allow the user to resume a coroutine, and the function to yield
> > values, continuing after the resume where it left off. Now this is
> possible
> > only using locales containing some state, jumping around the next
> function
> > using goto., which feels more clumsy than it should (for an example, see
> > the classes "permutations" and "altflipsgen" in my fannkuch
> implementation
> > here: http://www.jsoftware.com/pipermail/beta/2021-September/010048.html
> ).
> > I think this could be integrated with the pyx concept, where successive
> > openings of a pyx could be equivalent to successive "resume" (or "next")
> > calls. This would however make the content of a pyx a read-only-once
> value,
> > that is changed by the parallely executing thread after it is opened the
> > first time. This would also need a primitive (and/or control word for
> > explicit definitions) for yielding a value to the calling/opening thread.
> > This way, it would be impossible to pass values to the thread when
> resuming
> > though.
> > Another way of implementing this without modifying the pyxes' behaviour
> and
> > allowing passing new values to the thread, would be to have a separate
> > "resume" verb that can be called on a thread number. Perhaps this does
> not
> > even have to be integrated with the true concurrency, so that it could as
> > well be used as a conceptual abstraction (as in Lua, see the link above)
> on
> > systems not supporting true multi-threading (as appears to be the case
> for
> > 32 bit J at the moment).
> > Aside from allowing implementation of generators and whatnots, it would
> > also allow making specific threads dedicated to executing a specific verb
> > repetitively, on different data, which might (or not, I'm far from
> expert)
> > be more efficient as it could keep in memory the routine it is executing.
> >
> > 4. Did anyone try to combine this new threading model with
> reading/writing
> > globals (or even more fun, memory mapped files)? With the C FFI, or the
> wd
> > subsystem?
> >
> > Just my 5 cents.
> >
> > Jan-Pieter
> > ----------------------------------------------------------------------
> > For information about J forums see http://www.jsoftware.com/forums.htm
>
>
> --
> This email has been checked for viruses by AVG.
> https://www.avg.com
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
