> three issues: "How big is it", "Who owns it", and "Who locks it"

The issue with this kind of thinking is the belief that there is a "it", not "they".

Say, you are writing a HTTP server [1]. A beginner mindset (what seems to be demonstrated in this post) with start allocating left and right, for every HTTP header, for every piece of string, for every piece of metadata record, etc. Thus, "how big is it" become no bigger than it needs to be. The lifetime of these allocations and deallocations will be made as "narrow" as possible, meaning that the programmer will try to deallocate as soon the they stop needing the data stored; "who owns it" becomes the user of the data itself. And so on.

However, think of an alternative strategy, something which game and embedded developers have been using for decades. You allocate a memory arena when the HTTP request comes. From that point on, every "allocation" is equivalent to bumping a pointer in that arena. If the arena gets full, we allocate another and chain it to the previous one, as a linked list. No deallocations are performed (or could possible be performed) until the Request is parsed, relevant processing is done, and Response is constructed and sent. At this point, the entire arena chain associated with that particular request-response cycle is deallocated in one go.

How big is it? We don't care, smaller than the arena.

Who owns it? That particular request-response cycle.

Who locks it? No one, if different request-response are parallelised wrt each other; otherwise, depends on the nature of concurrency/parallelism.

[1] Usually, I would have given a gamedev example, and then people would have said that it only works in gamedev. That's why I have tried to give a webdev example, considering the majority demographic on this website.

Some reference:

1. Mike Acton's CPPCon Talk: https://m.youtube.com/watch?v=rX0ItVEVjHc

2. Rant by Casey Muratori (Brusqueness Allergy Warning): https://www.youtube.com/watch?v=f4ioc8-lDc0&t=4407s

> You allocate a memory arena when the HTTP request comes.

The per-request-arena concept is one of the most powerful and IMO underappreciated tools out there for dealing with memory-lifetime issues. I've used it or advocated for its use at multiple jobs and projects, quite successfully, even for kernel code. Windows NT uses it in IRPs. Network code in both BSD and SysV did something pretty similar, at least in the long-before-Linux days. It's tried and true. Having a clear moment when things should be freed and an equally clear description of what those things are is wonderful.

That said, even games and network servers and storage drivers often have other complex data structures not related to individual requests. It's usually not hard to come up with rules for each of these, but the rules forced on you by something like STL might not be as convenient, performant, and/or verifiable as those you come up with yourself.

I hope that some day programmers will stop using memory-unsafe languages except when they really need to, and that when it is necessary those languages will give them the tools to solve those problems themselves instead of pretending they're already solved. They're not. Rust's borrow checker plus Zig's arena concept plus a couple more pieces might actually get us there. C++'s feature salad never will.

Maybe I didn't express myself properly (English is not my native language), but the point wasn't that everyone should use Memory Arena™ instead of Smart Pointers™ or Borrow Checker™. I am not trying to sell a conference here :)

The point was, to put it in Mike Acton's words, "when there is one, there are many". Usually, things are grouped, perhaps semantically, and it make sense to think of them as a group rather than breaks them in pieces. Arenas are one rather simple grouping mechanism, but they are not the only one. Of course, explaining complex grouping will require explaining the associated problem-solution pair, which is obviously out of scope of a forum reply.

All I would say is, if one steps out of one-at-a-time thinking, and statically plans the dynamically happening data transformation, and therefore exploit patterns and relationships inherent in that data flow, programming in low level languages becomes much easier.

But you need to know the problem (really really know it), and you need to know the solution. Temet Nosce.

> Rust's borrow checker plus Zig's arena concept plus a couple more pieces might actually get us there. C++'s feature salad never will.

Looks like there's some new salad growing.

A nice, obvious way to get a per session arena for almost all resources is to fork a process.

Um, yeah, but there are other issues that make it not so nice. And it's an inoperative concept for most kernel/embedded work. I'd say in most contexts where forking would be OK you should be using a GC language anyway.

> And it's an inoperative concept for most kernel/embedded work

I recently integrated mini_httpd (a small forking server) into an embedded system as part of a solution for distributing updates across a cluster of these systems.

You must be talking about 15 cent microcontrollers (that still have a TCP/IP stack with SSL) or something, not ARM cores with MMU's running Linux.

