not really. The first version just leaked all over the place and had some design issues (though it did have some sweet simd). So I've started reimplementing it (actually, this is the second re-implementation) and take more care about architecture. But that's only just started

@Moonchild there are a few wrong assumptions in your question. apl doesn't have to produce garbage. every apl object could be collected the moment its refcount drops to 0. dyalog (note that apl≢dyalog) does produce garbage and needs mark-and-sweep gc only because they misdesigned namespaces (and that will be forever so because backwards compatibility).

namespace mutability ("reference semantics" as opposed to "value semantics") allows the creation of cycles in the object graph - pure refcounting can't deal with that.

@ngn I don't think you're being fair about Dyalog namespaces. They were deliberately designed with reference semantics to support OOP. You're making it sound like an unintentional mistake was made.

@Adám mistakes are never intentional. mistakes can usually be corrected. first step is to realize it was a mistake.

@Moonchild another assumption is that memory management has to be specifically tailored for apl. i think it doesn't have to. the buddy allocator (thanks dzaima for finding that link) works well for any language.

@ngn We've been around this loop before. No, it wasn't a mistake. It probably saved the company (and all the good things that came of it, including your involvement with APL). Yes, it had huge negative implications on complexity and performance, but (unfortunately) sometimes those have to pay for necessary (I know, not for you) functionality.

