the k tree

ngn

00:11

does anyone remember what int monad/ints meant in k3?

there's a question in matrix chat about the meaning of j v/i and "chase pointer" here

Hao Deng

00:28

q)3 {x+1}/ 1 2 3
4 5 6
I don't know abut k3, but in Q, it apply f x times to y.

ngn

@HaoDeng but the comment on nsl says "starting at index j"

Hao Deng

Like I said, I have no experience or access to k3.

Traws

00:46

@ngn i believe the "chase" means this

"j" would be a distinct starting index

ngn

@Traws i think understand the monadic case, but the dyadic is still a mystery to me

if j is the starting index, then what is i?

Traws

too bad we don't have an example of the j case to reverse engineer it

ngn

might be a mistake

Traws

01:17

@ngn it seems so.. the natural extension would be to keep indexing j times and that's what k7 does

ngn

yeah, it does that in all ks i'm aware of (with somewhat different syntax in k9)

(if we ignore base-encode/decode overloads)

Traws

the overloads are much better

but it kinda hides the lists are functions paradigm

ngn

@coltim i think i managed to vectorize find :) no intrinsics

ngn

01:42

finding a needle in a hay stack.
Algorithm A: go straw by straw and test if it's a needle
Algorithm B: this time you have a metal detector. you grab a bunch of straws and test if there are any needles there. if there aren't - discard it and grab the next bunch. if there are, start looking for the needle in the bunch using algorithm A

Bubbler

Applying Algorithm B hierarchically gives a B-tree :P

JohnE

02:07

an algorithm-b tree, surely

chrispsn

07:58

What is the best way in ngn/k to pad two strings to be equal length?

Spaces as padding char is ok

Bubbler

pad to the left or to the right?

chrispsn

Right

I mean pad each max length x,y is one way, but now that flip is gone, is there another way?

Bubbler

