the k tree

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

2:07 AM

an algorithm-b tree, surely

chrispsn

7:58 AM

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

8:10 AM

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

8:30 AM

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

9:42 AM

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

9:50 AM

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 AM

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 AM

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 AM

@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 PM

@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 PM

@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

1:13 PM

@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

1:22 PM

@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

1:58 PM

&#'=:?

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

2:36 PM

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

2:55 PM

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

3:16 PM

@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

3:37 PM

@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

5:07 PM

@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

6:12 PM

@xpqz this golf has some clever tricks. it can be adapted/golfed in ngn/k as ngn.codeberg.page/k/…

(the median of an empty list (I think that's what ⍬ represents?) being 0 is a bit odd. these return 0n, a floating point NaN, instead)

coltim

6:29 PM

@xpqz #7 could be (~&/3 5!\:)#. regardless, 0= can be replaced with ~ not

#8 could use a dictionary/group approach: {.|x@=x<0}, although what you have is quite nice

coltim

6:45 PM

#5 may need a trailing : to ensure the = is group and not equals

and #9 may need to be {x\y} (/ and \ always parse weirdly =|)

Traws

7:46 PM

@coltim @ngn another datapoint from that example.. previously: (gcc) 10s, now: (gcc) 7.5s, (clang) 3s, (gcc+small domain trick) 0.09s, (clang+sdt) 0.08s

@coltim @xpqz it could be (|/~3 5!\:)# aswell, maintaining the original logic

coltim

11:36 PM

@ngn >'1 exits the repl

Transcript for