ot

O(1) doesn't mean constant, it means bounded by a constant. An algorithm can be faster with small n and converge to a horizontal asymptote as n goes to infinity, and it would still be O(1).

In a real machine there is no infinity, but hundreds of GBs of memory are "infinity enough" compared to the cache size [1]. So asymptotic analysis is still a decent model.

I'm surprised that even a CS professor confuses this.

[1] Ok if we want to be pedantic memory access is logarithmic due to the traversal of page tables, but you can use huge pages.

> 512GB is a huge block size for bzip3

Sorry! That was a typo, it should have been 512MB (now fixed). Still huge.

The benchmarks are disingenuous, to the point of looking cherry-picked. The block size for bzip3 is set to 512MB, but the window size for zstd is left to its default (8MB I believe for high levels). So in this corpus, which is made up of all versions of Perl source code concatenated, the window is too small to see all the identical files and just match them. Also corpora made out of very long repetitions are pretty much the best case scenario for BWT-based compressors.

If we match the window size of zstd to that of bzip3 we get dramatically different results:

    % gzcat *.gz | time zstd -T8 -16 | wc -c  # baseline
     2819113884
    zstd -T8 -16  2054.50s user 3.47s system 783% cpu 4:22.80 total

    % gzcat *.gz | time zstd -T8 -16 --long=29 | wc -c
     196405076
    zstd -T8 -16 --long=29  1083.06s user 2.41s system 783% cpu 2:18.55 total

Almost 15x smaller than the baseline, and more than 2x smaller than bzip3, also CPU time halves (since long matches are found earlier, so there's less work to do).

(the baseline number is slightly different because I don't have the exact Perl version set used by the author)

Also, in the benchmarks using lrzip, which would make the window size less relevant, zstd is not even compared.

Reference to Aesop's fable?

https://en.wikipedia.org/wiki/The_Belly_and_the_Members

Indeed https://www.youtube.com/watch?v=dy-wFixuRVU

Subscription plans share data by default (it is possible to opt out though)

In Linux everything is XOrCrash, since allocations never fail but the OOM killer can get you later.

This is a great article but it goes into a lot of detail that can be intimidating at first.

For me, the reading that made asymmetric fences "click" is this: https://pvk.ca/Blog/2019/01/09/preemption-is-gc-for-memory-r...

It might be easier to read that first, as it also goes into practical applications, and then this one.

> GNU deadline

I think you mean readline?

Yeah the number sounds a lot less impressive if you say that you only get 2^61.44 integers out of 2^64. In other words, a 4% entropy loss.

Information quantities are more meaningfully expressed in number of bits.

That's a false dichotomy: you optimize both the application and the allocator.

A 0.5% improvement may not be a lot to you, but at hyperscaler scale it's well worth staffing a team to work on it, with the added benefit of having people on hand that can investigate subtle bugs and pathological perf behaviors.

It's not just that zeroing got cheaper, but also we're doing a lot less of it, because jemalloc got much better.

If the allocator returns a page to the kernel and then immediately asks back for one, it's not doing its job well: the main purpose of the allocator is to cache allocations from the kernel. Those patches are pre-decay, pre-background purging thread; these changes significantly improve how jemalloc holds on to memory that might be needed soon. Instead, the zeroing out patches optimize for the pathological behavior.

Also, the kernel has since exposed better ways to optimize memory reclamation, like MADV_FREE, which is a "lazy reclaim": the page stays mapped to the process until the kernel actually need it, so if we use it again before that happens, the whole unmapping/mapping is avoided, which saves not only the zeroing cost, but also the TLB shootdown and other costs. And without changing any security boundary. jemalloc can take advantage of this by enabling "muzzy decay".

However, the drawback is that system-level memory accounting becomes even more fuzzy.

(hi Alex!)

RSA was also not given that name by its authors, the name came later, which is usually the case.

In the original paper they do not give it any name: https://people.csail.mit.edu/rivest/Rsapaper.pdf

Here RE2 does not fall back to the NFA, it just resets the Lazy DFA cache and starts growing it again. The latency spikes I was mentioning are due to the cost of destroying the cache (involving deallocations, pointer chasing, ...)

> are there eviction techniques to guard against this?

RE2 resets the cache when it reaches a (configurable) size limit. Which I found out the hard way when I had to debug almost-periodic latency spikes in a service I managed, where a very inefficient regex caused linear growth in the Lazy DFA, until it hit the limit, then all threads had to wait for its reset for a few hundred milliseconds, and then it all started again.

I'm not sure if dropping the whole cache is the only feasible mitigation, or some gradual pruning would also be possible.

Either way, if you cannot assume that your cache grows monotonically, synchronization becomes more complicated: the trick mentioned in the other comment about only locking the slow path may not be applicable anymore. RE2 uses RW-locking for this.

This is drawing broad conclusions from a specific RW mutex implementation. Other implementations adopt techniques to make the readers scale linearly in the read-mostly case by using per-core state (the drawback is that write locks need to scan it).

One example is folly::SharedMutex, which is very battle-tested: https://uvdn7.github.io/shared-mutex/

There are more sophisticated techniques such as RCU or hazard pointers that make synchronization overhead almost negligible for readers, but they generally require to design the algorithms around them and are not drop-in replacements for a simple mutex, so a good RW mutex implementation is a reasonable default.

Glad that Moby Dick is in there.

> Presumably you mean you just double check the page value after the rdtsc to make sure it hasn't changed and retry if it has?

Yes, that's exactly what a seqlock (reader) is.

Yes you need some lazy setup in thread-local state to use this. And short-lived threads should be avoided anyway :)

You can do even faster, about 8ns (almost an additional 10x improvement) by using software perf events: PERF_COUNT_SW_TASK_CLOCK is thread CPU time, it can be read through a shared page (so no syscall, see perf_event_mmap_page), and then you add the delta since the last context switch with a single rdtsc call within a seqlock.

This is not well documented unfortunately, and I'm not aware of open-source implementations of this.

EDIT: Or maybe not, I'm not sure if PERF_COUNT_SW_TASK_CLOCK allows to select only user time. The kernel can definitely do it, but I don't know if the wiring is there. However this definitely works for overall thread CPU time.

If you look below the vDSO frame, there is still a syscall. I think that the vDSO implementation is missing a fast path for this particular clock id (it could be implemented though).

That's probably true for small primitive types, but if your objects are expensive to move (like a large struct) it might be beneficial to minimize swaps.

Yeah, was just about to edit the comment :)

