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

Groups > comp.lang.c > #110173 > unrolled thread

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

Back to article view | Back to comp.lang.c

Contents

  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

Page 1 of 5  [1] 2 3 4 5  Next page →

#110173 — How do the malloc() and free() algorithms work?

Can someone point me to a website or explain to me how malloc() and
free() work in a general sense on Windows?

I'd like to know how it propagates its structures from front-door
requests, through any layers, to the actual memory locations, and
what it uses to store data beyond that which is visible to us as
a buffer in an application program.

Thank you,
Rick C. Hodgin

[toc] | [next] | [standalone]

#110181

I ask because I've written one that is performing 3x to 8x faster than MSVC++'s,
and I can't believe it.  I am thinking I am doing something wrong.

Mine is semaphore'd, uses VirtualAlloc() with MEM_COMMIT, and is a
three-tiered design to various requested block sizes, supports pre- and
post-guard buffers of N,M bytes each for memory corruption
detection, and a slower variant allows un-committed virtual pages to be
inserted before and after, allowing for memory corruption detection on
the instruction creating the fault (the reason I wrote it, as an aid in
debugging memory errors).

It consumes more memory than malloc, but with the speedup, I think
most would tolerate the trade.

I'm doing stress testing tomorrow and Thursday.  I'm very surprised it can
even compete in the same ballpark as malloc() and free().  I would've
figured they were as optimized as could be due to their oft-use.

Thank you,
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#110183

On Tuesday, May 16, 2017 at 4:02:30 PM UTC-5, Rick C. Hodgin wrote:
> I ask because I've written one that is performing 3x to 8x faster than MSVC++'s,
> and I can't believe it.  I am thinking I am doing something wrong.

It's possible to optimize memory management code around different usage
patterns.  Code which is optimized for the usage patterns that are
actually encountered may be able to perform much faster than code which
is not.  In the era when the first versions of MSVC were created, heavy
use of malloc() and free() was practically an admission that one wasn't
interested in performance, since programs with memory management code
tailored to its actual needs could vastly outperform functions that had
to accommodate arbitrary sequences of acquisitions and releases.

[toc] | [prev] | [next] | [standalone]

#110191

On Tuesday, May 16, 2017 at 6:00:22 PM UTC-4, supe...@casperkitty.com wrote:
> On Tuesday, May 16, 2017 at 4:02:30 PM UTC-5, Rick C. Hodgin wrote:
> > I ask because I've written one that is performing 3x to 8x faster than MSVC++'s,
> > and I can't believe it.  I am thinking I am doing something wrong.
> 
> It's possible to optimize memory management code around different usage
> patterns.  Code which is optimized for the usage patterns that are
> actually encountered may be able to perform much faster than code which
> is not.

The tests I'm doing right now are on general purpose access using the
existing code bases I have.  I didn't design the algorithm for a specific
usage pattern.  In fact, I didn't design it to be efficient.  I simply
wanted a way to have a solid debugging tool that was drop-in replacement
for malloc(), realloc(), and free().  I didn't care about performance
at all, provided it was not 10x slower than malloc().  I needed a way to
find allocated buffer overruns.

Designing these algorithms though, I've seen about five different
variations that I could see having advantages in different cases.  I
have also considered how some of them could work with a CPU that
had a feature I'd call "stitching," which is a type of access that's
enabled by a special load instruction, which loads a pointer into a
register, along with its stitch buffer, which allows fragmented
blocks to appear contiguous and work together as though it were a
larger, linear block, all through the enabling of a few CPU resources
dedicated to that task.

> In the era when the first versions of MSVC were created, heavy
> use of malloc() and free() was practically an admission that one wasn't
> interested in performance, since programs with memory management code
> tailored to its actual needs could vastly outperform functions that had
> to accommodate arbitrary sequences of acquisitions and releases.

