The road to Zettalinux
lwn.net
lwn.net
CHERI is a much more interesting case, because it expands the definition of what a "pointer" is. Most low-level programmers think of pointers as just an address, but CHERI turns it into a sort of tuple of (address, bounds, permissions) -- every pointer is bounds-checked. The CHERI folks did some cleverness to pack that all into 128 bits, and I believe their demo platform uses 128-bit registers.
The article also touches on the UNIX-y assumption that `long` is pointer-sized. This is well known (and well hated) by anyone that has to port software from UNIX to Windows, where `long` and `int` are the same size, and `long long` is pointer-sized. I'm firmly in the camp of using fixed-size integers but the Linux kernel uses `long` all over the place, and unless they plan to do a mass migration to `intptr_t` it's difficult to imagine a solution that would let the same C code support 32-, 64-, and 128-bit platforms.
(comedy option: 32-bit int, 128-bit long, and 64-bit `unsigned middle`)
The article also mentions Rust types as helpful, but Rust has its own problems with big pointers because they inadvisably merged `size_t`, `ptrdiff_t`, and `intptr_t` into the same type. They're working on adding equivalent symbols to the FFI module[0], but untangling `usize` might not be possible at this point.
Many mainframes had function pointers which were more like a struct than a pointer.
The ObjC/Swift runtime uses that for instance, the class pointer of an object also contains the refcount and a few flags.
No, pointer tagging is spiritually a packed structure. That can be a simple union (as it is in ocaml IIRC) but it can be a lot more e.g. the objc “non-pointer isa” ended up with 5 flags (excluding raw isa discriminant) and two additional non-pointer members of 19 and 9 bits.
You mask things on and off to unpack the structure into component the system will accept. Nothing precludes using tagged pointers to discriminate between kinds and locations.
I nominally agree with most of your post. But I should note that modern systems seem to be moving towards a "one pointer space" for the entire cluster. For example, 8 GPUs + 2 CPUs would share the same virtual memory space (GPU#1 may take one slice, GPU#2 takes another, etc. etc.).
This allows for RDMA (ie: mmap across Ethernet and other networking technologies). If everyone has the same address space, then you can share pointers / graphs between nodes and the underlying routing/ethernet software will be passing the data automatically between all systems. Its actually quite convenient.
I don't know how the supercomputer software works, but I can imagine that 4000 CPUs + 16000 GPUs all sharing the same 64-bit address space.
Again, I'm not a supercomputer programmer. But the whitepapers often discuss RDMA.
From my imagination, it sounds like any other "mmap". You, the programmer, just remembers that the mmap'd region is slower (since it is read/write to a Disk, rather than to RAM). Otherwise, you treat it "like RAM" from a programming perspective entirely for convenience sake.
As long as you know my_mmap_region->next = foobar(); is a slow I/O operation pretending to be memory, you're fine.
---------
Modern systems are converging upon this "single address space" programming model. PCIe 3.0 implements atomic operations and memory barriers, CXL is going to add cache-coherence over a remote / I/O interface. This means that all your memory_barriers / atomics / synchronization can be atomic-operations, and the OS will automatically translate these memory commands into the proper I/O level atomics/barriers to ensure proper synchronization.
This is all very new, only within the past few years. But I think its one of the most exciting things about modern computer design.
Yes, its slow. But its consistent and accurately modeled by all elements in the chain. Atomic-compare-and-swap over RDMA can allow for cache-coherent communications and synchronization over Ethernet, over GPUs, over CPUs, and any other accelerators sharing the same 64-bit memory space. Maybe not quite today, but soon.
This technology already exists for PCIe 3.0 CPU+GPUs synchronization from 8 years ago (Shared Virtual Memory). Its exciting to see it extend out into more I/O devices.
Caring about where in memory your data lives is different from dealing with cache or paging. Programmers have to plan ahead to keep frequently accessed data in fast RAM, and infrequently accessed data in "slow" RAM. You'll probably need special APIs to allocate and manage memory in the different pools, not unlike the Address Windowing Extensions API in Microsoft Windows.
And once you extend "memory" outside the chassis, you'll have to design your application with the expectation that any memory access could fail because a network failure means the memory is no longer accessible.
If you only plan to deploy in a data center then maybe you can ignore pointer faults, but that is still a risk, especially if you decide to deploy something like Chaos Monkey to test your fault tolerance.
You have to deal with these things anyway in any kind of distributed setting. What this kind of location-independence via SSI really buys you is the ability to scale the exact same workloads down to a single cluster or even a single node when feasible, while keeping an efficient shared-memory programming model instead of doing slow explicit message passing. It seems like a pretty big simplification.
The marketing for SSI was that it was simple because programmers would not have to learn explicit message passing. Unfortunately, people that buy supercomputers tend to care about performance, so designing a supercomputer that is difficult to optimize misses the point. In real code, the only way to make them perform well was to layer topology-aware message passing on top of the shared memory model. At which point you should've just bought a message passing architecture.
There is only one type of large-scale SSI architecture that is able to somewhat maintain the illusion of uniform shared memory -- hardware latency-hiding e.g. barrel processors. If programmers have difficulty writing scalable code with message passing, then they definitely are going to struggle with this. These systems use a completely foreign programming paradigm that looks deceptively like vanilla C++. Exceptional efficient, and companies design new ones every few years, but without programmers that grok how to write optimal code they aren't much use.
It might make sense for large distributed systems to move to a 128-bit architecture, but I don't see any reason for consumer devices, at least with current technology.
No its not. That's why Kogge-Stone's carry lookahead adder was such an amazing result. O(log(n)) latency with respect to operand width with O(n) total half-adders used.
It may seem like its super-linear. But the power of prefix-sums leads to a spectacular and elegant solution. Kogge-stone (and the concept of prefix-sums) is one of the most important parallel-programming / parallel-system results of the last 50 years. Dare I say it, its _THE_ most important parallel programming concept.
> multiplication latency
You could just... not implement 128-bit multiplication. Just support 128-bit pointers (aka: addition) and leave multiplication for 64-bits and below.
I know it was one of the first time I thought to myself: this is not just a straightforward pipeline, yet it all follows such a beautifully geometrical interconnect pattern. Super fast, yet very elegant to layout.
"A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equation", by Kogge and Stone.
It proves the result for _all_ associative operations (technically, a class slightly larger than associative. Kogge and Stone called this a "semi-associative" operation).
A bit sad that 1974 papers are still behind a IEEE paywall...
Edit: Just finished reading it. I have to say that the generalization of 3.2 got a bit over me, but otherwise it's pretty amazing that they could define such a generalization. Intuition for those type of problem is often to proceed one step at a time, N times.
That it is provably doable in log2(N) is great, especially since it allows for a choice of the depth/number of processors you want to use for the problem. Hopefully next time I design a latency-constrained system I remember to look at that article
Nah. Your next step is to read "Data parallel algorithms" by Hillis and Steele, which starts to show how these principles can be applied to code. (Much higher-level, easier to follow, paper. From ACM too, so its free since its older than 2000)
Then you realize that all you're doing is following the steps towards "Map-reduce" and modern parallel code and just use Map Reduce / NVidia cub::scan / etc. etc. and all the modern stuff that is built from these fundamental concepts.
Kogge and Stone's paper sits at the root of it all though.
I feel like this sums up the way of thinking one must have in this paradigm.
It's funny because when designing digital hardware, you're kind-of trained to see things under that angle, since often the commands you write will expand in that tree-like structure, but to gates/ALU instead of data.
Then managing the data-path often piggy-backs on the hardware structure you just generated.
I feel like I have a overall grasp on these concept, yet there's so much interesting results that I don't know about...
There's going to be no issues implementing a 128-bit adder. None at all.
Transistors have a "latency" measured in picoseconds, not nanoseconds.
A 128-bit adder will have a latency of 1-clock cycle, a 10% increase from a 64-bit adder of latency of 1-clock cycle. Aka: it doesn't matter cause it'd almost certainly fit inside of the clock cycle of modern CPUs.
The VM system could quite simply track the physical addresses as a pair of `u64_t`s or whatever, and present those pages as 64-bit pointers.
It seems in particular you might want to have this anyways, because the actual costs for dealing with such external memories would have to be much higher than local memory. Optimizing access would likely involve complicated cache hierarchies.
I mean, it'd be exciting if we had need for memory space larger than 2^64 but I just find it implausible with current physics and programs? But I'm also getting old.
> If everyone has the same address space, then you can share pointers / graphs between nodes and the underlying routing/ethernet software will be passing the data automatically between all systems. Its actually quite convenient.
It's a disaster of latency issues too, but it's not like that's surprising anyone either, and we already have NUMA on some multi-core systems which is the same problem.
We have existing tools that can be extended in straightforward ways to deal with these issues. And it's not like there's a silver bullet here; having separate address spaces everywhere comes with its own disaster of issues. Pick your poison.
Having a single system image has many potential upsides, and understandability & reasonability are high among them.
I'm not advocating 128-bit pointers, or saying they're useful or realistic. I'm just saying, what if.
(For that matter, what happens when different segments of memory have complex access controls? What about needing to retry to failures like network partitions that don’t happen in a normal memory space?)
If latency matters, which it usually does, then you need some kind of memory access hierarchy, copying things back and forth, etc. and then you’ll almost certainly need a library of some kind to manage all this, prefetch from a slow range of memory and populate some of your fast local memory, etc.
At that point, we’ve done a lot of work, and are still pretending there is no network or the like, even though it’s there. It isn’t free, anyway. We’d also need checksums, cross network/fabric/access error handling, etc.
And with 128 bits, we could also use something like IPv6 with the lower 64 bits being byte address hah.
The HPC world is all about RDMA to direct-access their huge data sets, and likely hyperscaler clouds are starting to do that too.
The latency gap is just treated as yet another layer of the cache model.
And we already have error correction for local RAM.
Those were due to bottlenecks that don’t exist anymore, and even in your example were even then only emergency measures due to local resource shortages.
ECC is also not reliable/sufficient in the face of issues that arrive when networks start playing their part.
Having more space available usually opens up more interesting possibilities. I'm going to rattle off some assorted options. If there's multiple paths to a given bit of data, we could use different addresses to refer to different paths. We could do something like ILA in IPv6, using some of the address as a location identifier: having enough bits for both the location and the identity parts of the address without being too constrained would be helpful. We could use the extra pointer bits for tagged memory or something like CHERI, which allow all kinds of access-control or permission or security capabilities. Perhaps we create something like id's MegaTexture, where we can procedurally generate data on the fly if given an address. There's five options for why you'd want more address space than addressable storage. And I think some folks are already going to be quite limited & have quite a lot of difficulty partitioning up their address space, if they only have for example 1.6m buckets of 1TB (one possible partitioning scheme).
The idea of being able to refer to everything anywhere that does or did exist across a very large space sure seems compelling & interesting to me!
In the Grace Hopper whitepaper, NVIDIA says that they connect multiple nodes with a fabric that allows them to creat a virtual address space across all of them.
At that point, maybe you want 256bit or 512bit pointers so that you can build a single global addressable system for all memory in the world.
And seeing datacenter after datacenter shooting up like mushrooms, there might be some sort of abstraction running in this direction, that makes 128bit addresses feasible. At the moment 64bit seems like paging in this sense.
(They also fail to distinguish an equivalent of `off_t` out, too. Not that I think that would have the same bit width ambiguities. But it seems odd to refer to offsets by a 'size')
One use I can imagine is massively distributed computing where pointers can refer to things that are either local or remote. These could even map onto IPv6 addresses where the least significant 64 bits are a local machine pointer and the most significant 64 bits are the machine's /64. Of course the security aspect would have to be handled at the transport layer or this would have to be done on a private network. The latter would be more common since this would probably be a supercomputer thing.
Still... I wonder if this needs CPU support or just compiler support? Would you get that much more performance from having this in hardware?
I do really like how Rust has u128 native in the language. This permits a lot of nice things including efficient implementation of some cryptography and math stuff. C has irregular support for uint128_t but it's not really a first class citizen.
MS-DOS and 640K ...
Going past 2^64 bytes of local high speed RAM becomes a physics problem. I won’t say never but it would not just be an evolutionary change from what we have and a processor that could perform useful computations on that much data would be equally nuts. Just moving that much data on a bus of today would take too long to be useful, let alone computing on it.
Kilo is 10 bits. Mega 20. Gigs 30. Tera 40. 16TB is 44 bits. 1000* is another 10 bits so 54.
That is still an order of magnitude smaller than 16EiB. So no, not in a few years time.
Frontier's LustreFS based mind-boggling 700PB Orion storage subsystem writes at a similarly impressive 5TB/s [1]; so with a generous reading, it could potentially fill up in about 39h. Historically, disk density increased more rapidly than network bandwidth, which ultimately limits the performance of distributed file systems.
If it takes weeks or months to write such enormous data set, then there will be only few use cases, if it takes years there will be none.
[1] https://www.ornl.gov/news/frontier-supercomputer-debuts-worl...
Oops, that's nonsense. I had my coffee now...
Or rather than keep moving the long goalpost, keep long at u64/i64 and add prolong(ed) for 128. Or we could keep long as the “nominal” register value, and introduce “short long” for 64. So many options.
microsd card = 15x11x1mm, 0.5g
fits 437,503,976 cards = 379 EiB, costs $43.7B
219 metric tons
8 EiB ~ 10,000,000 TB = fills the shipping container 2.2% high or 56mm or 2 inches, 5 metric tons, costs $1B
shipping containers are rated for up to 24 metric tons, so ~40 EiB $5B 10 inches of cards etc
Seriously, that was great math you did there, and a neat way to think about volume. That's a standard shipping container [0], which is less than I thought it would be.
[0] - https://www.mobilemodularcontainers.com/products/storage-con...
So if you want to mmap() files stored in your datacenter warehouse, maybe you do need it?
rather than unsigned middle, could we just call it malcom?
An exabyte was an absolutely incomprehensible amount of memory, once. Nearly as incomprehensible as 4 gigabytes seemed, at one time. But as you note, 64 bits of addressable data can fit into a single warehouse now.
Going by the historical rate of increase, $100 would buy about a petabyte of storage in 2040. Even presuming a major slowdown, we still start running into 64 bit addressing as a practical limit, perhaps sooner than you think.
This was a major counterargument against 64-bit x86, where the transition came out as a net zero in terms of performance, due to the hit of larger pointer sizes counterbalanced by ISA improvements such as more addressable registers.
Many people in high-performance circles advocate using 32-bit array indices opposed to pointers, to counteract the cache pollution effects.
I don't know that that really means we need 128bit, 80 or 96bits buys a lot of time, but it's probably worth a little bit of thought.
I don't know how many of you remember the pre-386 days. It was an effort to write interesting programs though, 512KB or 640KB of memory to work with but it was 16bit addressable and so you're writing code to manage segments and stuff, it's an extra degree of complexity and a pain to debug. 32bits seemed like a godsend when it happened. I imagine most of the dorks on here have ripped a blu-ray or transcoded a video image from somewhere, it's not super unusual to be dealing with a single file that cannot be represented as bytes with a 32bit pointer.
It's all about cost and value, 64bits is still a staggering amount of memory but if the protein folding problems and climate models and what have you need 80bits of memory to represent the problem space, I would hope that the people building those don't also have to worry about the memory "shoe boxing" problems of yesteryear too.
It would be interesting to see something like this on x86 and ARM. I could imagine Apple implementing something similar.
In my opinion, developers should think about semantics first, optimization (device-specific or software) after (, unless you already know your device).
I slightly disagree with JVM "int = 32bit" but they essentially are forcing their own "virtual hardware", so I can understand that. For portable native code... I can only say that I'm disappointed in uint64_t. But also that, maybe, the current Rust isn't the end-all be-all of portable types.
On the other hand, filling out a 64 bit address space looks tough. I struggled to find something of the same magnitude of 2^64 and I got ‘number of iron atoms in an iron filing’, From a nanotechnological point of view a memory bank that size is feasible (fits in a rack at 10,000 atoms per bit) but progress in semiconductors is slowing down. Features are still getting smaller but they aren’t getting cheaper anymore.
Conceptually similar to ARM Morello/CHERI’s 129 bit pointers; although that is a much more sophisticated implementation than IBM 38/400/i.
Reminded me of Jeff Bonwick's answer to the following question about his 'boiling the oceans' quip related to ZFS being a "128 bit filesystem":
> 64 bits would have been plenty ... but then you can't talk out of your ass about boiling oceans then, can you?
Sadly his Sun hosted blog was eaten by the migration to Oracle, so thanks to the Internet Archive again:
http://web.archive.org/web/20061111054630/http://blogs.sun.c...
That one dives into some of the "handwaving" a bit:
https://hbfs.wordpress.com/2009/02/10/to-boil-the-oceans/
And that one goes into how much energy it would take to merely spin enough disks up:
https://www.reddit.com/r/DataHoarder/comments/71p8x4/reachin...
(1/2) kT
I multiplied that by 2¹²⁸, and got 1.41×10¹⁸ J of energy. 1 ton of TNT is 4.2×10¹² J, so that is a 335 kiloton explosion worth of energy just to boot.
That's not impossible, that much heat is extracted from a nuclear reactor in a few months. If you want to go faster you need a bigger system, but a bigger system will be slower because of light speed latency.
(You do better, however, at a lower temperature, say 1° K but heat extraction gets more difficult at lower temperatures and you spend energy on refrigeration unless you wait long enough for the Universe to grow colder.)
Used over the course of a year, that is a constant 44.4 GW. Less than Bitcoin uses already
- You could give every ant on Earth ~920 unique IDs without any collisions
- You could give unique IDs for every brain neuron for all ~215 million people in Brazil
- The ocean contains about 20 × (2^64) gallons of water (3.5267 × 10^20 gallons total)
- There are between 100-400 billion stars in the Milky Way, so you could assign each star between 46,000,000–184,000,000 unique IDs each
- You could assign ~2.5 unique IDs to each grain of sand on Earth
- If every cell of your body contained a city with 500,000 people each, every "citizen" of your body could have a unique ID without any collisions
Calculating these figures is actually a lot of fun!
https://web.archive.org/web/19990117001023/http://www2.hawai...
It takes only beach sand into account, and of course there's a lot of guessing involved. It could be easily off by many orders of magnitude.
And the original processor was 24 bits, then it was upgraded to 36 bits (not a typo: 36 bits), and then to POWER 64 bits.
(When that last happened, it was re-badged AS/400. Later, marketing renamed the AS/400 to iSeries, and then to IBM i, without changing anything significant. Still uses Power CPUs, AFAIK).
For users, upgrades were a slightly longer than usual backup and restore.
What's the hard part here?
Let's think critically for a moment. I grew up in the 1980s and 1990s, when we all craved more and more powerful computers. I even remember the years when each generation of video games was marketed as 8-bit, 16-bit, 32-bit, ect.
BUT: We're hitting a point where, for what we use computers for, they're powerful enough. I don't think I'll ever need to carry a 128-bit phone in my pocket, nor do I think I'll need a 128-bit web browser, nor do I think I'll need a 128-bit web server. (See other posts about how 64-bits can address massive amounts of memory.)
Will we need 128-bit computing? I'm sure someone will find a need. But let's not assume they'll need an operating system designed in the 1990s for use cases that we can't imagine today.
Like, no one has enough memory to need more than 64 bits for addressing, and that is likely to remain the case for the foreseeable future. However, 128- and 256-bit values are commonly used in domains like graphics, audio, and so-on, where you need to apply long chains of transformations and filters, but retain as much of the underlying dynamic range as possible.
I know it's hardly a typical or modern example, but the N64 had just 4MB of memory (8MB with the expansion pack). It most certainly didn't need 64-bit pointers to address that pittance, so it was a "64 bit processor" largely for the purposes of register/data size.
If the thing that can refer to a memory address changes size, there are very different problems than will arise if the size of "an integer" changes.
You could easily imagine a processor that can only address an N-bit address space, but can trivially do arithmetic on N*M bit integers or floating point values. And obviously the other way around, too.
In general, I think "N bit processor" tends to refer to the data type sizing, but since those primitive data types will tend to fit into the same registers that are used to hold pointers, it ends up describing addressing too.
But the argument that we need more than 64 bit capability for a lot of other reasons in conjunction with memory addressability is I think very strong. A lot of very powerful and safe techniques become available if we can tag pointers with more than a bit squeezed out here and a bit squeezed out there. I could even see hard-coding the CPU to, say, look at 80 bits as an address and then us the remaining 48 for tagging of various sorts. There's precedent, and 80 bits is an awful lot of addressible memory; that's a septillion+ addressible bytes, by the time we need more than that, if we do, our future selves can deal with that. (It is good to look ahead a decade or two and make reasonable preparations, as this article does; it is hubris to start trying to look ahead 50 years or a century.)
First, we should decide whether to have a microkernel or a monolithic kernel.
I think the answer is obvious: microkernel. This is much safer, and seL4 has shown that performance need not suffer too much.
Next, we should start by acknowledging the chicken-and-egg problem, especially with drivers. We will need drivers.
So let's reuse Linux drivers by implementing a library for them to run in userspace. This should be difficult, but not impossible, and the rewards would be massive, basically deleting the chicken-and-egg problem for drivers.
To solve the userspace chicken-and-egg problem (having applications that run on the OS), implement a POSIX API on top of the OS. Yes, this will mean that some bad legacy like `fork()` will exist, but it will solve that chicken-and-egg problem.
From there, it's a simple matter of deciding what the best design is.
I believe it would be three things:
1. Acknowledging hardware as in [1].
2. A copy-on-write filesystem with a transactional API (maybe a modified ZFS or BtrFS).
3. A uniform event API like Windows' handles and Wait() functions or Plan 9's file descriptors.
For number 3, note that not everything has to be a file, but receiving events like signals and events from child processes should be waitable, like in Windows or Linux's signalfd and pidfd.
For number 2, this would make programming so much easier on everybody, including kernel and filesystem devs. And I may be wrong, but it seems like it would not be hard to implement. When doing copy-on-write, just copy as usual, and update the root B-tree node; the transaction commits when the root B-tree node is flushed to disk, and the flush succeeds.
(Of course, this would also require disks that don't lie, but that's another problem.)
[1]: https://www.usenix.org/conference/osdi21/presentation/fri-ke...
I want better security in computing more than I want performance.
It's an unlikely hypothetical but imagine if fiber ran everywhere, and all computers seamlessly worked together sharing computer power as needed. Even 256 bits wouldn't be out of the question then. And before you say something like that will never happen consider trying to convince somebody from 2009 that in 13 years people would be buying internet money backed by nothing.
For 256 bit computers, we need entirely new CPU architectures and updated ISAs for not just x86/AMD64, but for other archs increasing in popularity such as ARM and even RISC-V. Even then compilers, build tools, and dependant devices with their drivers need updates too. On top of all of this technical work, you have the political work of getting people to agree on new standards and methods.
It may be of note that hypothetically one can have a soft-ISA 128 bit virtual address (a particularly virtual virtual address) which is JITed down into a narrower physical address by the operating system. This is as far as I'm aware how IBM i works.
More realistically though, we would throw away at least half that length like how we are handing out /64 blocks to everyone on IPv6.
> Right now our limitations in these regards are addressed by distributed computing and databases, but in a hyper-connected world there may come a time when such huge address space could actually be used.
Used at the core of the OS itself? How do you propose to beat the speed of light exactly?
Because you don’t need a zettabyte-compatible kernel to run a distributed database (or even file system, see ZFS), trying to DMA things on the other side of the planet sounds like the worst possible experience.
Hell, our current computers right now are not even close to 64 bit address spaces. The baseline is 48 bits, and x86 and ARM are in the process of extending the address space (to 57 bits for x86, and 52 for ARM).
> It's an unlikely hypothetical but imagine if fiber ran everywhere,
> and all computers seamlessly worked together sharing computer power
> as needed. Even 256 bits wouldn't be out of the question then.
The question is whether such an address makes sense for the Linux kernel. If your hyper-converged distributed program wants to call `read()`, does the pointer to the buffer really need to be able to identify any machine in the world? Maybe it's enough for the kernel to use 64-bit local pointers only, and have a different address mechanism for remote storage.
This sounds like it would be massively out of scope for Linux. It'd require a complete overhaul of most of its core functionality, and all of its syscalls. While not a completely infeasible idea, it sounds to me like it'd require a completely new designed kernel.
"A 64 bit memory space is large enough that if a process allocated 1MB every second, it could continue doing this until significantly past the expected lifetime of the sun before it ran into problems"
Can anyone explain the rationale for not simply naming types after their size? In many programming languages, rather than this arcane terminology, “i16”, “i32”, “i64”, and “i128” simpy exist.
> But a better solution might just be to switch to Rust types, where i32 is a 32-bit, signed integer, while u128 would be unsigned and 128 bits. This convention is close to what the kernel uses already internally, though a switch from "s" to "i" for signed types would be necessary. Rust has all the types we need, he said, it would be best to just switch to them.
Though I think there are portability issues concerns, that world is mostly gone (it remains in some corners of computing e.g. dsps) but if you’re only using fixed-size integers what do you do when a platform doesn’t have that size? With a more flexible scheme, you have less issues there, however as the weirdness landscape contracts the risk of making technically incorrect assumptions (about relations between type sizes, or the actual limits and behaviour of a given type) start increasing dramatically.
Finally there’s the issue at hand here: even with fixed-size integers, “pointer” is a variable-size datum. So you still need a variable-size integer to go with it. C historically lacking that (nowadays it’s called uintptr_t), the kernel made assumptions which are incorrect.
Note that you can still get it wrong even if you try e.g. Rust believes and generally assumes that usize and pointers correspond, but that gets iffy with concepts like pointer provenance, which decouple pointer size and address space.
Modern languages have unlimited size integers :-)
"Modern" as in "since at least the 80s, more likely 70s".
Either silently with overflows, usually leading to security exploits, or by crashing.
So in either case you are betting that these cases are somewhere between rare and non-existent, particularly for your core/performance intensive code.
Being somewhat slower, probably in very isolated contexts (60-62 bits is quite a bit to overflow), but always correct seems like the better tradeoff.
YMMV. ¯\_(ツ)_/¯
> but always correct seems like the better tradeoff.
Not if you are dealing with time constraints. Glitchy output isn't good, but locking up the system because some buggy code path is trying to allocate a 10 GB integer can be worse.
Er...all of them? I am not aware of one that uses growable integers as their default integer representation that does not use some form of tagged pointer optimisation.
> Glitchy output isn't good
Hmm...understating the problem here just a tad.
"In 2021, they ranked 12th in the updated Common Weakness Enumeration (CWE) list of the most common flaws, bugs, faults, and other errors in either hardware or software. The team behind the list ranked integer overflows just after “Missing Authentication for Critical Function”, due to the severity and prevalence of integer overflows."
https://www.comparitech.com/blog/information-security/intege...
> Some buggy code path is trying to allocate a 10 GB integer can be worse
Hmmm...overstating the problem here just a tad. Not even sure how you'd manage that, given that that would be an integer with 4 billion digits.
Yes, this, so much this
Who cares what an 'int' or a 'long' is. Except for things like the size of a pointer, it's better if you know exactly what you're working with.
The changes to the arithmetic rules mean you can't have sign-magnitude or 1s complement anymore IIRC
The only improvement that you really need over that is to differentiate between what c calls size_t and uintptr_t: the size of the largest possible array, and the size of a pointer. On "normal" architectures they're the same, but on architectures that do pointer tagging or segmented memory a pointer might be bigger than the biggest possible array.
But you still have to deal with legacy C code, and C was dreamt up when running code written for 16 bits on a 14 bit architecture without losing speed was a consideration, so the C type's are weird.
I've been using those since the 00s for bit banging code where I need guarantees for where each bit goes.
Nothing quite like working with a micro processor with 12bit words to make you appreciate 2^n addresses.
So you had almost three decades with everyone coming up with their own solution.
To be fair, the other languages were hardly any better than C in this regard.
Let's say you want to work with numbers and you want your program to run as fast as possible. If you specify the number of bits you want, like i32, then the compiler must make sure on 64bit CPUs, where the register holding this value has an extra 32bits available, that the extra bits are not garbage and cannot influence a subsequent operation (like signed right shift), so the compiler might be forced to insert an instruction to clear the upper 32bits, and you end up with 2 instructions for a single operation, meaning that your code now runs slower on that machine.
However, had you used 'int' in your code, the compiler would have chosen to represent those values with a 64bit data type on 64bit machines, and 32bit data type on 32bit machines, and your code would run optimally, regardless of the CPU. This of course means it's up to you to make sure that whatever values your program handles fit in 32bit data types, and sometimes that's difficult to guarantee.
If you decide to have your cake and eat it too by saying "fine, I'll just select i32 or i64 at compile time with a condition" and you add some alias, like "word" -> either i32 or i64, "half word" -> either i16 or i32, etc depending on the target CPU, then congrats, you've just reinvented 'int', 'short', 'long', et.al.
Personally, I'm finding it useful to use fixed integer sizes (e.g. int32_t) when writing and reading binary files, to be able to know how many bytes of data to read when loading the file, but once those values are read, I cast them to (int) so that the rest of the program can use the values optimally regardless of the CPU the program is running on.
There's a fun tool called "Git of Theseus" which can answer this question! You can see some graphs of Linux code on the web page: https://github.com/erikbern/git-of-theseus
Named after the Ship of Theseus: https://en.wikipedia.org/wiki/Ship_of_Theseus
A (Linux) kernel line has half-life 6.6 years. The highest of the projects analyzed. The lowest went to Angular with half-life 0.32 years.
import math
pi = 3141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590360
sign_bits = 1
sig_bits = math.ceil(math.log2(pi))
exp_bits = math.floor(math.log2(sig_bits))
assert sign_bits + sig_bits + exp_bits == 1209
[1] https://www.jpl.nasa.gov/edu/news/2016/3/16/how-many-decimal...
> For JPL's highest accuracy calculations, which are for interplanetary navigation, we use 3.141592653589793. Let's look at this a little more closely to understand why we don't use more decimal places. I think we can even see that there are no physically realistic calculations scientists ever perform for which it is necessary to include nearly as many decimal points as you present.
That's sixteen digits, so a quick trip to the dev tools tels me::
>> Math.log2(3141592653589793)
-> 51.480417552782754
I'm imagining the maths equivalent of Heisenbugs, is that correct?
E.g. https://redirect.cs.umbc.edu/~phatak/645/supl/Ng-ArgReductio...
Edit, if a 4GB (32-bits used) DRAMM pulls 1 watt, the rest of the memory space is 32 bit = 4E9 so your memory is pulling ~4Gwatts alone. That's not supportable, given the other electronics needed to go around it.
Fast-forward 18 years, and it's fascinating to me to see people now seriously floating the proposal to support 256-bit pointers.
Does anybody know why they don't use the existing fixed size integer types [1] from C99 ie uint64_t etc and define a 128 bit wide type on top of that (which will also be there in C23 IIRC)?
My own kernel dev experience is pretty rusty at this point (pun intended), but in the last decade of writing cross platform (desktop, mobile) userland C++ code I advocated exclusively for using fixed width types (std::uint32_t etc) as well as constants (UINT32_MAX etc).
1. The format specifiers for those types differ from the ones currently in use for the kernel. Nobody uses or wants to use PRId64 and PRIu64. If they did, they'd need to change thousands of occurrences (which is admittedly not too hard with tools like Coccinelle).
2. The stdint.h types are just typedefs (it's not like the compiler understands them intrinsically). And they're defined in terms of short, int, long, etc. The sizes of these are platform and compiler dependent. On the other hand, the Linux kernel tells the compiler "you must make long 64 bits if you are a 64 bit system" which may conflict with the defaults and throw those types out of whack. (at least, that's how I interpreted one of the points in the room, I could be wrong here)
3. Kernel is already using u32/s32, it's a smaller and easier change to go to u32/i32 in Rust style. People tend to find the stdint.h names to be verbose.
4. stdint.h brings in additional headers. I'm not sure if that's a problem or how - maybe in the Linux uapi headers?
There seemed to be general concensus in the room that stdint.h wasn't used for good reasons, so if these don't sound right, it's probably because I misinterpreted them.
Since then, it only roughly halved. What happened?
https://jcmit.net/memoryprice.htm
I know it's not process geometry, since we went from 45nm->5nm in the time, a roughly 81x decrease.
Is is realistic to assume scaling will resume?
or better yet, design a new abstraction for not having to hard-code the limit of the pointer size but instead allow it to be extensible as more addressable space becomes a reality, instead of having to transition over and over. is this even possible? if it is, shouldn't we head in that direction?
1. Any abstraction you could make will have worse performance than a fixed-size machine pointer
2. In order to support any kind of variably-sized type you need machine pointers to begin with, and those will always be fixed-size because variable size is even harder to support in hardware than native code
And furthermore going straight to 256 has its own problems. Each time you double the pointer size you also significantly increase the size of structures with a lot of pointers. V8 notably uses "pointer compression" - i.e. using 32-bit offsets instead of 64-bit pointers, because it never needs >4GB of JavaScript objects at once and JS objects are very pointer-ridden.
There's two forces at play here: pointers need to be small enough to embed in any data structure and large enough to address the entire working set of the program. Larger pointers are not inherently better[0], and neither are smaller pointers. It's a balancing act.
[0] ASLR, PAC, and CHERI are exceptions, as mentioned in the original article.
The size of large networked disk arrays will grow beyond 64 bit addresses, but I don't think we will exceed 2^128 bits of storage of any size, for any practical application. Then again, there's probably people who thought the same about 32 bit addresses when we moved from 16bit to 32bit addresses.
The most likely case for "giant" pointers (more than 128 bits) will be adding more metadata into the pointer. With time we might find enough use cases that are worth it to go to 256bit pointers, with 96bit address and 160 bit metadata or something like that.
There's a fun "quote" about 384k being all anyone would ever need, so clearly everyone just needs to settle down and figure out how to refactor their code.
Can we not play it save and immediately jump to for 65536-bit :)
We could call it 16-bit-bit.
These future OSes may be 128bit, but I don't think the current ones will make it to the transition.