@MartinJaniczek OK, so you gain backtick support but lose 2D movements, windows, etc.?

well, it can integrate with tmux now

yeah right now you don't have any of what you mentioned. It's quite literally a program that talks to Dyalog via RIDE, and does all user IO from scratch. Proof of concept that backtick can be done easily, but that's probably it

Haskell libs for readline-like features failed me when I tried them

perhaps something about buffering etc. I don't understand that well

@MartinJaniczek It'd probably be easy for Dyalog to add native backtick support to the TTY interface if that's what's wanted, but that interface isn't very nice.

Is everybody mostly working with the Windows GUI or RIDE? Or is there some portion of users who go TTY?

@MartinJaniczek I actually don't know, but while RIDE has its shortcomings, the native TTY interface is so awkward that I've only ever seen it used for quick things. I think there could be value in a simple REPL interface à la Python and Node, but APL's interactive nature means one would have to either prohibit or find solutions for when otherwise a window would pop up.

@Adám Fair point

Unsure if there is a nicer way to do the binary array on the right

"all permutations of 1 1 0" perhaps?

I'm trying to express "⌽ applied ⍳3 times to 1 1 0" but all the products and reduces fail me

<moon-child> just rotations will do it in that case

<moon-child> I would do (,⍳∘≢⍤0 1⊢)

<moon-child> err

<moon-child> I would do (,⍳∘≢⌽⍤0 1⊢)

That looks like it works if given 1 1 0, but I'm unsure how to read it. Is it a train?

<moon-child> you can drop the 3 3⍴ and the ,

<moon-child> yes, it's a train

<moon-child> in direct form: {, (⍳≢⍵) (⌽⍤0 1) ⍵}

<3 that is helpful.

Oooh the ⊢ by itself is the right ... pine? of the fork, right.

<moon-child> yes

<moon-child> ('tine')

<moon-child> you can also use ⍵×⍤1 1⊢ instead of (3 3⍴⍵)⊢

<moon-child> (instead of (3 3⍴⍵)× - apparently I can't type today)

Alright so the ⌽⍤0 1 is what I've been missing when trying the "⌽ applied ⍳3 times to 1 1 0" idea. Ranks again

Perhaps I should finally do this chapter of the workshop :) rikedyp.uk/APLWorkshop/course/6

Why not +/2×/7⍴⊢

(which is {+/2×/7⍴⍵} in direct)

uh, what

how does the 2×/ make 7-element array into 6-element array

<moon-child> ⋄ 2 ,/ ⍳7

1 2 2 3 3 4 4 5 5 6 6 7

It's called n-wise reduce

oh the 2 is argument to the / operator?

so 2 f/ vec applies f/ to each of (overlapping) 2-segments

Yes, it's the left argument to f/

gotcha

so 7⍴ x y z gives x y z x y z x, and applying 2×/ on that gives (x×y)(y×z)(z×x)(x×y)(y×z)(z×x)

then you just sum them

Makes sense. It still is a bit magical to me that you end up with the right number of multiplications. I can kind of see how that would generalize, but probably only for the cases where the window size = number of elements - 1... Hm

For the matrix approach, I could write {2×+/⍵×.×∘.≠⍨⍳3}

You don't need 3↑ there

facepalm. Right!

Since you're using a chain of ¨-ed functions, you could just chain them directly

