Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #4434

Re: Malloc Query

Cross-posted to 2 groups.

Show all headers | View raw

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?

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Malloc Query Pushpa <pushpa@nospam.invalid> - 2011-05-17 19:39 +0000
  Re: Malloc Query blp@cs.stanford.edu (Ben Pfaff) - 2011-05-17 12:55 -0700
    Re: Malloc Query "BartC" <bc@freeuk.com> - 2011-05-18 12:05 +0100
      Re: Malloc Query Pushpa <pushpa@nospam.invalid> - 2011-05-18 17:11 +0000
        Re: Malloc Query "BartC" <bc@freeuk.com> - 2011-05-18 22:42 +0100
        Re: Malloc Query Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-05-18 21:10 -0400
      Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-18 19:34 +0100
        Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-18 17:10 -0400
          Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-19 00:26 +0100
            Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-18 21:25 -0400
              Re: Malloc Query James Kuyper <jameskuyper@verizon.net> - 2011-05-18 21:38 -0400
                Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-19 14:11 -0400
                Re: Malloc Query James Kuyper <jameskuyper@verizon.net> - 2011-05-19 22:55 -0400
                Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-20 12:14 -0400
              Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-19 03:22 +0100
                Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-19 14:20 -0400
                Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-19 23:51 +0100
                Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-19 20:01 -0400
                Re: Malloc Query luser- -droog <mijoryx@yahoo.com> - 2011-05-22 02:49 -0700
                Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-22 10:46 -0400
                Re: Malloc Query Shao Miller <sha0.miller@gmail.com> - 2011-05-22 12:37 -0500
                Re: Malloc Query Shao Miller <sha0.miller@gmail.com> - 2011-05-22 13:02 -0500
                Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-22 14:12 -0400
                Re: Malloc Query Shao Miller <sha0.miller@gmail.com> - 2011-05-23 03:06 -0500
                Re: Malloc Query luser- -droog <mijoryx@yahoo.com> - 2011-05-23 00:42 -0700
                Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-23 11:10 -0400
                Re: Malloc Query Keith Thompson <kst-u@mib.org> - 2011-05-23 09:06 -0700
                Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-22 23:18 +0100
                Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-22 19:18 -0400
                Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-23 11:22 +1200
                Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-23 01:57 -0400
                Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-23 19:24 +1200
                Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-23 14:20 -0400
                Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-24 07:41 +1200
                Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-23 16:24 -0400
                Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-24 09:20 +1200
                Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-23 18:05 -0400
                Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-24 10:37 +1200
                Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-23 19:34 -0400
                Re: Malloc Query "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> - 2011-05-23 17:48 -0700
                Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-24 12:56 +1200
                Re: Malloc Query James Kuyper <jameskuyper@verizon.net> - 2011-05-24 07:19 -0400
                Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-24 11:32 -0400
                Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-23 01:04 +0100
                Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-23 02:36 -0400
                Re: Malloc Query luser- -droog <mijoryx@yahoo.com> - 2011-05-23 00:39 -0700
                Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-23 14:44 +0100
                Re: Malloc Query Seebs <usenet-nospam@seebs.net> - 2011-05-23 15:16 +0000
                Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-23 11:41 -0400
                Re: Malloc Query David Thompson <dave.thompson2@verizon.net> - 2011-06-01 16:33 -0400
                Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-19 18:34 -0400
                Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-20 02:36 +0100
                Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-20 12:26 -0400
                Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-20 23:32 +0100
                Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-20 21:17 -0400
                Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-21 14:30 +1200
                Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-21 11:13 -0400
                Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-22 08:50 +1200
                Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-21 20:03 -0400
                Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-22 13:23 +1200
                Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-22 10:01 -0400
                Re: Malloc Query "io_x" <a@b.c.invalid> - 2011-05-26 08:12 +0200
                Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-26 19:16 +1200
                Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-26 15:03 -0400
                Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-27 09:16 +1200
                Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-26 17:55 -0400
                Re: Malloc Query "io_x" <a@b.c.invalid> - 2011-05-27 05:47 +0200
                Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-26 15:02 -0400
        Re: Malloc Query "BartC" <bc@freeuk.com> - 2011-05-18 22:31 +0100
          Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-18 23:37 +0100
            Re: Malloc Query "BartC" <bc@freeuk.com> - 2011-05-19 01:50 +0100
              Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-19 02:50 +0100
                Re: Malloc Query "BartC" <bc@freeuk.com> - 2011-05-19 12:14 +0100
                Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-19 15:10 +0100
                Re: Malloc Query "BartC" <bc@freeuk.com> - 2011-05-19 15:48 +0100
      Re: Malloc Query cri@tiac.net (Richard Harter) - 2011-05-18 19:31 +0000
      Re: Malloc Query Ike Naar <ike@iceland.freeshell.org> - 2011-05-18 21:43 +0000
        Re: Malloc Query "BartC" <bc@freeuk.com> - 2011-05-18 22:58 +0100
  Re: Malloc Query Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2011-05-17 14:01 -0600
  Re: Malloc Query Columbus sailed the ocean China Blue <chine.bleu@yahoo.com> - 2011-05-17 13:21 -0700
  Re: Malloc Query BGB <cr88192@hotmail.com> - 2011-05-17 14:08 -0700
    Re: Malloc Query Michael Press <rubrum@pacbell.net> - 2011-05-17 19:49 -0700
  Re: Malloc Query Lauri Alanko <la@iki.fi> - 2011-05-18 00:50 +0000
  Re: Malloc Query Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-05-17 21:21 -0400
    Re: Malloc Query "io_x" <a@b.c.invalid> - 2011-05-18 19:31 +0200
    Re: Malloc Query Jorgen Grahn <grahn+nntp@snipabacken.se> - 2011-05-18 21:36 +0000
      Re: Malloc Query Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-05-18 21:26 -0400
    Re: Malloc Query Tim Rentsch <txr@alumni.caltech.edu> - 2011-05-19 02:07 -0700
      Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-19 21:13 +1200
  Re: Malloc Query Nobody <nobody@nowhere.com> - 2011-05-18 07:08 +0100
  Re: Malloc Query David Resnick <lndresnick@gmail.com> - 2011-05-19 07:51 -0700
    Re: Malloc Query Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2011-05-19 09:12 -0600

csiph-web