3 ms·

Asymptotically, there's no difference between allocating a n+1 buffer and a n+k buffer before copying your old data in. You'll still get O(n^2) In reality, it

Asymptotically, there's no difference between allocating a n+1 buffer and a n+k buffer before copying your old data in. You'll still get O(n^2) In reality, it depends on the data you're handling. You may never end up handling sizes where the O(n^2) asymptote is significant and end up wasting memory in a potentially memory constrained situation. At the end of the day, it all depends on the actual application instead of blind adherence to textbook answers. Program both, benchmark, and use what the data tells you about your system. If I've got a 500 MB buffer that I append some data to once every 5 minutes, I might want to reconsider before I spike my memory usage to fit a 1 GB buffer just to close the program 15 minutes later.

deathanatos 6y ago
The O(n²) here is the time spent copying of the data; it's not about the size of the buffer, or that you'll temporarily use 2× the space. The program would die by becoming unusably slow. Take your 500 MiB example. Let's say we start with a 4KiB buffer (well in excess of of what most vector types would start you with). If we grow it by a constant 4KiB each time it runs out of space, by the time the buffer is 500MiB we've copied ~30 GiB of data. If instead we grow the buffer by doubling it, we will have had to copy ~1000 MiB (1 GiB) by the time it hits 500 MiB, difference of 30×. (Which is why the program would slow to a crawl.) I'm ignoring the time aspect of your supposition; at that rate, you'd never really get to 500MiB using the starting sizes & strides suggested upthread. That's a highly exceptional case; for nearly everything, the general recommendation from CS is going to be the right one. Yes, profile & optimize where and when needed, but the thread is clearly about defaults, and this is one of those defaults that holds pretty tightly. Further, at that size, if you don't use the memory, most OSes will simply never allocate the page. (They'll assign a dummy zero-filled page that will get swapped with a real page of memory one once the first write happens. So even at a large size, you'll end up using 1000 MiB of virtual memory, but not real RAM.) O(n²) is playing with fire: it grows fast, fast enough relative to the data that it is a common source of bugs. Edit: Gah, I'm off by a factor of 1,000, I think, so it's "only" 30×. (The point stands, though; the next doubling is 2GiB vs. 128GiB, and the gap widens fast.)
- magicsmoke 6y ago
  Yes I'm aware of how the algorithm works. I also know that if I allocated 500 MiB at the beginning of the program expecting my memory usage to be roughly that size, and my prediction was off by 50 MiB maybe I don't want to go hunting for another 500 MiB of space before my program ends or I stop using the buffer and free it. But your point about the virtual memory makes that moot anyways. Thank god for modern OSes. I've clearly been spending too much time around microcontrollers.

deathanatos 6y ago

The O(n²) here is the time spent copying of the data; it's not about the size of the buffer, or that you'll temporarily use 2× the space. The program would die by becoming unusably slow. Take your 500 MiB example. Let's say we start with a 4KiB buffer (well in excess of of what most vector types would start you with). If we grow it by a constant 4KiB each time it runs out of space, by the time the buffer is 500MiB we've copied ~30 GiB of data. If instead we grow the buffer by doubling it, we will have had to copy ~1000 MiB (1 GiB) by the time it hits 500 MiB, difference of 30×. (Which is why the program would slow to a crawl.) I'm ignoring the time aspect of your supposition; at that rate, you'd never really get to 500MiB using the starting sizes & strides suggested upthread. That's a highly exceptional case; for nearly everything, the general recommendation from CS is going to be the right one. Yes, profile & optimize where and when needed, but the thread is clearly about defaults, and this is one of those defaults that holds pretty tightly. Further, at that size, if you don't use the memory, most OSes will simply never allocate the page. (They'll assign a dummy zero-filled page that will get swapped with a real page of memory one once the first write happens. So even at a large size, you'll end up using 1000 MiB of virtual memory, but not real RAM.) O(n²) is playing with fire: it grows fast, fast enough relative to the data that it is a common source of bugs. Edit: Gah, I'm off by a factor of 1,000, I think, so it's "only" 30×. (The point stands, though; the next doubling is 2GiB vs. 128GiB, and the gap widens fast.)

magicsmoke 6y ago
Yes I'm aware of how the algorithm works. I also know that if I allocated 500 MiB at the beginning of the program expecting my memory usage to be roughly that size, and my prediction was off by 50 MiB maybe I don't want to go hunting for another 500 MiB of space before my program ends or I stop using the buffer and free it. But your point about the virtual memory makes that moot anyways. Thank god for modern OSes. I've clearly been spending too much time around microcontrollers.