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

Groups > comp.lang.c++ > #68929

Re: alloca()-support

From Anton Shepelev <anton.txt@gmail.com>
Newsgroups comp.lang.c++, comp.lang.c
Subject Re: alloca()-support
Date 2019-10-03 01:47 +0300
Organization A noiseless patient Spider
Message-ID <20191003014754.39250b808212c3b7c3a755b3@gmail.com> (permalink)
References <qmsqs0$472$1@news.albasani.net> <qn1r0n$b77$1@gioia.aioe.org> <20191002162609.52a3f122331a7c7dd7040fe6@gmail.com> <qn2u1n$1m5p$1@gioia.aioe.org>

Cross-posted to 2 groups.

Show all headers | View raw

Chris M. Thomasson:

> Will have more time to get back to you later on tonight.
> However, take a deep look at reaps:
> https://people.cs.umass.edu/~emery/pubs/berger-oopsla2002.pdf

Their meaning of heap refers the group's previous researh
(Heap Layers) rather than to the general usage of the term
w.r.t. computer memory organisation.  Heap layers seem to
comprise a sort of hierarchical and flexibly composable
memory manager where each layer allocates and deallocates
memory from the layer on top (!) of it, implemented as a
mix-in "superclass", but I don't understand why mix-ins in
particular and OOP in general should be essential to this
architencture.  The rationale that they provide in the two
articles seems to be equally valid for conventional
dependency inversion.  Remeber at least the parser
combinators thread here (comp.lang.c) to see what level of
composability is possible in C.

This 12-page article devotes only a page-worth of space
(including diagrams) to the explanation of
reaps -- allegedly its central subject and the only original
contribution described.  When an object on in the region
part of the reap dies, it goes to an associated heap, which
is used for subsequent allocations until exhausted, when the
reap continues to grow.  How exactly it works with respect
to objects of variable size is unclear, and the only example
does not include the case of resurrections (allocations from
the heap part).