{+/{(⌊/3↑X)++/X←2×/7⍴⊃(//)'x'⎕VFI⍵}¨⍵}

(does it work?)

It does! I'm still reading it

so you got rid of the inner dfn

(//) made it possible to get rid of another one...

oh, no, I missed that there still is inner dfn

Yeah I think I get the fusion now

If you get to learn trains, you can golf a bunch out of it further

+/{(⌊/3↑X)++/X←2×/7⍴⊃(//)'x'⎕VFI⍵}¨

that's basically just eta-reduction, right?

+/{(⌊/++/)2×/7⍴⊃(//)'x'⎕VFI⍵}¨

Yeah, kind of, with the fact that 2-train works as function composition

(called "atop" in APL)

Thank goodness for the ]box display of trains.

(⌊/++/) inside inner dfn is a 3-train, or a "fork"

which can be read as "minimum plus sum"

Yup that's the one I was trying to parse. This is making my brain work out in all of the best ways

But I'll have to go to sleep, 3AM here. Thanks a lot @Bubbler and @Adám!

Good night :)

⋄(⌽@1)(⊂1 5),9

@Razetime 1 5 9

how do I make this give (5 1) 9?

⋄(⌽¨@1)(⊂1 5),9

@ngn 5 1 9

thanku

how do I get the middle element of a stencil?

Just index into it

ok got it

({x←∊{(⊃⌽⊃⍵),(⊃⊃⌽⍵)}¨{⍵⊆⍨(0@(⌈0.5×≢⍵))(≢⍵)/1}¨(1 1∘⍉⍵)(1 1∘⍉⌽⍵)((⌈0.5×≢⍵)⌷⍵)((⌈0.5×≢⍵)⌷[2]⍵)⋄y←(∊⍵)[⌈0.5×≢⍵]⋄1=y:1⋄(2=y)∧(5≤+/2=x):3⋄(3=y)∧(0=+/2=x):2⋄x}⌺(⍴mat))mat

i made this but I highly doubt it'll ever finish running

it's also giving weird output

+/2=∊({x←∊{(⊃⌽g⊃⍵),(⊃g⊃⌽⍵)}¨{⍵⊆⍨(0@(⌈0.5×≢⍵))(≢⍵)/1}¨(1 1∘⍉⍵)(1 1∘⍉⌽⍵)((⌈0.5×≢⍵)⌷⍵)((⌈0.5×≢⍵)⌷[2]⍵)⋄y←(⌈.5×⍴mat)⌷⍵⋄1=y:1⋄(2=y)∧(5≤+/2=x):3⋄(3=y)∧(0=+/2=x):2⋄y}⌺(⍴mat))⍣≡mat

need a bit of help finding out what's wrong here:

1 is floor, 2 is occupied, and 3 is empty

also g←{⍵/⍨1≠⍵}

My super gross solution for today

I figured there would be an easier way to do the 8-directional coordinate search considering I've seen concise APL solutions for n-queens, but I couldn't think of anything

For n queens problem, you only need to count the number of queens in each diagonal

but the aoc problem does not have such shortcut

Hrmm, true

@voidhawk coool

maybe I should ditch stencil and try something else

@voidhawk looks good but is rather slow

in my k solution i prepared neighbour lists for every cell, then used only indexing and arithmetic operations in the loop. this strategy works for both parts. it finishes in <4s, despite the wasteful use of 64bit ints everywhere. i'll try to make it even faster and translate it to apl when i'm back in an hour or two.

@ngn down to 1.7s

@ngn speeeeeeed

apl translation coming soon

2.9s in dyalog, but there's room for improvement:

tio.run/…

My AoC: gist.github.com/xpqz/ce3bb1088c4a14b907e5990e714b2433

Very verbose by @ngn's standards.

Part 1 was so simple but I've not done part 2 yet

@dzaima as fun as it would be to make an APL object interchange format, it's also extremely pointless

@rak1507 yep it takes a bit

@xpqz thanks for making it verbose

Ha.

I've compressed it a bit now.

good thing there's revision history

git ftw

Like @voidhawk, I'd be keen to see a smart "array-y" solution to the diagonals. I ended up basically a set of for-loops in disguise.

I'm working on it...

@xpqz that's my weakest spot too

if we have the coords of occupied seats, we can identify the horizontal, vertical, diagonal, and antidiagonal with ⊣/,⊢/,-/,+/ and we can group them with ⌸ and sort each group. then consecutive positions in a group should be treated as connected.

but it's easier to let rak1507 solve it first and then just steal :)

@rak1507 is the nominated brains of the outfit.

Haha

No pressure...

i'm expecting regexes

No regexes for this one

Although I was moderately pleased with:

Just thought that the plural of regex should be regices

coords←{⍵+⍣seat⊢pos}¨(⊂0 0)~⍨,∘.,⍨¯1 0 1

@rak1507 or regexen :)

Is there a ⌺ in numpy?

@Adám Nice Adám ! Just for fun, a suggestion : ⍎⌽⍕⌈*○≡⍬ ⌊ 10⊥≢¨'GOOG' 'LE'

@Adám December 17th is next week, how Dyalog is going to celebrate Ken Iverson's 100 birthday ?

@xpqz for (⊂0 0)~⍨,∘.,⍨¯1 0 1 i'd use 1-1↓4⌽,⍳3 3

⋄⍎⌽⍕⌈*○≡⍬ ⌊ 10⊥≢¨'GOOG' 'LE'

@Razetime 42

@brgal nice.

@Razetime APL is so much fun ;)

@ngn yup; shaves a few bytes

@xpqz you don't need a ⊢ after ⍣≡

When is ⊢ needed? If passing an array to ⍣ only?

⊢ is to prevent stranding

@xpqz it's useful only to prevent two arrays from stranding together, like f⍣array⊢anotherarray. without ⊢ it would parse as f⍣(array anotherarray)

@rak1507 @xpqz @Razetime i reached 360ms! (in k)

with this approach

@Marshall ge(e,i) is getting the ith ancestor?

@cannadayr yep

@dzaima would you recommend using a standard linked list for environments stored on the heap? I was considering a general balanced binary tree (its in stdlib)

im unsure of what access patterns end up looking like (write vs read heavy, random vs linear)

@ngn madness

@cannadayr the height is gonna be almost certainly below 10, i'd expect 3 max in most cases. So the constant factor most likely is the biggest deal

@ngn impressive. Mine takes ~5 seconds...

mine takes it's sweet sweet time

@dzaima (the height is the nestedness of the dfn in the source)

@xpqz your machine is probably much faster than mine. when i ran your part1 it took nearly 1minute. i didn't wait for part2.

@dzaima height as in number of environments at any time on the heap?

i could maybe use an array (tuple of tuples)

@cannadayr no, height as in the amount of actual surrounding blocks (curly braces) there are of the executing dfn

@cannadayr a regular array also works. No clue if that's better than the linked list

@dzaima yea ill pick whatever is easiest to get working. its going to be a bit different than the js ref since ill have to store/resolve the reference manually.

@ngn orly? Without measuring, I'd say part 1 takes perhaps 1s for me.

@Wezl parrot looks good

@xpqz yes, with your new version (only part1):

$ time ./a.dyalog
2481

real	0m54.665s
user	0m52.554s
sys	0m0.183s

i have sse3 but no avx

@ngn And SSSE3? Dyalog doesn't use SSE3.

@Marshall ah, yes, ssse3. i accidentally skipped an s. (i'm looking at /proc/cpuinfo)

* Benchmarking "+/2=∊{{T ⍵}⌺3 3⊢⍵}⍣≡DAY11"
             (ms)
 CPU (avg):  2798
 Elapsed:    2820

Apparently my laptop sports a "2.3GHz Dual-Core Intel Core i5"

when my thinkpad gets repaired, i'll have something like that too. for now: Intel(R) Atom(TM) CPU N455 @ 1.66GHz

I occasionally run Dyalog on a Pi3 -- most of this sort of stuff is fine, but occasionally hit something that feels instant on the laptop taking 5-10 mins on the Pi.

all the more incentive for me to write optimised solutions :)

@ngn Presumably IPC is terrible. Also, the cache is small (512 KB; no L3), so if the problem uses a lot of data that could be a bottleneck.

@xpqz changing {{T ⍵}⌺3 3⊢⍵}⍣≡ to ⊢∘T⌺3 3⍣≡ makes it a little (5s) faster

<phantomics> How do you benchmark in Dyalog?

phantomics: cmpx from dfns, with string expression arguments, or ]runtime which has its own syntax.

<phantomics> Cool thanks

@DyalogAPL or time dyalog -script <filename.dyalog

(for recent versions: without the <)

implementational question: if your array language has n integer types, say byte|short|int|long, how would you implement indexing? would you be dispatching to n*n specialized functions for all combinations? or always convert indices to longs and use just 1 function that tests types at each step? or..?

@ngn same question applies to pretty much any dyadic operation really

@dzaima yes, but many dyadic operations (like + for instance) can take advantage of converting both arguments to the wider type, which brings down the number of cases to N

@ngn but that widening is overhead just as much as in the indexing case

@dzaima hm.. maybe

also i'd expect indexing to be somewhat slower than, say, +, so for indexing the widening would even be more "free"

Is it just me or does using the rank operator successfully always feel like you've just done a magic trick

@dzaima it makes sense to widen only the index argument, e.g. always convert it to long

@ngn for dyadic + you also only should ever widen one argument

@dzaima with gather-scatter indexing is super-fast!

@dzaima with + it could be the left one or the right one, with a[i] it's always the "i"

@ngn deciding which to widen is a constant time operation, so it's still practically the same problem

@dzaima right, ok.. the question should be: am i losing too much by doing this?

@ngn depends on what you care about. binary size? yeah, you're definitely inflating it by n*n impls. performance? probably maybe gaining some by doing n*n impls

in many cases the "i" in a[i] is a much larger array than "a"

@ngn Would it boil down to pointer arithmetic at some point?

@ngn as for the answer - i'd either go with just int&long (int is almost always enough, and long must be done), or try n vs n*n, maybe keeping it as a compile-time option

@coltim in my experience compilers these days understand "for" loops with ordinary c indexing just as well as *pointer++ style code

@dzaima thanks. doing it only for int|long would make sense. if it's a smaller type, it can be widened to int.

@ngn in my (limited) experience C compilers do all sorts of integer promotion on their own (so even if e.g. your loop index variable is a char, it'll be sign-extended when it's used in an array access)

@coltim yeah, they do that. but i'm not sure if all combinations are available as vector instructions.

@dzaima (though if i ever would make a performance-first array language, i'd almost definitely want to go full-out with dynamically generated code merging multiple builtins together, at which point the n*n-ness is just "free"; </dreaming>)

Assuming x86, the SIMD gather/scatters only take i32/i64 offsets

but I would be surprised if compilers would generate them frequently

@ngn I have a strong suspicion you haven't benchmarked gather/scatter. It's not actually vectorized; the only benefit is that the result ends up in a vector register.

@coltim i guess that answers my question. thanks :) i was planning to look at the asm for all N*N combinations and make sure it looks vectorish, but it seems there's no point

@coltim there still could be benefit gained from widening at the call of the gather/scatter instead of creating a separate array copy holding the whole array widened

@dzaima that is certainly true!

@ngn 16 indexing routines is basically nothing; make the decision based on how much it complicates your codebase and not based on the binary size.

@dzaima (however extremely tiny that benefit may be when comparing a thing slightly more complicated than memcpy with random memory access)

@coltim they do. at least clang. it's a bit of a hassle to make sure there's no aliasing (restrict keyword), and alignment and padding are taken into consideration (otherwise the compiler generates a lot of crap for edge cases), but i've managed to make it work.

@Marshall I'd have to track down the exact answer, but from my recollection the SIMD gathers started getting faster than (or at least equivalent to) manual implementations around the Skylake generation (the first one I found is here)

@Marshall i haven't benchmarked it on purpose. i've just noticed after solving many eulers, aocs, golfs, etc, that indexing is unreasonably fast.

@Marshall i'm good with macros ;)

@ngn I guess the one difference from the APLs in the hardware gathers/scatters is their lack of conflict detection (i.e. they don't work for histogramming since duplicate indices aren't handled super gracefully)

@coltim They certainly weren't when I tried them on Skylake X. Maybe that's changed but I'd like to see actual timings and not theoretical cycle counts.

@Marshall hmm. I haven't done any testing on my own, but what about this?

(understanding that random access latency or memory bandwidth bottlenecks are both 1) super common and 2) not gonna be helped by SIMD)

@coltim I did it with L1-sized data. I'm not sure I tested the AVX2 version though, maybe just the AVX512 one?

@Marshall ooh, L1-only could be a factor. I'm definitely not a super expert on this stuff, most of what I've learned I've picked up from reading @PeterCordes' answers (among a few others). But I would imagine the AVX2/AVX512 split wouldn't be a super determining factor in this instance

It could have just been the scatter that was the problem, as the thing I was most interested in was using VPCONFLICTD for histogramming (which wouldn't have worked anyway because it turns out it's microcoded on Skylake X). I think I tested them both though.

@Marshall are you familiar with Orestis Polychroniou's work, e.g. this? I think there was some workaround for the histogramming issue in some of the hash join implementation (source available via here)

@coltim Ostensibly VPCONFLICTD is the solution for the histogramming issue, but all Intel's published code does is use it to detect if there are any conflicts and go into a slow path in that case.

I wasn't aware of the latter! Thought it would somehow address it more thoroughly...

@coltim That paper looks kind of familiar. I never found that database papers were useful for me as they're generally focused on memory issues rather than fast computation.

@Marshall There are definitely layers above the underlying ops that "get in the way" of matching hand-optimized SIMD code, but my understanding is that you have to be doing a decent amount of computation per input in order to not be bottlenecked by the latter (maybe FFTs? chess solvers? or however Prime95 is capable of burning out chips, heh)

(bottlenecked by memory issues I mean)

(also gemm, which is a glaring omission from the above!)

I'm so close to doing part 2 but my code doesn't work for some reason... multidimensional arrays are hard to debug :((

@rak1507 a nascent k fan :)

@coltim In array language implementation, adjacent vectors are usually independent (or can be made independent) so the bottleneck is memory throughput and not latency. Cache throughput is pretty fast, running in the 10s of gigabytes per second. With 32-byte instructions, you have to go about a nanosecond per iteration to hit that limit: 4 cycles or so. Pretty much only copying and basic arithmetic go that fast.

<moon-child> @Marshall copying and basic arithmetic go way faster than that

<moon-child> agner.org/optimize/instruction_tables.pdf coffee lake can perform two add r,m per cycle

moon-child: You have the overhead from the load, store, and index management as well (I consider these part of the computation). You're CPU-bound after a pretty small number of vector instructions.

Another aspect is that server class CPUs have pretty terrible per-core memory bandwidth, like ~10GB/s (a lot lower than the lower-core client CPUs)

<moon-child> @Marshall fair enough

@coltim Huh, didn't know that. We always benchmarked on consumer hardware at Dyalog.

@Marshall I semi-noticed this on my old Broadwell-E, but there's this

@coltim I'm now reading more carefully and I think I haven't actually seen this paper before. They use scatter then gather to detect conflicts, which they can only run on a Phi because their other CPUs don't have scatter. I think Phis have much better scattering than other hardware so this might not transfer so well. I'd imagine the numbers you're testing also have to be relatively small-range so you don't get a bunch of cache misses on the scatter?

Still, if scatter's improving then it might make sense depending on whether VPCONFLICTD is still microcoded (I can't find instruction timings for Ice Lake?).

If I'm reading the hash benchmarks right, the Phi per-core timings are just about on par with Facebook/Google/Dyalog hashes for small tables and otherwise everything's much worse. Not terribly surprising since those are all later work.

<moon-child> @Marshall now I'm curious: if memory bandwidth isn't a bottleneck, why does dyalog do bitpacking for boolean arrays?

@Marshall the paper's relatively old, and AVX2 didn't have scatter (only gather). I mean not that much has AVX512 (besides Skylake X/Server and random Ice Like/Tiger Lake laptop 15W CPUs), and Phi is sunset, so it's not the largest real-world domain that would even benefit from it

moon-child: Registers have a fixed size. Booleans fit eight times as many in a register as shorts, so you can ideally get eight times as much work done in an instruction.

I'm not super familiar with what the latest is on out-of-cache benchmarks, but I assume that most of that would be bandwidth related (and benefit from the DB-style memory optimizations). Plus Phi was a bit weird, with its 16GB of local RAM or whatnot

<moon-child> @Marshall you get a win there for boolean ops. But I guess the biggest use of boolean vectors is reduction; wouldn't you have to do slightly more work there?

@coltim Intel's messed up a fair amount of research by supposedly setting the direction of computing with Phi/KNL/AVX512 and not delivering. Will be interesting to see what exactly happens to vector instructions in the next few years, since it's not obvious any more that bigger is better.

moon-child: Reductions on boolean vectors have great performance. ∧∨⍲⍱<>≤≥ all shortcut; =≠ are commutative and associative so you can combine whole registers and then to a final reduction at the end, and + has a dedicated instruction (popcount) that can also be used for - with hardly any extra effort.

<moon-child> reductions--why? Wouldn't you have an unrolled loop with a bunch of tests and a memory fetch at the top; compared with the same loop but no extra memory fetch for bytevectors?

@Marshall Yeh, the SIMD stuff is super interesting to me so the gap in having it actually available has been meh. But it does feel like a really nice fit for the array-based languages, especially given the nuances involved in getting traditional compilers to utilize it

moon-child: You mean for shortcutting reductions, right? For these you can always stop the moment you see a 1, or a 0 depending on the operation. So you can read an entire register and check whether it's equal to the all-0 (or all-1) register.

@coltim I have described AVX-512 as APL: the instruction set. It literally has compress and expand.

<moon-child> @Marshall ahh, fair enough. And I guess then you can also do binary reduction on the register, instead of checking each bit individually