The query is incorrect, it will return any posting that contains the words "vision" and "pro", not necessarily consecutive.

It looks like phrasal search is supported, searching "vision pro" in quotes only returns 212 results worldwide

https://jobs.apple.com/en-us/search?search=%22vision+pro%22&...

Spot-checked a few and they all seem to be Vision Pro related.

--

EDIT: Actually even this is not accurate, as it matches postings with sentences like

> Fundamental to the success of iPhone, iPad, Apple Watch, Apple TV, Vision Pro, and Mac ...

but not specific to Vision Pro.

However we can filter on products and services for Vision Pro and visionOS, and it gives 106 results:

https://jobs.apple.com/en-us/search?search=%22vision+pro%22&...

> can avoid or defer a lot of the expected memory allocations of async operations

Is this true in realistic use cases or only in minimal demos? From what I've seen, as soon as your code is complex enough that you need two compilation units, you need some higher level async abstraction, like coroutines.

And as soon as you have coroutines, you need to type-erase both the senders and the scheduler, so you have at least couple of allocations per continuation.

Is it so hard for people to understand that Europe is a continent, EU is a federation of European countries, and the two are not the same?

> It kind of doesn’t matter if there are users [...] The point is that PCG is better

No that's not the point that the article makes and that I'm questioning, it says "everyone shrugged" which implies consensus, and I'm asking for evidence of that consensus, not of the objective quality of the two generators.

Also I don't think that that paragraph is even close to demonstrating "objectively better": the author of PCG pointed out one arbitrary metric, minimum state size, where PCG beats old variants of xorshift* on a statistical test suite, and in the meantime much better variants have come out. That metric is meaningless since everyone uses much bigger state anyway.

RNGs are a tricky subject, there isn't a singular measure of quality, statistical tests are necessary but not sufficient. The best testament to RNG quality is wide adoption, which builds confidence that there aren't undiscovered failure modes.

> Since nobody had figured out any downsides to PCG's yet, everyone shrugged and said "might as well just go with that then", and that is where, as of 2019, the art currently stands. The problem is solved, and life is good.

I wonder who "everyone" was, I'm not aware of many high-profile projects adopting PCG as a default. As of 2025, several high-profile runtimes (including all the major browsers) use xorshift variants [1]

Is there a list of users of PCG?

[1] See Adoption section in https://prng.di.unimi.it/

But then you could add another level of slower (but still faster than RAM) and larger cache. So it is after all the CPU caches, but the first of all the memory caches. A more mathematically correct name would be L_omega.

Reminds me of the old quote

> everyone only uses 20% of C++, the problem is that everyone uses a different 20%