the k tree

Razetime

04:58

k.miraheze.org/wiki/Amend I've added the ngn/k version of amend here.

ktye

05:11

@Razetime maybe doc what the 3-arg version does in sane variants of k: imply : as the 3rd argument

Razetime

05:27

@ktye "sane" variants?

ktye

@Razetime those that do the right thing

Razetime

ah yes that is very suitable for the wiki

ktye

you can write "some" and we know what that means

Razetime

05:39

specificity is quite important in a wiki

I'll figure a way out

Razetime

05:50

@ktye 4 argument amend is the same?

between ngn/k and others?

ktye

i'm not sure. what are the others, all versions of k?

Razetime

yeah

ktye

i guess they differ at least in detail. the k3 doc has detailed description of amend/dmend, e.g. with nested indexes, etc

Razetime

cool, I'll check the kx docs

ok, I've changed to indicate the difference

ngn

07:52

@[a;i;f;b;c] is like a[i]:f[a[i];b;c]
@[a;i;f;b]   is like a[i]:f[a[i];b]
@[a;i;f]     is like a[i]:f[a[i]]

@ktye ^

if @[a;i;x] was special-cased for non-functions x, what would the others valences of @ mean?

ktye

09:09

@ngn i didn't know these > 4 args exist!

@ngn what can we do about [that](https://ngn.codeberg.page/k/#eJzT1jeM11PSUDSwVtLRULJW0ldRNDQwMNDUUdJUAgBJdgTb)?
I figured out i reach a stack limit, when i parse a long list (1;2;...) because the byte code builds that list which pushes each element to the stack. you seem to do the same.
What can we do about that?

ngn

09:44

@ktye what do you need such a long expression for?

is it guaranteed to consist of ";"-separated ints?

ktye

@ngn i wanted to pass data in file.k as a list. maybe that's a bad idea, but it was the simplest.

ngn

@ktye maybe `I$";"\-1_1_ ? drop the leading and trailing "(" and ")", split by ";", parse as ints

ktye

i'll have to think about another method. it's still unfortunate that a native data structure (the list) cannot be parsed if it is too large, where large is 1000 already.

ngn

09:59

i think the threshold should be even lower..

if you have length1000 lists in your code, you should seriously consider putting them in a file

chrispsn

12:13

@ngn what if it's not so much about 'non-functions', as giving atoms function status?

ngn

i'll be back in 15 min..

ngn

12:30

goodness.. i've just had another one of those bright colourful zigzaggy visions. i hadn't had them for years.

rak1507

that doesn't sound good hope you're alright

ngn

@chrispsn what do you mean? we should treat @[a;i;atom] like @[a;i;:;atom] but @[a;i;list] like before.. or vice versa?

chrispsn

@ngn i don't mean 'give @[a;i;atom] special meaning` so much as 'if you give 2@0 meaning, the triadic case of @ might fall out naturally'

ngn

@rak1507 i'm alright, thanks. it just blocks my vision for up to half an hour at unpredictable times. doesn't hurt. and i hope it doesn't cause further long-term damage.

@chrispsn ah.. that makes sense

we could get rid of fd@ as "write()" and move it to fd 0: but what about all the `symbol@ overloads?

chrispsn

@ngn hmm

ngn

12:39

(don't say "keywords" please :) )

chrispsn

maybe symbols are special for that reason, and won't work well with triadic @

ngn

@chrispsn if we assume atom@ returns the atom, what would be the result from @[(1 2;3 4);0;5]?

chrispsn

(5;3 4) would be my guess

ngn

hm.. so, 5@1 2 should be 5?

chrispsn

if we want this result, then yes

it's weird though. should (1 2;3)[;1] be an error or 2 3?

if it's ok for something like (1 2;$:)[;1], it should be ok for an atom (if an atom is a constant function)

ngn

12:55

but functions are supposed to be first-class and behave like atoms..

i need an even simpler language, this one is still too complicated for me to implement :)

chrispsn

ngn/forth

xpqz

ha

k in forth seems like a match made in heaven

chrispsn

it's forth but you can't define new words and each builtin is a symbol

would probably look like a lot of the golf languages

xpqz

I know it's probably not @ngn's cup of tea, but running ngn/k inside a dev container in VS Code is a pretty cool environment to k.

ngn

@xpqz huh, how did you get syntax highlighting?

xpqz

13:09

There is a k-mode for VS Code.

k9, but good enough

chrispsn

for advent this year

it'd be cool if the ngn/k web editor let you drag a link into the window to temporarily store it

(store the file at the link)

ngn

@xpqz another item on my list of things to check out..

@xpqz just vscode or any codemirror-based editor?

Bubbler

K in forth... would be something like massively stripped down Factor actually

ngn

@chrispsn can't you do that now?

pressing ctrl-enter changes the # part of the url

you can drag that into your bookmarks and thus "save" the code

chrispsn

i mean a way to get the puzzle input into the window

xpqz

13:17

@ngn github.com/jshinonome/vscode-k9

ngn

@chrispsn ah..

yeah, we need that or at least 1:"http://.." in the wasm interpreter

ngn

13:51

@dzaima's timings of dzaima/cbqn vs ngn/k:
https://dzaima.github.io/paste/#0U1HITcxOVchWcHa2Tc5JzEtXUFbIS8/Tz@ZSgciU2OblZ2WWKKTZquv6Gyvounh5hsQHhzgGhdjqGqorJAPVOzsF@nFxKcSUKFQbalfUqisaGkAAl6GJiRGXgoKCJljqw9ypK2sPrXjUNhWuwNjQUM80txiqu0IbCSKbY2JiYAozB2SKNl4CzQ5LAwuoHdUaMEE7TSBTW1O/otaECypmAnEDdiWW5iDrDQ0ede3QVnjUsCi@PCMzJzVeAa4aKGGnqYBsGNi1ROgwMtazNAY6DwA

i can confirm i get proportional timings to those

his interpreter is now faster than mine

rak1507

what about non '

ngn

that's less important as statistically most code is scalar code

dzaima

@rak1507 I haven't yet started working much on optimized vectorized code, so ngn/k should easily be faster than CBQN on everything array-y

rak1507

@ngn not in an array language surely

@dzaima ah, fairs

ngn

@rak1507 i've heard rumours that one apl-using company decided to measure the avg array length in their application and it turned out to be between 1 and 2 :)

rak1507

13:56

lol

ngn

now should i destroy ngn/k.. ?

or send troops to capture and drug dzaima until he forgets about this bqn nonsense and starts doing k instead? :)

dzaima

a k interpreter in the CBQN vm should be possible (most complex thing is n-arg functions). but, unfortunately, i have BQN to worry about for now :)

ngn

@dzaima why worry about it when you can worry about simpler languages and focus more on optimizations?

dzaima

oh i'm already focusing like everything I've got on optimizations constantly. And have written like almost no optimized code for high-rank arrays anyways :)

chrispsn

@ngn I know you are not serious but: please do not destroy ngn/k

So the speed difference is because of interpreter/vm stuff rather than language design?

ngn

14:12

@chrispsn the problem is, a slow ngn/k gives k a bad name.. i assume you've read marshalls "there's no evidence that k is fast" :)

@chrispsn of course. how much bqn have you seen? it's even worse than apl (in terms of language design)

xpqz

@ngn That's not quite how I read @Marshall's article; more that some of the more outlandish claims of k's speed are more marketing than science.

ngn

@xpqz he is wrong

news.ycombinator.com/item?id=28366488

so, the claim that it's all marketing over science is wrong, and the claim that dyalog is 30x faster than ngn/k is also wrong - he was comparing +/ on a tall narrow matrix without splitting apl's matrix

dzaima

14:29

to be fair, that 30x thing was followed by "It's fine to say—as many K-ers do—that these cases don't matter or can be avoided in practice"

ngn

"fine to say"..

dzaima

point is that high rank allows you to do more things without worrying about performance. the 30x is small example in one point of the many in the article

xpqz

Reading geocar's entry doesn't seem to contradict @Marshall's claim that you're barred from publishing your own benchmarks? That you can always repeat pre-packaged sets doesn't really tell you anything beyond that a specific test case, defined by someone else, takes X s to run on some other system?

ngn

@dzaima no, he just had to use the flipped representation

@dzaima it was the only point mentioning something specific about my impl

dzaima

@ngn which could take effort and code redesign. some people don't like doing that. you being absolutely fine with it doesn't mean everyone is

ngn

14:35

@xpqz "there is no evidence" != "i have no access to such evidence". the evidence is there. it just costs a lot to access it.. and yeah, i too think that's bad. but that doesn't make k any slower.

@dzaima all it takes to do the fair comparison is a flip (monadic +)

@dzaima even dyalog sometimes recommends using "inverted tables" as roger calls them

dzaima

@ngn but the comparison is specifically about the fact that k requires you to write your axis in a specific order to be fast. that's the whole point

ngn

@dzaima i don't think the average reader would perceive it that way

dzaima

but it's literally followed by marshall saying this case doesn't matter in practice

ngn

i think this was a pr stunt to promote his own language more than a genuine attack on k or a protest against commercial benchmark suites

@dzaima if it doesn't matter why is it in the article at all?

dzaima

@ngn because it's still a point about how k restricts how you can write fast code

ktye

14:45

@dzaima what's your guess, why cbqn is faster for scalar code?

dzaima

concluding from the case being avoidable that it doesn't need to be mentioned is like saying an article about "JS bad" doesn't need to mention all the avoidable bad things in JS

ngn

@ktye obviously ngn doing unnecessary thing in some of his functions :)

xpqz

@ngn if you want some more tests, I've consolildated all the competition solutions in one file, with complete tests: github.com/xpqz/dyalogk/blob/main/tests.k

400 lines of k. Presumably longer than kOS.

dzaima

@ktye scalar performance is an extremely important thing I constantly work on and test. I think the most important thing I'm doing everywhere is managing inlining (and outlining - extracting rare cases to a noinline function) & shortening the number of steps in the fast path case (have spent way too long on that and made many things ugly (but still fast) in the process)

ngn

@xpqz ooh, big thanks!

@xpqz can i integrate them in ngn/k's repo (under the agplv3 licence)? if yes, how should i credit you - link to the original repo? name? ..

xpqz

14:57

@ngn Of course. No credit required, but a link to repo would be appreciated.

ktye

@dzaima and the general architecture, is it a byte code interpreter?

dzaima

@ktye yeah (except the instructions are 32-bit ints to allow for larger constants without limits of 255)

coltim

15:12

the claims around K fitting into L1 making it fast have bugged me too. the restrictions on benchmarking the official K's are frustrating, but I'm not sure that ngn/k is a valid substitute for that purpose. I think this claim (and some others, like K is as fast as/faster than C or whatnot) come from a specific time and place where K was competing directly against C for the purposes of implementing trading systems. Java went through the same stuff

dzaima

interesting note from a question in matrix - the vm itself isn't the slowest part

coltim

(the "problem" with Java was garbage collection causing unacceptable latency spikes. presumably this has been improved in the past couple of decades, but in the mid/late 90s it was likely a valid concern)

dzaima

so that's ~400ms spent in the vm, vs 270 in the case of CBQN, which is a lot closer

ngn

15:30

 0n=0%0 / i hate nans >:(
0

dzaima

@dzaima ..which is pretty good, considering that this (which i assume is the main vm loop?) doesn't look like it'll convert to a nice lookup table switch

ngn

@xpqz shorter p143:1_*+(|+\)\[;!2]@

@dzaima i've tried using a switch before but didn't notice much difference

dzaima

@ngn right, I doubt it would as-is, if just +' alone is already 2x slower than the whole vm & bytecode process :)

ngn

so, i need to rethink "each", i guess

dzaima

15:46

this is where my monadic ¨ ends up in this case. Specialized loop for an i32arr argument, and it directly calls the specific function pointer from the operand. 25 x86-64 instrs

ngn

16:01

@dzaima an entire .c file dedicated to "each"?! and i thought my 10-15 lines were too much code :)

@dzaima tbh, i don't understand any of this, but you probably don't understand any of mine either

dzaima

yeah, I went extreme with each. It was the first non-trivial thing I wrote for CBQN, and hasn't changed much since then

ngn

and you don't have 3+ adic each

dzaima

yeah. But even if I did, I'd still have special-cased monadic & dyadic and then a separate slow 3+ adic

ngn

right, special-casing those makes sense

dzaima

@ngn it's just for(i=0;i<length;i++) res[i] = f(operand, x[i]); where f is a C function pointer (in the case of {1+𝕩}¨ it points to the entry of function block monadic calling). but yeah, i don't even know where to find your each impl. But I don't think you need to go that crazy to have a good each

(there's of course some type conversion and overflow checking in the real code, as you can see from my link not being literally that, but that's unrelated sad mess)

ngn

16:14

@dzaima there. A1 is the type of a pointer to a monadic function.

probably still not "readable", as everything's abbreviated

dzaima

i can somewhat get by with your source code when i have an entry point to start with and ability to click things to view their definition

dzaima

16:26

eac itself in the perf report takes only 2% of time; the 3 functions it calls - apd, get, app - take much more time

ngn

apd=append, get=indexing, app=apply

dzaima

huh, would've expected append to be slower than apply

ngn

for things like +' eac() could look up the implementation of add() and call eac1() with that. i didn't think it would matter much..

@dzaima append only has to check the types and make sure there's enough room to put the new item at the end

dzaima

in CBQN, even a generic call to a monadic function takes: 1) check that it's a function; 2) untag pointer; 3) read field; 4) call it

@ngn but apply has to just call a function?

ngn

and that function has to do things..

idk, i'm just guessing

dzaima

16:32

but that doing of things shouldn't be part of the app function itself

ngn

i thought these were cumulative times

maybe a switch or two in apply() can help :)

ok, let me test..

dzaima

those should be times in the function itself, and none of its invocations (inlining can merge functions together though, but i don't think that should happen here)

(also, fwiw, my switches all have default: __builtin_unreachable(); to let the compiler know to not worry about bounds)

damn, "app" is huge
https://dzaima.github.io/paste/#07R1Zc9vG@T2/AklnWkCCKVzERVEaRU46HieOr9pKPBwNjoVNi4JoEpJAVe1j39P@w/6SfotDxLG7AESqoiJzxhaJxS72O/e7duFMp7zA7Xw6O0U7/pUzPnV2Po6jnZOdk29@uEBhZHPewpug@TffvEQzDy5w2ecbrvxh/346njvzOTp1JwvuLODmyIvGZyHXi1Ac2eyu0s1Hky1DkrhdZzrdq3RyMBg2ofcb7kDmkRyISObj6HA/fmd/h2az78RYEAh3OheBeLAYnh0MXm1Nh87s48XgPb81FRdfeOfwCr5tbwuC4ExlfkEZAYXpCG/Eq3QYNERhMgoSX02HW2h7W/wynG7Px/xU/MvwL8IAxvbewPCncOELjD64Sh/2Zfvbb7fwhcXQOYXnXQmD@Ilzvp8/3V4Qnx8DrPE4Amiv9j9OeLhPFgYS6dbP80A8OuTfH7z5mT90P2iSpY8Gz7jP82N04Uz4wy3xmYj/EwbPwmF@NT4U41B0xTe/cS5MiJeEgXMY8q4YCsKLZCgUAqph2kcHPHI8@C7C…

ngn

@dzaima yeah

dzaima

oh wow

ngn

actually, it can't be one big switch :(

dzaima

16:45

i assume tagged data vs heap-allocated objects or something?

@dzaima ah, that's the imperative equivalent of a virtual function call. yeah, that would be long. but I get away with it being a bunch of small functions and not one big one so it seems less bad :D

ngn

@dzaima no, it's just that some types require a certain number of args and overapplication could lead to either a rank error or making a projection

and some types are not even real types but collections of types, like Xz(..) means if(x is any kind of int){return ..}

dzaima

yeah, i see how that'd be a mess to switchify

I designed CBQNs object tags & types so it'd be as simple as possible to select a specific thing you want

ngn

@dzaima where do you store the type? in the bits before the pointer or in the header or both?

dzaima

both

ngn

i store the type together with the value as long as it's not a pointer

dzaima

16:56

this is how all function objects look. Then there's this field for heap-allocated objects that specifies what kind of function it is (user-defined block, builtin, etc)

ngn

if the type is 0, then it's considered a pointer and the real type is in the header

dzaima

i don't waste the tag bits for pointers :)

ngn

but i don't like having "type" in 2 places..

@dzaima is + a "function" in bqn?

dzaima

yeah

and it's heap-allocated

which does kind of suck, but does unify its handling with all other functions

ngn

how do you tell the difference between a user-defined function, +, derived functions, etc?

dzaima

16:59

that heap object type field

@ngn CBQNs two types each do their own thing though. The tag shows user-visible type - array/char/number/function/modifier/namespace; the heap type shows the actual internal implementation

@dzaima it's t_funBI for a built-in, and t_fun_block for a user-defined block. But in most cases you don't need to care about that

a call to one is always "untag, read field, call that"

ngn

ok, so you don't dereference the pointer when you only need to know it's a function in general

(if i understand correctly)

dzaima

yeah. isFun only looks at the tag

@dzaima but + is always gonna be in cache

ngn

on the other hand, when you do need to dereference, you have to do some bit manipulation to clear the tag

dzaima

yeah, that sucks

ngn

use tag 0 for something :)

dzaima

17:03

can't, that's a valid float :/ (i use NaN-boxing)

ngn

oh, 64bit floats are like that too.. ?

dzaima

yep. 64bit floats are always just the float itself and never heap-allocated

ngn

screw floats, pointers are more important :)

dzaima

yeah, adding a constant to make some pointer have a tag 0 is a thought I've had. JS engines do that

to note is that CBQN doesn't have any atom integer objects other than f64

those would complicate implementation a lot :)

ngn

i was just gonna mention 32bit int - most numbers you're gonna deal with are gonna be those. i know your numeric tower is float-only.

dzaima

17:07

yeah, 32bit int is the most frequent, but doing arith on them as floats doesn't cost much (and you gain having only a single type to worry about)

ngn

but your floats are stepping on the toes of the tag

dzaima

sadly

so there are two options: 1) have some zero tag, and scalar fns have to worry about both i32 and f64; 2) no zero tag, but scalar fns are very simple

ngn

if you stored 32bit "small int" floats in the tagged value, and big bad floats in the heap, the tag would be more pleasant to work with.. i think

dzaima

and would solve these two tag tests being very awful

ngn

what is x.u?

dzaima

17:11

B is a union. x.u reads it as u64

ngn

ah, i see. you know you can write *(u64*)&f and *(f64*)&l ?

dzaima

that's, uh, longer :)

ngn

could be a macro or something. helps get rid of the union, but probably doesn't matter much

dzaima

the union means i can't accidentally return a raw untagged integer. and since most things outside h.h don't need to look at the internal value manually, that's a good trade imo

ngn

fair enough

interesting conversation but i'll have to start cooking dinner

dzaima

17:18

@ngn in fact, originally I planned to actually have a separate i32 scalar type. But after writing a lot of code, i decided the extra complexity probably isn't worth it

(i never actually wrote any code for scalar i32 though, so who knows. maybe worth coming back to at some point)

ngn

17:51

@dzaima well, you know what i think :) apls's and bqn's numeric towers are wrong. floats should be kept separate from ints.

dzaima

but one tower is less towers!

but yeah, i kind of agree that floats would be nice to have be separate

but it would make things more complicated

ktye

19:38

@dzaima you are talking about no int-atoms. do you have int arrays? or is every number a float?

dzaima

there are int arrays (32-bit, 16-bit, 8-bit, and, as of recently and largely still unoptimized, bit arrays)

ktye

but these are only internal optimizations, for the user there are only numbers, right?

dzaima

yeah

that's just the BQN array model - there are only floats

ngn

javascript's and dyalog's too, though dyalog extends it to complex and has some nasty complications with ⎕fr←1287

Transcript for