NYCJUG/2022-07-12
Beginner's Regatta
Shifty Language
The meaning of J's "shift" verb |., used dyadically, might be stated the direction of dyadic shift is: positive numbers shift toward the lowest index along the axis corresponding to each shift amount. Some examples should clarify this.
1|.5 NB. Scalar: no leading axis 5 1|.i.3 NB. Rank 1: shift toward the 0 in 0 1 2 1 2 0 1|.i.3 3 NB. Rank 2: shift toward the 0 on dimension 0, i.e. shift rows 3 4 5 6 7 8 0 1 2 1|.i.3 3 3 NB. Rank 3: shift toward 0 on dimension 0, i.e. shift planes 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 0 1 2 3 4 5 6 7 8
The question came up in the meeting about how we shift some rows of a matrix but not others. It looks like the rank conjunction is need to do this. So, to shift row 0 by 1, row 1 by nothing, and row 2 by 2, we could do this.
1 0 2|."(0 1) i. 3 3 1 2 0 3 4 5 8 6 7
Continuing in this vein of multiple items in the left argument, let's see how we shift different dimensions variably.
1 2|.i.3 3 NB. shift 1 on dim 0, 2 on dim 1, i.e. shift by 1 row and 2 columns 5 3 4 8 6 7 2 0 1
Show and Tell
Multi-threaded Photo Flipping
Continuing to work on using multi-threading to run multiple processes in parallel, we've run into some hard-to-debug issues with the code.
Both the following variants rely on two global variables: MUTEX which is an instantiation of the mutual exclusion mechanism and FLS which is a list of file names in the current directory.
Common Set-up
The set-up for both methods looks something like this:
require '~Code/flipPhotoFns.ijs' NB. Multi-threaded photo flipping routines.
require 'photos'
info,<6!:2 'info=: getFrom1Drive ''F:\''' NB. Move pix from SD card mounted as F: drive
svdir=. 1!:43'' [ dd=. '/',~}.@:}:>{.info NB. "dd" is the target directory of photos.
FLS=: 0{"1 dir '*.jpg' [ 1!:44 ] dd NB. Move to target directory and get list of photo files.
createThreads 12 NB. Create more threads than we will need.
NB. MUTEX=: 10 T. 1 NB. Recursive mutex
MUTEX=: 10 T. 0 NB. Fast mutex
The documentation on the two types of mutex is somewhat confusing. The table entry for 11 t. says
The behavior when a mutex-owner requests a lock on the mutex it owns depends on the type of mutex: a fast mutex will never get the lock, while a shared mutex will return immediately with the lock.
It's not clear why one would ever use the fast mutex if it never gets a lock. However, most of my experimentation is with the fast version and it seems to allow us to coordinate each thread working only on its own, single file as we can see in the "original" code below.
Original Method
Our original method uses this function
flipNextPhoto=: 3 : 0
assert. *./nameExists &> 'MUTEX';'FLS' NB. Need these 2 globals
tn=. ' '-.~":3 T. '' [ tm=. 6!:1'' NB. Thread number "tn"; session start time "tm"
while. 0<#FLS do.
myFl=. 'ThisFL',tn [ 11 T. MUTEX NB. Lock mutex
nms=. myFl,' FLS' NB. Name file on which we work and the list
(nms)=: split FLS NB. Take 1 filename from list
13 T. MUTEX NB. Unlock mutex
if. 0~:#>".myFl do. flipPhotoByOrientation >".myFl end.
end.
(": (],~{.-}.)(6!:1''),tm) fappend 'Timing',tn,'_',(([: ": {.) , [: ; 2 lead0s }.) qts''
NB.EG flipNextPhoto t. '']0 [ flipNextPhoto t. '']1 NB. Start two threads.
)
The example at the end of the code shows how to run two threads; the arguments "0" and "1" are not used but distinguish the two invocations.
We used this code to compare timings of the multi-threading method to the existing method that spins off multiple processes.
usus ".&>(]{.~' 'i.~])&.>fread&.> 0{"1 dir 'Timing*_20220511*'
399.837 402.824 401.5 1.0407
usus ".&>(<' in ';' seconds ') fromBtw &.> tms0 NB. Timings for parallel processes instead of threads
376.818 489.863 442.142 31.7494
The two sets of four numbers denote the minimum, maximum, mean, and standard deviation of the timings for each of the separate processes or threads, respectively. We see that the multi-threading approach seems to be slightly faster on average, averaging 401.5 seconds per thread as opposed to 442.142 seconds per process. However, perhaps the more important improvement is the standard deviation of the timings which goes from almost 32 seconds for the parallel processes down to slightly over one second for parallel threads.
In fact the multi-process approach is only as fast as the slowest process which took 489.863 seconds in this example, about 20% slower than the multi-threaded version. This is due to differences in allocating the work. The multi-process approach divides the files between the processes in advance whereas the threading approach has each thread take only one file at a time.
Newer Approach
One occasional problem with the original threading approach is that it sometimes freezes up, forcing us to kill the main J process. It looks like this is some sort of exit problem as it looks like all the work has been done but something keeps the routine from finishing cleanly.
This led us to try a slightly different approach as seen here:
NB.* flip1Photo: flip a single photo.
flip1Photo=: 3 : 0
assert. *./nameExists &> 'MUTEX';'FLS' NB. Need these 2 globals: FLS=: 0{"1 dir '*.jpg' [ MUTEX=: 10 T. 0 NB. Fast mutex
tntxt=. ' '-.~":tn=. 3 T. '' [ tm=. 6!:1'' NB. Current thread number is "tn". "tm" is session start time.
if. 0<#FLS do.
myFl=. 'ThisFL',tntxt [ 11 T. MUTEX NB. Lock mutex
(nms)=: split FLS [ nms=. myFl,' FLS' NB. Take 1 filename from list
13 T. MUTEX NB. Unlock mutex
if. 0~:#>".myFl do. flipPhotoByOrientation >".myFl end.
end.
tn,(6!:1''),tm NB. Thread #, end, start session time.
NB.EG flip1Photo t. '']0
)
NB.* flip6: flip 6 photos in parallel on 6 different threads.
flip6=: 3 : 0
tms=. i.0
while. y<#FLS do.
pyx0=. flip1Photo t. '']0 [ pyx1=. flip1Photo t. '']1 [ pyx2=. flip1Photo t. '']2
pyx3=. flip1Photo t. '']3 [ pyx4=. flip1Photo t. '']4 [ pyx5=. flip1Photo t. '']5
tms=. tms,-/&>_2{.&.>pyx0,pyx1,pyx2,pyx3,pyx4,pyx5 NB. Accumulate timings
end.
)
This restricts us to only six threads in this instance by making explicit the number of invocations of flip1Photo. It remains to be seen if this method is more robust as we have not tested it as much as we have tested the other method. There may be a practical restriction on the number of threads that this avoids but we will have to run it more to see if this helps.
Puzzling Pyxs
We see in the code above that we are assigning the results of each of our six threads to local variables "pyxn" but we do nothing with the results. This is because I do not understand how these are supposed to work and what they do for us.
This underlines the basic problem with the multi-threading primitives: a lack of examples. With any luck, we have begun to address that lack here and in our other meetings where we discussed multi-threading, so we will keep everyone informed as we figure out more.
Watch this space!
You Must be this Tall to Write Multi-threaded Code
This essay gives a number of reasons why multi-threaded code is so hard to write, mainly because
Races are endemic to most large software projects because the traditional synchronization primitives are inadequate for large-scale systems. ... That is to say, safe and scalable parallelism is achievable by minimizing or eliminating concurrent access to shared mutable state.
In this approach, threads own their data, and communicate with message-passing. This is easier said than done, because the language constructs, primitives, and design patterns for building system software this way are still in their infancy.
It's not clear we have this capability in J yet. In fact, it looks like we must program it in at present.
Advanced J
Avoiding Duplicate Execution
We saw this query on the J forum recently.
From: Brian Schott <schott.brian@gmail.com> Date: Sun, May 29, 2022 at 5:42 PM Subject: [Jprogramming] Composite Item (m}y) with gerund m To: Programming forum <programming@jsoftware.com>
I have a problem similar to the one shown below.
Both the verbs g and h depend on calculating f first so this seems like an inefficient way of doing it where f produces only nonnegative integers from its argument.
Is there a better approach?
g=:,:f h=:*@f f=: 3&| NB. not the real f, but f is more compute heavy 3 : '(h y)}g y' i.10 NB. an example calculation 0 1 2 3 1 2 6 1 2 9 ]`h`g } i. 10 NB. another "tacit" calculation 0 1 2 3 1 2 6 1 2 9-- (B=) <-----my sig
Brian Schott
There was this initial response suggesting an in-line construct.
From: Elijah Stone <elronnd@elronnd.net> Date: Sun, May 29, 2022 at 6:08 PM Subject: Re: [Jprogramming] Composite Item (m}y) with gerund m
I would use a fork, and 'bind' the left argument to the result of f. There is a difficulty, because you can't compose adverbs with verbs. Perhaps something like this:
c=. (*@] {{x}y}} ,:) f c i.10 0 1 2 3 1 2 6 1 2 9You can get rid of the explicit definition using boxes, if you really care to, but I would not.
-E
Looking at this expression, I was initially confused by all the curly braces but then figured out that the internal right-curly was the insertion as shown in Brian's example. This is case where a couple of extraneous spaces could help clarify the code:
c=. (*@] {{ x}y }} ,:) f
Then there was this suggestion from Jan-Pieter Jacobs.
From: Jan-Pieter Jacobs <janpieter.jacobs@gmail.com> Date: Mon, May 30, 2022 at 5:48 AM
I had some fun learning modifier trains recently (might post about my experiences later) and I came up with this adverb, based on Brian's second approach (no clue how to name it as I didn't bother understanding its purpose):
adv=: ]: (]`(*@)`(,:([.].))}) 3&| adv ]`(*@(3&|))`(,: 3&|)} 3&| adv i. 10 0 1 2 3 1 2 6 1 2 9Jan-Pieter
Finally, Rob suggested that Elijah's approach is like that of the K language (kdb+).
From: 'Rob Hodgkinson' via Programming <programming@jsoftware.com> Date: Mon, May 30, 2022 at 8:30 PM
Ditto Elijah, very nice indeed.
FYI I have not seen this done so neatly in J before now, and there is a striking resemblance to that used in Kx (kdb+) via the “vector conditional construct”, described here:
https://code.kx.com/q/ref/vector-conditional/
A K Equivalent?
Looking at this K documentation, I'm not sure his analogy is accurate.
? Vector Conditional
Replace selected items of one list with corresponding items of another?[x;y;z]Where
- x is a boolean vector
- y and z are lists of the same type
- x, y, and z conform
returns a new list by replacing elements of y with the elements of z when x is false.
All three arguments are evaluated.
q)?[11001b;1 2 3 4 5;10 20 30 40 50] 1 2 30 40 5If x, y, or z are atomic, they are repeated.
q)?[11001b;1;10 20 30 40 50] 1 1 30 40 1 q)?[11001b;1 2 3 4 5;99] 1 2 99 99 5Since V2.7 2010.10.07 ?[x;y;z] works for atoms too.
Vector Conditional can be used in qSQL queries, which do not support Cond.
Learning and Teaching J
We have this general suggestion from Knuth for approaching problems by anthropomorphizing them:
Another aspect of role playing is considerably more important: We can often make advances by anthropomorphizing a problem, by saying that certain of its aspects are "bad guys" and others are "good guys," or that parts of a system are "talking to each other.
This approach is helpful because our language has lots of words for human relationships, so we can bring more machinery to bear on what we're thinking about.
Thinking in an Array Language
In this essay about the K language, we are shown an example of converting very loopy code for matrix multiplication into an array-oriented version.
The pseudo-code version of the scalar, looping code is taken from a wikipedia article:
Input: matrices A and B
Let C be a new matrix of the appropriate size
For i from 1 to n:
For j from 1 to p:
Let sum = 0
For k from 1 to m:
Set sum ← sum + Aik × Bkj
Set Cij ← sum
Return C
Starting with this direct translation of the pseudo-code into K gives us this code which the author says is "the worst K code I've ever written":
matmul: {
A::x
B::y
n::#A
m::#*A
p::#*B
C::(n;p)#0
i::0
j::0
k::0
sum::0
{
i::x
{
j::x
sum::0
{
k::x
sum::sum+A[i;k]*B[k;j]
}'!m
C[i;j]::sum
}'!p
}'!n
C}
By fixing the original code by replacing sections of it with array operations, we eventually arrive at an array-oriented version of the above in idiomatic K:
matmul: {x{+/x*y}/:\:+y}