| ▲ | zokier 4 days ago |
| > Today’s computers use only 48 bits of the 64 bits in a pointer 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 |
|
| ▲ | nly 3 days ago | parent | next [-] |
| Unfortunately 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 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. |
|
| ▲ | forrestthewoods 4 days ago | parent | prev | next [-] |
| std::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. |
|
| ▲ | mwkaufma 4 days ago | parent | prev | next [-] |
| In 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 4 days ago | parent [-] | | You 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 4 days ago | parent [-] | | That'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 4 days ago | parent [-] | | Stable 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 4 days ago | parent | prev | next [-] |
| I 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 3 days ago | parent [-] | | > 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. |
|
|
| ▲ | cornstalks 4 days ago | parent | prev | next [-] |
| What kind of setups use over 256 TiB of RAM? |
| |
| ▲ | TapamN 4 days ago | parent | next [-] | | It 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 2 days ago | parent [-] | | Do many programs want to use that much data but not control when it swaps in and out? | | |
| ▲ | wittystick 2 days ago | parent [-] | | No, 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. |
|
| |
| ▲ | bonzini 4 days ago | parent | prev | next [-] | | In 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 4 days ago | parent [-] | | And 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? | | |
| ▲ | winocm 4 days ago | parent | next [-] | | At 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. | |
| ▲ | 4 days ago | parent | prev | next [-] | | [deleted] | |
| ▲ | loeg 4 days ago | parent | prev [-] | | amd64 has had 48-bit addressing / 4-level paging from the beginning. | | |
| ▲ | hinkley 3 days ago | parent [-] | | I must be thinking of intel’s failed 64 bit attempts prior to amd64 winning. | | |
| ▲ | wittystick 2 days ago | parent [-] | | Physical addresses may be limited to 40 bits, but 48-bit virtual addresses have been the norm since 4-level paging. |
|
|
|
| |
| ▲ | reorder9695 4 days ago | parent | prev [-] | | "640k ought to be enough for anybody" |
|
|
| ▲ | 4 days ago | parent | prev | next [-] |
| [deleted] |
|
| ▲ | penguin_booze 3 days ago | parent | prev | next [-] |
| What's all that icons on the diagram that illustrates 5-level paging - snowflakes and triangles? |
| |
|
| ▲ | sestep 4 days ago | parent | prev [-] |
| Does std::deque support random access? |
| |
| ▲ | ksherlock 4 days ago | parent | next [-] | | The 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 4 days ago | parent | prev [-] | | Yes, you can see operator[] in the linked reference docs. |
|