Maybe something in the line of ((#x)|#y)$(x;y) i.e. just pad manually, but $ works on list of strings right arg

chrispsn

@Bubbler oh interesting, I didn't know that about pad

Bubbler

Me too. I just thought "padding would be sensible to apply to each string in y" and tried it out, and it did work

chrispsn

08:10

Makes me wonder if pad could take a fn on the left to avoid repeating

(|/#')$

Given it is designed to take lists of lists

xpqz

Is there a neat way to find the location largest element of a list (i.e *>), but if there are several instances of the largest element, return a list of locations? I got to {&x=|/x} -- is that the way?

Bubbler

I think that's the right way

chrispsn

Could do :/= in k9 since group sorts

chrispsn

08:30

What does *|<="racecar" give you in ngn/k

(Sorry, can't test myself right now)

Bubbler

"e"

chrispsn

Ah well

Bubbler

<dict is sort keys by values, and (unsurprisingly) the largest value is always the last one, so...

chrispsn

@Bubbler I get mixed up on how the grades work between k dialects

Bubbler

understandable

xpqz

09:42

Anyone golf this down? Find the (possibly several) most frequent items in a list: {(!t){&x=|/x}@.#'t:=x}

ngn

@xpqz {&d=|/d:#'=x}

rak1507

would be nice if f#x worked on dicts {x=|/x}##'=:

ngn

@rak1507 good idea

rak1507

CMC: {x=|/x} golfed

Bubbler

=/|/\

rak1507

09:50

yep

Bubbler

assuming input is simple list

rak1507

well that was boring

xpqz

@ngn wow, k dicts rock

Bubbler

@Bubbler but no bytes saved when used as a left arg

chrispsn

a possible alternative approach to the projections problem, if anyone wants to have a crack

idea being to convert the input lists into occupied slots or unoccupied slots (;), then expand and merge

not sure how you'd get the input lists into the appropriate form or if the approach generalises correctly

but at least it avoids splitting on ;

xpqz

10:04

I am blown away by the utility of being able to do this:

&`a`b`c`d!0 1 0 1
`b`d

@ngn I think this should be in your repl's \+ under &d, unless I just can't see it.

rak1507

10:20

can't give away all the secrets! takes away the fun of discovering them...

xpqz

Someone clearly thought through how dicts should work in an array-y language.

dzaima

11:00

@JohnE it's unfriendly companies that copyleft licenses help with. With a permissive license, a company could just take your array language, put a couple thousand man hours into optimizing it, and sell it as a 2x faster version. Then they're gaining money directly from not contributing to intellectual commons!

good people/companies won't have trouble sharing their modified source. Bad people will do bad things regardless of anything. As such, bad companies are the only ones hurt by copyleft

coltim

12:36

@xpqz the part that clicked for me was that operations that either take or return indices (when working on e.g. a simple list) instead work on the dictionary's keys. this includes things like &x, <x, >x, x@y, x?y, =x, x_i (there may be others...)

@dzaima I think it's more that the companies that are hurt are the ones with conservative legal teams that would rather not deal with copyleft licenses at all

dzaima

12:59

@coltim eh, true. But those wouldn't share the source if given a permissive license anyways

xpqz

@coltim I was pleased with my 1 byte saving going from {x[<#'x]} to {<x!#'x} by dictifying

@dzaima Well, working for a big multi-megacorp, we're certainly very dilligent with sharing back everything we change or fix in a huge range of OSS projects with permissive licenses. We also have an outright ban on anything xGPLx.

dzaima

huh.

xpqz

The other megacorps though.... :)

rak1507

@ngn how does ngn/k deal with overloads in the source? I can't read it very easily atm.. so not sure

chrispsn

@xpqz now help me convince ngn to make (f)! {y!x y}

xpqz

13:13

@dzaima If I was building a database, an in-memory cache layer or distributed full-text search engine (picking some examples at complete random), I'd think extremely carefully about licenses before a hyper scaler picked it up 'as a service'.

@chrispsn what does that mean?

rak1507

overload f!x so f!x is x!f x

xpqz

Ah, I see. Like python's {k:f(k) for k in x}?

rak1507

that would be f' but yes

(at least, I think, there's probably some debate as to whether it should be x!f x or x!f'x like there was for #...)

coltim

@rak1507 which part do you mean? like how the code is structured, how the determination of which overload to apply is made, etc etc

rak1507

@coltim both, was wondering if I wanted to add in an overload for f#d for example, how would I do that

coltim

13:22

@rak1507 hmm. as far as I can tell, the overloads are sometimes within the same C function, and sometimes split out into separate ones. I assume that the determination of which overload is done with all the helper macros that examine the type of the input

@rak1507 otherwise I would track down the commits where the overload was added/modified =|

rak1507

@coltim ok, that's what I guessed

'helper macros' - what I didn't want to hear

coltim

this commit is where f_x was added. I assume if you are able to implement your tweak in K you can insert it somewhere as a K-string

rak1507

thanks

CMC: golf {x@<x?x}

(sort by first occurrence)

coltim

13:58

&#'=:?

xpqz

@coltim clever.

coltim

@xpqz it's a part of @chrispsn's "ungroup-dict" implementation: {(&#'x)@<,/x}

(and @ktye's too!)

@ngn on @Traws' example it's now ~7% faster on my machine, although the ASM looks like an unrolled for loop rather than SIMD stuff

one way to SIMD it would be to do something like idx += tzcnt(movemask(cmp_eq(load(chunk), lookup))), maybe unrolled a bit

(but I would be surprised if a compiler would transform it to that =|)

dzaima

14:36

I get an unrolled loop too:
https://dzaima.github.io/paste/#0tVfdbtowFL7nKVxVqmJwgx0CDdBsatVNQ0K06lCrlaEpJA64hRAIQ@nW3e6@2hvuSeb8EEIIgU5gyYL4@JzvOz85HMyGAEFxMB7RovFDYyOt2Gez4lPxKfdhTq1ZDejP@pA6udwNner8AIQrB1ZX9vMVczTHoaPe8BmMTeBQfcbGFhBn1J3VslVxbBkVDYNzs/EuoWNyJ2q78Dg2qMksCgZCG35dFbUaoAnM4@O2cH2Xt1HLQs05/CZcg3ZeU200Uef1G2F@Onl5ObJQqwkbTMWorz5cFD8/CHkNIlPF9XuBnVsnJ0cmehT6yHxRtQ4rFLqqOoGQnar9und8KfBT/4zLIFd4z2rc4DqfO/BxyWeE2l8E8xKaiD9PfH75KfwZ8JvUmWChqWfWFGw0Qh4ChL9SfbQ9oxfcZht4Hl64at6utyzVtepNpvohcO@QheaQe8zOMcrbqmbPBRed8CMLMrhqdSBcwoHwie8G302YTAG1jN60Im@qlBl1/KqaOgzxvSr@@/sPeKTBd4JLafqj8dxx…

for that matter, + doesn't look too good either:
https://dzaima.github.io/paste/#0lVjdbqNGFL7PUyBZqsCesDMw2JCsI7VK1Uba7KZbS6vWciUM44TUNgQcl1R7vfdV37BP0vkBe4AZnHABeOb8fHO@c84w/nFPtrsLI3qJ1qQ4O7sjeUQHjOo6M5pX/@/rpAiLgmyW6xcjXRkFiXZJujXsHSl3F/2q8Hg5HsbQeB/e3Fy1lOiQaV0otAcxWSVbYjx8MldgBtbgHhDbti3jYcUHbsw1@PDRDC3rQzKFl1/M5P0WkMtH8x7k88fFdE9vVjKa3l@Go@l6eH@5ZO85vVmJZbx7VzxnWZrvjHRP8tU6/avQuP@@dm@JCQnPzNjP7xfcJfM2Defr4eNitGSeZ0ZKUbGp9OvUFDN/cEzfmUxAvFt3Znp19evv5swa@ucIJJalgXHbA2MwcJRIhiabsjgeNnVnsslz6ow9mTOdt9TcgZl1nKBRCAeD3WAwoz4h@IkBtsTgTAyievDW3HQl@WBLUuN623b9seF6ZImBgzE@ILscVgMHiWHLFV3dEvxg0cc…

dzaima

14:55

oh, apparently I need to explicitly make CC=clang

Bubbler

wasm simd when

dzaima

yeah, with that things actually look right:
https://dzaima.github.io/paste/#0lZZbT9swFMff@ymMkFBSTOu0hqYt2QRi0yqVi1gFAoYmx3Goobk0CVFg7HXv077hPsmctM2tpc0spZLt479/x@f4uOZAkkFz7FisabwSbpHmAw@aT82n2qeQ2UEP0Bc6YX6tdsE8KgbAvNVAsa3tn3Cf@D6z9MkLcEzgMxpwxwaNgEVBb@1KlDasKK0WAofm4ENxiSk86G1m2DaYyW0GxtJI/laYORuAITC3t0fS@VXdhWc2HIbyd@kcjOpEc@FUC/sXUrg3fXvbsuHZUB5wDcEH7fao@fVWqhMZmhrqX0v80N7Z2TLho/QAzTeN3PHd3XtNm8oy39Me@vHwsSRGkzExJ4sFH3lPCC7hXIHPGY4FRzeSeSybUPSnCV7dk3/M8KZ9LtnQi1VNyYUWjDeQ5Z@rPHRjzSMhOQKxf0eRVnf7Z7YW2f0h15IDiK6gDUNZ@MsPEay7GnFDKYI7YsiWuVwQHUvH8lj6Ir6B@IbxJGqg9mLackKi@/OORyKIIhUVWyleAfPT…

Jun 7 at 17:41, by ngn

@dzaima actually, that + still has 52 instructions for the 8 packed additions, which is way too much

it appears to be both reading and writing the items one-by-one..

lol CBQNs unvectorized + is a bit faster than ngn/k's :D

(comparison)

JohnE

15:16

@xpqz this is precisely my experience in the corporate world. In another field I intersect with, video games, GPLed libraries are also poison; the linking/distribution requirements are often hard or impossible to satisfy when distributing games for many platforms. This isn't just hurting greedy corporations, either- independent creators with shoestring budgets are hurt far more, and they often find themselves forced to use commercial products instead of open-source alternatives

coltim

15:37

@dzaima ah, that does it for me too. clang is much better at autovectorization than gcc. now getting >2x performance

dzaima

@JohnE the whole static/dynamic linking thing is pretty stupid, yeah. unfortunately defining what's a modification and what's usage is pretty hard.

coltim

@dzaima you could try using i64's (your example uses i32's) with something like a:100000?0. it's ~2x as fast for me locally. I assume the 32bit version is doing all that stuff in order to handle overloads

(the ASM looks much more like one would expect as well)

dzaima

the CBQN example is using i32s too, and has to check for overflow just like ngn/k

of course i64 code is gonna be simpler

lol, i8 addition:
https://dzaima.github.io/paste/#0nZhtj5s4EIC/769AinSCxCWYt8Bus9JFW91V6rarXqSqt8pJBpyEbRI4ICm7us/9XvUf9pecjSE45KUGpARiz8zjscczwWgykRVpuIzWeBi8oHCNhoswG34Zfrl6s8Ob7Fryn/0VTq@uHnDikwapvK6kw@vy77swRWmK197qWYrmUor9LIw2kprhPLu@rKrtL1MfIaxJr9FkcttQQtSN6xPavQDPww2Wlh/kOZiCFVgArKqqIi3nRcNbeQXevZeRorwLx9rNJzl8vQH45klegOTxaTbekS8lHIwXN2gwXvUXNx59TsiXEpJ5G6bbOI6STIp2OJmvoq/pGfzvFV5hHdx4ptLucTErkJQ2Ro@r/tNs4FHyVIrIqGhX9N9YZj3/FGP6TaYC7Fl5kKPb27/@lqdK33kFQagoZ4Zxf2EYvZ5@ciR9mXYpxXho14NMO18RGL1T2DlaJGdgqtQdZBZQr5f1elPC1MAfdMAKa5yyRlg13svrY8misSF5Br1pot8foAcKa9gbKxp4ZL9s2Ev0GyjinQcmCrktwZ…

coltim

I wonder what the best way to SIMD-implement overflow logic would be. upscale each chunk to the next integer size, do the addition, check if it's larger/smaller than INT_MAX/INT_MIN, and if it is, punt to the error handling logic?

dzaima

the upscaling is probably gonna make it not worth it. ((x^res) & (y^res)) < 0 is probably the best way

in The APL Orchard, Jan 20 at 20:42, by Marshall

@dzaima Ah, I thought I remembered having to do the bitwise version for something. I feel like I got it an instruction or so better than ((w^r)&(x^r)) < 0, but I don't remember how.

rak1507

17:07

@coltim yep

xpqz

Here are my solutions to the 2016 competition if anyone wants to golf/laugh: gist.github.com/xpqz/d055cb2668e2e10ea496b39ce7b47354

Problems start here: problems.tryapl.org/psets/2016.html

Number 2 was the stand-out poor solution.

coltim