Re: Buddy System Memory Allocator

From	"Rod Pemberton" <do_not_have@notemailnotz.cnm>
Newsgroups	comp.lang.forth
Subject	Re: Buddy System Memory Allocator
Date	2012-11-06 20:54 -0500
Organization	Aioe.org NNTP Server
Message-ID	<k7cepb$f6t$1@speranza.aioe.org> (permalink)
References	<yZzls.238791$it2.2729@fx22.am4> <k792o8$c4l$1@speranza.aioe.org> <94819742-bce4-43d3-ae7c-55c553851580@a6g2000vbl.googlegroups.com>

Show all headers | View raw

"Alex McDonald" <blog@rivadpm.com> wrote in message
news:94819742-bce4-43d3-ae7c-55c553851580@a6g2000vbl.googlegroups.com...
> On Nov 5, 7:06 pm, "Rod Pemberton" <do_not_h...@notemailnotz.cnm>
> wrote:
> > "Mark" <m...@dibsco.co.uk> wrote in message
> >  news:yZzls.238791$it2.2729@fx22.am4...
...

> > > However, I'm not sure about the tracking of allocated blocks. I want a
> > > quick and easy way of tracking allocated blocks and buddies using a
> > > method that doesn't involve dynamically growing a linked-list or tree
> > > at run-time. It seems that this is commonly done using a bitmap, but
> > > I don't understand how you keep this manageable if you have a
> > > reasonable amount of memory and want a relatively small minimum
> > > block size. A bitmap of 32 bits will only give me coverage for 8k of
> > > memory if I use a minimum block size of 256 bytes. I am trying to
> > > figure out how to avoid having a bitmap that is hundreds or thousands
> > > of bits long. Is there any easier or alternative technique?
>
> > This issue affects file systems too. So, you may wish to think of your
> > memory allocator as a type of in-memory file-system or read up on how
> > file systems to understand how they solve the problem.
>
> Although that may superficially appear to be the case, [...]

It's not superficial.  It affects old and modern filesystems.  However, it
especially affects older, simple filesystems.

> [...] file systems are designed to solve a quite different problem;
> how do you minimize file IO, [...]

Minimizing the access time of blocks of memory is an issue for a memory
allocator too.

1) If the blocks of memory contain a file as raw sectors from the disk,
e.g., a ramdisk, you've got the same problem in memory as on disk.  You want
those sectors ordered and contiguous.  You don't want them randomly arranged
and distributed all across memory.

2) Many programs allocate and free large quantites of small sized memory
blocks.  After a while, the resulting memory fragmentation results in
various problems for the memory allocator.  Any one or perhaps all of which
can slow the allocator down dramatically.

> [...] reduce seeks to a minimum [...]

This only affects physical hard disks (HD) which have to physically move a
read/write head.  It doesn't affect solid state disks (SDD) which have the
same (near zero) seek time per sector.  For many years now, HDs have come
with cache's for minimizing that problem.  I'm not sure what improvement a
filesystem can offer over a large, fast cache in hardware on the hard disk.
I wouldn't doubt it if modern performance drives automatically moved sectors
around to boost performance, but I don't know if they do...  They do map and
lock out bad tracks.

Also, I'd think you'd want to 'reduce seek time' to a minimum for memory
allocation too, i.e., have good spatial locality.  Without it, it's possible
you could up with situations with unwanting "thrashing", possibly of the
memory allocator code, the microprocessor cache, or the swap space on disk.

> [...] and parallelise operations across many devices
> to decrease latency and increase bandwidth.

That would definately be true for certain RAID configurations, e.g., data
striping.  It'd also be true for multiple devices each with a portion of a
filesystem when mounted into a single filesystem, like for POSIX
environments.  However, some filesystems treat each device as having a
separate filesystem.  And, some hardware doesn't have hardware support
configuring multiple physical drives as one virtual drive.  I.e., this can
be true for more advanced modern hardware.

> The OP needs to state the use case for his allocator.

We're not expecting him to write a specialized allocator or world-class
allocator for Forth are we?  As I understood it, He just wanted something
simple and quick.

Rod Pemberton

Thread

