Re: How do the malloc() and free() algorithms work?

Newsgroups	comp.lang.c
Date	2017-05-30 14:08 -0700
References	<733ff530-fc43-46a2-88b1-b3b25c50ac49@googlegroups.com> <1e0e39d4-1170-4753-a98b-45c2d2fded49@googlegroups.com> <5vATA.31041$e57.27209@fx46.am4> <052199bc-c8b3-40bb-9d8f-809cadeddfdc@googlegroups.com>
Message-ID	<ec17cbac-5ec5-46bf-bf70-83ef16db8422@googlegroups.com> (permalink)
Subject	Re: How do the malloc() and free() algorithms work?
From	"Rick C. Hodgin" <rick.c.hodgin@gmail.com>

Show all headers | View raw

On Friday, May 19, 2017 at 7:05:59 PM UTC-4, Rick C. Hodgin wrote:
> Bartc wrote:
> > The program below is the Binary Trees benchmark, which is sensitive to 
> > the quality of malloc and free implementations. But it is limited as a 
> > test because it only allocates and frees large numbers of the same small 
> > allocation (the 'treenode' struct). 
> >
> > What differences does your version make with this? (You can change the 
> > n=15 line for a bigger test.)
> 
> This test exposes a serious flaw in my implementation.  Mine takes
> 4,264ms compared to malloc()'s 862ms, ~5x slower.
> 
> I'll add an optimization over the next few days to remove this flaw
> and post new results.
> 
> My algorithm is ahead on the first pass by 6%, but falls off sharply
> as the allocation count grows.

I haven't forgotten about this.  I've coded the change I needed, but
it's also brought up another performance bottleneck that I'm going to
try to code around as well.

Thank you,
Rick C. Hodgin

Thread

