5 ms·

> almost always, whatever problem you're trying to solve would be better done with a regular resizable vector Resizing a vector brings the whole of it into cac

> almost always, whatever problem you're trying to solve would be better done with a regular resizable vector Resizing a vector brings the whole of it into cache, potentially dragging all of it all the way from actual RAM. Prepending an entry brings nothing into cache. Cache is king.

KerrAvon 4y ago
So use an array deque if you need O(1) prepending.
- chrisseaton 4y ago
  Resizing the array in the array dequeue brings the entire thing into cache. That's a disaster.
  - kragen 4y ago
    It's a disaster but it's an amortized O(1) disaster.
  - CyberDildonics 4y ago
    It's far from a disaster because the best way to deal with a list is still to use a contiguous array. Allocation isn't free. You have to do it sometime and doing it all in bulk is going to have the same consequences as just one small allocation anyway. If you are mapping new pages into main memory, making system calls or looping through a heap structure, you're not only affecting the data cache but also the TLB while also pointer chasing. Making a list out of an allocation for every element is performance suicide on modern computers. Even the amortized resizing of an array is done at the speed of memory bandwidth because of the prefetcher. Thinking that is some sort of performance hindrance is absurd because it outweighs the alternative by orders of magnitude. If there really are hard limits on the time every insertion can take, then the solution needs to be links of large chunks of memory to still minimize allocations on every element.
    - jameshart 4y ago
      Obviously the compromise is to use a linked list, but preallocate a contiguous block of memory to hold all your linked list nodes. Like an array of linked list nodes, each with a pointer to the array index of the next node. Then you just need to double the size of that block of memory and copy all the nodes to the new block whenever it fills up. Hmm, but you’d probably end up needing some kind of a list of free blocks of space within that array to deal with fragmentation… you’d need another linked list to store those blocks in. If only there was some sort of system that could take care of all that allocation and freeing of memory for you?
      - CyberDildonics 4y ago
        It looks like you are conflating a linked list with a heap. Once you have an array/vector for your node list the unused memory can be a list itself, each index pointing to the next free index. You just need the next free index to get memory and you point to the current free index when you free a node. You don't need to manage the memory further than that.
- kragen 4y ago
  That's amortized O(1), not WCET O(1). For transformational systems they're equivalent, for reactive systems they aren't.
jameshart 4y ago
> Resizing a vector brings the whole of it into cache I don’t do low level code on modern systems; is there not a way to just blit chunks of memory around without a CPU looping it’s way through word by word carrying out MOVQ instructions which do a full RAM read/write? If you’re streaming data out of memory to a PCIe bus or something, that wouldn’t go via cpu cache, right? There’s some kind of DMA model, so there’s something in the system architecture that allows memory access to be done off-CPU (I vaguely think of this as being what the northbridge was for in the old school x86 architecture but I’m fuzzy on the details?). Mechanical copying of byte arrays feels like something a CPU should be able to outsource (precisely because you don’t want to pollute your cache with that data)
- chrisseaton 4y ago
  Not in architectures I've seen or maybe I'm missing the instructions to do it? Even if there were and you can bypass the CPU, hauling data out of RAM is still going to take a long time.
  - NobodyNada 4y ago
    > maybe I'm missing the instructions to do it? Yes, they’re called “non-temporal” load and store instructions. AFAIK most memcpy implementations will automatically use non-temporal access when copying blocks larger than a certain threshold, precisely to avoid destroying the cache during bulk copies. Additionally, a well-optimized memcpy implementation (e.g. making good use of prefetch hints) should not suffer too much from RAM latency and be able to pretty much max out the bandwidth available to the CPU core.
    - chrisseaton 4y ago
      You're thinking of like MOVNTDQA? Those still have to reach into RAM - that's still double-digits nanoseconds away and still creates a stall in the processor at n complexity!! No thanks? I can allocate a new linked list node with memory guaranteed already entirely in cache (except for TLA failure.) > be able to pretty much max out the bandwidth available to the CPU core Why max out a slow link at n complexity when you can just avoid doing that entirely and use a linked list?
