3 ms·

> 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 with

> 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?
    - deleted 4y ago
      [deleted]
    - Dylan16807 4y ago
      Surely you know the answer, if you're analyzing at this level of detail? It's because spending 1 millisecond per X operations doing vector moves is preferable to spending 20 milliseconds per X operations stalling on list links. If you set a good vector size from the start, the moves will be rare to nonexistent. Or you could reserve some address space and never have to move the data.
tsimionescu 4y ago
In the ideal case (and assuming a vector large enough that it spans many pages), you would actually be able to work with the OS's virtual memory manager to re-allocate and move only the page that contains the address you want to write to, while all other pages can stay untouched. But there is quite a bit of careful work to do to implement something like this and make sure you are not invalidating pointers or even internal malloc() data structures.

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?
  - deleted 4y ago
    [deleted]
  - Dylan16807 4y ago
    Surely you know the answer, if you're analyzing at this level of detail? It's because spending 1 millisecond per X operations doing vector moves is preferable to spending 20 milliseconds per X operations stalling on list links. If you set a good vector size from the start, the moves will be rare to nonexistent. Or you could reserve some address space and never have to move the data.

tsimionescu 4y ago

In the ideal case (and assuming a vector large enough that it spans many pages), you would actually be able to work with the OS's virtual memory manager to re-allocate and move only the page that contains the address you want to write to, while all other pages can stay untouched. But there is quite a bit of careful work to do to implement something like this and make sure you are not invalidating pointers or even internal malloc() data structures.