4 ms·
Not using exponential growth in buffers / vectors / other contiguously allocated collections is a rookie mistake. It shouldn't be made by anyone who's ever stud
by barrkel 12y ago
Not 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.
- zaroth 12y agoNot even thinking about the buffers being used to actually store your data is more like it.
- abcd_f 12y agoWhat a remarkably misguided rant. To each his own. What works for a general-purpose app on a desktop hardware doesn't work for a resource-constrained firmware (that still has to deal with potentially unbounded inputs). Yes, there's exponential reallocation, but there's also a multitude of other strategies, each best fit for its particular application domain. "Rookie mistake".
- barrkel 12y agoI've been burned far more often by O(n^2) algorithms being used inappropriately than by slightly too high memory usage. It usually comes up when you give a piece of software an order of magnitude more data than it's used to, and discover it becomes unusable. Resource constrained firmware is a special case, because the package is tested as a unit, rather than individual software modules which may themselves be used in very different use cases. The default algorithm should still usually be exponential growth, with tuning back where necessary to meet memory usage goals.
- deleted 12y ago[deleted]
- pja 12y agoYou're making a pedantic special case correction to a generally correct truth. This is not an endearing trait. Everybody knows that a statement such as the one the parent post made will have special case exceptions: The point is that exponential growth should be the default & any other choice requires justification. Asserting this is not a "misguided rant".
- nnethercote 12y ago> Everybody knows that a statement such as the one the parent post made will have special case exceptions Thank you for reading with a spirit of intellectual generosity. When I write posts like this I always wonder about how many qualifications and weasel words I should add just in case it makes Hacker News and the nitpickers come out in force. In this case I wrote things like "A strategy that is usually better is exponential growth" but still many of the comments are polite variations on "exponential isn't best in all circumstances, you idiot".
- Someone 12y agoInstead of weasel words, [RFC 2119] should be sufficient (https://www.ietf.org/rfc/rfc2119.txt https://www.ietf.org/rfc/rfc2119.txt) (Google also gave me http://tools.ietf.org/html/rfc6919 http://tools.ietf.org/html/rfc6919, which I did not know about yet. The third month of the year often sees remarkable productivity, culminating in superb output in the beginning of the fourth month)
- vidarh 12y agoIf you know you have special case constraints, you presumably will know enough to deal with them properly. In my experience the far more frequent mistake is developers on "normal" systems that seems to think that system calls in general are "free" and are far too cavalier about doing things like small reads, or allocating small buffers. As a more general advice, rather than growing buffers exponentially: Developers should in general treat kernel space as a remote system in terms of performance, and remember that every system call is slow. You can typically afford to do quite a lot of extra bookkeeping in user space to cut the number of system calls and still come out on top (e.g. user space buffering of reads). And learn to love strace/dtrace/systemtap/whaever mechanism to trace and profile system calls. Paying attention to this can have a dramatic impact on performance for very little effort.
- deleted 12y ago[deleted]
- jaggederest 12y agoI've personally tuned a lot of software that ran better with a constant growth factor than an exponential one. The problem with exponential growth is that, if you're doing a thing that is (kn)+1 bytes, where n is the growth factor and n is a decently large number, you end up with k(kn) bytes, which leaves k^2 * n - kn - 1 bytes useless. Depending on the value of k that can be a big chunk. Particularly in situations where you're memory constrained and creating long-running processes, adding some-large-percentage of your buffer in empty overhead just wastes resources. It's better to spend the extra allocations in the first minute, and then have it run for a day, than have the first minute be faster and have it take 36 hours because it can't fit the working set into memory.
- caf 12y agoIn most cases the empty overhead won't be part of the working set, though.
- RDeckard 12y agoBut the system still has to commit for the amount of allocated memory, which may deny memory allocations to the rest of the system.
- Roboprog 12y agoIf 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 :-)
- sysk 12y agoI studied algorithmic complexity and software enfineering. I don't think there was ever a mention of buffers or how to allocate them. I do remember there was a brief mention of dynamically allocated arrays and that the usual way to do those was to double up their space when needed. Anyways, there are tons of programmers working in high level languages and I wouldn't call them rookies for not being C programmers.
- hvidgaard 12y agoIf you studied algorithmic complexity, you also know that doubling (or larger) the size of a fixed array when you need more space, is about the only way to ensure amotized constant inserts using continuous finite arrays (ignoring the cost of allocating the memory). From there you ought to deduce that allocating any fixed amount is going to blow up, in terms of big-O.
- chronial 12y agoYou should have learned that the exponential growth is the precise reason why appending to dynamic growth arrays is O(1) – a very surprising and unintuitive result in my opinion. Not knowing about exponential growth, I would have sworn that that must be impossible. If this didn’t leave a strong impression on you, I would say that whoever taught you algorithmic complexity simply failed in this point.
- marcosdumay 12y agoYes, sure. You should know that in the real world basing everything on asymptotic behavior does not work very well. That's why we profile things, because reality is way more complex than CS classes.
- barrkel 12y agoAssuming with asymptotic behaviour, provided the constant factor is acceptable, ought to be your default. This is because software tends to need to work with greater volumes of data over time, on machines with more memory, and more and faster CPUs. If your algorithms grow with greater than linear complexity as a function of input, your software will tend to get worse over time.
- ajkjk 12y agoMan, you really want people to know how dumb they are if they don't know this already.
- deleted 12y ago[deleted]