> > which is that over time, as program changes and evolves over years, things tend to drift toward the more general mechanisms that rely on malloc/free on an individual objects, and the program gets slower and slower
I think the idea is that a small program can organize its allocations and data structures to minimize number of calls to malloc, e.g. with preallocated workspace structs, or slab allocation, and similar approaches. But as a program gets bigger, there's a pressure to have looser coupling, to have subsystems with simple convenient APIs which leads to them doing on-demand malloc calls internally, rather than having consumers pre-allocate their needed workspace. Because that kind of workspace management results in more complex APIs and more burden on the consumer.
That said, I don't really believe it either, at least for the kind of codebase where it would matter (scientific computing, in-memory DB server, etc). A codebase that places an emphasis on minimizing heap operations in hot codepaths can do so by consistently using workspaces and allocation-avoiding APIs. I don't think it's so difficult really, but it does take a conscious design decision to do so. But writing something like a web browser in this way could be annoying due to most data having wildly variable sizes, and zig's arena concept would be very handy -- but rust has crates like bumpalo for that purpose.
My personal mantra: "Think in FORTRAN, code in Rust/Julia/C++". But I'm mostly working on HPC-style code where I don't have to do with wildly varying input or output sizes.
> but rust has crates like bumpalo for that purpose.
Except that's not composable - not only do you need specialised data structures, but all (transitively) allocating calls need to be specialised. That's the exact same issue we have in C++, and that's the issue Zig seeks to address. BTW, just the other day there was a post here about a language with another interesting approach, but I have yet to give it a close look: https://github.com/aardappel/goose/
> But I'm mostly working on HPC-style code where I don't have to do with wildly varying input or output sizes.
There you have it. The problems arise more quickly in concurrent rather than parallel code, and when there are lots of features added over the years that touch the hot paths.
> in-memory DB server
Actually, here there can be big problems (as it's also about concurrency rather than parallelism). Last week a colleague of mine looked at Moka and saw that it could only offer half the throughput as Java's Caffeine at the same latency and RAM footprint (almost; the Java program used 5% more RAM). When he looked into it, he saw that over 40% of the program's CPU was spent on the epoch-based reclamation.
> not only do you need specialised data structures, but all (transitively) allocating calls need to be specialised
Most crates for containers will be written such that the container types take an optional allocator type parameter that defaults to the global allocator. You can set it and it transparently uses the other allocator.
To improve the ergonomics, you'd define local aliases that use that allocator.
When that is the case (and it isn't yet; and remember that it's not only the containers, and strings, that need to be parameterised, but any routine that allocates them, transitively), then that's what Zig does. But the question was doesn't Rust solve memory management already, and this is an important aspect it clearly doesn't solve just yet.
there is nothing stopping you from using custom allocators with your own code or with calls to thirdparty dependencies
but custom allocators are rarely used in rust because they're simply not needed the vast majority of the time. if your language is not memory safe and you need to manage memory yourself, they're more important. but this isn't the case with rust.
c and zig folks are obsessed with arena allocators particularly because they can group lifetimes of individual objects, reducing the amount of malloc/free calls and thus the amount of use after free, double free, nullptr derefs, or leaks that can occur.
in rust this isn't a concern so custom allocators are only used for performance reasons.
but it turns out that in performance sensitive areas, you generally use custom data structures or those that already have their own allocation strategy baked in, like the generational_arena crate.
most of the time you are not calling thirdparty crates that allocate in performance-sensitive regions. either the crate is designed for this usecase and already uses a performant allocation strategy, or you're writing your own code here.
and in the rare case, you can trivially vendor the crate and pass your own allocator into it, or toggle the global allocator for callers.
but you also need to benchmark first before choosing an allocation strategy because it's not clear that a custom allocator will always guarantee better performance anyways.
and btw zig doesn't guarantee this anyways. you could pull in a dependency that instantiates their own allocator. at least in rust almost all crates use the global allocator as a default which lets you swap it out. if a zig dependency uses their own allocator the only recourse is to fork it.
rust doesn't have a performance problem, so any claims about it's custom allocator support leading to poor performance is unfounded. and thus so are claims about the superiority of zig's approach to allocators.
> i find it fascinating how big of a rust hater you are. willing to outright lie to make your point.. because you can do this with_allocator
You say I outright lie for not mentioning the existence of something that doesn't exist??? I guess you're saying it's possible to create such a mechanism (or that some libraries do create ad-hoc ones), but that's not the point.
> there is nothing stopping you from using custom allocators with your own code or with calls to thirdparty dependencies
I didn't say there's anything in the language stopping C++ and Rust from having such a standard library and ecosystem of libraries. They just don't have that yet.
> if your language is not memory safe and you need to manage memory yourself, they're more important. but this isn't the case with rust. c and zig folks are obsessed with arena allocators particularly because they can group lifetimes of individual objects, reducing the amount of malloc/free calls and thus the amount of use after free, double free, nullptr derefs, or leaks that can occur. n rust this isn't a concern so custom allocators are only used for performance reasons.
This is simply untrue. I won't call it an outright lie, as it's probably just a lack of experience with low-level programming.
First, I'm trying to point out the problems we've had in C++, most of which only became apparent when evolving large codebases over time. People who have not had experience evolving large C++ or Rust codebases over years simply don't know about these problems and certainly can't claim they don't exist. Writing smaller programs in C++ or even large but young programs has always been a pleasure. The language is expressive and productive. Some of the biggest issues only arise years later, when the program gets either expensive to maintain or slow.
Second, experienced C and C++ folks cannot be "obsessed" with arenas for the reasons you mentioned because until maybe 20 or even 15 years ago memory safety wasn't a widespread obsession. It was a correctness issue like all others, and its outsized role as the cause of security vulnerabilities wasn't widely known until more recently.
Lastly, you don't pick Rust for safety. Most software in the world today is already written in languages that are at least as memory-safe safe as Rust, sometimes more so. These days, you pick C, or C++, or Rust, or Zig when you want to do something that's largely low-level. Things that are low-level often also need to be reasonably fast, and large low-level codebases that evolve over years tend to suffer serious performance issues because of memory management (because, being low-level, they can't move pointers and so can't use things like a moving GC to reduce the overheads of their malloc/free runtimes; this is why companies with actual experience with long-maintained large low-level codebases make huge runtimes like TCMalloc to help them to a degree, which you also may not have needed yet), and arenas are the primary way to get memory performance similar to what you see with modern moving GCs (and even somewhat better).
Now, you could say that C++ only started moving in that direction with pmr in C++ 17, and that's true. But the need was recognised as early as 2005, traditionally C++ codebases didn't rely on many libraries so interoperability has typically not been a large concern, and the number of large C++ programs that would benefit from such a thing declined over the years because of the low-level maintenance issues I mentioned and the growing availability of fast high-level languages.
My distaste for Rust isn't because I like C++ so much. Even though it's been one of my primary programming languages for the past 25 years, I "hate" it for the very same reasons. Most Rust superfans are people who have not had enough experience with it and they don't know about the problems. Not all, of course, and even C++ has superfans, which is why I said that among the people who are experienced in low-level programming, there are people who like the C++/Rust approach (of trying to make low-level code appear high-level) and people who don't.
> I did not like, and did not understand, epsilons and deltas.
It's nice to have this perspective validated by someone like Serre! I felt like I was missing something when I first encountered that formalism. In fact, all of my introductory calculus classes sucked and turned me off of math for a few years.
Euler was a master manipulator of formal expressions; don't think it bothered him very much whether, e.g., an infinite series converged or not. (Unfortunately don't remember a source for this offhand -- maybe a leftover impression from having read ET Bell's book long ago? I also don't know how reliable Bell is.)
Cauchy is the one who introduced rigor to calculus with the formalization of limits, including epsilons and deltas, a full century after Leibniz and half a century after Euler.
Nonstandard analysis [0] [1] uses infinitesimals but is still completely rigorous. I haven't ever really used nonstandard analysis myself, but there's a fairly well-regarded textbook available online [2].
Also conceptually it feels just right to use nilpotents to probe the smooth structure. In a way nilpotents are violently smaller than even non standard analysis infinitesimals, as the laters’ powers are incredibly small but never vanishing.
Another way to see this is that it makes Taylor expansion exact by killing terms above a bound so it works naturally with the ecosystem surrounding it
Finally duals are very similar to complex in a way. i can be defined as root of X^2 + 1 = 0 even if it felt impossible initially, the dual number as a non nul solution of X^2 = 0 even if it is as counterintuitive.
There's no alternative that's significantly easier to understand and to use. The so-called "nonstandard analysis" hasn't caught on, because it's mostly the exact same arguments wrapped in slightly different language, not making them any simpler or shorter.
The language used by mathematicians is subject to constant evolution. 18th and 19th century results in analysis are not expressed and taught in the same way their original authors did it. Newton, Leibniz, Euler, Lagrange, Fourier, Riemann -- none of them expressed their results in terms of epsilons and deltas. These only caught on in the second half of 19th century, and they did so, because they were a better tool to rigorously prove the ideas.
New terminology inventions that make the subjects easier to understand take the field by storm. Some of the relatively recent examples are category theory, homological algebra, or, for that matter, the notion of sheafs, popularized by J.P. Serre himself. Mathematicians are very open to innovation, and intransigence is not the reason why we're stuck with epsilon-delta.
The reason is that nobody has yet come up with a better way of talking about these concepts. I repeatedly observe many people who seem to believe that their difficulty in understanding math stems from mathematicians gatekeeping their results. I think that this belief is just a coping mechanism. Mathematics is genuinely hard, and when people have trouble understanding something, it's easier to think that it's someone else's fault, rather than accepting one's own deficiencies.
> The so-called "nonstandard analysis" hasn't caught on, because it's mostly the exact same arguments wrapped in slightly different language
No. Let's take a nonstandard proof of the intermediate value theorem on [0,1] by Nelson.
By the transfer principle it is enough to prove this for a standard continuous function f on [0,1] with f(0)<0<f(1).
Take a finite subset of [0,1] containing every standard point. Colour its points blue, green, or red according to whether f is negative, zero, or positive at tha point.
The first point of the interval is blue and the last red. Hence either awe can find some green point, or we can find two neighbouring points that have different colours, the first blue and the second red.
In the first case there is a zero, so we are done. In the second, let the neighbouring points be p and q. By the completeness of the real numbers, every nonstandard real in [0,1] is infinitesimally close to exactly one standard real. So p and q are infinitesimally close to some standard real number, let's call it z.
Standard continuous functions send infinitesimally close points to infinitesimally close points. So f(p) and f(q) are both infinitesimally close to f(z). But f(p) is negative and f(q) is positive. The only standard number infinitesimally close to both positive and negative numbers is zero. Thus f(z) is zero. This proves the theorem.
You tell me, which standard proof is this? It's certainly not the nested interval proof. Not the supremum proof. Not the bisection proof in disguise. Which argument does it wrap in slightly different language? Can you point to a single textbook, course note or lecture that gives such an argument?
No. One could of course argue that this is not simpler/shorter than the usual arguments. But it is very different from them. Saying that it's the same arguments repackaged in a different language is just wrong, and detracts from an otherwise valid point.
This is the standard nested interval proof, you’re just replacing the limiting step of taking smaller and smaller intervals with the nonstandard way of expressing the same thing.
I'll be honest: your one sentence response tells me you did not read the proof above in any detail.
I chose Nelson's proof precisely because its construction is well-studied and well-understood. The same construction of a mesh containing all standard points, with the coloring forcing a tiny multicolored cell, extends from the interval to the triangle. In one dimension you get two adjacent differently colored points; in two dimensions you get an infinitesimal triangle whose three vertices have the three relevant colors. Taking their common standard part and applying continuity gives a short proof of Brouwer's fxied-point theorem on the triangle.
But it is well-understood (there's a whole field studying such questions [2]) that the nested interval proof of the Intermediate Value Theorem does not generalize to proving Brouwer's fixed point theorem on the triangle [1]. This fact can be derived from a computability argument as well [3].
Nelson's argument does generalize to prove Brouwer, so it's not the nested intervals argument. But really, nobody cares about these technical reasons. It's obvious to most math undergraduates that Nelson's proof is not the nested interval proof, the clear absence of any nested construction kinda gives it away. The only reason it was necessary to get technical is that you did not really inspect the proof before claiming it was nested intervals. The technical results cited above are just a formal way to show that any correspondence you might imagine between the two proofs is just not there.
[1] Shioji/Tanaka: "Fixed Point Theory in Weak Second-Order Arithmetic", Annals of Pure and Applied Logic v47, pp 167188 (1990).
What you just described is a classic proof of Brouwer's fixed point theorem using Sperner's lemma. The proof you cited earlier does not generalize to it on its own, the Sperner's lemma is a crucial combinatorial ingredient. It's crucial, because it only works on spaces with the topology of the triangle; you cannot perform the same argument on, say, an annulus.
In the standard formulation, you apply the Sperner's lemma to find smaller and smaller triangles, and apply compactness, precisely as in the standard proof of intermediate value theorem.
The rest of your post, where you quote reverse mathematics stuff, is completely irrelevant to the point I was making. Nothing I said is about what theorems follows from what axioms, but rather whether nonstandard analysis is meaningfully different, clearer, or more useful language than standard one. It is not.
You made a sweeping claim that nonstandard analysis arguments are the exact same arguments, wrapped in nonstandard langauge. I explained that (while your other claims about simplicity may be valid) this is not so and detracts from the rest of your points. I challenged you to defend your "same arguments" claim by finding any standard analysis textbook which teaches a standard language version of Nelson's argument as a proof of the IVT. Let me recap what happened since then:
1. Two comments ago you confidently claimed that Nelson's IVT proof is "the standard nested interval proof" with the limiting step written in nonstandard language. That is a straightforward claim about the structure of the proof, one that you didn't bother to substantiate, and that is straightforwardly false.
2. After I explained why it's false (Nelson's construction proves BFPT, which no nested interval type proof can do), you changed your response: now the Sperner lemma was a "crucial additional ingredient". But Nelson's combinatorial step, that opposite endpoint colors force a blue-red interval, _is_ the one-dimensional instance of the Sperner lemma (and indeed the base case when you prove Sperner's lemma for arbitrary dimensional simplices by induction; the analytic part is independent of dimension, once you find an infinitesimal multicolored simplex, you take its common standard part and apply continuity exactly as before).
3. Then you wrote this:
> In the standard formulation, you apply the Sperner's lemma to find smaller and smaller triangles, and apply compactness, precisely as in the standard proof of intermediate value theorem.
There is a standard proof of Brouwer via the Sperner lemma, and it is _also_ not of the same form as the standard nested interval proof of the IVT. In the nested interval proof, you find a sign-change interval, then find a smaller sign-change interval inside it, and so on. The intersection of all of these contains a point, and that's your zero. Nelson's proof does not do this, and neither does the standard proof of Brouwer via the Sperner lemma: you do not, and cannot, take a 3-color interior triangle, then find a smaller 3-color interior triangle inside it and so on. Even the first step would not work, since the inherited labelling does not satisfy the right boundary condition relative to the small triangle!
And this is also why the computability paper I cited ("where I quote reverse mathematics stuff" ;) was very much relevant. There can be no effective "nested triangle" proofs of the Brouwer fixed point theorem at all, because such a proof would let you compute a Brouwer fixed point, and there are examples of computable maps on the triangle without computable fixed points. If Nelson's IVT proof was the nested interval proof, then swapping in the higher-dimensional Sperner step would give a nested-type proof of BFPT. No such proof can exist. Since Nelson's argument proves the BFPT without any change to the analytic part, it is not a nested interval type argument.
You first misidentified Nelson's proof as nested intervals, and then treated Sperner as an additional ingredient even though the coloring step in Nelson's proof is already the corresponding Sperner argument. Those are both fairly serious misunderstandings about these proof. Given this, I don't think our exchange leaves readers with much confidence in your assessment of NSA's drawbacks and benefits. That's a disappointing outcome, as far as I'm concerned. There are good arguments to make that NSA adds little value to undergraduate education, such as simplicity or the difficulty of the prerequisites, and good conversations to be had about them. But "NSA proofs are the same proofs wrapped in a different language" is not one, and I wish you had just narrowed it instead of doubling down.
I never said the triangles in the standard proof are going to be nested, so your whole segue into reverse mathematics is, just like I said, irrelevant. The point of the argument is that you can find a sequence of triangles with differently colored vertices, the vertices of which all converge to the same point (thanks to compactness), which contradicts continuity of the retraction on the boundary. The nonstandard version of this is exactly the same argument, it just replaces the explicit limiting step that contradicts continuity with the an argument that uses the nonstandard formulation of continuity in terms of infinitesimals.
If that makes it easier for you to understand it, in the standard proof, you also color every point of the rectangle, with the color of the edge it retracts to (picking the colors of the vertices of the big triangle arbitrarily, just making sure that the color of each vertex is a color of one of the edges it belongs to, not one of the opposite edges). Then, an easy argument from continuity shows that no interior point will have points of three different colors arbitrarily close to it. Finally, applying Sperner's lemma as above proves that such point must nevertheless exist, obtaining contradiction with the existence of the retraction.
and then treated Sperner as an additional ingredient even though the coloring step in Nelson's proof is already the corresponding Sperner argument.
I don't understand what are you saying here. What I'm saying is that for the coloring proof of BFPT to work, whether clothed in standard or nonstandard language, you must perform a combinatorial argument that uses a topology of a triangle as a necessary ingredient, similar in shape to the proof of Sperner's lemma.
You opened with the claim that nonstandard analysis hasn't caught on because it's "mostly the exact same arguments wrapped in slightly different language". I pointed out that the arguments are in fact very distinct: e.g. Nelson's proof of the intermediate value theorem is something that any NSA student would see, but no standard textbook teaches IVT by a standard language counterpart of it.
One post later, you answered that Nelson's IVT argument is in fact the "standard nested interval proof" with the limiting step rewritten in nonstandard language.
That claim is simply wrong. Why? Because Nelson's construction straightforwardly generalises to Brouwer, while the nested intervals proofs cannot. The discussion of reverse mathematics / computability is not a tangent, it explains precisely why Nelson's proof can generalise to give the BFPT in two dimensions, whereas the nested intervals proofs (which you claim is the same) cannot.
You then brought up that the BFPT generalisation of Nelson's argument needs the Sperner lemma as "crucial additional ingredient". Now you make the same point again:
> What I'm saying is that for the coloring proof of BFPT to work, whether clothed in standard or nonstandard language, you must perform a combinatorial argument that uses a topology of a triangle as a necessary ingredient, similar in shape to the proof of Sperner's lemma.
Presumably you keep pointing this out because you think it justifies some claim like '1D Nelson is actually nested intervals with the limiting step recast in nonstandard language, even if the 2D generalization of Nelson is not'.
But it does not. The combinatorial content is the same, the 1-dimensional interval case uses the topology of the domain just as much as the 2-dimensional triangle case does. The 2D argument wouldn't work on the annulus, and the 1D version would not work on the union of two disjoint intervals. The Sperner lemma is present in 1D, and present in 2D. If instead your point is only that proving the BFPT requires a harder case of the Sperner lemma than IVT, then of course it does. But what relevance does that have to the original claim that Nelson's IVT proof is the nested-interval proof? The proof of the Sperner lemma is pure combinatorics, it does not involve any (standard or nonstandard) analysis.
Or have you changed your mind on your earlier claim that Nelson's proof is "is the standard nested interval proof"?
If so, I think that's great, and closes the thread on whether NSA is largely the same arguments, since even the first proofs of the basic results are different.
If you still think that it's the nested interval proof, well, I am not sure what else to say, apart from linking the literature which studies this exact question, that I've already done, and that you dismissed as a tangent.
Either way, this discussion went on for too long at this point, so I won't monitor it further.
A professor of mine had an anecdote of meeting Serre and complaining to him about Bourbaki style and how hard it is for students.
Serre's reply was "But we never wrote those books for students! We wrote them for researchers to have a handy reference for all proofs of basic results."
None of this makes sense or is supported by the facts. Stripe is reportedly valued at $159B, PayPal's market cap is currently $52.59B, and your claims about memes and Wall St are asserted without any citations or facts.
I agree with you in principle but I don't think that market cap is the right metric. Market cap captures a lot of assumptions around product mix and growth rates that have been in Stripe's favor for a long time.
The most apples-to-apples comparison is just looking at payments volume and ignoring all their other products. In that case, Stripe just recently overtook PayPal! PayPal is enormous! But Stripe has that compounding growth on its side and GP's argument has become outdated in a short amount of time.
This is ignoring the bit about pc which I just disagree with.
But that value is not tested or backed by the wider market.
Market cap of paypal is.
Also having just spaffed "$8bn" on openrouter, I would be surprised that they have enough resources to get the ~$50bn to buy paypal. Much less the work it would take to integrate a much larger company in to the "stripe" way
This might just be realistic about the median American's tolerance for walking. Most Americans live in suburbs that are not walkable. At least, I know my own tolerance for walking is very abnormal for an American, and it's due to having lived in walking-oriented cities like Berkeley.
Transit App allows you configure both your walking and cycling speeds. Works great (will show you 15-20min walking), generates lots of options on how-to-get-there (e.g. bike-on-bus, Uber to train station), gives more accurate ETAs. Also instead of reducing "public transit" to a binary, it gives you much more granularity in enabling/disabling which bus/tram/light-rail/mass transit/train options, and even which specific bus route numbers to prefer.
> This might just be realistic about the median American's tolerance for walking.
This might be unrealistic about the number and relevance of Median-Americans. Turns out more than a few Americans that are outside of the median own telephones.
The author cites a study (Rozado, 2024, in PLOS ONE) that supposedly shows the base models (before assistant-specific post-training) basically scored at the center (0, 0).
I think the idea is that a small program can organize its allocations and data structures to minimize number of calls to malloc, e.g. with preallocated workspace structs, or slab allocation, and similar approaches. But as a program gets bigger, there's a pressure to have looser coupling, to have subsystems with simple convenient APIs which leads to them doing on-demand malloc calls internally, rather than having consumers pre-allocate their needed workspace. Because that kind of workspace management results in more complex APIs and more burden on the consumer.
That said, I don't really believe it either, at least for the kind of codebase where it would matter (scientific computing, in-memory DB server, etc). A codebase that places an emphasis on minimizing heap operations in hot codepaths can do so by consistently using workspaces and allocation-avoiding APIs. I don't think it's so difficult really, but it does take a conscious design decision to do so. But writing something like a web browser in this way could be annoying due to most data having wildly variable sizes, and zig's arena concept would be very handy -- but rust has crates like bumpalo for that purpose.
My personal mantra: "Think in FORTRAN, code in Rust/Julia/C++". But I'm mostly working on HPC-style code where I don't have to do with wildly varying input or output sizes.
reply