@ngn in "x div y" y(divident) may be 64bit. same for mod. you need large x as well?

@ktye yes, for project euler, e.g. in miller-rabin primality testing

i did it with recursion: divide by 2*x, multiply the result by 2, and add the last bit depending on how the remainder (from the division by 2*x) compares against x

but there might be a better way

From reading arthur's k.h, it seems k9 vectors are limited to length 2^31 ; I find that surprising, especially since the lowliest Raspberry Pi ever had as many addressable bits, and that arthur likes to post benchmarks involving 10B trades and quotes. What am I missing?

@beagle3 i asked arthur directly. "the arrays are distributed on many processes. k9 has room for unlimited vectors but 4B can be a nice limit -- time to think about going parallel."

@ngn Thanks! He's not wrong, but ... it's rather arbitrary (or he doesn't want to have a 12 or 16 byte object header :) following him through the years, I suspect the latter).

@beagle3 i think it's just that 32bit calculations are faster. the size of the header doesn't matter that much.

Is the entire header packed into 8 bytes? I could see that making it easier to pull into a register and pick out the parts you want to

@coltim so, 4 bytes for length, 4 for refcount, and there isn't room for anything else?

@ngn I'm just going off of @beagle3's comment about having a 12 or 16 byte header

Also I wonder if 4 bytes for the refcount is necessary or if you could go with some smaller amount. Plus maybe you could pick up a few bits from stuffing things into pointers (even more than "normal" if you want to align arrays for wide-SIMD ops)

@coltim 3 bytes for refcount would mean more processing and a larger binary. i'm not sure if a 2-byte refcount would cover realistic uses of k.

The k.h that arthur posted to the mailing list indicates 1 byte for type and 4 bytes for vector length, and nothing else; not sure if the sorted/unique bits are in the type or not, but that surely leaves 16-24 bits for refcnt. Unlike vector length, refcnt is an optimization - if you have too many references, make another copy, it would be slower but semantics won't change

@beagle3 so, every time you increment the refcount of a k object, you'd have to check for overflow?

@coltim for sure, the k.h macros use the upper 16 bit of a K value for type, and the lower 48 for value (which I would assume is the value itself if it is <= 48 bit) or pointer to value (macros exist for j, f). So the type byte is not even strictly necessary - perhaps that macro is a red herring to keep us guessing :)

@ngn well, you have to anyway - unless you have a 56-bit refcnt (or however much is needed to saturate your virtual address space), you might overflow. It's an unlikely/cold, but .. You either have to do it on each incref or at other strategic points that guarantee you won't overflow (and the exact number at which you overflow makes little difference)

@beagle3 red herring - i don't think arthur does that :)

What are realistic numbers for the maximum value a refcount would hit in practice? Even 255 seems high?

@coltim if empties like () are shared, 255 isn't that much

even if () isn't shared, 256#,,anything would reach the limit

@beagle3 what if you use a 4-byte refcount and don't check? would anybody notice.. :)

@ngn how bad would it be to use saturating arithmetic? I guess that would mean things could get stuck and never freed, but if that's rare/unexpected...

@ngn Given that even f and j are refcounted, 5000000000#(0;0.0) which only takes 40GB or so of ram.... :) The place you'd notice is when you try to destroy a copy of that, and decref from 2^32+1 down to 2^32 (assuming unsigned refcnt), freeing the memory, and then have all the dangling pointer fun.

Is using the high 16 bits of tagged pointers workable going forward? The newest intel chips expand the virtual address space from 48 to 57 bits (en.wikipedia.org/wiki/Intel_5-level_paging)

@coltim No, it isn't, not in the long run when you'll want to mmap more than 250 TB in the same address space, but there's likely time until that happens, and you could use multiprocess (as was done with 32-bit k4) as a stop gap measure until k12 that resolves this comes out :)

/me still has fond memories of the early Atari ST / Amiga / Mac days, when we used the upper 8 bits of the 32-bit address registers for data&tagging, because ... 16MB of address space is so much already (and the 68000/68008's limit IIRC) in the days of 512K memory (1024K if you're rich!) that it's not worth planning for the future.

@beagle3 Is it dependent on actually using more than the 250TB limit, or is it dependent on what hardware the code is running on?

Ah, it looks like unless your application goes out of its way, no allocations will use anything above 47 bits: lwn.net/Articles/717293