dzaima

> What I'm saying is that the typical change to a file shouldn't be committed to my local repo until I indicate that it's ready.

I was extremely hostile to this aspect of jj too, but I've settled on a workflow where @ (i.e. the change/commit referring to the working copy) is always the same, named ".WIP: …", and as such is clearly never supposed to break out of the local system, and can never accidentally get pushed down the log. (..my jj workflow is just blatantly copying my git workflow (with the same-name shell aliases/helpers even), but even with said git emulation I'd say it's nicer than git itself)

Still may be weird/undesired to have the local repo preserve the changes (especially annoying if it happens to find an unignored build artifact, though there is a size limit for automatic tracking by default), but it's also rather neat that you can dig out your old deleted printf debugging or whatnot later on if you wanted to.

Unfortunately I cannot find where I had read that, might've just misinterpreted discussion about delays as about dropping messages / interpreting messages as answers to questions I didn't actually post... Sorry for the unnecessary negativity!

FWIW, my specific room didn't lose much due to the missed syncing, I manually copied over the lost messages (..and we're used to doing so due to the flaky discord bridge). I just noted it as it seemed like a generally relevant thing (and of course perhaps more important for other affected rooms). Thanks for looking into it though, good to know that's at least not how it's supposed to function!

Thanks for the link to the postgres discussion! An incident report would definitely be interesting.

I haven't reported the missing messages thing anywhere as I assumed that was just expected (IIRC (and this is a big IIRC) it was mentioned a long time ago (i.e. entirely unrelated to this) by TravisR on Discord bridge problems as a possible cause for missing messages).

Here is one event in an affected room, made by a t2bot.io account on July 6, to which t2bot.io accounts can reply to, but which gets an "Event not found." error when requested by me, @dzaima:matrix.org: (and for reference t2bot.io functioned properly on other rooms during that time, so overall t2bot.io↔matrix.org federation should've been fine; and for reference there's a third homeserver that federated with t2bot.io fine in that room just fine too; and to be clear the room works fine now)

    https://matrix.org/_matrix/client/v3/rooms/!WpdazzauuDxyGNAiCr:matrix.org/context/$BM9s8e3vUhk_iHfdg7D_s7CsQ5COFSPdlJdygz7TKvU

I've heard that messages not getting through federation in some cases is just a thing that can happen. How that's compatible with calling matrix as having good federation, I don't know.

The issue of broken rooms was reportedly the database having gotten corrupted indexes, which affected a bunch of rooms (2/55 of ones I was in): https://github.com/element-hq/synapse/issues/18606#issuecomm....

Not much a protocol/implementation can do about that. It did take over 2 weeks for it to be resolved though, which is a rather long period of time.

Also on the status page - https://status.matrix.org/incidents/8gljb3gtlv11 (shows start at Jul 2, but I noticed it on Jun 28)

After that was resolved, messages that were sent and received by/on other homeservers during that time never ended up on matrix.org, so much for federation :/

Ah, that appears true. I just tested some commit creation & state inspection commands, didn't bother with network stuff.