I said most kernel or embedded. It's lovely that there are all sorts of embedded devices nowadays capable to support a style of programming indistinguishable from a general-purpose system, but that's not the only or even most relevant case. There are also billions of devices out there - not just 15-cent microcontrollers either - that don't lend themselves to that style because of real-time or other requirements. Even within a conventional system, there's a ton of stuff in the kernel - pre init, board support, most storage and networking - that can still use a per-request-arena approach to good effect but can't fork a process.

As I said, if you can fork all the time you probably shouldn't be using a memory-unsafe language anyway. Nothing you've said so far has suggested otherwise. The basic techniques for implementing your own memory safety are still valuable and worth discussing for people who aren't in Easy Mode all the time.

This subthread is strictly about web serving. Requirements combinations like "HTTPS serving in pre-init or board-support code" or "real-time HTTPS serving in under-powered embedded board" are not practical or relevant, unless we replace "HTTPS serving" with something else.

With regard to the other point, if we are using a memory-safe language, then we can use fork to get an instant arena, regardless of how that language performs resource management under the hood. Whatever allocations happen in the request, of memory or file descriptors, are reliably gone when that exits. If there is any problem in the implementation of the memory safety, the failure is contained to a process. Thus we have an additional reason to use process containment: not having control over the memory management, and not trusting it 100%.

A meta comment, not really related to your point, but I found it amusing in context.

You're writing about how doing lots of little things in an HTTP server is inefficient; and you're replying to John Nagle, who contributed the Nagle TCP optimization that debounces tiny sends with a little bit of delay, in the hope of doing more work in one go!

(On topic of your HTTP example: this is where generational GC can shine. Ideally one of your younger generations covers the full allocation cycle for a request & response, so that nothing survives the collection and it's ultra-cheap to collect since tracing the roots doesn't find anything. The nice thing about GC instead of an explicit arena is that it's global, so you don't need to contort all your library calls to ensure they're using the right allocator.)

Game dev here. Try reading the Godot code base. It's tiny allocations all the way through.

It's really quite bad.

BUT

I'm using it professionally and it's useful. It's hard for me to mentally reconcile how good and bad the creator of Godot simulatenously was (is?).

Casey also goes way too far in his take (as usual).

RAII is a method to guarantee safety and correctness. It's useful in many many scenarios.

Game dev and c++ is a great area to hone your performance skills. And it's awesome to really squeeze the power out of a CPU, but doing that is only a small small piece of the game development journey. Ultimately, you must make a product that is entertaining.

PS: Mike Acton's talk is really only tangentially related. He's just talking about uber perf in general.

As productive and useful as Godot is (it is an awesome engine), its design resembles game engines of the late 90s to early 2010s when OOP was all the rage. Back then, most game engines were written that way (lots of tiny heap-allocated objects, connected by shared pointers). It's really just since the 2010s that the CPU/memory gap is the main driving force of game engine design (which wasn't much of an issue in the late 90's).

On the other hand, many games don't need to juggle more than a few dozen to a few hundred dynamic instances of one "thing" (outside of the particle- and animation-systems at least), so for most games a modern ECS design is definitely overkill (except for some specific parts of the game). Providing a good "game building workflow" in the editor is definitely more important.

Hey Floh, love your work! It's validating to hear you say these things. For me, the biggest annoyance with Godot's code base is the lack of clear ownership semantics (no use of smart pointers), and the use of fully hand rolled collection types for everything. It makes it hard to inspect variables in a debugger! Also the performance of the collection types are bad because of all the allocations. Seems like those problems will never get solved as it would be too expensive to rectify.

Well, I'd be surprised if the design/"entertainment" focussed part of the game is bring written in C or C++.

Actually, you know what, I would not be surprised, just disappointed :)

EDIT: Unless its a small indie studio, of course. In that case, do whatever works for you. Go nuts, have fun!

A fairly common way is to first implement experimental gameplay logic in a scripting- or visual-language, and once it works, extract the performance-critical parts into "proper" C++. Basically, the common lower level gameplay building blocks are written in C++, glued together by some higher level mechanism (like noodle graphs or a scripting language, and common features move into C++ as needed). Unless it's Unity, in that case, replace C++ with C#.

Wow, Casey doesn't hold back. Clearly, without hesitating says that 100% of code written in RAII* style sucks. Interesting considering Stroustrup considers RAII to be "the basis of some of the most effective modern C++ design techniques."

I'd like to hear Casey's comments on TDD.

*RAII style is lumped together with try/catch, smart pointers, tons of malloc/free new/delete