(does the garbage collector in dyalog even have any performance implications? i'd assume it'd practically never get touched (in cases where it isn't needed, obviously, which is almost always). Complexity, sure, but performance?)

@dzaima If you use namespaces, yes. In fact, if you use namespaces with a ref-count of 0 to the outside (only being kept alive by code that's running), it can slow everything to a crawl, because it constantly tries to clean up.

@ngn if I have an expression like 2-3×6+x, and x is a 1gb array, you don't want to allocate+free 3 additional gb for subexpressions, you want to just allocate one extra 1gb buffer and reuse it for computations. Doing that for basic arithmetic is trivial, for other things may be more difficult.

@Adám that sounds more like an issue of the implementation (why would the running code not count towards the refcount? shouldn't the gc have some cooldown?) than fault of mutability and namespaces (i do realize i asked about dyalog specifically now though)

@Moonchild i would say it's hard even for basic arith, even for experienced language implementers :)

there are many important decisions to be made, and it's not always obvious what the right choice is

for instance: would you allow objects with refcount=0 to be temporarily tossed around? do dyads consume both their args? the memory of which arg(s) should they try to reuse?

@dzaima Possibly. I'd be happy to have this fixed:

'cmpx'⎕CY'dfns'
Stuff←{⎕NEW⍵.(SharpPlot⊣⎕CY'sharpplot')}
cmpx 'Stuff s←⎕NS⍬' 'Stuff⎕NS⍬'

@Adám pretty sure Stuff s←⎕NS⍬ is interpreted as (Stuff s) ← ⎕NS⍬ there

still, it is a 3.5x speed difference

@dzaima Ah, you're right. Just make that Stuff⊢s←⎕NS⍬

(Man, I hate that unparenthesised strand assignment is allowed in dfns.)

@dzaima Apparently, wrapping in a dfn helps. Try:

'cmpx'⎕CY'dfns'
cmpx '⎕NEW(s←⎕NS⍬).(SharpPlot⊣⎕CY''sharpplot'')' '⎕NEW(⎕NS⍬).(SharpPlot⊣⎕CY''sharpplot'')'

@Moonchild Generally you just keep reference counts on arrays, and reuse the array when its reference count is 1. In theory, calling code that will apply a few different functions to one array could choose which of these functions to call last in order to optimize reuse, but I've never heard of anyone actually doing this. Note that reuse is only trivial for arithmetic that you know doesn't overflow.

Allocation costs are pretty low for array languages relative to other interpreted languages unless the programmer decides not to do any array programming. Dyalog uses a very simple rotating first fit allocation algorithm and this is basically good enough.

@Marshall so, if we make two large vectors of the same size, and repeatedly append scalars to both of them, will they be leapfrogging?

Btw, is it correct that we don't have any lightweight online interpreter that can run Dyalog 18.0 (not on TIO, not on TryAPL)?

@ngn In Dyalog, yes, unless you use the append idiom, which overallocates. I guess you can fix that in the allocator, but I wouldn't necessarily consider it an allocation problem.

@Bubbler Yes. Dennis seems to be inactive again, and we're having an internal meeting tomorrow to plan an overhaul of TryAPL.

@Marshall Do you remember why you went with ˘ for Cells rather than ˇ ? The latter fits better with the Rank's ⎉.

@Marshall ⫒ is half way between ⊑ and the generic dyadic operator symbol ○.

@Adám, regarding your "I'd like to see some of the APL-specific uses of the Boolean functions' results, i.e. Boolean arrays, e.g. to generate left arguments for Compress and Expand, the right operand of @, grouping by predicate with ⌸, etc. And common reductions and scans like ∨/ and ∧\ and their combinations. Not to mention ∨.∧, etc. etc." and my suggestions for further content on the first notebook

we discussed the possibility of splitting the boolean content on (+)2 notebooks so I was wondering about dividing it like so: the first notebook could be on boolean algebra in APL and the 2nd notebook could be on using boolean functions for practical stuff, like all the things you mention and more

@RGS Sure, either way works.

@Adám +← 1

@Marshall with buddy allocation the "pockets" are always padded to a power of 2, so this problem doesn't exist. arrays are moved around much less than with first-fit + compaction.

@ngn as a side-effect, you're wasting more RAM, which may or may not be acceptable. And if there was really a need to fix that, it wouldn't be too hard to make any size changing builtin overallocate in any memory management system

@dzaima "wasting more RAM" - not ram but address space! that would have been a consideration ~30 years ago when those were in 1:1 correspondence. first fit + compaction was an excellent strategy back then. but now we've got virtual memory (addresses are backed by physical ram only when you "touch" them) and practically unlimited address space (often 48bit), so the "waste" doesn't matter. it actually helps because the "pockets" have room for growth and are moved around much less often.

@Adám It fits better with ∾≍, which combine arrays in a flat manner. Again, I really don't think ˘ versus ⎉ is worth any sort of effort to fix. No one will forget what one of these primitives is just because they look a little different.

@ngn i guess that's not an issue when allocating new blocks, but wouldn't it still turn up when reusing (or do you have a way of freeing pages from having physical RAM but still be usable?)

@ngn Only for arrays much larger than the page size, right? If you have a program that uses entirely fixed 40-byte arrays, I'd expect it to waste a substantial amount of space.

I didn't say to use rotating first fit though (and my language I allocates in powers of two like you suggest). I was using it as an example to say that pretty much anything will work.

@dzaima (actually, if there is a way to do that, that'd be applicable to any memory management system; other management systems benefit from virtual pages too, buddy has to rely on it though)

@dzaima when reusing - good point. most often reuse happens for same-length arrays, but there may be situations in which pages are wasted like you describe.

@Marshall right. the waste is at most 50% of 2*⌈2⍟sizeof(header+data)

not much of a problem, unless you're using huge pages

@dzaima why "rely"?

@Marshall btw, small arrays could fit in registers (xmm.. ymm.. etc) but the implementation might become a little too fiddly :|

@Marshall also, how do you deal with alignment in a first-fit memory manager? isn't there waste too, of about the same size?

@ngn if there were no purely-virtual pages, buddy allocation would waste a lot (~20%) of ram always, which might be anywhere between annoying and just unusable

@ngn I've wanted to do an APL\avx512 for a while. 16k workspace, half the size of APL\360 initially. But it has hardware support and probably runs like a trillion times faster.

@dzaima but it would still be faster because of less moving around of data. so, depends on the relative costs of ram and time.

@ngn Unless the element type is larger than a word, things are word-aligned in Dyalog. So you waste 7 bytes per array at most (plus 4 bytes in 64-bit because the header has to fit in 32 bits).

@ngn And on how much the programmer catenates arrays together.

@Marshall right.. which leads to another question: what's the point of word-alignment? you still have edge cases with simd. only 32-or-more byte alignment sounds sensible to me (though, it's not really clear..)

@ngn are there other causes of reallocating than what we've talked about? overallocating should get the same behavior as buddy, and if that only happened with ,⍪ or similar, it'd even mean the benefit of not overallocating when there isn't much change likely to occur soon

@dzaima compaction can cause a lot of reallocating

@ngn Handling boundaries with SIMD was a total nightmare.

@Marshall +←1 :)

@Marshall Confusing bits and bytes. It's a 2k workspace.

@dzaima with first-fit you've got this trade-off for ws size: if it's too small, compactions will be frequent, and possibly slow you down. if it's too large, there'll be "waste" in the gaps between the pockets.

@ngn it's literally the job of compaction to compact. Either i wouldn't call it when it's not needed, or live with the consequences as i did want less used memory (and probably got it, even if that means it has to reallocate things which shouldn't have been compacted). (having separate "GC" and "compact" calls would be good)

@ngn maybe i should look up stufff about first-fit before taking any more :p

@dzaima This is why I say problems resizing arrays isn't necessarily an allocator issue. A compiler can often determine that an array will never be resized, so it should have the ability to allocate without extra space.

@dzaima "wouldn't call it when it's not needed", if the interpreter is out of ws, it has no other choice but to compact

@ngn buddy would've already errored by then though, it can't compact :)

@dzaima it can mmap() more memory though :)

