purplesyringa

As I understand it, the reason for so much work is that eMudhra was not a root CA. It wasn't added to any official root CA list, instead it was signed by a different root CA with the assumption that eMudhra will complete the work required to become a root CA and this hack will become unnecessary. This is a common, temporary process. So while all the mechanisms for root CA revocation were in place, no one was quite prepared for intermediate certificate revocation.

I respect your annoyances, but I think in this case they're overblown. I mention LLMs in two places. The first time is a neutral fact explaining why LLM swarms don't work as a solution, and the second time is one sentence at the very end of the post. I don't think it's reasonable to make inferences about the intended framing from one throw-away sentence.

That looks really cool! The discussion also contains a ton of useful pointers. Thanks!

That keeps the lowest bit in the mantissa, but it also keeps the hidden bit intact, so you get 2^e + 2^k as a result (where `e` is the initial exponent and `k` is the actual lowest bit). I wanted to retain just the lowest set bit, without the hidden bit. Reasonable attempt though.

At this scale, there simply aren't any interactions with hardware that you'd need benchmarking for. Each instruction takes a well-known amount of cycles, and for most instructions in question (+, -, &, |, ^), that's the exact same amount, because they execute on the same ALU.

Thanks for the comment!

> This is fine since the target is wasm which has fsub/fadd, but was initially odd to see in a floating point emulator.

For more context, I'm emulating a full-feature FPU (with exceptions, rounding modes, etc.) over a basic FPU (just the five basic operations or so).

> Apparently a ctz solution is a bit longer, but doesn't cross from the floating to integer domain at all, so might be better in the overall algorithm.

That's what I tried originally, in fact I left this snippet in comments:

    let exp = (x.abs().to_bits() >> 23).max(1) as i32 + 125; // max(1) for subnormals
    let ctz = (x.to_bits() | (1 << 23)).trailing_zeros();
    exp + ctz as i32 - 23

The problem with this approach is that you need quite a lot of wiring to handle subnormals and powers of two correctly. `max(1)` in particular requires `cmov`s or equivalently slow bit tricks. I quickly found out that using FP subtraction is significantly faster on modern hardware.

There is also another reason why I preferred the FP-based solution, and that's vectorization. The brute-forced algorithm can be easily vectorized on all major platforms, but `trailing_zeros` is only vectorizable with AVX-512 on x86, and even then it's not even available in WASM. So, in a twist of fate, I actually think emulating CTZ with floating-point is a more interesting avenue than the other way round. I don't want to self-promote, but you can find a recent relevant article on my blog.

Thanks! I did some more research and updated the post.

lobste.rs has a `vibecoding` tag that you can hide.

I don't think "no one cared" is a fair characterisation. The paper doesn't support this conclusion, and from experience I'd say that the two difficulties in fixing unsoundness are doing so without breaking existing code (Rust guarantees stability unless the code is unsound, and introducing previously missing checks can cause sound code to stop compiling, which is a problem if it occurs often) and doing so in a reliable way that can be supported long-term. Rust is currently in the progress of stabilizing next-solver and Polonius, both of which fix multiple long-standing bugs and have been worked on for years now due to intrinsic complexity, performance considerations, compatibility issues, etc. It's not that no one cares, it's just that this stuff is hard and takes time.

Thanks! Do you have any source for that by any chance? I'd like to update the post.

Using de Bruijn sequences for this purpose is very well known, I'm not claiming to have invented it, it'd be strange if I did, especially when the Wikipedia page directly references this bit trick.