How do the malloc() and free() algorithms work? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-05-16 12:39 -0700
  How do the malloc() and free() algorithms work? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-05-16 14:02 -0700
    Re: How do the malloc() and free() algorithms work? supercat@casperkitty.com - 2017-05-16 15:00 -0700
      Re: How do the malloc() and free() algorithms work? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-05-16 17:56 -0700
        Re: How do the malloc() and free() algorithms work? supercat@casperkitty.com - 2017-05-17 07:56 -0700
    Re: How do the malloc() and free() algorithms work? "Chris M. Thomasson" <invalid@invalid.invalid> - 2017-05-16 15:15 -0700
  Re: How do the malloc() and free() algorithms work? "Chris M. Thomasson" <invalid@invalid.invalid> - 2017-05-16 15:06 -0700
  Re: How do the malloc() and free() algorithms work? "Chris M. Thomasson" <invalid@invalid.invalid> - 2017-05-16 15:13 -0700
  Re: How do the malloc() and free() algorithms work? "Chris M. Thomasson" <invalid@invalid.invalid> - 2017-05-16 15:45 -0700
  Re: How do the malloc() and free() algorithms work? Robert Wessel <robertwessel2@yahoo.com> - 2017-05-16 22:31 -0500
  Re: How do the malloc() and free() algorithms work? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-05-17 07:22 -0700
  Re: How do the malloc() and free() algorithms work? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-05-17 09:15 -0700
    Re: How do the malloc() and free() algorithms work? supercat@casperkitty.com - 2017-05-17 10:35 -0700
    Re: How do the malloc() and free() algorithms work? bartc <bc@freeuk.com> - 2017-05-19 12:17 +0100
      Re: How do the malloc() and free() algorithms work? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-05-19 04:56 -0700
      Re: How do the malloc() and free() algorithms work? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-05-19 16:05 -0700
        Re: How do the malloc() and free() algorithms work? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-05-30 14:08 -0700
          Re: How do the malloc() and free() algorithms work? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-07-29 09:47 -0700
  Re: How do the malloc() and free() algorithms work? "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2017-05-18 20:48 +0800
    Re: How do the malloc() and free() algorithms work? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-05-18 07:19 -0700
      Re: How do the malloc() and free() algorithms work? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2017-05-18 07:33 -0700
        Re: How do the malloc() and free() algorithms work? "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2017-05-18 23:32 +0800
          Re: How do the malloc() and free() algorithms work? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-05-18 08:45 -0700
            Re: How do the malloc() and free() algorithms work? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-05-18 08:47 -0700
        Re: How do the malloc() and free() algorithms work? Keith Thompson <kst-u@mib.org> - 2017-05-18 09:24 -0700
          Re: How do the malloc() and free() algorithms work? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2017-05-18 12:18 -0700
            Re: How do the malloc() and free() algorithms work? asetofsymbols@gmail.com - 2017-05-19 14:37 -0700
              Re: How do the malloc() and free() algorithms work? Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2017-05-19 16:01 -0600
                Re: How do the malloc() and free() algorithms work? asetofsymbols@gmail.com - 2017-05-31 00:05 -0700
                Re: How do the malloc() and free() algorithms work? Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2017-05-31 10:11 -0600
                Re: How do the malloc() and free() algorithms work? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2017-05-31 09:20 -0700
                Re: How do the malloc() and free() algorithms work? Jerry Stuckle <jstucklex@attglobal.net> - 2017-05-31 13:03 -0400
                Re: How do the malloc() and free() algorithms work? David Kleinecke <dkleinecke@gmail.com> - 2017-05-31 12:14 -0700
                Re: How do the malloc() and free() algorithms work? Jerry Stuckle <jstucklex@attglobal.net> - 2017-05-31 16:11 -0400
                Re: How do the malloc() and free() algorithms work? David Kleinecke <dkleinecke@gmail.com> - 2017-05-31 20:23 -0700
                Re: How do the malloc() and free() algorithms work? Jerry Stuckle <jstucklex@attglobal.net> - 2017-06-01 11:13 -0400
                Re: How do the malloc() and free() algorithms work? Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2017-05-31 21:50 -0600
                Re: How do the malloc() and free() algorithms work? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-06-01 11:28 +0100
                Re: How do the malloc() and free() algorithms work? supercat@casperkitty.com - 2017-06-01 07:40 -0700
                Re: How do the malloc() and free() algorithms work? scott@slp53.sl.home (Scott Lurndal) - 2017-06-01 15:36 +0000
                Re: How do the malloc() and free() algorithms work? Jerry Stuckle <jstucklex@attglobal.net> - 2017-06-01 11:14 -0400
                Re: How do the malloc() and free() algorithms work? Robert Wessel <robertwessel2@yahoo.com> - 2017-06-01 11:36 -0500
                Re: How do the malloc() and free() algorithms work? gordonb.zj91o@burditt.org (Gordon Burditt) - 2017-06-05 01:11 -0500
                Re: How do the malloc() and free() algorithms work? supercat@casperkitty.com - 2017-06-05 08:01 -0700
                Re: How do the malloc() and free() algorithms work?  gordonb.gl67j@burditt.org (Gordon Burditt) - 2017-06-05 23:49 -0500
                Re: How do the malloc() and free() algorithms work? supercat@casperkitty.com - 2017-06-06 10:13 -0700
                Re: How do the malloc() and free() algorithms work? David Kleinecke <dkleinecke@gmail.com> - 2017-06-06 16:50 -0700
                Re: How do the malloc() and free() algorithms work? Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2017-06-06 21:33 -0600
                Re: How do the malloc() and free() algorithms work? Robert Wessel <robertwessel2@yahoo.com> - 2017-06-07 00:37 -0500
                Re: How do the malloc() and free() algorithms work? David Kleinecke <dkleinecke@gmail.com> - 2017-06-07 17:13 -0700
                Re: How do the malloc() and free() algorithms work? Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2017-06-07 21:35 -0600
                Re: How do the malloc() and free() algorithms work? David Kleinecke <dkleinecke@gmail.com> - 2017-06-07 22:06 -0700
                Re: How do the malloc() and free() algorithms work? Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2017-06-13 08:45 -0600
                Re: How do the malloc() and free() algorithms work? Jerry Stuckle <jstucklex@attglobal.net> - 2017-06-08 08:36 -0400
                Re: How do the malloc() and free() algorithms work? supercat@casperkitty.com - 2017-06-08 07:51 -0700
                Re: How do the malloc() and free() algorithms work? Jerry Stuckle <jstucklex@attglobal.net> - 2017-06-08 11:19 -0400
                Re: How do the malloc() and free() algorithms work? Robert Wessel <robertwessel2@yahoo.com> - 2017-06-08 11:39 -0500
                Re: How do the malloc() and free() algorithms work? supercat@casperkitty.com - 2017-06-08 10:39 -0700
                Re: How do the malloc() and free() algorithms work? Jerry Stuckle <jstucklex@attglobal.net> - 2017-06-08 14:01 -0400
                Re: How do the malloc() and free() algorithms work? Robert Wessel <robertwessel2@yahoo.com> - 2017-06-08 13:06 -0500
                Re: How do the malloc() and free() algorithms work? Robert Wessel <robertwessel2@yahoo.com> - 2017-06-08 13:18 -0500
                Re: How do the malloc() and free() algorithms work? scott@slp53.sl.home (Scott Lurndal) - 2017-06-08 18:33 +0000
                Re: How do the malloc() and free() algorithms work? Robert Wessel <robertwessel2@yahoo.com> - 2017-06-08 14:21 -0500
                Re: How do the malloc() and free() algorithms work? supercat@casperkitty.com - 2017-06-13 10:37 -0700
                Re: How do the malloc() and free() algorithms work? scott@slp53.sl.home (Scott Lurndal) - 2017-06-13 18:08 +0000
                Re: How do the malloc() and free() algorithms work? Robert Wessel <robertwessel2@yahoo.com> - 2017-06-14 20:15 -0500
                Re: How do the malloc() and free() algorithms work? scott@slp53.sl.home (Scott Lurndal) - 2017-06-08 15:44 +0000
                Re: How do the malloc() and free() algorithms work? David Kleinecke <dkleinecke@gmail.com> - 2017-06-08 11:34 -0700
                Re: How do the malloc() and free() algorithms work? scott@slp53.sl.home (Scott Lurndal) - 2017-06-08 12:52 +0000
                Re: How do the malloc() and free() algorithms work? Robert Wessel <robertwessel2@yahoo.com> - 2017-06-08 10:48 -0500
                Re: How do the malloc() and free() algorithms work? asetofsymbols@gmail.com - 2017-05-31 13:10 -0700
                Re: How do the malloc() and free() algorithms work? Jerry Stuckle <jstucklex@attglobal.net> - 2017-05-31 16:12 -0400
                Re: How do the malloc() and free() algorithms work? asetofsymbols@gmail.com - 2017-05-31 13:25 -0700
                Re: How do the malloc() and free() algorithms work? Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2017-05-31 21:51 -0600
                Re: How do the malloc() and free() algorithms work? "Chris M. Thomasson" <invalid@invalid.invalid> - 2017-05-31 21:05 -0700
      Re: How do the malloc() and free() algorithms work? "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2017-05-18 23:28 +0800
        Re: How do the malloc() and free() algorithms work? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-05-18 08:42 -0700
        Re: How do the malloc() and free() algorithms work? Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2017-05-18 09:46 -0600
        Re: How do the malloc() and free() algorithms work? supercat@casperkitty.com - 2017-05-18 09:08 -0700
          Re: How do the malloc() and free() algorithms work? "Chris M. Thomasson" <invalid@invalid.invalid> - 2017-05-18 15:48 -0700
            Re: How do the malloc() and free() algorithms work? supercat@casperkitty.com - 2017-05-18 16:07 -0700
              Re: How do the malloc() and free() algorithms work? "Chris M. Thomasson" <invalid@invalid.invalid> - 2017-05-20 15:17 -0700
  Re: How do the malloc() and free() algorithms work? Siri Cruise <chine.bleu@yahoo.com> - 2017-05-20 16:06 -0700

csiph-web