@ngn ah, "out of ws" wasn't meant as hitting the system (or user-set) limit, just hitting currently allocated space limits

so i assume first-fit relies on compaction to be usable?

@dzaima kind of.. otherwise fragmentation might prevent you from allocating even a not-so-large pocket

@dzaima Dyalog's does, but I'm sure there are ways to do gradual defragmentation.

@dzaima @Marshall another important question is: does it rely on a firm predetermined ws size? the buddy allocator happily adopts a newly mmapped power-of-2 chunk of memory as its own, so there's no need for an upper limit for the ws

@ngn Not really. Dyalog already starts with a smaller workspace than requested and resizes when it runs out of space (this is way too conservative). MAXWS just stops it from resizing more.

@Marshall does the resize have to be continuous (new memory right after the old, like a stack)? or can the two parts of the ws (old and new) be separated?

@ngn Dyalog uses continuous memory. I'm pretty sure you can map separate sections of memory together though.

Again, no one is recommending rotating first fit.

@Marshall it would be interesting to see what mm you choose for bqn :)

is the ability to split a big allocated pocket in smaller parts that important? how about having buddy without splitting, and with smaller size bounds than a 2× span? (i assume this has been tried by many before, but it seems to me to have the advantages of buddy without nearly as much waste)

@ngn Going to be non-rotating first fit (use once, never look back) for a while. I have some research to do.

@ngn if i'm ever implementing a thing that needs memory allocation, i'm definitely gonna try like all the different methods, if not even making it a choice for the user

@dzaima so, you'd have a predetermined number of, say, 32-byte chunks, a predetermined number of 64-byte chunks, etc? what happens if you run out of 32-byte chunks?

(i mean 32,64,.. or maybe not necessarily powers of 2)

@ngn probably just allocate more. At some point you'd still need compaction, but it would be much simpler and less important

@dzaima i don't understand. compaction in a buddy system?

@ngn still some logarithmic scale (heh, double-buddy - regular buddy with 2*n and 3×2*n, each like a separate buddy system, and allocating chooses the nearest good one)

@ngn it's not really the buddy system anymore, that's very true (^ is a different thought)

@dzaima or the fibonacci sequence

@ngn One thing I'm hoping to be able to do is to incorporate "manual" memory management that the compiler figures out. That is, do lifetime analysis and figure out where everything goes before running a function, then just use computed addresses to run. It can't always be used but it should be possible most of the time.

@Marshall sounds almost like a c compiler :)

@ngn But the allocations usually will need to be computed at runtime to allow functions taking different argument shapes and so on.