But if you look closer, my algorithm is actually not de Bruijn. First, using de Bruijn with a 32-bit input requires a 32-element table, or even a 33-element one depending on the circumstances, while I make do with 16 elements (repeated twice because that's how AVX works). Second, the de Bruijn snippet multiplies the constant by `x & -x`, a number that has exactly one bit set, i.e. looks like `2^k`, so the multiplication is effectively a shift by `k`. But in my code, I have to use `~x & (x-1)` to reuse a calculation, which produces values of form `2^k - 1`, for which de Bruijn fails spectacularly: `c * (2^k - 1) = c * 2^k - c`, but this subtraction introduces carries, which affects the top 4 bits unpredictably. The magic number I found kinda sorta looks like de Bruijn, but truth be told I found it by brute-force. If anyone knows how to generate such numbers algorithmically, I'm all ears.

Yes, that's a good argument, thank you. You bring up a good point and I'll try to avoid making such claims in the future.

Perhaps I didn't formulate this too well. Say, rustc is a gigantic program, but the parser alone, or the borrow checker alone, or the LLVM backend alone are small enough to work on individually, and from the perspective of any such unit all the others can be treated as black boxes, deliberately designed to have as small of a public API surface as reasonable and to be as predictable as possible. That's just architecture 101. With LLM code, I notice, such abstractions fall apart, and the interconnectedness, duplicated code, and unclear expectations make it impossible to reason about the result except as a giant lump. Of course, tech debt is nothing new, but at least it used to be held back by the physical inability to make progress once things get dire; with LLMs, this misery gets prolonged.

I'll take your claim that I'm capable of writing a psyop piece as compliment :) Truth be told I'd rather be writing a psyop arguing the opposite point than dealing with these emotions.

To your main argument: I absolutely agree that LLMs are terrible at producing working code, or efficient code, and that they're incapable of solving lots of important problems. I've seen LLMs make embarrassing typos, patch vulnerabilities with differently vulnerable code, and go through the motions of optimization as if blindfolded.

That is, however, not the central matter here. IMO, at present what management thinks LLMs are capable off has a larger impact than what LLMs are actually capable off, and while I'm hoping that the market will regulate itself once more and more slop projects break down, that'll take time, and I'm not confident that LLMs won't improve sufficiently by that point that the most glaring mistakes will be fixed. Of course, new and non-obvious issues may still be present, and they may cause trouble at a later point, but again, that won't happen immediately and I think we'll just end up in this infinite loop for the time being.

I will also add that AI companies' claims affect the general public's perception of the acceptable level of software quality. If Anthropic says 1000ms is great, and other companies follow the same approach, people will consider that the norm and not demand better software. This enshittification has started a long time ago -- just look at how bloated Windows and the web are -- and I don't think it's going to end just because we know things can work better.

Taking a step back, I think it's really a question of how many people will understand the value of what people like you and I can deliver. That number has been falling bit by bit before the LLMpocalypse, but now it's just becoming abysmal.

Yeah, this struggle doesn't ever really end, it just gets easier.