tsimionescu 4y ago
Sure, prepending or adding at the end(assuming you're keeping a tail pointer, which is easy and common) are basically the only cases where a linked list can beat an array.
- chrisseaton 4y ago
  Yeah, and we deliberately prepend because that doesn't involve writing to a field in a node which may not be in cache. It's the consumer's job to reverse the list if they ever actually need it.

KerrAvon 4y ago

So use an array deque if you need O(1) prepending.

chrisseaton 4y ago
Resizing the array in the array dequeue brings the entire thing into cache. That's a disaster.
- kragen 4y ago
  It's a disaster but it's an amortized O(1) disaster.
- CyberDildonics 4y ago
  It's far from a disaster because the best way to deal with a list is still to use a contiguous array. Allocation isn't free. You have to do it sometime and doing it all in bulk is going to have the same consequences as just one small allocation anyway. If you are mapping new pages into main memory, making system calls or looping through a heap structure, you're not only affecting the data cache but also the TLB while also pointer chasing. Making a list out of an allocation for every element is performance suicide on modern computers. Even the amortized resizing of an array is done at the speed of memory bandwidth because of the prefetcher. Thinking that is some sort of performance hindrance is absurd because it outweighs the alternative by orders of magnitude. If there really are hard limits on the time every insertion can take, then the solution needs to be links of large chunks of memory to still minimize allocations on every element.
  - jameshart 4y ago
    Obviously the compromise is to use a linked list, but preallocate a contiguous block of memory to hold all your linked list nodes. Like an array of linked list nodes, each with a pointer to the array index of the next node. Then you just need to double the size of that block of memory and copy all the nodes to the new block whenever it fills up. Hmm, but you’d probably end up needing some kind of a list of free blocks of space within that array to deal with fragmentation… you’d need another linked list to store those blocks in. If only there was some sort of system that could take care of all that allocation and freeing of memory for you?
    - CyberDildonics 4y ago
      It looks like you are conflating a linked list with a heap. Once you have an array/vector for your node list the unused memory can be a list itself, each index pointing to the next free index. You just need the next free index to get memory and you point to the current free index when you free a node. You don't need to manage the memory further than that.
kragen 4y ago
That's amortized O(1), not WCET O(1). For transformational systems they're equivalent, for reactive systems they aren't.

jameshart 4y ago

> Resizing a vector brings the whole of it into cache I don’t do low level code on modern systems; is there not a way to just blit chunks of memory around without a CPU looping it’s way through word by word carrying out MOVQ instructions which do a full RAM read/write? If you’re streaming data out of memory to a PCIe bus or something, that wouldn’t go via cpu cache, right? There’s some kind of DMA model, so there’s something in the system architecture that allows memory access to be done off-CPU (I vaguely think of this as being what the northbridge was for in the old school x86 architecture but I’m fuzzy on the details?). Mechanical copying of byte arrays feels like something a CPU should be able to outsource (precisely because you don’t want to pollute your cache with that data)

chrisseaton 4y ago
Not in architectures I've seen or maybe I'm missing the instructions to do it? Even if there were and you can bypass the CPU, hauling data out of RAM is still going to take a long time.
- NobodyNada 4y ago
  > maybe I'm missing the instructions to do it? Yes, they’re called “non-temporal” load and store instructions. AFAIK most memcpy implementations will automatically use non-temporal access when copying blocks larger than a certain threshold, precisely to avoid destroying the cache during bulk copies. Additionally, a well-optimized memcpy implementation (e.g. making good use of prefetch hints) should not suffer too much from RAM latency and be able to pretty much max out the bandwidth available to the CPU core.
  - chrisseaton 4y ago
    You're thinking of like MOVNTDQA? Those still have to reach into RAM - that's still double-digits nanoseconds away and still creates a stall in the processor at n complexity!! No thanks? I can allocate a new linked list node with memory guaranteed already entirely in cache (except for TLA failure.) > be able to pretty much max out the bandwidth available to the CPU core Why max out a slow link at n complexity when you can just avoid doing that entirely and use a linked list?

tsimionescu 4y ago

Sure, prepending or adding at the end(assuming you're keeping a tail pointer, which is easy and common) are basically the only cases where a linked list can beat an array.

chrisseaton 4y ago
Yeah, and we deliberately prepend because that doesn't involve writing to a field in a node which may not be in cache. It's the consumer's job to reverse the list if they ever actually need it.