Pedant:Doubling is geometric, not exponential. Right?
Both okay according to http://en.wikipedia.org/wiki/Exponential_growth
Please grow your buffers exponentially
101–110 of 166 posts
Re: Please grow your buffers exponentially
#102Earlier quoted context omitted.
In most cases the empty overhead won't be part of the working set, though.
But the system still has to commit for the amount of allocated memory, which may deny memory allocations to the rest of the system.
If you have arrays/buffers that take up a significant chunk of a 64 bit address space, you might make a 2nd pass to tune those. Otherwise, "just" make plenty of swap space for the idle memory chunks.
And yes, "swap space" is going to be a bit more constrained on a 32 bit mobile app. CPU cache is the real memory, and DRAM is the new swap :-)
Re: Please grow your buffers exponentially
#103This doesn't always work. When you have 512MiB of memory and your current allocation is 256MiB, where do you go? Also when your dataset allocates 64MiB up front, then chucks two bytes on the end, where do you go? Know thy data and test test test is the only rule.
Well, consider it in the context of a web browser or other generic desktop application.
If you have (say) 4G memory, and you have to process 2G, then you more or less accept that things are going to be slow. (Unless you are in some kind of embedded system, but then I assume you actually measure exactly how many bytes you need anyway...) And if it really bothers you, you would probably add more RAM to your machine and the problem will go away.
If you extend arrays by constant amount, you instead end up with a 4MB data that takes five minute to process. Your users won't like it a bit. What is worse, this problem can't be solved by adding more RAM.
Re: Please grow your buffers exponentially
#104That's bad general advice in my opinion, instead encourage that a programmer reserves the expected capacity beforehand, or at least tweaks grow attributes for the specific 'growth pattern'. At least in games (only area where I have experience), dynamic containers will often grow very quickly to and remain at a fairly predictable size for a long time (several seconds to minutes). Reserving capacity beforehand to the e…
Back when I was writing parser/tokenizer stuff for a dev tool shop called "Morada" back in the early 90s, it was a bit hard to predict how many lines (parsed items) the input files would be, unlike a game with a constrained "arena". So, this double-upon-realloc was exactly the approach I used in some library calls I made up for dynamic array / "index" / list functions I put together in C. So, I would say that the article is very GOOD advice for many, if not all, usages.
. . .
To me, it seemed an obvious implementation of the "List ADT" stuff that I learned in uni in the 80s (even if it was in Pascal back in the day), but my bosses were minicomputer guys from the 70s, so they wanted to be sure I didn't "steal" the code from somewhere. (and this is pretty much the approach taken in the Java runtime for Vector & ArrayList)
It was my first job coding C on a regular basis. I think my employers may have confused my initial unfamiliarity with where to put my "asterisks and ampersands" (C gobble-de-gook syntax) with some kind of general ignorance :-)
(to their credit, they knew I wasn't stupid - I had done a sub-contract job for them in another language)
Re: Please grow your buffers exponentially
#105From the comments, the linked SO question is probably better a treat of the title than the article: http://stackoverflow.com/questions/1100311/what-is-the-ideal... I would have guessed by now it is common knowledge that you should grow your buffers exponentially. The only question being by how much? For general usage it seems 1.5 is usually used but another factor could be better if you have different constraints for…
Agreed. I thought everyone knew by now to do this. I'm somewhat surprised Mozilla decided to write a blog post on it. I guess it's always news to someone.
Re: Please grow your buffers exponentially
#106This is great until you start vending an api to a higher level client that makes several arbitrary mutable copies of your buffer object. There are still 32 bit machines and it is not unlikely to have a contiguous 4 meg region of heap unavailable in a long lived app. (One option to help is to ensure that the naive object duplication code always compact the new copy. But malloc can (and will) fail.)
If you are handing out (long lived) references to your elements, then yes, you cannot relocate them. In that case, you need an array of pointers, rather than an array of inline values. In this case, your memory use will become even more fragmented, though.
Either way, make sure you have swap space, and you should be all right, especially if the swap is usually just holding idle slop. 2 GB (2^31 bytes) is still a pretty big address space for many purposes. It will hold about 500 4 MB buffers (512, less overhead).
Re: Please grow your buffers exponentially
#107This is great until you start vending an api to a higher level client that makes several arbitrary mutable copies of your buffer object. There are still 32 bit machines and it is not unlikely to have a contiguous 4 meg region of heap unavailable in a long lived app. (One option to help is to ensure that the naive object duplication code always compact the new copy. But malloc can (and will) fail.)
If you are handing out (long lived) references to your elements, then yes, you cannot relocate them. In that case, you need an array of pointers, rather than an array of inline values. In this case, your memory use will become even more fragmented, though. Either way, make sure you have swap space, and you should be all right, especially if the swap is usually just holding idle slop. 2 GB (2^31 bytes) is still a pret…
P.S. - I never had to deal with 8-bit machines, but spent plenty of time on 16-bit machines. 32 bits is a big address space, despite Microsoft having pissed all of it (and a CPU core) away just to load the OS, leaving little-to-nothing for actual work.
Re: Please grow your buffers exponentially
#108Earlier quoted context omitted.
> haha, cue firefox going back to using ridiculous amounts of memory in 5, 4, 3, 2, 1. I just had to force-kill Firefox (v. 33.0.2, on a OS X v. 10.8.1 with 4GB of memory) when it decided to not respond anymore after I had tried (silly me) to open a 14 MB XML page stored on disk. Looking in the Activity Monitor that XML file caused FF to load one of the CPUs at 100% and to use 1.5GB of memory (for opening a 14MB file…
I bet if you work out how many nodes and attributes are in that XML file, multiply that by (what's a good size for a C++ object? 256 bytes?) and I bet it's a substantial fraction of that 1.5GB.
Exactly. If you have to have a "DOM" of an XML, it's going to take A LOT of memory.
I recently replaced some generalized Java code (my own, alas) that built a DOM of some XML with substring operations to find the element text in the only element in the XML that mattered. (fortunately, I could guarantee that the text had no markup related special chars in it) This caused about 6 GC cycles (in a 32 bit JVM) to disappear from this process.
However, if you have to display or navigate the document tree, you are stuck with the memory hogging DOM.
Re: Please grow your buffers exponentially
#109Not using exponential growth in buffers / vectors / other contiguously allocated collections is a rookie mistake. It shouldn't be made by anyone who's ever studied algorithm complexity, never mind studied CS at any level. About the only exception is when you have global knowledge about how a buffer is going to be used. But that's rare in modern modular software.
[deleted]
Re: Please grow your buffers exponentially
#110I just addressed this the other day, when a pull request wanted to use exponential growth in the buffer. I told them not to. The difference is that this software is going to run on an embedded sytsem for which I wrote the kernel, and I wrote the realloc function for. My realloc expands the block instead of moving data when possible, and I know that that's a likely scenario during normal operation. On top of that, there's only 32K of memory to go around, so wasting space on exponential growth is a bad idea.
Always be willing to question the standard doctrine.