ot

> You do need a fence in the unlock path though (at least a release fence).

Well yes but on x86 that comes for free. The overhead of the full fence brought in by lock cmpxchg or lock xchg is in the order of ~10ns, which for an uncontended lock means that a mutex is almost 2x as slow as a spinlock.

A load acquire + store release would be a couple of ns (assuming everything in L1 etc...)

> Reason: locks that have the ability to put the thread to sleep on a queue must do compare-and-swap (or at least an atomic RMW) on `unlock`. But spinlocks can get away with just doing a store-release (or just a store with a compiler fence on X86) to `unlock`.

This is something I've thinking about a lot over time, that the CAS is only there to atomically determine if there are any sleeping waiters on unlock and you have to do a futex_wake. I would really want some way to get away with non-fenced operations (at least on x86), but I don't know if it's just that nobody has figured out why, or there is a fundamental reason why that's not possible.

Yeah, that specific benchmark is actually likely to prefer undesirable behaviors, for example pathological unfairness: clearly the optimal scheduling of those threads runs first all the increments from the first thread, then all of the second thread, etc... because this will minimize inter-processor traffic.

A mutex that sleeps for a fixed amount (for example 100us) on lock failure acquisition will probably get very close to that behavior (since it almost always bunches), and "win" the benchmark. Still, that would be a terrible mutex for any practical application where there is any contention.

This is not to say that this mutex is not good (or that pthread mutexes are not bad), just that the microbenchmark in question does not measure anything that predicts performance in a real application.

Even if we were talking about real numbers (which we're not), it would still be true that (0, 1) and (1, +inf) have the same cardinality :)

As touched on in the post, 1/x is an explicit bijection (but any set of real numbers that contains an interval has the same cardinality)

VByte is a weird baseline to compare to: it is a byte-aligned encoding scheme, so it trades off some space efficiency for speed of decoding. The proposed method is bit-aligned, so it should be compared against bit-aligned encoding schemes.

For large integers, it is hard to beat Elias Delta coding [1], which asymptotically uses log(n) + o(log(n)) bits, and in practice it breaks even with most other encoding schemes quite early on.

More importantly, Elias Gamma and Delta are complete, meaning that there is no redundancy (another way to look at it is that any sequence over the alphabet is decodable). VByte is complete over the byte alphabet. Any complete code is optimal for some integer distribution (see "implied probability" in the Wikipedia page).

So if your integer distribution is heavier on the large integers, there are already plenty of complete encodings to pick from, and almost certainly one that fits well the distribution.

The scheme proposed here, instead, is not complete, as mentioned in the README ("this method does introduce some redundancy, particularly when sequences must be padded to prevent unintentional "101" patterns"), so it cannot be optimal for any distribution.

The Wikipedia page on the Kraft–McMillan inequality [2] explains this in more detail.

[1] https://en.wikipedia.org/wiki/Elias_delta_coding [2] https://en.wikipedia.org/wiki/Kraft%E2%80%93McMillan_inequal...

From the article

> According to the Times, Shah wants CNET because it’s a “well-known industry brand” and still has an audience that’s large enough to be attractive to tech advertisers.

> there's a large company with an almost identical name

Are you suggesting that this wasn't intentional? The name is clearly a play on "zero shot" + "xerox"

You could say the same thing about std::monostate, which is not a dummy type. If you need a unique sentinel type you have to make one for that purpose.

You can use void for that.

Folly has DeterministicSchedule, which also wraps atomics and it is used to test its core synchronization primitives, but I don't think it's as sophisticated as loom.

https://github.com/facebook/folly/blob/main/folly/test/Deter...

> It's a shame because I know Google can put out easy to read code (see: the go standard library).

My guess is that the difference is that go is managed by a small group of engineers that have strong opinions, really care about it, and they have reached "fuck you level", so they can prioritize what they think is important instead of what would look good on a promo packet.

I'm one of the authors of the paper, nice to see it on HN.

I remember when we first experimented with this, the compression improvement compared to our previous heuristic was massive, but the algorithm took a day to run on a double-digit-node Giraph cluster for a single index shard. I was very skeptical we'd ever be able to use it in production, given that we had to run it on thousands of index shards every few days.

Eventually we reimplemented it in C++, optimized all the data structures to make them fit in memory, and we were able to run it in a couple of hours on a single (beefy) machine. Over the years it has been optimized further.

The algorithm has been reproduced externally with an open-source implementation [1], which AFAIR was pretty good when I looked at it.

[1] https://culpepper.io/publications/mm+19-ecir.pdf

I haven't worked in this field for a while, but if you look at the citations of the paper [1] there are quite a few applications.

One that I find very interesting is optimizing function layout in binaries to improve their compressibility [2], which is important for mobile apps.

[1] https://scholar.google.com/scholar?cites=1196492606453931313...

[2] https://arxiv.org/pdf/2211.09285

> Google said this change is to allow the search company to serve the search results faster on more searches

I'm surprised that this makes enough of an impact: in order to find the top 10 results the engine needs to retrieve and rank a much larger number anyway (I'd guess at least 100 make it to the final stages of the funnel), and that is where virtually all the cost is. That initial set is probably held in some cache so that subsequent page loads don't re-do the search from scratch.