Casey hasn't a clue. He's only written games and he hasn't actually had to solve the issues that are being solved by in other domains. If he actually did have that experience he'd see his ideas don't scale. Games are in generally, vastly different than other apps (word processors, video editors, browsers, etc) in for one, for the most part, they get to choose all of their data upfront. If you're making "The Last of Us 2" there is no user data. There's no "some people will use this to write a letter to grandma and yet some other people will write an 800 page book on physics with mathematical diagrams" and yet another will write a report on the market with linked live data.

Consider "games" like Minecraft, Roblox or Dreams, those are entirely user-data-driven. Different types of games are at least as different to each other as to other types of applications (or rather, they are not less diverse than other applications, they usually just have a higher focus on performance).

How are they different? You have some primitives like a block, and meaning is given by users to a group of them. The program has to care only about the primitives.

(Of course making it performant, not rendering/“simulating” everything and the like is exceedingly hard, but it is true that it is more of a “closed world” as opposed to some other areas of software development.)

This type of "creative games" lets users combine basic building blocks in the same way a word processor application allows to write entire books by combining a a limited set of characters. The limitations of strictly linear games like Last of Us are not because of technological restrictions but because it's hard to tell a cinematic story while still giving the user complete freedom.

I'm pretty confident Minecraft, Roblox, and Dreams are not following Casey's practices.

What makes you say that?

Minecraft was created in Java with ducktape and hacks and a lot of ugliness and perf characteristics which wouldn't fly past a pedantic programmer like Casey

Is your argument that arenas don't scale because user-provided data is variable in size?

Although arena memory is casually described as "allocate one huge chunk of memory up front," you are not literally only allocating one block ever and praying it never runs out. If you run out, you allocate another block. The point is that you don't call malloc for every string, object, list, etc. Adhering to this largely eliminates the need for RAII. What about this doesn't scale?

Personal anecdote: I'm building an IDE, where literally all of my data is provided by the user, and arenas have worked perfectly. I don't think I have a single destructor except for dealing with things like file descriptors, etc.

I wonder, has Bjarne Stroustrup even shipped any industrial-grade software? Because he's mostly an academic AFAIK.

Bjarne Stroustrup is a Director at Morgan-Stanley, a major investment bank in New York where software difficulties may cost millions of dollars per minute. He has described his workday as people coming to him with a difficult software engineering problem, about which he asks increasingly detailed questions until light dawns, and they go away ready to re-write the badly designed subsystem causing the trouble.