A property of the initial XOR trick for 2 different elements is that it guarantees finding a way to partition in one pass (and with very trivial code; no hashing involved!), which is lost by replacing that with hashing. (the original trick does take two passes - finding the bit to partition on, and doing the actual partitioning, whereas hashing is 1+ε passes, but the first pass in the original is just an xor-fold, and the partitioning really only needs to be a "accumulator ^= (current_val & mask) ? current_val : 0" (other partition is just xoring the results of both passes), both of which can be trivially parallelized and SIMD'd with O(1) extra memory usage)

The approach in my comment achieves guaranteeing finding partitions, and still avoids actual hashing or anything strictly-probabilistic, but does still lose the extreme triviality and mechanical sympathy of the original approach.

Git - jj[1] uses gitoxide for its git interop/backend (git being the backend of jj you're expected to use), both Apache/MIT; it functioned so cleanly I assumed it was invoking git directly, but apparently it's all custom!

For new things I'd guess PostgreSQL vs MySQL is probably on the same order as llvm vs gcc; probably with PostgreSQL being better off than llvm even.

[1]: https://github.com/jj-vcs/jj/ (started by a Googler as a hobby project, now their full-time job at Google, so kinda fits into the "big orgs will replace things with permissive-licensed versions" narrative)

A rough sketch for a more direct way to extend the XOR trick to finding more than two differences:

For e.g. 3 differences: instead of a binary xor (i.e. binary-digit-wise sum mod 2), do a binary-digit-wise sum mod 3 (negating one input); a 0 (mod 3) sum result for a given bit means that the bit is the same in all entries, and 1 (mod 3) or 2 (mod 3) mean that you can partition on the bit, resulting in partitions with sizes `sum` and `input_different_element_count - sum`; then you repeat this recursively until they reach containing just 1 difference. (rounding the modulo up to the next power of two instead of odd modulos for the summing is perfectly fine, the final infinite-precision sum is in the range of [0; diffcount] anyway)

Extends trivially to more than 3 differences, and collapses to the basic trick for 2 differences. The accumulator size is O(log(diffcount) * element_size), but the recursive partitioning takes O(n) space or O(diffcount * n) time (plus some logarithm something maybe). Tradeoffs are probably reasonably possible, but the basic hashset approach can reduce its O(n) space requirement at the cost of taking >O(n) time too by partitioning on a hash.

L1 latency is 4 cycles typically (1 nanosecond would be closer). And of course it gets longer if you're chasing through multiple pointers.

It of course depends on the specific program, but, looking at any optimization at the level of separate impacted assembly intructions, everything other than mispredictions, division, and vectorization is "just a couple cycles" so that's not really a meaningful way to look at them.

Yeah, I meant specifically C in an ergonomic way with operators working on them and being passable to existing functions.

Though wrapping in different structs doesn't seem to even make gcc & clang properly optimize utilizing the types as non-aliasing: https://godbolt.org/z/r1MT9W9db. Clang just completely fails to do anything, but gcc somehow manages to reorder the load but not do the trivial part of constant-propagating afterwards..

I don't think the usefulness is that skewed towards numerics?

Both clang/llvm and gcc can do alias checking at runtime if they can't at compile-time, which makes loops vectorizable without alias info, at the cost of a bit of constant overhead for checking aliasing. (there's the exception of gather loads though, where compile-time aliasing info is basically required)

And on the other hand there's good potential for benefit to normal code (esp. code with layers of abstractions) - if you have a `&i32`, or any other immutable reference, it's pretty useful for compiler to be able to deduplicate/CSE loads/computations from it from across the whole function regardless of what intermediate writes to potentially-other things there are.

Rust's aliasing rules are very different from C's.

In C you have a nuclear `restrict` that in my experience does anything only when applied to function arguments across clang & gcc, and type-based aliasing which is both not a generally-usable thing (don't have infinite different copies of the int64_t type (and probably wouldn't want such either)), and annoying (forces using memcpy if you want to reinterpret to a different type).

Whereas with Rust references you have finely-bounded lifetimes and spans and mutability, and it doesn't actually care about the "physical" types, so it is possible to reinterpret memory as both `&mut i32`/`&i32` and `&mut i64`/`&i64` and switch between the two for the same memory, writing/reading halves of/multiple values by the most bog standard Rust safe reads & writes, as long as the unsafe abstraction never gives you overlapping `&mut` references at the same time, or split a `&mut` into multiple non-overlapping `&mut`s.

re edit - While the hardware differences are significant, some by necessity, some by tradition, it's not my point.

My specific point is that "how to write code that is generic across block size, boundary conditions, and thread divergence." is just not the correct question to ask for many CPU SIMD use-cases. Many of those Just Do Not Fit That Paradigm. If you think you can just squeeze CPU SIMD usage into that box then I don't think you've actually done any CPU SIMD beyond very trivial things (see my example problem in the other thread).

You want to take advantage of block size on CPUs. It's sad that GPU programmers don't get to. In other places I've seen multiple GPU programmers annoyed at not being able to do the CPU SIMD programming paradigm of explicit registers on GPUs. And doing anything about thread divergence on CPUs is just not gonna go well due to the necessary focus on high clock rates (and as such having branch mispredictions be relatively ridiculously expensive).

