4 ms·
> Today’s computers use only 48 bits of the 64 bits in a pointer https://en.wikipedia.org/wiki/Intel_5-level_paging https://en.wikipedia.org/wiki/Intel_5-level
by zokier 1y ago
> Today’s computers use only 48 bits of the 64 bits in a pointer
https://en.wikipedia.org/wiki/Intel_5-level_paging https://en.wikipedia.org/wiki/Intel_5-level_paging introduced in Ice Lake 6 years ago.
But anyways, isn't this just variant of std::deque? https://en.cppreference.com/w/cpp/container/deque.html https://en.cppreference.com/w/cpp/container/deque.html
- cornstalks 1y agoWhat kind of setups use over 256 TiB of RAM?
- reorder9695 1y ago"640k ought to be enough for anybody"
- bonzini 1y agoIn practice it's over 64 TiB because kernels often use a quarter of the available addressing space (half of the kernel addressing space) to map the physical addresses (e.g. FFFFC000_12345678 maps physical address 0x12345678). So 48 virtual address bits can be used with up to 2^46 bytes of RAM.
- hinkley 1y agoAnd how long has 48 bit addressing been de rigeur? Not so long ago we had processors that could address 40 bits of address space. Or was that 38?
- deleted 1y ago[deleted]
- winocm 1y agoAt least since maybe the DEC Alpha 21264. It could address 48-bits of VA space, but that comes with caveats due to PALcode specific intricacies. I think VMS (or was it Tru64?) uses this mode, but many other OSes just use 43-bit or 40-bit addressing. Realistically though, I don’t think many users would be using workloads that addressed more than 38-bits worth of contiguous VA space in 1998-1999.
- loeg 1y agoamd64 has had 48-bit addressing / 4-level paging from the beginning.
- hinkley 1y agoI must be thinking of intel’s failed 64 bit attempts prior to amd64 winning.
- wittystick 1y agoPhysical addresses may be limited to 40 bits, but 48-bit virtual addresses have been the norm since 4-level paging.
- bonzini 1y agoYou're probably thinking of PAE (36 bit physical address space on 32 bit virtual address space). But Intel for quite some time had a 36 bit physical address space limit on 64-bit consumer processors, even if the virtual address space was 48 bits. I think it only changed 5 years ago or less.
- TapamN 1y agoIt not necessarily physical RAM. If you memmap large files, like maybe a large file from RAID or network share, you could still need that much virtual address space.
- Dylan16807 1y agoDo many programs want to use that much data but not control when it swaps in and out?
- wittystick 1y agoNo, but 5-level paging is opt-in anyway, so its presence isn't problematic if assuming a 48-bit address space. Linux won't allocate space outside the 48-bits unless you give an address hint to mmap outside the 48-bit range.
- deleted 1y ago[deleted]
- sestep 1y agoDoes std::deque support random access?
- mwkaufma 1y agoYes, you can see operator[] in the linked reference docs.
- ksherlock 1y agoThe cppreference documentation specifies "Random access - constant O(1)" (same as std::vector). There's a slight overhead from going through 2 pointers instead of 1 and keeping track of how many items are in the first bucket (so you know which bucket to check), but that's a constant and the big O don't care about constants.
- mwkaufma 1y agoIn principle it's not that different that deque, though: (1) deque uses fixed-sized blocks, not increasing-size blocks. (2) dequeue supports prepending, which adds another level of indirection internally.
- sigbottle 1y agoYou can support prepending by mirroring the allocations, probably? eg for the "negative index" case do an exponential thing in the other direction. Your indexing has some legitimate math to be done now which can be annoying (efficiency perspective) I think you can still get o(1) with careful allocation of powers of 2.
- o11c 1y agoThat's fine if you only ever add, but is likely to fail if you pop FIFO-style. This too is ultimately fixable but means we can no longer assume "every bucket size doubles". That said, IMO "stable pointers" is overrated; "minimize copying" is all that's useful.
- dwattttt 1y agoStable pointers is a limitation for simplicity's sake. If C were better at tracking pointer invalidation, we'd be better at propagating updated pointers.
- sigbottle 1y agoI don't know the precise details of how deques are implemented in C++, but given the most popular stack overflow explanation of them, some immidiate pitfalls are that the T* map itself sounds unbounded and if each chunk allocates only a fixed constant size it's probably horrible for fragmentation or overallocation. The indexing also seems dependent on division. With this power of twos approach you can't really truly delete from the front of the array but the amount of pointers you store is constant and the memory fragmentation is better. (Though OP never claimed to want to support deque behavior, it shouldn't be that hard to modify, though indexing seems like it has to go thru more arithmetic again) I haven't used OP's array, but I have been bit plenty of times with std::deque's memory allocation patterns and had to rewrite with raw arrays and pointer tracking.
- fc417fc802 1y ago> The indexing also seems dependent on division. As long as the number of slots in a bucket is a power of two division reduces to right shift (I have no idea what std::deque does though). One of the advantages of not growing exponentially is that you can use a deque the way you would a ring buffer without it attempting to eat the entire address space.
- forrestthewoods 1y agostd::deque details vary by implementation and is largely considered unusable for MSVC. MSVC uses a too small block size making it worthless. libc++ block size is 16 elements or 4096 bytes. It is generally better to use a container you can actually understand the implementation details and control. I would not call it a variant of std::deque myself. Not wrong. But not a helpful observation imho.
- penguin_booze 1y agoWhat's all that icons on the diagram that illustrates 5-level paging - snowflakes and triangles?
- Retr0id 1y agoHuh, seems like a bug in the SVG renderer. The SVG itself looks normal: https://upload.wikimedia.org/wikipedia/commons/2/2b/Page_Tables_%285_levels%29.svg https://upload.wikimedia.org/wikipedia/commons/2/2b/Page_Tab...
- penguin_booze 1y agoThanks for that. I was worried I don't understand paging anymore. FWIW, I was using Firefox.
- Retr0id 1y agoThe images you see on wikipedia are rendered to a bitmap, so it's an issue on their end somewhere (and you'll see the same regardless of browser)
- nly 1y agoUnfortunately std::deque is hobbled in the Microsoft implementation. Its block size is such that if T is larger than 8 bytes it devolves to a linked list. And it can't be fixed due to binary compatibility. https://github.com/microsoft/STL/issues/147 https://github.com/microsoft/STL/issues/147 By contrast the GNU implementation has a block size of 512 bytes Fortunately in high performance systems the times where you actually want an unbounded queue are limited.