I was not aware of that.  I figured malloc() and free() would be among
the most heavily optimized algorithms in existence.  I've never looked
into them, but I have seen memcpy() come up from time to time, and I've
seen where it is hand-coded assembly.  I just assumed the same for the
core portions of malloc() and free().

Thank you,
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#110206

On Tuesday, May 16, 2017 at 7:56:36 PM UTC-5, Rick C. Hodgin wrote:
> > In the era when the first versions of MSVC were created, heavy
> > use of malloc() and free() was practically an admission that one wasn't
> > interested in performance, since programs with memory management code
> > tailored to its actual needs could vastly outperform functions that had
> > to accommodate arbitrary sequences of acquisitions and releases.
> 
> I was not aware of that.  I figured malloc() and free() would be among
> the most heavily optimized algorithms in existence.  I've never looked
> into them, but I have seen memcpy() come up from time to time, and I've
> seen where it is hand-coded assembly.  I just assumed the same for the
> core portions of malloc() and free().

If code running on a single thread will be churning many objects of a
particular type which contains a pointer to something of the same type
called "link" [that could be used for arbitrary purposes in allocated
objects], performance may be improved substantially be using an allocator
designed for that purpose.

    THING *thing_recycle= 0;
    THING *thing_alloc(void)
    {
      THING *ret;
      if (thing_recycle)
      {
        ret = thing_recycle;
        thing_recycle = ret->link;
      }
      else
      {
        ret = malloc(sizeof (THING));
        ret->link = 0;
      }
      return ret;
    }

    void thing_free(THING *p)
    {
      p->link = thing_recycle;
      thing_recycle = p;
    }

    void thing_empty_trash(void)
    {
      THING *temp;
      while(thing_recycle)
      {
        temp = thing_recycle->link;
        free(thing_recycle);
        thing_recycle = temp;
      };
    }

Any storage which was ever allocated for a "THING" would be ineligible for
use as any other type unless/until code calls thing_empty_trash, but the
combined cost to release a thing and reallocate it without an intervening
thing_empty_trash call would, with mild optimization, be three loads,
three stores, and one null check.  No general-purpose "malloc" could hope to
come close to that except in cases where a compiler can "see" the entire
lifetime of an allocated object and can see that nothing "unusual" happens
to it.

Incidentally, all that would be necessary to make the code thread-safe
would be to give each thread its own copy of thing_recycle, and make each
thread responsible for calling thing_empty_trash on its own pool of
things.  No special handling would be required to accommodate things which
might be allocated on one thread and released on another, since the pools
would have no reason to care about what happens to things after they are
allocated.

[toc] | [prev] | [next] | [standalone]

#110186

On 5/16/2017 2:02 PM, Rick C. Hodgin wrote:
> I ask because I've written one that is performing 3x to 8x faster than MSVC++'s,
> and I can't believe it.  I am thinking I am doing something wrong.
>
> Mine is semaphore'd,

Fwiw, here is a fast semaphore:

https://groups.google.com/d/topic/comp.lang.c++/60IpFwqbtu8/discussion

Thanks to Joe Seigh, a very smart guy indeed!



> uses VirtualAlloc() with MEM_COMMIT, and is a
> three-tiered design to various requested block sizes, supports pre- and
> post-guard buffers of N,M bytes each for memory corruption
> detection, and a slower variant allows un-committed virtual pages to be
> inserted before and after, allowing for memory corruption detection on
> the instruction creating the fault (the reason I wrote it, as an aid in
> debugging memory errors).
>
> It consumes more memory than malloc, but with the speedup, I think
> most would tolerate the trade.
>
> I'm doing stress testing tomorrow and Thursday.  I'm very surprised it can
> even compete in the same ballpark as malloc() and free().  I would've
> figured they were as optimized as could be due to their oft-use.

[toc] | [prev] | [next] | [standalone]

#110184

