tag:blogger.com,1999:blog-5246987755651065286.post1466956722833147550..comments2022-07-09T06:36:43.613-07:00Comments on cbloom rants: 01-22-10 - Exponentialcbloomhttp://www.blogger.com/profile/10714564834899413045noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-5246987755651065286.post-41555177761831353822010-01-25T07:16:07.158-08:002010-01-25T07:16:07.158-08:00Pretty much all decent devs can initially write N ...<i>Pretty much all decent devs can initially write N features in NlogN time</i><br /><br />To clarify, I absolutely didn't mean NlogN time, just NlogN in size (or some complexity metric). And I agree that maintainence and support time should be measured when considering time (or equivalently cost).<br /><br />Also, O(NlogN) size isn't from just the current project, that's my intuition drawn from <i>a lot</i> of projects. I only brought up my current project to point out that I doubt anybody does O(N^2) testing.<br /><br />(stupid openID server be borked)Sean Barretthttps://www.blogger.com/profile/14465498859800664552noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-36963957331269403512010-01-24T06:16:58.874-08:002010-01-24T06:16:58.874-08:00Besides lines of code to implement N features I th...Besides lines of code to implement N features I think there is another superlinear cost -- designing a reasonable UI. That can be pretty vicious. Dunno if it's actually exponential.Thatcher Ulrichhttps://www.blogger.com/profile/01374419756386535175noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-21331125805034897572010-01-23T12:44:38.028-08:002010-01-23T12:44:38.028-08:00Yeah I should definitely be saying "polynomia...Yeah I should definitely be saying "polynomial" instead of "geometric".<br /><br />I think if you could measure your dev complexity vs. your feature count that would be a good measure of how good you are as a coder. That is, if your abstractions are perfect, you can do N features in NlogN dev cost, if your abstractions suck it takes N^2 dev cost.<br /><br />Also, Sean, I don't think your data point is valid yet. Pretty much all decent devs can initially write N features in NlogN time, but most people underestimate the long term cost of features in bugs and support over the life of a product. Does that become N^2 over the long run? Hard to say. (for example, how does the # of stupid questions from clients scale? is that N^2 ?)cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-9074905903895265632010-01-23T10:42:48.075-08:002010-01-23T10:42:48.075-08:00Yeah, I agree with ryg, there's an unfortunate...Yeah, I agree with ryg, there's an unfortunate redunancy between 'geometric' and 'exponential'. To refine his comment, I'm not sure how "geometric growth" is officially defined, but there is absolutely a thing in math called "a geometric sequence", the elements of which can be defined with an exponential function.<br /><br />But none of this changes the fact that almost nothing is exponential growth. (Or, thus, even geometric growth.)<br /><br />Anyway, there is absolutely no way I have tested anything resembling N^2 features of my current project. The size of my tests are probably closer to O(N).<br /><br />I'd argue that the use of abstractions and black boxes are designed to bring complexity to be something like O(N log N); i.e. you're making a hierarchical tree of abstractions.<br /><br />You get some cross terms, the tree isn't binary and may cross levels, but I think that's true to a first approximation.<br /><br />Whether that means you really need O(N log N) tests or O(N^2) or O(2^N) tests I dunno.<br /><br />Another way to do this is to look at the math. If you can have M bits of input, then you have at most 2^M possible test cases. To be 100% sure of tests, you have to test all 2^M test cases, and this is true regardless of how big N is. How far short of that are you willing to stop?<br /><br />Anyway, my guess is that software complexity for N features is something like O(N log N), and # of bugs is something like O(LOC * something-that-grows-slower-than-log-N), but the problem is how much testing you need to find those bugs.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-61866965856434137352010-01-23T05:52:52.970-08:002010-01-23T05:52:52.970-08:00Nitpick first: Geometric growth is exponential, no...Nitpick first: Geometric growth <b>is</b> exponential, not quadratic (The definition of a geometric progression is that x_(n+1) / x_n = const for all n). I don't think there's a commonly used synonym for quadratic growth.<br /><br />On the actual subject: Games have the big advantage that most of their essential (behavior-determining) interactions take place between components that are part of the codebase. The same isn't true for most web apps, for example, and I suspect that goes for most business apps too, though I have no experience on the matter. Web apps are completely dependent on several black boxes (web server, DB engine, network and IO subsystems of the kernel, ...), usually with several caching layers inbetween that accumulate hidden state all over the place (some of them completely out of your control, like in the browser), and all of these pieces interact behind your back in nonobvious ways.<br /><br />This kind of construction is most definitely a bug magnet, and basically everyone has given up on fixing all but the most obvious bugs. Basically all big websites I know will occasionally barf, displaying an error message in the vein of "so this didn't work, but just hit Refresh to make me try the same thing again and I guess everything will be okay". If this kind of shit would happen in one of my "real" programs, I'd be terrified.<br /><br />(PS: Blogger just told me that "Your request could not be processed. Please try again." while trying to post...)ryghttps://www.blogger.com/profile/03031635656201499907noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-24537773038145446232010-01-22T19:36:39.227-08:002010-01-22T19:36:39.227-08:00One semi-related way to think about exponential co...One semi-related way to think about exponential complexity in programs is test coverage. Getting 100% test coverage is pretty clearly O(size of program), but what does that buy you? It doesn't cover each scenario for which your code is used. <br /><br />Something truly exhaustive would be path-complete testing. The number of paths in your program is big-O exponential, but that isn't a very tight bound. In reality, not all of your paths are independent. Perhaps one path excludes another, or 2 paths commute because they affect independent state.<br /><br />I think the essence of good software design is making your different paths as orthogonal (there's another word that can become a pet peeve...) as possible, to keep the non-linear term as small as possible. This, of course, matches my intuition, or maybe is just a roundabout way of justifying it.won3dhttps://www.blogger.com/profile/09787472194187459747noreply@blogger.com