I think you might be interested in reading the post Are We Really Engineers (https://www.hillelwayne.com/post/are-we-really-engineers/), which in part covers the point about whether "engineer" is closer to a profession designator or a respectable title. It really surprised me when I read it first time!

I won't lie, of course my code has bugs. The difference, as I see it, is the kinds of bugs that manifest, and how well they can be avoided.

There are two steps to writing the program: building a model in your head to map understanding to algorithms, and then implementing the algorithm in code (and of course this can get recursive if the algorithm relies on other high-level mechanisms, like data structures).

I have found that most of the time, the kind of bugs that unit tests find are typos, i.e. mistakes in the second step; but the errors that actually cost time to resolve are errors in understanding, i.e. the first step.

They can't be found with testing or verification because what it means for code to be correct depends on the specification, and the error is that the specification itself is incorrect. Asking an LLM to check this one specific part of the software is thus useless, and whole-program analysis is not cheap enough to employ at this point.

So what about avoidance? When I say hand-written code is 100% correct (or at least approaches that number), I mean that with experience, I learn more about which models tend to be correct, and thus avoid bugs of the latter kind by construction. Of course typos still exist, which is why I write unit tests, and I expect LLMs to be able to find them as well; but I believe the only way to avoid incorrect models is to learn stuff by doing, failing and failing again, figuring out nitty-gritty low-level details, until at some point you become an expert in that area and know what to use.

To expand on this, the imprecision arises the moment you write 0.1 (decimal) in source code and the compiler converts it to binary; the arithmetic itself is (mostly) exact. So as long as you use numbers that look "good enough" in base-2, floats behave very reasonably. The constantly made assumption that floats are imprecise is, in this sense, a user error -- the user shouldn't have used decimals.

`log_a x < log_b x` is the mathematically correct result. Due to inherent rounding from floats being a finite representation of real numbers, `log_a x <= log_b x` would be expected from any correct implementation using floats. So either `true true false` or `true false true` would be reasonable. (I made a mistake in the previous comment, LuaJIT returns `<` for me, just like in your comment, not `=`.)

The topic of the post is that in PHP and Lua (without LuaJIT), sometimes this inequality doesn't hold, and instead we get `log_a x > log_b x`, which is very incorrect and cannot be explained away by rounding.

Does that make more sense?

I sort of needed to do that. I needed to compress data with an approximately geometric distribution, and as part of that process I needed to invert its CDF, which is `CDF = 1 - (1 - p)^x`. That translates to `x = log_(1 - p) (1 - CDF)`, which is variable over both the argument and the base. At that point I wondered how consistent the implementation of double-argument `log` is, since the encoder and the decoder need to agree about it, which led to this article.

That's interesting! On my PC it reproduces under Lua 5.5 (`log_a x > log_b x`), but not under LuaJIT (`log_a x = log_b x`). I took a look at LuaJIT's implementation (https://github.com/LuaJIT/LuaJIT/blob/faaf663340347a78b22ed9...) and noticed that it always uses the `ln x / ln a` formula -- or, rather, `log_2 x / log_2 a`, which is just as correct I guess. Have you perhaps misinterpreted the results? (I do think it's valuable to add that this doesn't apply to LuaJIT though.)

Thank you! This point has been driving me mad for the last couple of years.

While answering a sibling comment, I found a paper analyzing various libms for their precision: https://homepages.loria.fr/pzimmermann/papers/glibc238-20230... (2023). I only skimmed it, but it looks like only LLVM's libm guarantees 0.5 ulp for every supported single-precision operation, and everyone else is wildly off. That's a pretty good result, though -- it means there's at least one reasonably compliant libm :)

Another sibling comments says that guaranteeing 0.5 ulp for double-precision operations is nigh impossible (and then another says it is after all). I don't have the knowledge to confirm which is true, but it's possible that this is the best we can get.

Thank you! I completely agree with this, floats are treated as a lot more magical than they actually are. I myself often rely on their exact guarantees for fun tricks (e.g. fast precise int<->float conversion: https://purplesyringa.moe/blog/fast-limited-range-conversion...). But while IEEE-754 is very precise, some subtleties arise when you add library functions to the mix -- many libm's and userland libraries don't guarantee 0.5 ulp precision for certain operations and don't document the guaranteed precision either, at which point you're left guessing and saying "well, I guess I should treat floats as magic in this case after all". I added "it's not imprecision" to step around this whole question.

The log base is a parameter, not a function, so that doesn't typecheck. Multivariate monotonicity isn't really a popular term, as far as I'm aware, so I'm not aware of good terminology for this. Maybe "log is non-monotonic with respect to the base"?

Python, PHP, and Rust do indeed use libm. Not LLVM's libm specifically, though, but rather just about anything they can find in runtime, and those libraries can have suboptimal accuracy.

Node uses V8, which notably implements a ton of math manually, because it needs the results to be deterministic across devices. It seemingly uses LLVM's libm, which IIRC promises 0.5 ulp for most operations. (https://github.com/v8/v8/blob/f24c62fbc342d616032734b714116e...)

Go avoids dynamic linking, so they also have their own implementation. (https://github.com/golang/go/blob/543ead71a8e7acc2bd6f326327...) They only promise 1 ulp, but I guess in this specific case it works out better than approximations used by the default libm on their system by pure chance?

> PHP uses a JIT from Lua.

Wow, TIL! I was certain this is a mistake, but apparently PHP uses DynAsm (https://wiki.php.net/rfc/jit), which was developed for LuaJIT (https://luajit.org/dynasm.html). Cool stuff!

To answer your question, probably not. I dated the PHP change that added this "optimization" back to 2014 (https://github.com/php/php-src/commit/b547e1358d3846fad4cd0c...), while DynAsm only started being used around 2019 (https://wiki.php.net/rfc/jit). I think this is just convergent evolution.

(I'm putting "optimization" in quotes because it changes semantics.)

Yeah, I simplified it a little. Though I must say I'm surprised pretty much every library I looked at uses the natural logarithm specifically, and not log2, which would seemingly be easier to compute with floats. Does anyone here know why, by any chance?

> 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:

...but I think I've figured out the problem. It seems like Lua 5.1 specifically forbids level-0 opening brackets within level-0 strings:

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

...and Cobalt implements this check for compatibility. So that's another edge case to handle, I guess.

> 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.