On 5/16/2017 12:39 PM, Rick C. Hodgin wrote:
> Can someone point me to a website or explain to me how malloc() and
> free() work in a general sense on Windows?
>
> I'd like to know how it propagates its structures from front-door
> requests, through any layers, to the actual memory locations, and
> what it uses to store data beyond that which is visible to us as
> a buffer in an application program.

The best performances use per-thread memory pools with some 
wait/lock-free magic to allow memory allocated in one thread to be freed 
in another. I have some work on this, so does Intel.

https://software.intel.com/en-us/forums/intel-moderncode-for-parallel-architectures/topic/300265
(read all!)

https://www.threadingbuildingblocks.org/tutorial-intel-tbb-scalable-memory-allocator

https://groups.google.com/forum/embed/#!topic/comp.programming.threads/gkX0tIWR_Gk
(very old work!)

:^)

[toc] | [prev] | [next] | [standalone]

#110185

On 5/16/2017 12:39 PM, Rick C. Hodgin wrote:
> Can someone point me to a website or explain to me how malloc() and
> free() work in a general sense on Windows?
>
> I'd like to know how it propagates its structures from front-door
> requests, through any layers, to the actual memory locations, and
> what it uses to store data beyond that which is visible to us as
> a buffer in an application program.

https://www.bsdcan.org/2006/papers/jemalloc.pdf

[toc] | [prev] | [next] | [standalone]

#110189

On 5/16/2017 12:39 PM, Rick C. Hodgin wrote:
> Can someone point me to a website or explain to me how malloc() and
> free() work in a general sense on Windows?
>
> I'd like to know how it propagates its structures from front-door
> requests, through any layers, to the actual memory locations, and
> what it uses to store data beyond that which is visible to us as
> a buffer in an application program.

Also, take a look at:

https://en.wikipedia.org/wiki/Hoard_memory_allocator

;^)

[toc] | [prev] | [next] | [standalone]

#110196

On Tue, 16 May 2017 12:39:13 -0700 (PDT), "Rick C. Hodgin"
<rick.c.hodgin@gmail.com> wrote:

>Can someone point me to a website or explain to me how malloc() and
>free() work in a general sense on Windows?
>
>I'd like to know how it propagates its structures from front-door
>requests, through any layers, to the actual memory locations, and
>what it uses to store data beyond that which is visible to us as
>a buffer in an application program.


If you install MSVS with the right options, most of the source to the
C library is included.

But the short answer is that it mostly punts to the HeapXxxx
functions.

[toc] | [prev] | [next] | [standalone]

#110205

The algorithm I have is three-tier.  It has a root, that branches out
to pages which have control blocks indicating what memory is associated
with that page, which then branch out to allocated pages.

    root ==> page ==> data

There are several roots based on allocation size:

    root8     // Anything allocated 8-bytes or smaller
    root16    // Anything allocated 16-bytes or smaller
    root32    // Anything allocated 32-bytes or smaller
    root64    // Anything allocated 64-bytes or smaller
    root128   // Anything allocated 128-bytes or smaller
    root256   // Anything allocated 256-bytes or smaller
    root512   // Anything allocated 512-bytes or smaller
    root1024  // Anything allocated 1024-bytes or smaller
    root2048  // Anything allocated 2048-bytes or smaller
    root4096  // Anything allocated 4096-bytes or smaller
    root8192  // Anything allocated 8192-bytes or smaller
    root16384 // Anything allocated 16384-bytes or smaller
    root_bg   // For bigger allocations, or memory with guard bytes

Each root has some entries which allow access:

    struct root {
        int     size;
        page*   firstPage;
        page*   firstFreePage;
        page*   lastPage;

        void*   (*malloc)(int size);
        void*   (*realloc)(void* p, int new_size);
        void*   (*free)(void);
    };

Each allocation page has some allocation slots, and basic fields:

    struct slot {
        int     size;          // Allocated size of memory block
    };

    struct page {
        slot*   slots[N];      // N is determined by page size

        void*   base;          // Allocated memory for this page
        page*   prev;          // Prev page in linked list
        page*   next;          // Next page in linked list
        int     firstFreeSlot; // First free slot num on this page
    };
    // Note:  Pages are typically 4KB, with sizeof(slot) being 4,
    //        or page::slots[N] of (4096 - 16) / 4 = 1020 slots