You of course don't need any of fancy anything if you have a pure embarassingly-parallel problem, for which GPUs are explicitly made. But for these autovectorization does actually already work, given hardware that has necessary instructions (memory gathers/scatters, masked loads/stores if necessary; and of course no programming paradigm would magically make it work for hardware that doesn't). At worst you may need to add a _Pragma to tell the compiler to ignore memory aliasing, at which point the loop body is exactly the same programming paradigm as CUDA (with thread synchronization being roughly "} for (...) {", but you gain better control over how things happen).

I haven't used CUDA (don't have nvidia gpu), but I've looked at examples of code before. And it doesn't look any more simple than CPU SIMD for anything non-trivial.

And pleasepleaseplease don't have locks in something operating over a 20-element array, I'm pretty damn sure that's just simply gonna be a suboptimal approach in any scenario. (even if those are just "software" locks for forcing serialized computation that don't actually end up in any memory atomics or otherwise more instructions, as just needing such is hinting to me of awful approaches like log(n) loops over a n=20-element array, or some in-memory accumulators, or something awful)

As an extreme case of something I've had to do in CPU SIMD that I don't think would be sane in any other way:

How would I in CUDA implement code that does elementwise 32-bit integer addition of two input arrays into a third array (which may be one of the inputs), checking for overflow, and, in the case of any addition overflowing (ideally early-exiting on such to not do useless work), report in some way how much was processed, such that further code could do the addition with a wider result type, being able to compute the full final wider result array even in the case where some of the original inputs aren't available due to the input overlapping the output (which is fine as for those the computed results can be used directly)?

This is a pretty trivial CPU SIMD loop consisting of maybe a dozen intrinsics (even easily doable via any of the generalized arch-independent SIMD libraries!), but I'm pretty sure it'd require a ton of synchronization in anything CUDA-like, and probably being forced to do early-exiting in way larger blocks, and probably having to return a bitmask of which threads wrote their results, as opposed to the SIMD loop having a trivial guarantee of the processed and unprocessed elements being split exactly on where the loop stopped.

