The APL Orchard

Bubbler

06:09

Showcase: Manipulating indices instead of elements

Adám

08:52

@Bubbler With the rate at which you're producing challenges, maybe we can hire you to create problems for our contest?

xpqz

09:15

@ngn that's indeed a lot faster. Can you outline how it actually works?

ngn

~15m to finish my cooking and i'll be back

RGS

@Adám +← 1 but then no one will be able to solve the problems xD

ngn

09:33

@xpqz it's recursion, not too different from yours. i use a boolean mask for which dominoes are available and i have a lot of precomputed stuff.

Bubbler

@Adám It matters which degree of "hire" it is. I'd love to participate in creating problems, even for free, but I don't know if it's legally OK to earn money from somewhere other than the company I'm currently working for.

ngn

@xpqz e are the edges of the graph (the dominoes). s are their weights (sums of from+to). g is a representation of the graph - the i-th row is a boolean mask of which edges i can go to from vertex i. n is the number of vertices. the dfn accepts a vertex (i.e. connector) as ⍺ and a boolean mask of available edges as ⍵.

Bubbler

@RGS I have some ideas for not-that-hard ones too :)

xpqz

@ngn and u is a nxn matrix of 1s but 0 along the main diag?

ngn

@xpqz oops, i forgot that one. yes - the negation of a unit matrix

i'm not sure if it actually helps with performance

c is a boolean mask of candidates for the next step in the recursion. t is something temporary.

xpqz

09:43

So just when I start to think I'm getting the hang of this it's useful to get a reminder how far there is to go :) Thanks for the master class -- I'll spend some time on really understanding it.

ngn

@xpqz "master"? :) not really. i forgot to mention: ⎕io←0 as usual. and ≡¨ is a golfing trick to make a vector of 1s.

xpqz

10:00

Ok, I'm getting there. What does this mean:

↓⍵∧⍤1⊢c⌿u

Bubbler

Filter rows of u by boolean vector c, row-wise AND with ⍵ then wrap rows to nested vector. Sounds self-explanatory, even without context.

xpqz

So c is the graph connectivity, and u is an inverted identity matrix, so c⌿u simply ensures that we exclude the connected-to-self case.

/me talking to self

ngn

@xpqz yes (c is candidates)

we exclude the domino used in the current step from future steps

ngn

11:34

@xpqz the same in my k6-like language takes only ~600-700ms:

\t e:.''"/"\'0:"24.txt";u:~=#s:+/+e;g:e(|/=)\:/:!1+|//e;{0|/t+(-x-t:s c)o'y*/:u c:&y*g x}[0]e~'e

RGS

12:03

@Bubbler don't worry, tough challenges are also nice :D I can imagine it already, 2021 Dyalog APL competition is out. The one to solve a problem wins ehehe

Adám

12:18

Hehe, a list of unsolved APL problems…

IIRC, when Morten was a student, the professor gave a programming task known to be impossible. So Morten wrote a solution in APL, and then translated it to whatever they were using (COBOL or ALGOL or something). Professor refused to even have a look, knowing it couldn't be. Of course, Morten's solution was correct!

dzaima

@ngn was curious, converted to BQN, dzaima/BQN takes 1.6s (Dyalog is 1.4s)

ngn

@dzaima bqn - not bad!

it feels like dyalog should be able to beat me (ngn/k) here because of their bit bools, but i guess their interpretative overhead plays a big role too

or maybe i didn't optimize the apl enough. it's not a fair comparison anyway.

@dzaima can i see the bqn? i wouldn't be able to understand it but i'm curious

dzaima

got down to ~1s by generating less arrays and forcing more things to bit booleans

@ngn here