Often, just the act of explaining your problem to someone results in possible answers. (see Rubber Duck Debugging https://rubberduckdebugging.com)

When using a "rubber duck" I think you just force yourself to turn loose thoughts into coherent ideas by having to express them clearly. This can reveal some problems that were not apparent before the idea was expressed. It's a "rubber duck" because it's really just a monologue and an inanimate object could do the job of the listener.

What's described above seems more like Socratic questioning, where a person asks questions that reveal facets of an idea that the person being asked may not have considered, thereby prompting the asked to rethink their assumptions and draw new conclusions.

Everybody describes their own day like that

I have no idea what "industrial grade software is", but I ship a cross-platform DAW written in C++, and RAII is tremendously awesome.

Are you saying that it is better than the alternatives? Have you tried writing code from a grouped-resources perspective? What was your conclusion?

I don't see grouped resources as an alternative to the way we use RAII. It doesn't mean that the approach doesn't have its own merits, but it doesn't cover the things we do with RAII. The architecture of a DAW isn't much like a server that responds to requests, even if there are elements of it that do correspond to that pattern.

Alternatively, you are referring to something I'm not aware of.

Edit - Already answered in more detail, below.

He is at Morgan Stanley,

https://www.morganstanley.com/profiles/bjarne-stroustrup-man...

I don’t know how close he is to the grind, but I imagine he at least talks to people who are reasonably often.

Does TDD here mean ‘Type Driven Development’ a la Idris or, as I assume (and seems more likely) does it mean Test Driven Development?

If you mean test driven, I don’t think I have heard Casie discuss anything remotely close to the standard presentation of TDD strategies. I would imagine, based on watching a large amount of Casie streaming, both alone and with Blow, that he would view testing (as in TDD) as unproductive for his particular style of development and his goals as a programmer. But, since it’s in my brain now I will ask him next time I catch a live stream just to satisfy my curiosity.

I can’t speak to any discussions specifically about TypeDD. But would bet Casie would be wholly uninterested and consider it theoretical academic fluff that pulls away from the fundamental data transformation work of development.

Your comment reads like you disagreed in some way with the parent, but then you showed a scenario and defined it in a way you can answer the important questions. Just drop the "we don't care" part and they're all good answers that can be used to model the ownership and usage.

The lack of locks in this scenario is important in itself and can be expressed in types. (It shows for example that as long as the whole process is migrated to another thread, you can have safe N:M scheduling) The process ownership of the arena can be well defined as well.

The "alternative strategy" as you described it doesn't have different questions - just different answers.

No, the point wasn't a scenario. The point was to stop focussing on individual allocation-deallocation and start thinking about the data transformation pipeline. And every program is a data transformer — because data transformation is all a computer does or can possibly do.

When one starts thinking in terms of data transformation pipeline, and start to relate lifetime of data with the lifetime of various phases of that pipeline, then one stops worrying about individual "objects" and start thinking in terms of aggregates. Suddenly, there is no need to track the ownership or size for each object, because those properties are now shared with the same (or isomorphic) properties of the phases of pipeline itself. As long as the position in the pipeline is tracked for (e.g., the call stack), all other lifetimes will automatically be tracked.

I get the idea you're describing and use it for various purposes. But I don't agree "there is no need to track the ownership or size for each object". You can offload some of that thinking to the arenas, the same way you'd do it with GC, sure. But you can't just ignore ownership - sure request context is owned by the arena - but do you need to copy the values you pass to logging? do you need to wait for log flush before destroying request context?

What about the more common cached data / process state?

Arenas simplify the processing just like GC but they're not magic and don't solve everything.

Arenas are just one tool amongst many; I am not talking about some specific magic tool, but about software architecture itself.

Please read this other reply I made in the same thread: https://news.ycombinator.com/item?id=26938577

EDIT: And about data sharing (with logging, etc.), that's part of the data pipeline too. So yes, your aggregation mechanism will take it into account. These are not two separate problems, irritatingly coupled due to reality; these are two parts of the same problem.

> From that point on, every "allocation" is equivalent to bumping a pointer in that arena.

I'm not a C++ developer, so I have a hard time imagining how would this be implemented in real code. I know how to allocate a blob of memory, but how do I redirect all the later allocations (that use `new` or that are hidden in std::string and other containers) to use parts of that blob? How do I know when the blob is going to overflow so that I need to allocate another one? Is it possible to give 5-10 lines example showing the basics of the technique?

It’s not an either or thing, there is probably no need to allocate strings in the arena. Some cpp structures do allow for custom allocators, but you are more likely to have an arena instance and call some specific function on it and it will do the allocation for you. It usually operates on only a few types, not meant for arbitrary allocations.

> Some cpp structures do allow for custom allocators,

Yeah, that's what I was thinking about, but my only knowledge of allocators comes from gcc error messages which include all the template parameters - I have no idea how they work or how to switch to another one :(

I get the idea, though, it's basically what Erlang does for its processes - each one has a "private heap" just for it. If the process exits, the whole chunk of memory can be reclaimed and there's no need to run GC on it anymore (there's no sharing of memory between processes in Erlang, at all, so it's safe).

You either pass the allocator around to every stl container, and everything that uses an stl container. Or you override new/delete and have a sidechannel that defines what arena to allocate in.

The second option seems much more convenient - I didn't know you can do that!

Sure, here is a snippet: https://pastebin.com/XGUeKdyk

Disclaimer: Quickly typed it on phone, so might make your computer explode.

Another optimization would be to keep the request buffer around and use it as backing storage for all the strings objects that result. The weakness of this strategy is that it doesn't make sense to keep it around if you only need a small part of it. It's a common source of memory leaks in Java where `String.substring()` just creates a new object with different start and end indexes for the same backing buffer.

A possible disadvantage of arena allocators is that everything is now tied to the lifetime of the arena, even though it might not be required that long. You'd need to practice a strategy like subarenas, RAAI, garbage collection or reference counting within the request as well.

The occurrence and advantages of all these strategies unfortunately are heavily workload-dependent. Most strategies work well for 80% of the workload. Different workloads of course.

This is why I'm a strong advocate of hiring former game developers - they know what matters when it matters, not before, and not after. how? Pain and tears of being there, trying in the obvious wrong way first, and then fixing it during production while kiddies shout at you. Former game devs are the Marines of software.

What asiachick wrote below.

Muratori has demonstrated to me one time too many that he hasn't a got a clue about the things he's talking about.

To be precise: He may or may not have a clue about some things he's talking about, but I don't know enough about them to form an opinion. But in more than one occasions he went on to talk (sometimes at great length) about things where I know he's mostly or completely wrong in what he said.

I don't have a way to know the scope of these things, the things he doesn't know or understand yet talks about. Maybe it's just when it comes to "systems programming". Maybe it's everything that isn't game design and programming. And maybe he's wrong about games too. As I said, I don't know enough to judge everything he says, but the things I was able to judge convinced me not to trust him and his opinions.

And since I can't set the scope safely, I have to not trust him regarding everything.

For example, while his post[1][2] on ETW being "the worst API ever made" is slightly amusing and has _some_ good points, it mostly demonstrates:

(a) Inability or unwillingness to read the documentation. It would have saved most of his problems. But let's say that to criticize the _design_ of an API we can disregard that for a moment.

(b) Inability or unwillingness to pick the right tool for the task or pure trolling.

(c) Worst of all: Complete lack of understanding of the goals, purposes, limitation, design goals and tradeoffs of the system.

You can't criticize the design as being too complicated, while offering an irrelevant alternative for a "glorified memcpy()" (his words), when you don't understand what it does or what it's supposed to do.

(I emphasize again: I'm not saying the API is a paragon API design and that all is perfect there. I am saying the criticism is both grossly exaggerated and demonstrates misunderstanding of what the API actually does.)

After a couple of those I don't trust him and you shouldn't either but you're welcome to.

[1] https://caseymuratori.com/blog_0025 [2] https://news.ycombinator.com/item?id=8146124 See the discussion there.

> You can't criticize the design as being too complicated...

I hadn't finished reading the ETW rant; but I don't see anything wrong with it. All he seems to be saying is that for communicating with OS, ioctl-like all-in-one APIs are bad while epoll like APIs are better. Not really a controversial statement.

> After a couple of those I don't trust him

Who said anything about trust? I have made enough mistakes and learnt enough lessons, and it's nice to see other well-respected programmers (like Casey and Mike) come to the same conclusions like mine. To paraphrase your post: "You shouldn't repeat those mistakes but you're welcome to".

EDIT: Actually, after finishing reading the blog post, wow! I thought Linux's perf_event API was shit, but this ETW crap takes the cake. Well done, Microsoft; you had one job.

While I agree with the sentiment, my impression is that the GP's point is about memory safety rather than performance. So yes, this applies for common patterns like per-frame memory in games, in which case the "it" is the arena. Otherwise, as a general rule, profile first, then optimize.

> this applies for common patterns like per-frame memory in games

Even though I went to the trouble to give a non-gamedev example...

It's not about optimization, it's about resource management, an alternative to GC or RAII.

I made a special purpose http sever in C++. I had a function called request() and just allocated everything in the stack of that function. Only a few KB. eg a vector of the headers etc. Of course after the function was done the memory was freed.

> You allocate a memory arena when the HTTP request comes. From that point on, every "allocation" is equivalent to bumping a pointer in that arena. If the arena gets full, we allocate another and chain it to the previous one, as a linked list.

Didn't you just describe the regular memory management as applied by OS in a process scope? At the completion of the process, all memory allocated by the process is reclaimed.

On some systems this approach is combined with granular quotas to allow multi-process coexistence.

Shifting this sort of memory management over to application scope may yield benefits now, but ultimately it's an OS-level concern.

Asking the OS for memory is a low-level operation, which means it is not portable and should be done by a library or framework. Also, since it's a syscall (involving a context switch), you don't want to do in performance-sensitive code.

Some applications might benefit from allocating huge pages. By default, the page size is something of the order of 4KB or 16KB. Large numbers of pages result in huge overhead. By allocating fewer, large pages on the order of MBs can help.

Interestingly it's exactly what the PHP memory model does, each request is a shared nothing VM space, nothing survives the end of the request, even if allocated memory objects don't get free'd.

The same Mike Acton that now is an Unity employee, being one of the team leads on Burst compiler for HPC#, and not a big C++ fan anyway.

It took me a while to understand what C++ was: a quest for the highest level semantics possible with the lowest performance overhead. It is a quest started a long time ago with a lot of dead ends and circumvolutions.

The quest is still valid but really, the complexity that C++ has given birth to is not worth it anymore. Other languages restarted from a blank state and are probably better bets. I almost switched to D years ago, for a while it looked like Go was going to take over but finally Rust seems to be it. My current work forced me to get into rust, and I don't think I'll go back to C++ anytime soon.

It was a fun ride. So long and thanks for the fish.

That is an interesting take, I don’t really disagree (regarding the high-level semantics/lowest overhead). I do question the use of ‘highest’ as the qualifier for the semantic level, but certainly would support a claim that the goal was some indeterminate high with regards to the semantic level. Even at the inception of C++ as something different than C with classes, there were at least a few languages with a higher semantic level than where C++ is today. Although I do not think there was any then current strategy for making those languages as low overhead as C in practice. So as time has progressed and the cruft and complexity have built up I think they have now decided to find the highest level they can reach, while maintaining backwards compatibility and the low overhead requirements.

I am inclined to agree that a green field language is probably a better bet for achieving the goal, but I am not sold on any of the current contenders. So I still plod along doing my performance sensitive development in stripped down C++ and plug away at my pet language project.

> It took me a while to understand what C++ was: a quest for the highest level semantics possible with the lowest performance overhead.

I find it interesting that it took you a "while" even though Stroustrup was already defining like that before C++98: https://books.google.fr/books?id=hS9mDwAAQBAJ&pg=PT151&lpg=P...

I'm not sure what you mean by "global analysis," but Rust's borrow checker doesn't do any analysis that I'd consider "global."

I think there's something important here, potentially obscured by imprecise terminology.

The Rust safety invariants are, at heart, global properties. The central one is that mutable references are unique. Another way of saying that is: if you hold a mutable reference, then all other references held by all other objects in the system do not conflict with it (either because it is included in the "stacked borrow" or because it doesn't reference the data at all). That kind of property is ordinarily quite difficult to prove.

Rust does it though, by encoding these invariants in the types of functions. Most importantly, these types compose, meaning if you've got one function that respects these invariants calling into another, then the whole thing will also be sound. You can compile them separately and still be confident.

By contrast, achieving similar goals in the C family of languages does require a global analysis. The classic example is alias analysis. It's implemented in many compilers, tons of PhD ink has been spilled, but long story short it doesn't work. You get okay results sometimes on small programs[1], but as systems scale up, basically there always becomes a way for one pointer to alias another.

Thus, the claim I would make is the following: it will not be practical to retrofit Rust-style borrow checking onto an existing unsafe language, because the type system has to be rich enough to express the types of invariants required. The Rust type system has been carefully crafted to be powerful enough, at considerable cost: the complexity of the type system is one of the biggest complaints about the language, and slow compile times, one of its correlates, is another.

I would also claim that trying to scale up static analysis (based on alias analysis and other similar global analysis techniques), while perhaps somewhat helpful, is not going to give comparable results as Rust. In order to get anywhere near the level of confidence that all possible safety problems have been caught, the false positive rate would be unacceptably high.

I think this is one of the enduring achievements of Rust, and one likely to be carried forward in future programming language designs, but extremely unlikely to be successfully retrofitted to existing languages.

[1]: https://digitalcommons.calpoly.edu/cgi/viewcontent.cgi?artic...

The point of the borrow checker is to replace the global property 'all memory has an owner' with the (approximate, conservative) equivalent 'all code passes the borrow checker'.

By tracing ownership information through each component, and forbidding (or ignoring via `unsafe`) situations which cannot be traced in this way, the latter property can be decomposed and solved locally.

In other languages, like C++, we may still want this global property, but we can't break it down into local reasoning. Even if we decide on an approximate, conservative equivalent like 'all code passes STATIC ANALYSER X', getting local reasoning to work would require enough changes that it's arguable whether we're actually programming in the same language anymore. For example, we may need to add extra annotations to our code (which aren't present in existing codebases); we may need to extract extra information from sources (preventing the normal use of separately-compiled libraries); we (and our dependencies!) may need to avoid certain valid/legal patterns of code which the analyser can't handle; etc.

Writing the above, I'm reminded of trying to use the mypy type checker in Python!

In other languages, like C++, we may still want this global property, but we can't break it down into local reasoning.

That's exactly it. You want some set of machine-checkable constraints which add up to the desired global properties. Rust managed to do that. Attempts to fix this in C++ yield a set of slightly leaky constraints which sort of almost do that. Fixing this requires taking things out of the language, which is unpopular.

It's embarrassing that the code below still compiles with default gcc options, in either C or C++ mode. Yes, it's terrible C++. The compiler allows it.

    #include <stdio.h>
    #include <string.h> 
    int main(int argc, char* argv[]) {
        char buf[20] = "\0";
        char* s = buf;
        for (int i = 0; i<argc; i++)
        {   s = strcat(buf, argv[i]); }
        printf("%s\n",s);
    }

(Even Microsoft has "strcat" deprecated by default.)

D's ownership/borrowing system does data flow analysis within functions, i.e. it's intra-function. Inter-function (global) is handled via the function signature.

I think the idea is more like "the entire program is covered by lifetime analysis / borrow checking, so that nothing gets missed." Something like that?

Data-flow analysis is what I assume the author meant. Fancy word for "reasoning about behavior at a level higher than just a syntax node" (usually within a function or module, possibly within an entire program though)

Both D and Rusts compilers do it, and I'm uncertain whether Zig's does but it may too.

"Global analysis" is specific compiler optimization terminology. It refers to analysis across so-called "basic blocks" (also compiler terminology). See here: https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/l...

That's not true. Global analysis is a synonym for interprocedural analysis, which crosses function boundaries. An intraprocedural analysis that crosses many basic blocks is still "local" rather than "global".

This slide deck is weird. I've taught 143 before. Where did this come from? Perhaps in really old stodgy terminology before there was any interprocedural anything people used the words this way? I really don't know any static analysis or compilers person who would consider "global analysis" to mean "intraprocedural analysis that considers more than one BB".

It's funny because I also remembered it as cross-function analysis, but when I went back to grab a link I saw this and thought maybe I'm mistaken somewhere, so I just used this definition. Oh well. Main thing I was just trying to convey was that it's technical terminology.

Yeah that's so bizarre. Is this Alex's slide deck? Did a TA write it? Could it be tremendously old? Weird.

I don't know if it's actually wrong though, given that a procedure is just a block of code with one entry point (and let's say one return, for the sake of discussion). I'd have to jog my memory, but I'm thinking: if you can already optimize inside a function (but outside basic blocks), then I don't recall what would be so drastically different across functions. The fundamentally hard part does seem to be going from one basic block to multiple. I might be forgetting something though... do you recall?

Also, I don't think they're alone in this terminology either... see here: https://www.csd.uwo.ca/~mmorenom/CS447/Lectures/CodeOptimiza...

The only explanation I can think of is that this is old terminology that has stuck around in course material based off older textbooks that aren't bothering with any sort of interprocedural anything.

Function boundaries do make things fundamentally more difficult than basic block boundaries, for a large number of reasons. You can no longer have single definitions of values and updates to those values are not global updates for the entire program. This is why you need stuff like context/object sensitivity for interprocedural analysis but it doesn't matter for local analysis. Graph structures also become way more chaotic, preventing the nice efficient lattice movement you see in classical local fixed point computation.

Like, static analysis and compilers is my job and none of my colleagues would use this term this way.

But clearly there is some material using it that way. Weird. I've been wrong before and I'll be wrong again in the future. So I'm happy to be wrong here. Clearly there are some situations where "global analysis" is used to describe whole-function analysis.

Interesting... now I'm thinking maybe I was confusing it with interprocedural analysis? I've definitely seen the distinction made between them before, though I'm not sure if I've seen them mentioned alongside local analysis in the same text. I guess if you want to have fun this week, go ask your colleagues what the difference between local, interprocedural, and global analysis is. See if they say the last two are synonymous. :-)

Regarding the difference for interprocedural analysis: I'm not entirely sure I follow it unfortunately. Let's say you can do everything within a function. Can't you just inline all of its callees (at whatever depth you want) and do your analysis/optimizations based off the result of that? Inlining itself is a rather trivial mechanical transformation, and after that everything is inside one function again, which you can already handle. The only real obstacle here seems to be recursion, but if you just treat that as any other opaque function call that you can't optimize across, you should otherwise get the rest of the way there, right? What am I missing?

As a preface, it is difficult to speak about true fundamental limitations of things like abstract interpretation because "print Top" is a valid algorithm that will work for all programs. It is just completely useless. So you can model function calls in trivial ways (just treat calls and returns as giant phi nodes and widen whenever you hit mutual recursion). But this tends to produce pretty poor results for real programs and your fixed point computation tends to take longer due to the shape of real program call graphs. Add in dynamic dispatch and you've got all sorts of fun (watch all your pointers in a java program get merged through the receiver to Object.equals(), for example).

In practice, these structural differences require new approaches. The field has done a really good job at intraprocedural analysis, solving a lot of really important problems many decades ago. How to do fixed point computation over SSAed CFGs is well understood, even when you've got heap relationships to think about. Interprocedural analysis still largely sucks. Even modern approaches like CFL-reachability for dataflow analysis produce a ton of garbage. This is one reason why I say it is just harder.

As you mention, recursion prevents you from inlining everything into one giant function. You do get "the rest of the way there" by inlining to some depth limit in the sense that inlining is a way of achieving context sensitive analysis (though it is generally not preferred). But you've still got big problems at the points of mutual recursion (either you need to widen badly or you need to actually do interprocedural analysis) and your program is also exponentially larger in pathological cases.

Ahh I see! Thanks for the explanation.

>My comment for too many years is that C/C++ fails to deal with three issues: "How big is it", "Who owns it", and "Who locks it".

Ada has is pretty good at dealing with all three of these, TBH.

"How big is it" — Given by the 'Size attribute, and representation-clauses explicitly control record-layout.

"Who owns it" — The declaring entity, which is why you can have dynamically-sized arrays without heap-allocation and "allow the scope to clean things up".

"Who locks it" — a bit more convoluted than the above, but generally one of several options: (1) the Task / protected-object via entries; (2) the object itself, via controlled/limited_controlled inheritance; OR (3) the subprogram/compilation-unit via parameter-passing and/or interface-control (i.e. the only way to alter the interior-value is by some exported interface).

I think the biggest problem with C++ is the lack of explicit safety requiring you understand the internal mechanisms of how everything works in order to make use of almost anything, combined with extremely high levels of abstraction.

The high levels of abstraction are powerful, but quickly become footguns to the uninitiated (and the initiated alike at times).

> Figuring out how to do something safely can be quite difficult. It can involve solving puzzles, and often involves rewriting things at several levels, especially when threads are involved.

I think this gets to the core of really closing the gap. While the "insider" knowledge of C++ is really understanding the internal workings of these abstractions so you don't do something stupid with memory, the "insider" knowledge of Rust is knowing the specific patterns and routes that will work with the safety features of the language rather than against it for solving various problems.

I can still say for me I spend a lot of time 'exploring' Rust, having the compiler bitch at me, and tweaking things about until they work.

Sometimes it can be extremely frustrating, and given I have the insider knowledge of C++ with 20+ years experience, it's easier for me to just drop in and do exactly what I want to do (because I know it's safe... or at least I think it is ;) )

