@ngn have you seen the gcc/clang builtins for multiplication overflow? the note about "promote the first two operands into infinite precision signed type" sounds a bit slow though

@coltim yes, i've seen them. if i understand correctly, the "infinite precision" thing is just to describe the semantics, not the way they actually work.

when i tried using __builtin_add_overflow() in a loop, the compiler (at least gcc; i'll try clang later) couldn't vectorize it as i hoped, but luckily it does vectorize the trick for detecting overflows manually: (x^r)&(y^r)

for multiplication, i'll probably have to go with marshall's advice and temporarily cast to a wider type

I was toying with the idea (if I ever get to implementing another K) of having a 2-level page directory, which would make append (and possibly prepend) an O(1) operation, Copy-On-Writes become per-page, at some cost for random access, and minuscule cost for vectorized operations. In such a setting, "upgrade on overflow" can be done per-page and may actually be the most reasonable implementation.

@ngn thinking about the question of what deep where should return for a ragged list

in theory if atoms are constant functions then "c" . 0 1 2 ... would return "c" ?

in other words it might not matter whether 'missing' levels are filled with 0N or 0 as long as ~/"c" ./: 0N 0

and of the two, you'd probs prefer 0N to preserve more info re: the depth of each leaf

it would imply that indexing beyond the max depth shouldn't be a rank error:

 0 1 . 0 1
'rnk
0 1 . 0 1
    ^

and yes, as previously discussed if we had the room i think it needs its own slot, separate to 'shallow where', to remove the discontinuity

I was thinking 'why isn't there deep group' but maybe it's less useful? (And 'deep grade'?)

@beagle3 does that mean double indirection? and no prefetch, because the pages for an array might not be contiguous?

@chrispsn 0N to preserve more info - yeah, good point

@chrispsn another option is :: which is supposed to act as a universal array-preserving index

@chrispsn i've no idea what that would mean. <x =x >x are inherently shallow - working only at the first level of depth.

@ngn they'd be finding indices of atoms, in their respective ways

@chrispsn what if you do want to sort/group a list of compound structures?

@ngn shallow group/grade are unchanged

I'm not saying those primitives should exist - merely that they are similar 'holes' to deep where

@ngn that's interesting

of course :: would blow up int lists into generic lists..

'Deep where, grade, group (and I suppose) find and without' are all just fully atomic variants of the existing shallow primitives

Which suggests it could be a verb attribute or adverb

Rank-sensitivity could be another one

@chrispsn how often do you need that..

even deep where for a rectangular matrix is rare enough

Oh I agree

now there's this big question of find's rank-sensitivity. find is important - it's used in many places, sometimes invisibly to the user.

'Deep without' came up here chat.stackexchange.com/transcript/90748?m=56701113#56701113

@ngn in your view is it equivalent to the question 'what should be the result of indexing into a dict'?

@chrispsn yes, dict indexing is d[i] <=> (. d)@(!d)?i

I'm still absorbing your notes from chat.stackexchange.com/transcript/90748?m=56796867#56796867

but i'd be very reluctant to implement ? this way

classic example: x?"ab" - i want this to find the positions of "ab" in x (or 0N if not found), whatever the inner structure of x may be

What about table?dict ?

@chrispsn you mean what find should do with them?

@ngn yeah, as in table find dict

@chrispsn i'm not sure. a table is conceptually a list of dicts. dicts - sometimes they act like scalars, sometimes like lists.

with rank-sensitivity, i guess it would be t?d <=> (+.+t)?. d

with flat find, i guess: t?d <=> *(+.+t)?,. d

@chrispsn what is your answer? :)

I think it should be an atom but I need to check in my morning

@ngn fwiw, I like the "rank-sensitive" version more. as I tried to articulate earlier, ? and its derivatives feel different than the other primitives since they're centered around relating otherwise disparate data. so putting a finger on the scale of making that "easier" (versus maintaining the structure of the right arg/consistency with other primitives) feels worth it

@coltim heh.. looks like arthur was right, again :|

@ngn the design of k kinda makes me think of that japanese sword forging method of flattening and folding the steel 20 times

@ngn For gather/scatter it means double indirection, yes. But for vector operations, it means one additional indirection per page (so, for an 1024 element page, 1/1024 more accesses - less for longer pages). But you can still prefetch a page in advance. It's basically adding another foreach(page in array) loop around the linear per-page implementation, and you can prefetch the next page when you start this one.

@beagle3 i see. so that's a bit like doing the job of the memory controller.

or: a bit like adding a second layer of virtual memory

just like page tables map virtual addresses to physical ram, your two-layer system maps array slices to their adresses. did i understand correctly?

@ngn well, yes, sort of. assume you have a vector with 10G floats, and you want to change one item in it. With linear arrays, you have to make a complete copy, paying both memory and CPU/BUS bandwidth. If the operating system let you play with the page tables, you would have been able to pay just virtual address space, but no memory and no bandwidth. In the simplest form, that's all such a 2-level thing will do.

But the reason I was reminded of it was the discussion about restarting with a different size after overflow; For very little additional cpu, you can make different pages different size ints; and then a restart would (a) only apply to the latest page, not from the beginning, and (b) wouldn't necessarily apply to the end.

it's somewhat complicated though

@ngn you mention "slices", I was talking about uniform sized pages (was thinking of a compile time constant). For full-vector operations, general slices aren't even more complicated, but for gather scatter there is no solution I'm aware of that's not extermely complicated or O(log n) instead of O(1) per element

@ngn It's not simple, no, but no auto-enlarging solution is. You have to pick your complexity poison there (or trigger an exception and move complexity to the user)

given i'm struggling with implementing overflow detection.. :) i must simplify things a bit before going further