[OT] Buddy System Memory Allocator "Mark" <mark@dibsco.co.uk> - 2012-11-04 20:10 +0000
  Re: Buddy System Memory Allocator Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-11-04 15:05 -0800
    Re: Buddy System Memory Allocator Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-11-04 22:02 -0800
      Re: Buddy System Memory Allocator "Mark" <mark@dibsco.co.uk> - 2012-11-10 12:53 +0000
        Re: Buddy System Memory Allocator "Rod Pemberton" <do_not_have@notemailnotz.cnm> - 2012-11-10 20:25 -0500
          Re: Buddy System Memory Allocator Josh Grams <josh@qualdan.com> - 2012-11-11 11:49 +0000
            Re: Buddy System Memory Allocator Bernd Paysan <bernd.paysan@gmx.de> - 2012-11-11 17:43 +0100
              Re: Buddy System Memory Allocator Josh Grams <josh@qualdan.com> - 2012-11-12 01:55 +0000
            Re: Buddy System Memory Allocator "Elizabeth D. Rather" <erather@forth.com> - 2012-11-11 07:06 -1000
    Re: Buddy System Memory Allocator Alex McDonald <blog@rivadpm.com> - 2012-11-05 06:33 -0800
    Re: Buddy System Memory Allocator "Mark" <mark@dibsco.co.uk> - 2012-11-10 12:05 +0000
      Re: Buddy System Memory Allocator Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-11-13 19:49 -0800
  Re: [OT] Buddy System Memory Allocator Paul Rubin <no.email@nospam.invalid> - 2012-11-04 16:55 -0800
    Re: Buddy System Memory Allocator Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-11-04 19:08 -0800
    Re: [OT] Buddy System Memory Allocator "Mark" <mark@dibsco.co.uk> - 2012-11-07 08:49 +0000
  Re: [OT] Buddy System Memory Allocator Ron Aaron <rambamist@gmail.com> - 2012-11-05 08:17 +0200
    Re: [OT] Buddy System Memory Allocator "Mark" <mark@dibsco.co.uk> - 2012-11-07 09:02 +0000
  Re: [OT] Buddy System Memory Allocator "Rod Pemberton" <do_not_have@notemailnotz.cnm> - 2012-11-05 14:10 -0500
    Re: Buddy System Memory Allocator Alex McDonald <blog@rivadpm.com> - 2012-11-05 12:58 -0800
      Re: Buddy System Memory Allocator "Rod Pemberton" <do_not_have@notemailnotz.cnm> - 2012-11-06 20:54 -0500
        Re: Buddy System Memory Allocator Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-11-06 21:50 -0800
          Re: Buddy System Memory Allocator "Mark" <mark@dibsco.co.uk> - 2012-11-07 08:36 +0000
          Re: Buddy System Memory Allocator "Rod Pemberton" <do_not_have@notemailnotz.cnm> - 2012-11-07 19:49 -0500
            Re: Buddy System Memory Allocator Alex McDonald <blog@rivadpm.com> - 2012-11-08 04:42 -0800
            Re: Buddy System Memory Allocator Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-11-08 19:43 -0800
              Re: Buddy System Memory Allocator albert@spenarnc.xs4all.nl (Albert van der Horst) - 2012-11-09 10:48 +0000
              Re: Buddy System Memory Allocator Bernd Paysan <bernd.paysan@gmx.de> - 2012-11-09 22:15 +0100
        Re: Buddy System Memory Allocator Alex McDonald <blog@rivadpm.com> - 2012-11-07 12:46 -0800
      Re: Buddy System Memory Allocator "Mark" <mark@dibsco.co.uk> - 2012-11-10 13:09 +0000
        Re: Buddy System Memory Allocator Alex McDonald <blog@rivadpm.com> - 2012-11-10 07:43 -0800
    Re: [OT] Buddy System Memory Allocator "Mark" <mark@dibsco.co.uk> - 2012-11-07 09:34 +0000
      Re: Buddy System Memory Allocator Mark Wills <forthfreak@gmail.com> - 2012-11-07 04:07 -0800
        Re: Buddy System Memory Allocator "Rod Pemberton" <do_not_have@notemailnotz.cnm> - 2012-11-07 19:44 -0500
          Re: Buddy System Memory Allocator Paul Rubin <no.email@nospam.invalid> - 2012-11-07 16:57 -0800
            Re: Buddy System Memory Allocator "Rod Pemberton" <do_not_have@notemailnotz.cnm> - 2012-11-07 20:14 -0500
              Re: Buddy System Memory Allocator Paul Rubin <no.email@nospam.invalid> - 2012-11-07 17:32 -0800
                Re: Buddy System Memory Allocator anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-11-08 12:32 +0000
                Re: Buddy System Memory Allocator Paul Rubin <no.email@nospam.invalid> - 2012-11-08 20:00 -0800
                Re: Buddy System Memory Allocator "Rod Pemberton" <do_not_have@notemailnotz.cnm> - 2012-11-09 02:20 -0500
                Re: Buddy System Memory Allocator Paul Rubin <no.email@nospam.invalid> - 2012-11-09 00:53 -0800
                Re: Buddy System Memory Allocator "Rod Pemberton" <do_not_have@notemailnotz.cnm> - 2012-11-09 19:10 -0500
                Re: Buddy System Memory Allocator Paul Rubin <no.email@nospam.invalid> - 2012-11-09 18:47 -0800
                Re: Buddy System Memory Allocator "Rod Pemberton" <do_not_have@notemailnotz.cnm> - 2012-11-10 02:16 -0500
                Re: Buddy System Memory Allocator "Elizabeth D. Rather" <erather@forth.com> - 2012-11-09 17:51 -1000
                Re: Buddy System Memory Allocator Mark Wills <forthfreak@gmail.com> - 2012-11-09 22:51 -0800
                Re: Buddy System Memory Allocator "Rod Pemberton" <do_not_have@notemailnotz.cnm> - 2012-11-10 02:26 -0500
                Re: Buddy System Memory Allocator "Elizabeth D. Rather" <erather@forth.com> - 2012-11-09 22:01 -1000
                Re: Buddy System Memory Allocator Mark Wills <forthfreak@gmail.com> - 2012-11-09 22:49 -0800
                Re: Buddy System Memory Allocator "Rod Pemberton" <do_not_have@notemailnotz.cnm> - 2012-11-10 02:15 -0500
                Re: Buddy System Memory Allocator Mark Wills <forthfreak@gmail.com> - 2012-11-09 22:57 -0800
            Re: Buddy System Memory Allocator Mark Wills <forthfreak@gmail.com> - 2012-11-08 00:22 -0800
        Re: Buddy System Memory Allocator "Mark" <mark@dibsco.co.uk> - 2012-11-10 13:43 +0000
  Re: [OT] Buddy System Memory Allocator Chris Hinsley <chris.hinsley@gmail.com> - 2012-11-07 13:10 +0000
    Re: [OT] Buddy System Memory Allocator Chris Hinsley <chris.hinsley@gmail.com> - 2012-11-07 13:31 +0000
  Re: [OT] Buddy System Memory Allocator Charles Mélice <charles.melice@gmail.com> - 2012-11-11 05:29 -0800

csiph-web