That being said, I'm very excited for languages like Rust, but there is still a gap of cost/benefit between it and C++ for the time being, at least for my professional use.

> footguns to the uninitiated

Well, that depends on the uninitiated. Those who come from a more "user-friendly" language, e.g. Java, are pretty much safe - they can continue with C++ and its Standard Library as if it was Java (as long as they respect the RAII principle). The C people, on the other hand, should expect to be bitten on the ass many times (try, for example, to use the pointer to an element of an std::vector after you have pushed some more elements into it!), and so you are right, those people are, unfortunately, better off knowing the internals.

> As a result, "unsafe" is too often used as an escape hatch when someone can't spend the time to get it right.

Isn't that exactly the same as C++ then?

Every time somebody got lazy and used "unsafe" in Rust that's unavoidably annotated in the code. If the compiler can't prove it's safe and you don't label it "unsafe" it won't compile at all.

Even coming in years later, a maintenance programmer can identify this code is suspect, whereas these other parts are safe.

Whereas if you get lazy in C++ you can do whatever unsafe things you want, anywhere, and it leaves no trace.

I don't see `unsafe` being used as an escape hatch IMO.

Same here, lots of large projects I worked didn't have any unsafe at all. It's a very niche feature, mostly for people doing very low-level stuff.

But I suspect this is survivorship bias. I only ever worked with very experienced developers when doing Rust. I'm pretty sure as soon as I start working with more inexperienced devs I'll start seeing a multitude of clever ways to bypass the borrow checker, similar to the cleverness I currently see them doing in other languages.

It's a feature that's necessary when dealing with FFI or when implementing containers. It's a tool, rather than a crutch to work around the borrow checker. In fact, unless one is using raw pointers everywhere, it's very impractical to use unsafe blocks to circumvent the borrow checker.

I was with you until the last sentence. I write Rust code at scale, with schedule and performance constraints. I’ve literally never had to use the word unsafe in my code.

If you can’t figure out how to do it without fucking up the borrow checker, that’s because you can’t figure it out, and you need to learn how to do your job. You’re never “forced” to hack anything.

Blaming “a whip of agile” is just bad taste. Don’t be bad. Like, wtf, you had a decent comment and then shat the bed right at the end.