Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!gegeweb.org!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail From: Uncle Steve Newsgroups: comp.lang.c,comp.programming Subject: Re: Malloc Query Date: Fri, 20 May 2011 12:14:21 -0400 Organization: Friends of the Galactic Collective Lines: 119 Message-ID: <3becd0b0bf54528-55a98@gmail.com> References: <87aael3xw1.fsf@blp.benpfaff.org> <0.9e954b297cf63735a997.20110518193428BST.87zkmjuabv.fsf@bsb.me.uk> <0.3ac369f64d11bcd06d18.20110519002615BST.87ei3vtwtk.fsf@bsb.me.uk> <98a074c87051012-452fb@gmail.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 8bit Injection-Info: mx03.eternal-september.org; posting-host="7vRVhz7e0oLxOOqEmyLMzA"; logging-data="29901"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19JX6rcxJtNKw9kWEkyh5Xa" User-Agent: nn 6.7.3 Content-Length: 5831 Cancel-Lock: sha1:21fw5VEVpecOrhCNvrlbUQfhSBI= Xref: x330-a1.tempe.blueboxinc.net comp.lang.c:4434 comp.programming:342 On Thu, May 19, 2011 at 10:55:35PM -0400, James Kuyper wrote: > On 05/19/2011 02:11 PM, Uncle Steve wrote: > > On Wed, May 18, 2011 at 09:38:05PM -0400, James Kuyper wrote: > >> On 05/18/2011 09:25 PM, Uncle Steve wrote: > ... > >> If you don't have sufficient spare time to test whether or not your > >> custom allocator actually significantly improves the speed of your > >> programs, you don't have enough spare time to justify wasting it > >> producing untested custom allocators. > > > > That's a little bit presumptuous. Are you suddenly in charge of my > > development schedule? I must have missed the memo. > > You're right - I should have expressed that differently: if you have > enough spare time to write your allocator, you're going to receive a > serious lack of sympathy when you complain about not having enough time > to bother testing it. You are, of course, free to ignore the ridicule > you deserve for prioritizing your time that way. The main reason I didn't time the thing previously is that the allocator will usually be a small fraction of the total 'k' for any given application. A binary tree using the allocator is going to spend more time doing comparisons on an insert than the cost of allocating the node. I've known this for a while. Measuring the performance of a binary tree algorithm is another kettle of fish altogether, and if I were making similar claims about one, I think there'd be better grounds for criticism in that case. Personally, I think that a demand for test data in a trivial case such as this is a little harsh. If a programmer is making claims about algorithm performance in a real-world application, that is another thing altogether, an in that case you would be perfectly justified in demanding test results. But on Usenet, and about something that is available to inspection by competent individuals... Not so much. > > development in a very limited amount of free time. You seem to be > > saying that as I am talking about the algorithm in a public newsgroup, > > that I should have also proved it in the lab and in the field, not to > > mention publishing all the testing data and methodologies. > > What I said has nothing to do with the fact that this is a public > newsgroup. Even if you're just doing it for yourself, it's a serious > waste of your time (which you are, of course, completely free to decide > to waste) to go to the trouble of building a custom allocator without > bothering to test whether you gained any benefit from doing so. I have no qualms about testing and verification, I just did not think it was quite so important in this particular instance. > > Are we 'reviewing' code in this newsgroup? I thought we were > > discussing it. > > I don't see a distinction. I don't see how you could discuss code in any > meaningful sense without first reviewing it - otherwise, how would you > know what it was that you were discussing? Perhaps you thought I was > using the word "review" strictly in some more formal sense? I thought you may have been implying association with a 'peer review' process, which is necessarily much more formal. The discussion of a topic would generally imply familiarity with its material, necessitating /a/ review of it, but that says nothing about the degree of analytical engagement. In a public newsgroup, I would anticipate a more casual approach to the discussion of an algorithm or fragments of same. I have posted a very shaky test-harness (written in less than one hour) that is exclusively intended to show the gross performance improvement over the 'standard' malloc(), whatever that may be on your platform. That is all, and I 'proved' the validity of my hypothesis, so far as that goes. If we were discussing real computer science, post latency would be on the order of days or weeks, not the minutes or hours turnaround generally expected in a Usenet thread. > >>> Oh, absolutely. Using integers as a sort of offset from a base is > >>> the kind of thing more common to assembly language programmers, but > >>> even in C it's a common idiom to use an array index, > >> > >> It's not as common as you seem to think. > > > > I don't really know how common it is, so you're already ahead of me on > > that score. > > C is notorious for the ubiquity of pointers in contexts where other > languages would use integer indices. Which is why I get the impression that some of you are a little puzzled by my use of integer-multiplied offsets from the array base? I would have thought that a more common idiom merely for the fact that it is such a useful arrangement in circumstances where the data is of a uniform size. C makes this easy. In another language, I might have had to maintain the free list with a bitmap, or some other contrivance. For most people this will be a non-issue because they will use the language-supplied libraries for everything, and they'll never have to worry about the implementation details of their binary tree structures, or whatever. C is different in that respect, and so naturally I've thought about methods for reducing algorithm complexity and memory requirements. If I use this algorithm consistently in my new programs I lose no coding time in doing so, as opposed to trying to jam it in to an already existing application that uses malloc. Even if it only improves a real-world algorithm by five percent, I have probably lost nothing by using it, and the educational value derived from writing and using it is 100% free. I've added comp.programming to the Newsgroups: line. I think this discussion is not so much about C, the language as it is about C programming technique or algorithm design. Regards, Uncle Steve -- Should a professional politician be charged with molestation if he kisses babies while attending political rallies?