In fig. 3b, which fails to explain the meanig of arrows,
`sbrk' is connected only with RegionHeap.  Does it mean that
LeaHeap is composed directly of the removed chunks in the
region area?  if so, whence does it take the memory to store
its metadata, which can hardly be of constant or upper-
bounded size?  In general, LeaHeap seems to operate on the
"holes" in the region in order to prevent growing the region
unless absolutely unavoidable.  I wonder, therefore, if this
allcoator does not, after an initial period of region
growth, degrade to LeaHeap performance in case of an
approximately balanced alloc/free sequence, because
ClearOptimizedHeap, by definition, will then work with
LeaHeap most of the time.

My personal and, as usual, naive thought was to manage a
collection of custom relocatable pointers:

   struct relpointer
   {  void* _;  };

or indirect poiners void**, and defragment the region from
time to time.  The user will use these pointers and the
memory allocator will make sure survive the rearangement.
In order avoid double indirection at every pointer access, a
lock mechanism can be introduced to ensure that a pointer is
not relocated while the lock holds.  Locks should guard
performace-critical secsions with intensive pointer access.

In order to avoid serious slow-downs due to this occasional
tidying-up, one could do it no more than one "hole" at a
time using a fancy algorithm of step-wise defragmentation,
where each step is a fast operation that decreases
fragmentaion in one of several ways:

  1.  by moving a hole up the stack, so that collapsing it
      requires the relocation of a smaller memory block from
      top of the region-stack,

  2.  by moving a hole up the stack to a place adjacent with
      another hole,

  3.  by collapsing a hole (located sufficiently close to
      top of stack) through shifting all the memory in front
      of it to the left by the size of the hole,

  4.  by plugging a hole with a block or blocks of the same
      total size somewhere up the stack,

  5.  by allocating the space of a hole for a new object of
      the same size,

Existing algorithms for efficient real-time disk
defragmentation may serve as an inspiration.

-- 
()  ascii ribbon campaign -- against html e-mail
/\  http://preview.tinyurl.com/qcy6mjc [archived]

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

Thread

alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-30 14:02 +0200
  Re: alloca()-support Frederick Gotham <cauldwell.thomas@gmail.com> - 2019-09-30 07:02 -0700
    Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-30 16:09 +0200
      Re: alloca()-support Bo Persson <bo@bo-persson.se> - 2019-09-30 17:29 +0200
        Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-30 17:33 +0200
    Re: alloca()-support gazelle@shell.xmission.com (Kenny McCormack) - 2019-09-30 16:26 +0000
  Re: alloca()-support Anton Shepelev <anton.txt@g{oogle}mail.com> - 2019-09-30 17:12 +0300
    Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-30 16:16 +0200
      Re: alloca()-support Anton Shepelev <anton.txt@g{oogle}mail.com> - 2019-09-30 17:30 +0300
        Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-30 16:44 +0200
          Re: alloca()-support Anton Shepelev <anton.txt@gmail.com> - 2019-10-02 00:36 +0300
            Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-02 06:28 +0200
              Re: alloca()-support Anton Shepelev <anton.txt@gmail.com> - 2019-10-02 16:08 +0300
                Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-02 15:42 +0200
    Re: alloca()-support scott@slp53.sl.home (Scott Lurndal) - 2019-09-30 14:30 +0000
      Re: alloca()-support Anton Shepelev <anton.txt@g{oogle}mail.com> - 2019-09-30 17:33 +0300
        Re: alloca()-support David Brown <david.brown@hesbynett.no> - 2019-09-30 16:56 +0200
    Re: alloca()-support Melzzzzz <Melzzzzz@zzzzz.com> - 2019-09-30 15:29 +0000
      Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-30 17:31 +0200
        Re: alloca()-support Melzzzzz <Melzzzzz@zzzzz.com> - 2019-10-01 07:03 +0000
          Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-01 10:57 +0200
            Re: alloca()-support Melzzzzz <Melzzzzz@zzzzz.com> - 2019-10-01 18:49 +0000
              Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-01 21:20 +0200
                Re: alloca()-support scott@slp53.sl.home (Scott Lurndal) - 2019-10-01 20:39 +0000
                Re: alloca()-support Melzzzzz <Melzzzzz@zzzzz.com> - 2019-10-02 04:15 +0000
                Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-02 06:28 +0200
                Re: alloca()-support Melzzzzz <Melzzzzz@zzzzz.com> - 2019-10-02 04:29 +0000
    Re: alloca()-support Keith Thompson <kst-u@mib.org> - 2019-09-30 11:14 -0700
  Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-30 18:04 +0200
    Re: alloca()-support William Ahern <william@25thandClement.com> - 2019-09-30 11:01 -0700
      Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-01 07:19 +0200
    Re: alloca()-support Paavo Helde <myfirstname@osa.pri.ee> - 2019-09-30 22:26 +0300
      Re: alloca()-support scott@slp53.sl.home (Scott Lurndal) - 2019-09-30 19:46 +0000
    Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-01 07:32 +0200
      Re: alloca()-support Paavo Helde <myfirstname@osa.pri.ee> - 2019-10-01 09:08 +0300
        Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-01 08:35 +0200
  Re: alloca()-support Soviet_Mario <SovietMario@CCCP.MIR> - 2019-09-30 18:48 +0200
    Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-30 18:51 +0200
      Re: alloca()-support Soviet_Mario <SovietMario@CCCP.MIR> - 2019-09-30 18:55 +0200
        Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-30 18:58 +0200
          Re: alloca()-support Soviet_Mario <SovietMario@CCCP.MIR> - 2019-09-30 19:53 +0200
            Re: alloca()-support Keith Thompson <kst-u@mib.org> - 2019-09-30 11:13 -0700
            Re: alloca()-support scott@slp53.sl.home (Scott Lurndal) - 2019-09-30 19:38 +0000
              Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-01 07:41 +0200
                Re: alloca()-support scott@slp53.sl.home (Scott Lurndal) - 2019-10-01 15:19 +0000
                Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-01 17:31 +0200
                Re: alloca()-support Melzzzzz <Melzzzzz@zzzzz.com> - 2019-10-01 18:58 +0000
                Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-01 21:24 +0200
                Re: alloca()-support Melzzzzz <Melzzzzz@zzzzz.com> - 2019-10-02 04:28 +0000
                Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-02 06:30 +0200
                Re: alloca()-support Melzzzzz <Melzzzzz@zzzzz.com> - 2019-10-02 04:36 +0000
                Re: alloca()-support David Brown <david.brown@hesbynett.no> - 2019-10-02 10:01 +0200
                Re: alloca()-support Melzzzzz <Melzzzzz@zzzzz.com> - 2019-10-02 04:42 +0000
                Re: alloca()-support David Brown <david.brown@hesbynett.no> - 2019-10-02 10:10 +0200
                Re: alloca()-support Mel <mel@zzzzz.com> - 2019-10-02 15:13 +0200
                Re: alloca()-support David Brown <david.brown@hesbynett.no> - 2019-10-01 21:10 +0200
                Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-01 21:25 +0200
                Re: alloca()-support scott@slp53.sl.home (Scott Lurndal) - 2019-10-01 20:44 +0000
                Re: alloca()-support David Brown <david.brown@hesbynett.no> - 2019-10-01 23:26 +0200
                Re: alloca()-support Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2019-10-01 21:08 -0600
                Re: alloca()-support David Brown <david.brown@hesbynett.no> - 2019-10-02 10:19 +0200
                Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-02 06:39 +0200
                Re: alloca()-support David Brown <david.brown@hesbynett.no> - 2019-10-02 10:34 +0200
                Re: alloca()-support Mel <mel@zzzzz.com> - 2019-10-02 15:14 +0200
                Re: alloca()-support Mel <mel@zzzzz.com> - 2019-10-02 15:18 +0200
                Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-02 15:21 +0200
                Re: alloca()-support Melzzzzz <Melzzzzz@zzzzz.com> - 2019-10-03 04:09 +0000
                Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-03 07:48 +0200
                Re: alloca()-support Melzzzzz <Melzzzzz@zzzzz.com> - 2019-10-03 05:49 +0000
                Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-03 07:52 +0200
                Re: alloca()-support Melzzzzz <Melzzzzz@zzzzz.com> - 2019-10-03 06:46 +0000
                Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-03 10:59 +0200
              Re: alloca()-support Soviet_Mario <SovietMario@CCCP.MIR> - 2019-10-03 13:39 +0200
                Re: alloca()-support scott@slp53.sl.home (Scott Lurndal) - 2019-10-03 13:23 +0000
                Re: alloca()-support David Brown <david.brown@hesbynett.no> - 2019-10-03 15:38 +0200
                Re: alloca()-support scott@slp53.sl.home (Scott Lurndal) - 2019-10-03 14:51 +0000
                Re: alloca()-support David Brown <david.brown@hesbynett.no> - 2019-10-04 09:49 +0200
                Re: alloca()-support Soviet_Mario <SovietMario@CCCP.MIR> - 2019-10-03 21:47 +0200
                Re: alloca()-support David Brown <david.brown@hesbynett.no> - 2019-10-04 09:53 +0200
                Re: alloca()-support Soviet_Mario <SovietMario@CCCP.MIR> - 2019-10-03 21:52 +0200
            Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-01 07:39 +0200
        Re: alloca()-support James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-09-30 21:36 -0400
      Re: alloca()-support Philipp Klaus Krause <pkk@spth.de> - 2019-09-30 19:14 +0200
        Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-30 19:16 +0200
          Re: alloca()-support Robert Wessel <robertwessel2@yahoo.com> - 2019-10-01 00:18 -0500
            Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-01 07:43 +0200
            Re: alloca()-support Keith Thompson <kst-u@mib.org> - 2019-10-01 02:42 -0700
              Re: alloca()-support James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-10-01 08:11 -0400
              Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-01 14:53 +0200
      Re: alloca()-support scott@slp53.sl.home (Scott Lurndal) - 2019-09-30 17:52 +0000
    Re: alloca()-support Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2019-09-30 11:20 -0600
      Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-30 19:42 +0200
        Re: alloca()-support Soviet_Mario <SovietMario@CCCP.MIR> - 2019-09-30 20:02 +0200
      Re: alloca()-support Soviet_Mario <SovietMario@CCCP.MIR> - 2019-09-30 19:54 +0200
        Re: alloca()-support Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2019-09-30 14:28 -0600
          Re: alloca()-support David Brown <david.brown@hesbynett.no> - 2019-10-01 09:38 +0200
      Re: alloca()-support Soviet_Mario <SovietMario@CCCP.MIR> - 2019-09-30 20:01 +0200
        Re: alloca()-support Manfred <noname@add.invalid> - 2019-10-01 17:45 +0200
  Re: alloca()-support Frederick Gotham <cauldwell.thomas@gmail.com> - 2019-10-02 00:03 -0700
    Re: alloca()-support Paavo Helde <myfirstname@osa.pri.ee> - 2019-10-02 11:30 +0300
    Re: alloca()-support Ian Collins <ian-news@hotmail.com> - 2019-10-02 21:34 +1300
      Re: alloca()-support Frederick Gotham <cauldwell.thomas@gmail.com> - 2019-10-02 01:36 -0700
        Re: alloca()-support Ian Collins <ian-news@hotmail.com> - 2019-10-02 21:41 +1300
          Re: alloca()-support Frederick Gotham <cauldwell.thomas@gmail.com> - 2019-10-02 02:28 -0700
  Re: alloca()-support "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-10-02 02:35 -0700
    Re: alloca()-support Frederick Gotham <cauldwell.thomas@gmail.com> - 2019-10-02 02:43 -0700
    Re: alloca()-support Anton Shepelev <anton.txt@gmail.com> - 2019-10-02 16:26 +0300
      Re: alloca()-support "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-10-02 12:33 -0700
        Re: alloca()-support Anton Shepelev <anton.txt@gmail.com> - 2019-10-03 01:47 +0300
          Re: alloca()-support "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-10-05 14:08 -0700

csiph-web