(i'm very surprised bit booleans help at all, i was even about to look into temporarily switching off their usage hoping for performance!)

ngn

12:34

@dzaima thanks. in some cases they help, in some they make things worse. for instance boolean and,or,xor.. on whole arrays are super fast but anything that must extract individual bits (e.g. indexing) is slow.

RGS

@Adám Gotta love those stories. Reminds of the story about how little Gauss computed +/i100

Marshall

@Bubbler I'm sure there's a loopless solution for this. Consider this computation, which gets the distance each left child has to travel to get to the left of its parent.

Subtracting the sum scan of that from the indices gives you new target indices that you can grade to move all the nodes by that distance, but it's flawed because the left child needs to also account for its own right children in the distance it moves (so you get subtrees interleaved).

dzaima

@dzaima (applying those same optimizations to APL gets dyalog down to ~1.2s)

Bubbler

@Adám @RGS Remotely relevant: The company asked me to pose some coding tasks to use in job interviews (for undergrads without working experience). I gave them two problems. Out of ~150 applicants, only two got perfect scores. ~100 failed to solve even one of them.

Adám

@Bubbler Seems like it was an effective way to filter out all but the best. Did you one of the two?

dzaima

12:48

performance of builtins there (1.6s total due to the timing taking time):
https://dzaima.github.io/paste/#0zZa/S8QwFMf3@yuyi/G9/Hp5oH/MYcXlDsU7xFEc5DxUFCo4ODgILo6O4h/Tv8S09dLWa4dOpmTIC0n48OWTpEV@W@SXfe1j5PjYOQ@TIr86ujg9E0KE3uF0NltUveXJcjoT80U9Pj0/rvtVFda8DOz3NXJ87Jy3kncv25AIT2jBlz1UJNEDkSkrIUACABqbAG@xeo/EiGyd4YqRnETlgGyLGJxOgHi3SdhoS7bONCTsHTFicrw7f3jrRBVIZh1am9f4FIxYPzbEZNlzJLaOoEusKAUj5n1GIEnjMBqxiTgB3v1e3nBLSO3RdU6cSsKIu/uGuPys@yWWDGAtR2KtWSdBvFpnLWLlN8QgneUgcdsJlcItcZB1EhYqElrNKp455dhhEu/GzWubWKOOCSN5haptcZX@/zvx3bVYNG@FJmdoq0qAOBsiRoIm8Vj9O/H107zX45IRHPvGCqurP40EPB60IsSqeasKq/KBHT9Hjo…

Adám

@Bubbler Missing word: "hire"

dzaima

@dzaima (as i expected, / is the slowest thing due to bit booleans being rather annoying)

Marshall

@dzaima Time to reveal the secrets of fast replicate by boolean then?

dzaima

@Marshall don't know what may you have in mind, but it'd probably be cool

Bubbler

@Adám I don't know, but it was for hiring many people at once, so I'm pretty sure the company hired both, at least.

Marshall

12:53

@dzaima The best general way I know is to work with indices. You'll generate byte-sized indices for 256 left argument elements at a time, then iterate through them to select from the corresponding 256-element chunk of the right argument. The indexing is branchless and scales with the length of the result, not the argument.

dzaima

@dzaima (also sum of all builtin times is 370ms, so much time is just executing overhead)

@Marshall i doubt generating the indices itself could be done fast enough

Marshall

@dzaima To generate indices, use a lookup table that goes from bytes to 8-byte index lists, and either popcount or another lookup table to get the sum of each byte. The table is 256×8 bytes: still pretty small.

The indices are generated into a buffer. For each left argument byte, get the indices and write them to the current index in the buffer. Then increment that index by the byte's sum. The next indices will overlap the 8 bytes written, with the actual indices kept and junk values at the end overwritten.

dzaima

@Marshall my bit booleans are long[]s, going to bytes from that would cost a lot

Marshall

@dzaima Can't you just shift right the same way you do to get individual bits out?

dzaima

@Marshall i don't have good experience with things like that being fast, but it may be. worth a try anyways

Marshall

13:00

The index generation step is typically a little faster, so I think it can tolerate a little inefficiency. I guess the question will be whether you can write eight bytes to a byte array at an arbitrary offset and have that compile to a single unaligned move.

dzaima

@Marshall that's all down to what System.arraycopy decides to do, which i have little control over (and i have also failed to get the jvm to give me assembly)

RGS

@Bubbler can you share those problems? :)

