Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #110367
| Subject | Re: How do the malloc() and free() algorithms work? |
|---|---|
| Newsgroups | comp.lang.c |
| References | <733ff530-fc43-46a2-88b1-b3b25c50ac49@googlegroups.com> <1e0e39d4-1170-4753-a98b-45c2d2fded49@googlegroups.com> |
| From | bartc <bc@freeuk.com> |
| Message-ID | <5vATA.31041$e57.27209@fx46.am4> (permalink) |
| Organization | virginmedia.com |
| Date | 2017-05-19 12:17 +0100 |
On 17/05/2017 17:15, Rick C. Hodgin wrote:
> This new memory algorithm has significantly increased the performance
> of some of my existing and well-debugged applications. I am floored
> by the change from simply moving from one memory algorithm to another.
> I'm in debug mode and am seeing almost a 10-fold increase in speed
> on algorithms that load and parse data, and on algorithms have data
> existing for relatively short lifetimes. It's unbelievable the
> performance difference. I haven't even compiled into release mode
> yet (with optimizations, debug mode is slow unoptimized code with
> all kinds of checks enabled to validate data isn't being corrupted
> accidentally).
>
> -----
> Is it common knowledge in 2017 that malloc() and realloc() and free()
> are inherently slow in their implementation? I'm thinking that if
> some existing common widely-distributed applications switched to a
> different heap management subsystem, they too might see staggering
> increases in performance with no other changes to their system.
Do you have any benchmark code we can try out? Using regular
malloc/free. Then we can appreciate what a 10x speed increase might be like!
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.)
//-------------------------------------------
#include <stdio.h>
#include <stdlib.h>
int nallocs;
typedef struct _node {
struct _node *left;
struct _node *right;
int item;
} treenode;
treenode* newtreenode(treenode* left, treenode* right, int item) {
treenode* t;
t=malloc(sizeof(treenode));
++nallocs;
t->left=left;
t->right=right;
t->item=item;
return t;
}
int itemcheck(treenode* tree) {
if (tree->left==NULL)
return tree->item;
else
return tree->item+itemcheck(tree->left)-itemcheck(tree->right);
}
treenode* bottomuptree(int item, int depth) {
if (depth>0)
return newtreenode(bottomuptree(2*item-1,depth-1),
bottomuptree(2*item,depth-1),item);
else
return newtreenode(NULL,NULL,item);
}
void deletetree(treenode* tree) {
if (tree->left) {
deletetree(tree->left);
deletetree(tree->right);
}
free(tree);
}
int main(void) {
treenode *stretchtree, *longlivedtree, *temptree;
int n,depth,mindepth,maxdepth,stretchdepth,check,iterations,i;
n=15;
mindepth=4;
if ((mindepth+2)>n)
maxdepth=mindepth+1;
else
maxdepth=n;
stretchdepth=maxdepth+1;
stretchtree=bottomuptree(0,stretchdepth);
printf("Stretch tree of depth %d\tcheck: %d\n",
stretchdepth,itemcheck(stretchtree));
deletetree(stretchtree);
longlivedtree=bottomuptree(0,maxdepth);
depth=mindepth;
while (depth<=maxdepth) {
iterations=1<<(maxdepth-depth+mindepth);
check=0;
for (i=1; i<=iterations; ++i) {
temptree=bottomuptree(i,depth);
check=check+itemcheck(temptree);
deletetree(temptree);
temptree=bottomuptree(-i,depth);
check=check+itemcheck(temptree);
deletetree(temptree);
}
printf("%d\tTrees of depth\t%d\tcheck: %d\n",
iterations*2,depth,check);
depth=depth+2;
}
printf("%s %d %s %d\n","long lived tree of depth",
maxdepth,"\tcheck:",itemcheck(longlivedtree));
printf("Nallocs= %d\n",nallocs);
}
//-------------------------------------------
--
bartc
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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