(for addition specifically you can also undo the addition to recover the input array, but that gets way worse for multiplication as the inverse there is division; and perhaps in the CUDA approach you might also want to split into separately checking for overflow and writing the results, but that's an inefficient two passes over memory just to split out a store of something the first part already computes)

It has single-threaded semantics per element. Which is fine for anything that does completely independent computation for each element, but is quite annoying for everything else, requiring major algorithmic changes. And CPU SIMD is used for a lot of such things.

That's because the things GPUs do just isn't what CPUs do. GPUs don't have to deal with ad-hoc 10..100-char strings. They don't have to deal with 20-iteration loops with necessarily-serial dependencies between invocations of the small loops. They don't have to deal with parallelizing mutable hashmap probing operations.

Indeed what GPUs do is good for what GPUs do. But we have a tool for doing things that GPUs do well - it's called, uhh, what's it, uhh... oh yeah, GPUs. Copying that into CPUs is somewhere between just completely unnecessary, and directly harmful to things that CPUs are actually supposed to be used for.

The GPU approach has pretty big downsides for anything other than the most embarassingly-parallel code on very massive inputs; namely, anything non-trivial (sorting, prefix sum) will typically require log(n) iterations, and somewhere between twice as much, and O(n*log(n)) memory access (and even summing requires stupid things like using memory for an accumulator instead of being able to just use vector registers), compared to the CPU SIMD approach of doing a single pass with some shuffles. GPUs handle this via trading off memory latency for more bandwidth, but any CPU that did that would immediately go right in the thrash because that'd utterly kill scalar code performance.

I think LLVM should be able to handle up to less than 65536-bit vectors? At least I saw some llvm issue noting that that's where some things broke down; so a 32kbit vector would be f64x512. But I meant an exaggeration as far as actually using it goes, f64x64 is hilariously overkill even on AVX-512, and utterly awful on pre-AVX512.

If by that absolute value thing you mean _mm512_abs_pd, that's a pseudoinstruction for 'and'ing via a mask that zeroes out the top bit, which can be done equally as well on 128/256-bit vectors, just without an intrinsic for some arbitrary reason. But yeah the gaps are super annoying. Some of my personal picks:

- There's only 8- and 16-bit integer saturating add/subtract, even on AVX-512

- No 8-bit shifts anywhere either; AVX2 only has 32- and 64-bit dynamic shifts (and ≥16-bit constant shifts; no 64-bit arithmetic shift right though!), AVX-512 adds dynamic 16-bit shifts, still no 8-bit shifts (though with some GFNI magic you can emulate constant 8-bit shifts)

- Narrowing integer types pre-AVX-512 is rather annoying, taking multiple instructions. And even though AVX-512 has instructions for narrowing vectors, you're actually better off using multiple-table-input permute instructions and narrowing multiple vectors at the same time.

- Multiplies on x86 are extremely funky (there's a 16-bit high half instr, but no other width; a 32×32→64-bit instr, but no other doubling width instr; proper 32-bit multiply is only from AVX2, proper 64-bit only in AVX-512). ARM NEON doesn't have 64-bit multiplication.

- Extracting a single bit from each element (movemask/movmsk) exists for 8-/32-/64-bit elements, but not 16-bit on x86 pre-AVX512; ARM NEON has none of those, requiring quite long instruction sequences to do so (and you quite benefit from unrolling and packing multiple vectors together, or even doing structure loads to do some of the rearranging)

- No 64-bit int min/max nor 16-bit element top-bit dynamic blend pre-AVX512

Overly-wide vectors I'd say are a pretty poor choice in general.

If you're using shuffles at times, you must use native-width vectors to be able to apply them.

If you're doing early-exit loops, you also want the vector width to be quite small to not do useless work.

f64x64 is presumably an exaggeration, but an important note is that overly long vectors will result in overflowing the register file and thus will make tons of stack spills. A single f64x64 takes up the entire AVX2 or ARM NEON register file! There's not really much room for a "widest" vector - SSE only has a tiny 2048-bit register file, the equivalent of just four AVX-512 registers, 1/8th of its register file.

And then there's the major problem that using fixed-width vectors will end up very badly for scalable vector architectures, i.e. ARM SVE and RISC-V RVV; of course not a big issue if you do a native build or do dynamic dispatch, but SVE and RVV are specifically made such that you do not have to do a native build nor duplicate code for different hardware vector widths.

And for things that don't do fancy control flow or use specialized instructions, autovectorization should cover you pretty well anyway; if you have some gathers or many potentially-aliasing memory ranges, on clang & gcc you can _Pragma("clang loop vectorize(assume_safety)") _Pragma("GCC ivdep") to tell the compiler to ignore aliasing and vectorize anyway.

If your interpreter is interpreting a program with unpredictable branches, of course no predictor will magically make your interpreter get branches better predicted than an equivalent compiled program will.

The question here is about all other branching the interpreter will do. i.e. even if you have a unpredictable `if (a+b < 0)`, there's still the dispatching to the "load-variable" and "add" and "load-constant" and "less-than" and "do-branch" opcodes, that still will benefit from being predicted, and they could very well if you have it repeated in a loop (despite still having a single unpredictable branch), or potentially even if you just have a common pattern in the language (e.g. comparison opcodes being followed by a branch opcode).

The timestamps just get moved around sometimes: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...

More generally than the other replies, BQN is an array language, and as such "a+b" & "a×b" etc automatically map over arrays, and the interpreter can thus trivially vectorize them (and, if you're curious, yes, in a naive interpreter (which CBQN currently is) this does mean intermediate arrays go through memory, which is probably a significant part of the difference in speed).

As a fun note, here's a talk of automatically reordering LLVM passes to optimize for code size, which seemingly worked enough to make a talk/paper about: https://www.youtube.com/watch?v=_SqWd74zG2Y

Yeah, it is a good bit down; that said, bump allocators are a very common (most common?) option around GC anyway; I personally scrolled straight to the disassembly, and it's pretty clear from that, and the explicit mention of bump allocator is just around there too.

The article does include:

> The allocation fast path of the RPython GC is a simple bump pointer,

and the assembly for it.

Indeed a bump allocator has the disadvantage that it effectively continuously thrashes the lower cache layers, but I'd think that'd be a pretty universal workload-independent issue. (and the cache's LRU will still preserve used parts in the cache, and the thrashing is by definition gonna be pretty evenly spread, giving the user code plenty of time to do other things in between using the thing desired to stay in cache again, slightly lowering the issue)

And given that a Python impl will necessarily need to have a GC path anyway, which already will thrash cache (and Python users aren't and won't be writing free()s regardless), it's probably not a bad trade overall.

I'd assume for pushing to lists the runtime just explicitly reserves capacity ahead-of-time instead of trying to integrate into the memory manager in any way. You'd want to do that anyway even if using malloc & malloc_usable_size or similar, as you'll end up reallocating way too much without that (in a quick test I see my system malloc + malloc_usable_size + realloc used to push 100000 8-byte elts ending up reallocating 8500 times, with the entire code being just this, realloc settling on rounding up to the next 4KB; the actual pointer only changes 10-50 times, but that's still pretty bad, and would presumably get much worse if the code did anything other than just pushing to a single vec)

For malloc/free specific workload is much more important than for a bump allocator; malloc potentially has branching and different cache access/utilization patterns depending on requested sizes or distance/pattern between mallocs & frees, whereas a bump allocator is just bumping a single pointer, with basically zero mispredicts, and very simple linear cache utilization that's easily prefetched.

Beyond what others have mentioned, I think another big differentiating factor between APL and the rest of those languages is that APL isn't focused on allowing the user to expand the language meaningfully, but rather on being a well-rounded language by itself (which is how it can be reasonably useful without objects with named fields, mutation, explicit loops (or only gotos in APLs infancy!), no first-class functions, no macros, and only one level of higher-order function (though of course most APL implementations have some of those anyway)).

As such there's really no pretty "core" that pulls its weight to implement in 1000LoC and is useful for much.

Here's a simple minimal APL parser in JS that I wrote once to display one way of parsing APL: https://gist.github.com/dzaima/5130955a1c2065aa1a94a4707b309...

Couple that with an implementation of whatever primitives you want, and a simple AST walker, and you've got a simple small APL interpreter. But those primitive implementations already take a good chunk of code, and adding variables/functions/nested functions/scoping/array formatting/etc adds more and more bits of independent code.

Perhaps if you accept defining bits in the language in itself via a bootstrap step, BQN is a good candicate for existing small implementations - a BQN vm + minimal primitive set is ~500LoC of JS[0] (second half of the file is what you could call the native components of a stdlib), 2KLoC for first public commit of a C impl[1], both of those having the rest of the primitives being self-hosted[2], and the compiler (source text → bytecode) being self-hosted too[3]. (the C impl also used r0.bqn for even less required native primitives, but modern CBQN uses very little of even r1.bqn, having most important things native and heavily optimized)

[0]: https://github.com/mlochbaum/BQN/blob/master/docs/bqn.js though earlier revisions might be more readable

[1]: https://github.com/dzaima/CBQN/tree/bad822447f703a584fe7338d...

[2]: https://github.com/mlochbaum/BQN/blob/master/src/r1.bqn (note that while this has syntax that looks like assigning to primitives, that's not actual BQN syntax and is transpiled away)

[3]: https://github.com/mlochbaum/BQN/blob/master/src/c.bqn

The precise requirements of IEEE-754 may not be important for any given program, but as long as you want your numbers to have any form of well-defined semantics beyond "numbers exist, and here's a list of functions that do Something™ that may or may not be related to their name", any number format that's capable of (approximately) storing both 10^20 and 10^-20 in 64 bits is gonna have those drawbacks.

AFAIK GPU code is basically always written as scalar code acting on each "thing" separately, that's, as a whole, semantically looped over by the hardware, same way as multithreading would (i.e. no order guaranteed at all), so you physically cannot write code that'd need operation reordering to vectorize. You just can't write an equivalent to "for (each element in list) accumulator += element;" (or, well, you can, by writing that and running just one thread of it, but that's gonna be slower than even the non-vectorized CPU equivalent (assuming the driver respects IEEE-754)).