Each page allocates the full size of its slot allocation, so a
single allocation of 6 bytes, for example, creates the first
page, which is 4KB, and it uses slot 0, leaving 1019 slots still
available for use before more allocation for small sizes is
required.  It allocates base = malloc(N * root->size);, which
would be base = malloc(1020 * 8); in this case, which would
allocate a 8160, which is rounded up to the nearest 4KB block
to align with page sizes.

The reallocate, and release/free algorithms traverse the base
range, and determine if a pointer is within that min..max range.
If it is, it determines the start of the slot (allowing for a
pointer in any area of the allocated block to be used to free
the block).  If it's a reallocate and there's enough leftover
room, it immediately returns after updating the size.  Otherwise,
it allocates a new block, copies the data, and frees the original
block, returning the new pointer.  Free algorithms simply release
whatever's there.

For big / guard memory it's a little different.  It uses more
comprehensive page and slot structures, containing base, size,
preguard, postguard bytes, along with some callback information,
and has the option to allocate a virtual page that can be used
to capture invalid access for reads or writes before and after
the memory block.  This may result in a mis-aligned pointer in
the case of using guard pages, and depending on the size, but
the benefit of being able to trap the exact instruction that is
causing the invalid write is well worth it.

That part of the memory management is about 2x to 6x slower than
the traditional malloc() and free() because of the overhead of
creating all of the virtual pages on every call, and the average
misalignment when using guard bytes.

It's less than 2,000 lines long and I'm still stress testing
and debugging it today.  This particular version belongs to the
company I work for.  I plan on writing an expanded version which
contains the variants I mentioned above, and will release the
source code for it when completed.

It's working quite well ... much to my amazement to be honest.
In fact, it's turned out far better than I expected.  I'm rather
stunned to be honest.

Thank you,
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#110212

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.

Thank you,
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#110223

On Wednesday, May 17, 2017 at 11:15:45 AM UTC-5, Rick C. Hodgin wrote:
> 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.

Programmers should be aware that allocation systems that operate on fixed-
sized chunks can vastly outperform those that have to accommodate chunks
of arbitrary size.  Unfortunately, there is no standard means by which one
could make a fixed-size block allocator that was usable in type-agnostic
fashion from code that doesn't always write storage before reading it.
Some algorithms can benefit from being able to use a pattern like:

    unsigned index = thing->table1[key];
    if (index < thing->count && thing->table2[index] == key)
      ... Item was found

which would be unaffected by what value was read from any entry of
table1 that it hadn't written with a known value, but such code could
behave in arbitrary fashion if storage was recycled after having been
used as another type.  For example, a compiler that could see the
sequence:


    thingAsOtherType->whatever = 12345678;
    free_chunk(thingAsOtherType);
    thing = alloc_chunk();
    thing->count = 0;
    ...
    unsigned index = thing->table1[key];
    if (index < thing->count && thing->table2[index] == key)
      ... Item was found

would be entitled to replace it with:

    thing = (THING_TYPE*)thingAsOtherType;
    thing->count = 0;
    int ok = thing->table1[key] < thing->count;
    thingAsOtherType->whatever = 12345678;  // Moved from above
    if (ok && thing->table2[thing->table1[key]] == key)
      ... Item was found

Such substitution could cause the value of thing->table1[key] used for
indexing to be beyond the range of thing->table2, which could in turn
trigger other arbitrary problems.

Unless one knows that a compiler won't perform that style of aggressive
optimizations, or the compiler provides a way of blocking them, the
only safe way to reuse storage as different types without having to
clear it before use is to use malloc/free.

[toc] | [prev] | [next] | [standalone]

#110367

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

[toc] | [prev] | [next] | [standalone]

