purplesyringa

small source files

How small are we talking? We've had great success with bzip-style compression on ~400 KB (about 20% better than gzip), but I don't know if it scales well. It's also relatively fast to decode (something like 2x slower than DEFLATE, IIRC).

I was also considering other approaches, specifically GLZA (https://encode.su/threads/2427-GLZA) looks promising. I think it should be well-suited for code due to its design, and it seems to produce better results than bzip on LTCB (https://mattmahoney.net/dc/text.html), and with a faster decompression time.

We considered it, but that requires knowing the path to the file and being able to open it, which I don't think is possible in general (e.g. if the file is loaded with `loadstring`, or if it's loaded from tmpfs and then deleted, etc.).

Thanks! I relayed this to Yuki and we'll make sure to fix the issues.

You can include the start delimiter in the string:

At first I had no clue why we thought that didn't work, in fact, my prototype had a fun commit specifically about adding opening brackets:

    -while b"]" + b"=" * level + b"]" in obj:
    +# Somewhat surprisingly, Lua forbids even opening brackets inside brackets.
    +while b"[" + b"=" * level + b"[" in obj or b"]" + b"=" * level + b"]" in obj:

    > print [[ a [[b c ]]
    stdin:1: nesting of [[...]] is deprecated near '['

Another note that this doesn't cover is ending with a part of the ending terminator.

That's very useful to know, thanks!

So you can't just use the bracketed form to encode arbitrary byte sequences, [...] if you care about the exact representation of line breaks

That's right, and the post actually covers how we resolved that closer to the end. In a nutshell, we replace CRs with an escape character, and then use a bitset to denote which symbols are supposed to be CRs and which ones are literal characters. It's not quite a string literal per se, but it's rather cheap in runtime and minimizes file size.

the fence basically means "resolve all funny business with this variable before proceeding"

Thanks, that's a good explanation! I understand it better now.

What I'd actually worry most about is poisoning the prefetchers, and speculation more generally.

I didn't know prefetchers rely on address generation instructions, I thought they only tracked accessed memory. Good to know! Do you know any relevant external resources about this, by any chance?

A huge part of the problem here is that you're playing with the 8-bit registers. [...]

That's an interesting thought, though in this particular case I think it's a little misguided. 8-bit arithmetic (or, god forbid, 16-bit arithmetic) can quickly cause unexpected stalls, but there is no arithmetic here: the only inherent difference between 8-bit and 32-bit code is the use of `movzx` versus `mov` in a memory load, which to the best of my knowledge are equivalent in performance (modulo store-to-load forwarding and such).

It does look like LLVM generates ugly code for address calculation, though. I don't think it's necessarily going to cause a large effect, since `movzx r8d, cl; lea rdx, [rdi + r8]` doesn't depend on the previous iteration, and the critical latency chain here is just `inc rax`, but it might affect throughput a little. It's quite unfortunate that the induction heuristics didn't do their best here.

so there's an `asm volatile` style fence

I've seen a couple people suggest the compiler fence, and all of them did the same thing -- they put `asm volatile` after the assignment to `j`, not before. Could you explain your thought process here? I thought putting it before the second load would make more sense, because I can imagine

    if (j != next_j[i][j]) {
        j = next_j[i][j];
        asm volatile("" : "+r"(j)); 
    }

    unsigned char value = next_j[i][j];
    _Bool flag = j != value;
    j = value;
    if (flag) {
        asm volatile("" : "+r"(j)); 
    }

    if (j != next_j[i][j]) {
        asm volatile("" : "+r"(j)); 
        j = next_j[i][j];
    }

I have no doubt that putting the fence after the assignment works in this scenario (clearly it does, since LLVM and GCC recognize it), but I don't intuitively see why.

The right-shift is the problem. You need to shift right by `j * 8`, which itself requires a shift to compute (`j << 3`), so you have two shifts on the critical path, resulting in a latency of 2 cycles. It's better than a load, but it's still noticeable.

I knew the loop was latency-bound and I couldn't easily decrease the latency, so I knew I had to somehow avoid the dependency chain at all. I remembered that CPUs predict some properties of memory accesses (e.g. they might predict that a store and then a load from different addresses likely don't intersect), but not addresses, so I thought about another way to force it to predict `j` well. Branch prediction turned out to be the simplest way to do so.

Actually, since then I've found out that I could reduce latency by replacing a load on the critical chain with a vector shuffle instruction (`pshufb`, takes just 1 cycle on x86). Ironically, if I realized that sooner, I probably wouldn't have tried to use branch prediction at all!

The optimization in the post is only advantageous if `next_j[i][j] == j` holds often enough. Without prior knowledge, the compiler can't know if it's going to improve performance, and the worst losses are greater than the best wins (branch misprediction is very expensive), so it decides not to interfere.

That would be great, if only it worked as intended! From the perspective of an optimizing compiler, `a == b ? a : b` is worse than `b` regardless of the probability you assign to `a == b`.

ETA: someone on Lobsters (https://lobste.rs/s/1an425/quadrupling_code_performance_with...) noticed that `[[unlikely]]` actually works on LLVM (not on GCC, and with worse codegen on LLVM, but it's still good to know) -- updated the post.

Thanks!

My brain does not understand how one can see `(+ a b)` in text and read it as `a b +`. I suppose you can argue that moving operators to the right and removing all parentheses converts `(+ a b)` to `a b +`, sure, but that applies to pretty much any language -- next thing you'll tell me is the JavaScript expression `f(1, g(2), h(3))` actually uses stack and is just syntactic sugar for `1 2 g 3 h f`.

It is explicity sugar for the stack operations, per my reading of the spec.

The entire Wasm text format is syntax sugar for binary Wasm, so this is kind of a vacuous truth -- if Wasm's spec says it's a stack machine, of course everything is sugar for a stack machine. But if you weren't aware of Wasm and just saw a program in textual Wasm for the first time, I don't think the idea that it's stack-based would cross your mind.

There used to be hype about Wasm, now it's a technology as any other. It's still used, and used a lot; it just doesn't get focused on as much.

tl;dr: the LISP syntax is just syntax sugar. The textual format is as "stack-like" as the binary format.

Not that you're technically wrong, but I think you're begging the question.

Stack-based languages/encodings, in a colloquial sense, are equated to postfix notation, e.g. `a b +` instead of the infix `a + b`. Both LISP and textual Wasm use prefix notation, e.g. `(+ a b)`. Neither of the three is any more foundational than the other -- all notations can encode all expression trees, and postfix and prefix notations in particular have the same coding efficiency.

So sure, the LISP syntax is sugar, but for what? It's not sugar for a stack program, because prefix notation in general can't represent an arbitrary stack program; it's sugar for a mathematical expression. Which is encoded in postfix notation in binary, sure, but that's just an implementation detail, and prefix notation could've been selected when Wasm was born with little adversarial consequences.

There's just so many "but"s to this that I can't in good faith recommend people to treat floats as deterministic, even though I'd very much love to do so (and I make such assumptions myself, caveat emptor):

- NaN bits are non-deterministic. x86 and ARM generate different sign bits for NaNs. Wasm says NaN payloads are completely unpredictable.

- GPUs don't give a shit about IEEE-754 and apply optimizations raging from DAZ to -ffast-math.

- sin, rsqrt, etc. behave differently when implemented by different libraries. If you're linking libm for sin, you can get different implementations depending on the libc in use. Or you can get different results on different hardware.

- C compilers are allowed to "optimize" a * b + c to FMA when they wish to. The standard only technically allows this merge within one expression, but GCC enables this in all cases by default on some `-std`s.

You're technically correct that floats can be used right, but it's just impossible to explain to a layman that, yes, floats are fine on CPUs, but not on GPUs; fine if you're doing normal arithmetic and sqrt, but not sin or rsqrt; fine on modern compilers, but not old ones; fine on x86, but not i686; fine if you're writing code yourself, but not if you're relying on linear algebra libraries, unless of course you write `a * b + c` and compile with the wrong options; fine if you rely on float equality, but not bitwise equality; etc. Everything is broken and the entire thing is a mess.

And here are the constants for the ostensibly more useful 54x54->108 product: https://play.rust-lang.org/?version=stable&mode=release&edit...

I tried to go even higher, but the bounds seems to break at 55 bits.

I think it fails because it seems like the difference between 32-bit and 64-bit floats is 2x, but in reality we should look at the mantissa, and the increase from 23 bits to 52 bits is much greater.

Although I managed to tweak this method to work with 3 multiplications.

ETA: I just realized you wanted to use 32x32 -> 64 products, while my approach assumes the existence of 64x64 -> 64 products; basically it's just a scaled-up version of the original question and likely not what you're looking for. Hopefully it's still useful though.

First, remove the bottom 8 bits of the two inputs and compute the 44x44->88 product. This can be done with the approach in the post. Then apply the algorithm again, combining that product together with the product of the bottom half of the input to get the full 52x52->104 output. The bounds are a bit tight, but it should work. Here's a numeric example:

    a = 98a67ee86f8cf
    b = da19d2c9dfe71

    (a >> 20) * (b >> 20)         = 820d2e04637bf428
    (a >> 8) * (b >> 8) % 2**64   =       0547f8cdb2100210
    ->
    (a >> 8) * (b >> 8)           = 820d2e0547f8cdb2100210

    (a >> 8) * (b >> 8)           = 820d2e0547f8cdb2100210
    (a * b) % 2**64               =           080978075f64355f
    ->
    a * b                         = 820d2e0548080978075f64355f

Very tangential, but I could swear QBasic included an on-disk documentation system accessible from the editor. Maybe only later versions?

Perhaps my installation didn't include it, or maybe you're confusing it with QuickBASIC, a more feature-complete IDE with a compiler (instead of just an interpreter). I don't exactly remember.

I don't think it's possible to apply this trick to 64-bit floats on 64-bit architecture, which OP mentions in the last sentence. You need a 52 x 52 -> 104 product. Modular 64 x 64 -> 64 multiplication gives you the 64 bottom bits exactly, widening 32 x 32 -> 64 multiplication approximately gives you the top 32 bits. That leaves 104 - 64 - 32 = 8 bits that are not accounted for at all. Compare with the 32-bit case, where the same arithmetic gives 46 - 32 - 16 = -2, i.e. a 2-bit overlap the method relies on.

You can still write code without LLMs, much like you can write code without modern IDEs, or use C and assembly instead of higher-level languages. But there are significant differences between the skills you learn in the process, which I believe inhibits upward mobility.

The formulas are provided in the supplementary information file, as mentioned in the paper. https://arxiv.org/src/2603.21852v2/anc/SupplementaryInformat... You want page 9.

I must admit I'm surprised to see this -- Lemire offhandedly mentioned in the famous remainder blog post (https://lemire.me/blog/2019/02/08/faster-remainders-when-the...) that 64-bit constants can be used for 32-bit division, and even provided a short example to compute the remainder that way (though not the quotient). Looking a bit more, it seems like libdivide didn't integrate this optimization either.

I guess everyone just assumed that this is so well-known now, that compilers have certainly integrated it, but no one actually bothered to submit a patch until now, when it was reinvented?

The paper doesn't require a bitshift after multiplication -- it directly uses the high half of the product as the quotient, so it saves at least one tick over the solution you mentioned. And on x86, saturating addition can't be done in a tick and 32->64 zero-extension is implicit, so the distinction is even wider.

Honorary mention: byte swapping instructions (originally added to CPUs for endianness conversion) can also be used to redistribute entropy, but they're slightly slower than rotations on Intel, which is why I think they aren't utilized much.

I think the reason real-world implementations don't do this is to speed up access when the key is a small integer. Say, if your IDs are spread uniformly between 1 and 1000, taking the bottom 7 bits is a great hash, while the top 7 bits would just be zeros. So it's optimizing for a trivial hash rather than a general-purpose fast hash.

And since most languages require each data type to provide its own hash function, you kind of have to assume that the hash is half-assed and bottom bits are better. I think only Rust could make decisions differently here, since it's parametric over hashers, but I haven't seen that done.

I work on the machine code level, so the only characteristic I'm interested in is how many ticks it takes to compute the result, not how many transistors it requires or anything like that. All modern CPUs take 1 tick to compute both XOR, addition, and many other simple arithmetic operations, so even though addition is technically more complicated in CPU designs, it never surfaces in software. In the context of this post, I preferred addition instead of XOR to reduce cancel-out and propagate entropy between bits.

Yes, that's my point. It's not true that all hash functions have this characteristic, but most fast ones do. (And if you're using a slow-and-high-quality hash function, the distinction doesn't matter, so might as well use top bits.)

Djb2 is hardly a proven good hash :) It's really easy to find collisions for it, and it's not seeded, so you're kind of screwed regardless. It's the odd middle ground between "safely usable in practice" and "fast in practice", which turns out to be "neither safe nor fast" in this case.

"nobody cares about BigInt addition performance" is an odd claim to make when half of the world's cryptography is based on ECC.

I suspect that LLVM is optimized for compiling with `-ftrapv`, perhaps for cheap sanitizing or maybe just due to design decisions like using unsigned integers everywhere (please correct me if I'm wrong). I'm personally interested in how RISC-V behaves on computational tasks where computing carry is a known bottleneck, like long addition. Maybe looking at libgmp could be interesting, though I suspect absolute numbers will not be meaningful, and there's no baseline to compare them to.

I was wondering why, in my Firefox, the image appears saturated when embedded on the website, but opening it in a new tab by a direct URL shows an unsaturated version. The `img` tag on the website seems to be styled with `mix-blend-mode: multiply`, which makes the image darker because the background is #f0f0f0.