Bubbler

@RGS Maybe next year? I don't want to waste any potential competition problems :P

RGS

@Bubbler sure :p

@Bubbler btw what were the languages that the students being interviewed could use?

Bubbler

13:20

@RGS C and C++.

dzaima

13:43

@Marshall i assume you left out that after copying from the lookup table you have to add the current offset to the added elements?

Marshall

@dzaima Yeah, forgot about that bit. Easy if you can treat the bytes as a single 8-byte int, not easy otherwise.

Marshall

14:07

@Bubbler Aha! You just want to not reverse the initial index array, then move each index just after the current location of the index that's one greater, assuming that index is to its left (making it the leftmost child). 24 characters in BQN with little golfing.

dzaima

@Marshall golfed that to a horrible 19 chars

Marshall

@dzaima I have 18 as a train that I don't consider horrible.

Adám

CMC: Implement ⎕C. You can use 819⌶ but of course not ⎕C.

dzaima

@Marshall so i assume it contains parenthesis

Marshall

@dzaima Yes.

Adám

14:43

Good test data (remember to try monadic and with left arguments ¯3 ¯1 and 0): ,∘⊂/'Σσς'#'Ꮚꮚ'(⍪⍳2)'ẞß'42

dzaima

@Marshall no clue

Marshall

@dzaima The magic of the monadic ⊸. (⍋↕∘≠⌊⊢⊐1+⊢)⊸⊏∘⊐⊏⊣

What did you have? Yours probably translates directly to Dyalog Extended, but this requires a ⍨.

dzaima

@Marshall ⊣⊏˜⊐⊏˜·⍋↕∘≠∘⊐⌊⊐⊐1+⊐

i guess ⊣⊏˜(⍋↕∘≠∘⊐⌊⊐⊐1+⊐)⊏⊐ would probably be APLifiable

Marshall

@dzaima The first one should be as well if you just use ⍋∘⌊.

dzaima

right

Marshall

14:57

So two (untested) APL solutions are ⊣⊇⍨⍳⊇⍨⍳⍤≢⍤⍳⍋⍤⌊⍳⍳1+⍳ and (⍋⍳⍤≢⌊⊢⍳1+⊢)⍛⊇⍨⍤⍳⊇⊣.

user41805

@ngn thank you for updating this for 18.0

xpqz

15:20

Is there a way to find the first (l-r) occurring duplicated integer in a vector? Thus for

v←7 14 14 7

the answer is 14

Marshall

@xpqz Sounds like a task for Unique Mask.

xpqz

@Marshall indeed it does!

dzaima

15:32

@dzaima ..how many things that i tried failed because •RAND n⥊2 leaves garbage at the array's tail? (it's allowed to do that, it's the job of the array user to handle/clear/set the garbage to more preferable stuff)

and it's actually faster o.O

faster with no System.arraycopy and instead doing the copying and incrementing in the same loop

haha

Marshall

@dzaima If that's the case you're probably better off with the branchless bit-at-a-time version. There the idea is you copy every element from the argument to the result, but increment the current index afterwards only if it corresponds to a 1. You do have to either overallocate by 1 or shorten the length so the last bit of the left argument is a 1 ahead of time, though.

RGS

@xpqz check the last APL Cultivation; unique mask was covered and we did an exercise that was half way solving that task

dzaima

16:04

@Marshall ~700ns

~600ns by (properly) moving from x.get to values() earlier and regular indexing afterwards

Marshall

16:22

@dzaima I guess Java is doing something pretty smart with the copy/increment loop then. Or it's just faster than I would have thought. Either way, pretty cool.

dzaima

16:40

ah, a cause may be that i didn't actually complete the implementation (i.e. no handling of >256 items) and so only after filling the buffer i made the result array with the already known item amount. introducing precalculation of the result size brings it up to ~550ns