#110370

I will benchmark it later tonight.  I created the algorithm, but the
source code belongs to thw company I work for.  I'll have to create
my own variant before I can publish source code.

Thank you,
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#110432

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.

It's an interesting test.  Do you have any more?

Thank you,
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#110967

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

[toc] | [prev] | [next] | [standalone]

#115404

On Tuesday, May 30, 2017 at 5:08:55 PM UTC-4, Rick C. Hodgin wrote:
> 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.

I am returning to development on this algorithm.  I'll try to complete it
in the coming week or two.

Thank you,
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#110270

On 17/5/2017 3:39 AM, Rick C. Hodgin wrote:
> Can someone point me to a website or explain to me how malloc() and
> free() work in a general sense on Windows?
> 
> I'd like to know how it propagates its structures from front-door
> requests, through any layers, to the actual memory locations, and
> what it uses to store data beyond that which is visible to us as
> a buffer in an application program.

Depends on the implementation of operating systems? Is it really related 
to C? :)

-- 
   @~@   Remain silent! Drink, Blink, Stretch! Live long and prosper!!
  / v \  Simplicity is Beauty!
/( _ )\ May the Force and farces be with you!
   ^ ^   (x86_64 Ubuntu 9.10)  Linux 2.6.39.3
不借貸! 不詐騙! 不援交! 不打交! 不打劫! 不自殺! 請考慮綜援 (CSSA):
http://www.swd.gov.hk/tc/index/site_pubsvc/page_socsecu/sub_addressesa

[toc] | [prev] | [next] | [standalone]

#110281

On Thursday, May 18, 2017 at 8:48:32 AM UTC-4, Mr. Man-wai Chang wrote:
> On 17/5/2017 3:39 AM, Rick C. Hodgin wrote:
> > Can someone point me to a website or explain to me how malloc() and
> > free() work in a general sense on Windows?
> > 
> > I'd like to know how it propagates its structures from front-door
> > requests, through any layers, to the actual memory locations, and
> > what it uses to store data beyond that which is visible to us as
> > a buffer in an application program.
> 
> Depends on the implementation of operating systems? Is it really related 
> to C? :)

The C Standard defines malloc(), realloc(), free(), and others.  How
they mechanically apply to a given OS and its set of low-level function
call APIs is another matter.  I'm curious about how they are designed
in general (such as what type of model do they use for allocation and
free operations, as I assume there is some core algorithm that's been
developed over time, evolving into the one that's most preferred due
to its general reliability, speed, and minimal fragmentation).

    http://www.iso-9899.info/n1570.html

    7.22.3 [Memory management functions]
    7.22.3.1 [The aligned_alloc function]
    7.22.3.2 [The calloc function]
    7.22.3.3 [The free function]
    7.22.3.4 [The malloc function]
    7.22.3.5 [The realloc function]

I think for CAlive I am going to directly define three types of memory:

    1)  fx-memory  (fixed, process-only)
    2)  mv-memory  (movable, process-only)
    3)  go-memory  (global, system-wide)

When allocating with fx_malloc(), you receive a pointer to a fixed
memory block in the local heap.  It is pointing directly to the place
where memory is, and you can directly manipulate that data.

When allocating with mv_malloc(), you receive a pointer to a pointer
to a fixed memory block in the local heap.  This allows the underlying
memory to be moved around as needed.  You reference it the same way in
source code, but a mild performance hit is had because it's going
through indirection for each reference.

When allocating with go_malloc(), you receive a pointer to a global
memory block in the global heap.  Other processes can request their
access into this heap, with even access to the indicated pointer.

The go-memory will be a direct pointer pointing to the location
where memory is, and since it is managed by the OS, the underlying
virtual pages which relate to the offset allow it to be moved as
needed without application awareness.

Thank you,
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

Page 1 of 5  [1] 2 3 4 5  Next page →

Back to top | Article view | comp.lang.c

csiph-web