@ngn i guess fibonacci would mean still being able to divide while wasting less (but it does mean potentially unusable divisions) and it is indeed an explored idea

@dzaima it also messes up alignments

@ngn word alignment could be gotten by just multiplying by 8. page alignment though..

other than page alignment (3 page alignment is acceptable imo), two buddy systems seem reasonable though

@dzaima so, if a chunk is allocated in the 2*n (power of 2) system and you append to it, and it grows beyond 2*n, should it be moved to the 3×2*n system?

@ngn yeah. (obviously you could keep it in the next 2*n system if it seems preferable, but again, this is more about allocating memory than implicitly optimizing for appending)

@dzaima so, it's just a different waste vs moving tradeoff

@ngn i don't see any detriment to moving, other than it being the programmers responsibility more than the allocators

@dzaima too much moving = slow

btw, powers of two have the advantage that ⌈2⍟n can be computed quickly as 64-clz(n) (the "count leading zeroes" instruction)

@ngn just make growing stay in the current buddy system. i would assume most arrays aren't continuously growing, and for those being in a tighter pocket is preferable. (might mean that having some compaction is good, but here that wouldn't mean losing to buddy)

@ngn it's not that complicated to check after that whether it's in the lower or upper half

allocation has bigger costs than the ~3 cycles spent doing that (though it would involve branching depending on the result, which would be relatively extremely costy)

@dzaima right

anyway, i think that's about as much i can say theory-wise, and i don't really have anything to test this on in practice

@dzaima i wish i could test it in ngn/k but there are too many places where i rely on chunks having size 1<<something

and, other than on a medium amount of medium-sized arrays (where cache comes in play), i don't think it'd mean much of a speed increase either. ¯\_(ツ)_/¯

@dzaima actually i have no clue what i meant there, cache lines are 64 bytes :|

@dzaima yeah, it's complicated. pages, cache lines, multiple levels of cache, prefetch..

my rule of thumb: if you can't prove conclusively that something is faster, choose the simpler/shorter code

@ngn that implies that ram usage pretty much doesn't matter, in which case, yeah, the buddy system is indeed very very good. here i'm more thinking about ways of decreasing ram usage without hurting performance much/if at all

@dzaima so.. no speed increase it is. Doesn't mean it's pointless, but less interesting, definitely

Can anyone think of a clever way to identify the index of odd one out in a vector where all elements are equal, bar one? Here's what I did:

d←243 243 251 243 243
h←{⍺,≢⍵}⌸d
d⍳h[h[;2]⍳1;1]

It gives the correct answer, but sure ain't pretty

⊃(//)↓⍉{(1=≢⍵)⍺}⌸d

{1=≢⍵}⌸⊢⍤/∪

∪(/⍨)1=⊢∘≢⌸

@xpqz Is the vector always simple?

Always simple

Note: seeking the index, not the value

Oh.

so with the above vector, should return 3

∊{⊂⍵/⍨1=≢⍵}⌸

Right! Let me decipher that :)

In Dyalog 18.0, find the major cell that is unique going forwards and backwards: ⍸≠∧⌽∘≠∘⌽

@Adám Ah I get it

@Marshall Ah, that's clever… and another use case for under. ⍸≠⍢⌽∧≠

@xpqz The fast way for a simple vector is to find elements that are not equal to either neighbor, wrapping at the edges: ⍸{⍵∧1⌽⍵}∘{⍵≠¯1⌽⍵}

Replace ⌽ with ⊖ and ≠ with ≢⍤¯1 for arbitrary arrays.

@Marshall ≢

@edom Hi there. Interested in APL?

@Adám @xpqz simpler as ∊{∩/⍵}⌸

@ngn Here comes ngn with a clever reduction again. Also, in 18.0: ∊∩/⍤⊢⌸

@ngn what kind of voodoo is this?

@xpqz +←1, was just trying to decipher this.

@xpqz ⍵ there consists of indices. if it has one element, reduction will preserve it. if it has more than one, we know that they will be different (because ⌸ wouldn't give us duplicate indices), so ∩/⍵ will be empty.

@ngn clever