(yes, for some reason, summing Long.bitCount of 4 longs takes 100ns. ¯\_(ツ)_/¯)

@dzaima actually, a better reason would be that it doesn't need to check for out-of-bounds writes if the for loop end is the same as the array size

RGS

@Bubbler do you code in C/C++ at work?

dzaima

17:03

@dzaima seems System.arraycopy is slower than a manual loop for 8 items in general

currently my fastest working replicate is a version of index tables, storing the deltas in the buffer instead of indices (so no 256 item limit) with ~500ms for the 200 items, 4000ns for 2000 items

@dzaima (i haven't tried to get the original index table version working)

@dzaima (note that i'm pretty certain it's at least somewhat broken, and it creates a new buffer every time because it relies on the 0-initialization, so there's definitely stuff to improve)

@dzaima (actually no, it shouldn't be broken (at least not the way i thought it was))

PuercoPop

17:33

When I open a ride session again I can scroll up and see my past sessions. This means that I can't really scroll comfortably with the mouse. How can I clear the past output from the window? I've tried )CLEAR and )ERASE without success

Adám

@PuercoPop You should be able to find the log file so you can delete it. Probably ~/.dyalog/session_log_180U64.dlf

PuercoPop

Ok do I just clear the file in ~/.config/Ride-4.4/hist.txt right?

Adám

@PuercoPop Hm, I'm not sure that's the right file. I'd expect a .dlf file.

dzaima

@PuercoPop that file holds the inputs which you can go back to via the "Backward or Undo" shortcut, it's unrelated to what's displayed in the main RIDE view

@Adám deleting/moving that away works for me

ngn

for me too

dzaima

17:42

probably doesn't help much if what's wanted is for RIDE to never show the previous sessions though

ngn

@PuercoPop are you more comfortable editing in ride or in emacs?

PuercoPop

@ngn in Emacs, but I have been unsuccessful using dyalog-mode

Adám

@dzaima If you never want to save a log, try setting LOG_FILE_INUSE=0 as an env var or on the command line

PuercoPop

@Adám I've found two dlf files, ~/.dyalog/default.dlf and ~/.dyalog/session_log_180U64.dlf but they are binary files. Should I just delete it?

Adám

@PuercoPop Delete the long-name one.

PuercoPop

17:46

@Adám thanks, that worked

@ngn by any chance are you n9n on gitlab?

Adám

@PuercoPop He is.

ngn

@PuercoPop yes, "ngn" was taken there

@PuercoPop you could use the bash trick to write #! scripts (unless you insist on using the apl repl)

Adám

iirc, you can also ask RIDE to use emacs instead of its built-in editor.

ngn

@PuercoPop or configure ride to use emacs for editing functions etc (not for the session, though): export RIDE_EDITOR=emacs

Adám

:-)

ngn

17:52

telepathy :)

Adám

Nah, just gmta.

PuercoPop

@ngn Thanks for vim-apl, I had some trouble getting the input through prefix work due to a setting I had (timeoutlen=0) but after fixing that it worked great. I tried extending it to use the built-in terminal as a REPL but for some reason I can't get chansend to 'press enter' through a vim command

ngn

@PuercoPop chansend? too advanced for me :)

PuercoPop

@ngn it is the command you use to send input to a terminal

@Adám I'll try setting RIDE_EDITOR. dyalog-mode tries that approach afaict, it is bundled with some APL code that is needed to setup Emacs as the editor but when I try ]LOADing it it always fails. Even the recent version which was updated for 18.0

Adám

@PuercoPop What is dyalog-mode?

Moonchild

18:00

in general, x-mode refers to 'x' language support in emacs

PuercoPop

It is the emacs mode for dyalog github.com/harsman/dyalog-mode

Adám

@PuercoPop It ]loads for me.

@PuercoPop Cool. I've updated APL Wiki.

dzaima

19:32

@dzaima a better per-bit if-then-write seems to be somewhat better than that too. (and i've realized the cumulative breaks with an >255 streak of 0s)

Transcript for