So either this is a small win in frontend efficiency, or continuous scrolling is fast enough that a large fraction of users goes past the initial set?

LAN can be oversubscribed too, even if your switches have sufficient capacity you can have short packet bursts that fill up the queues. You cannot assume reliable delivery.

Everything at some layer has to run over datagrams, since that's what IP is.

This is literally the point of the article: if you want to create a protocol over raw datagrams, you have to implement a lot of things that are very hard to get right, so you should just use QUIC instead, which does them for you.

I would speculate that OpenAI is in a phase where speed of delivery is make-or-break, and any bloat would be a distraction. I bet they're extremely deliberate in their acquisitions.

I guess I stand corrected then :)

(Hi!)

EDIT: I forgot to say, with the recent hires and the Rockset team, OpenAI is building quite the infra dream team :)

Very unexpected acquisition. I don't think that Rockset is a suitable infrastructure for RAG, a purpose-built inverted index would be far more efficient (both in terms of compute and storage), so I'm not sure how much of the technology would actually be useful for them.

I can think of two options

- Pure acqui-hire: virtually all of Rockset engineering leadership is ex-Meta, and OpenAI has been hiring several senior infra engineers from Meta, so these are all people that have worked together previously.

- OpenAI is building some product where customers can ingest large amounts of data, which could be managed by the Rockset infrastructure as source of truth, and then indexed by their RAG systems.

You might be thinking of JBIG2

https://en.wikipedia.org/wiki/JBIG2#Character_substitution_e...

My overall point is that neither your function or my function are actually O(1). Whenever you see the notation O(...), there is an implicit context "As input size n grows arbitrarily, ...". You can check the formal definition on Wikipedia.

The cost function for both our functions is not defined for arbitrary n, because they both stop working when input size crosses a threshold. So the O(1) notation is not well-defined in this case.

Now you could come up with a different formal definition for O(1) for bounded input sizes, which is fine, but I don't think you can find one that makes your function O(1) and my function non-O(1). So it would be not be a meaningful definition in this case.

Ultimately, you're using O(1) colloquially. In your words, calling my function O(1) is misleading while it is fine for yours because the constant is "small". "Small" is a subjective term, while O(1) is a formal term.

If your definition hinges on a subjective characterization, why not just say "it's fast", instead of incorrectly using a technical term?

(If we really want to be pedantic, there is really no such thing as "constant-time" when accessing memory, a TLB miss for example will make the CPU traverse a tree; a page fault can execute arbitrary code).

> This function is O(1)

I think I addressed that in my comment, but to be more explicit, this function is O(1) too:

  size_t find_sorted(void* object, void** list, size_t size) {
    for (size_t i = 0; i < SIZE_MAX; ++i) {
      if (i < size && list[i] > object) return i;
    }
    return SIZE_MAX;
  }

If O(1) cannot distinguish your function from this function, what is its informational value?

> Asymptotic bounds are useful when your input can grow arbitrarily large

But your inputs can't grow arbitrarily large, that's why you can hardcode 3 levels. O(1) is an asymptotic bound, and my point is that it is not very informative here.

Radix trees are not O(1), they're O(log n). Data structures that support constant-time predecessor lookup do not exist, there is a super-constant lower bound, even in the RAM model [1].

Often I hear people say "well pointer size is constant, so log(64) = O(1)", but that is misleading: if you assume constant pointer size, any function of that is O(1) as well, so any bounded algorithm is O(1). The notation just becomes meaningless.

Asymptotic bounds must be presented and understood in context.

[1] https://en.wikipedia.org/wiki/Predecessor_problem#Mathematic...

In general the compiler/linker cannot assume that derived classes won't arrive later through a shared object.

You can tell it "I won't do that" though with additional flags, like Clang's -fwhole-program-vtables, and even then it's not that simple. There was an effort in Clang to better support whole program devirtualization, but I haven't been following what kind of progress has been made: https://groups.google.com/g/llvm-dev/c/6LfIiAo9g68?pli=1

Or "something is wrong with my benchmark setup", which is also a possibility :)

Without a comparison of generated code, it could be anything.

Surprised that neither the article or this thread link to https://xkcd.com/570/

It is worth noting that this does not come for free, and it would have been nice for the article to mention the trade-off: reconstruction is not cheap on CPU, if you use something like Reed-Solomon.

Usually the codes used for erasure coding are in systematic form: there are k "preferential" parts out of M that are just literal fragments of the original blob, so if you get those you can just concatenate them to get the original data. If you get any other k-subset, you need to perform expensive reconstruction.

But in the case of HN the RNG was seeded by millisecond-granularity timestamps. This was universally considered bad already in 2009 (it would have been even in 1999). The Debian SSL key scandal happened in 2008.

It is quite a leap to say "timestamp-based seeds are insecure, let's upgrade to lava lamps".

I wish articles like this described the technique for what it is, that is a fun gimmick, or maybe even an art installation, rather than misleading the reader into thinking that this is produces better randomness than any other common entropy source (there is no indication of that). It is misinformation that does not make the reading any more entertaining or informative.

"critical to the security of the global internet"? Really?

Did you read the article? It is specifically about how the series looks simple, but the error is actually very bad if you do things naively.