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

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

alloca()-support

Started byBonita Montero <Bonita.Montero@gmail.com>
First post2019-09-30 14:02 +0200
Last post2019-10-05 14:08 -0700
Articles 9 on this page of 109 — 21 participants

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

Contents

  alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-30 14:02 +0200
    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 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 gazelle@shell.xmission.com (Kenny McCormack) - 2019-09-30 16:26 +0000
    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 Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-10-06 06:16 -0700
                  Re: alloca()-support Anton Shepelev <anton.txt@gmail.com> - 2019-10-06 16:22 +0300
                    Re: alloca()-support Keith Thompson <kst-u@mib.org> - 2019-10-06 12:58 -0700
                      Re: alloca()-support "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-10-06 13:16 -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 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-10-02 02:35 -0700
      Re: alloca()-support Anton Shepelev <anton.txt@gmail.com> - 2019-10-02 16:26 +0300
        Re: alloca()-support jadill33@gmail.com - 2019-10-02 08:00 -0700
          Re: alloca()-support Anton Shepelev <anton.txt@gmail.com> - 2019-10-03 02:38 +0300
            Re: alloca()-support jadill33@gmail.com - 2019-10-03 08:42 -0700
        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

Page 6 of 6 — ← Prev page 1 2 3 4 5 [6]

#146500

FromManfred <noname@add.invalid>
Date2019-10-01 17:45 +0200
Message-ID<qmvsaf$1ffu$1@gioia.aioe.org>
In reply to#146461
On 9/30/2019 8:01 PM, Soviet_Mario wrote:
> On 30/09/2019 19:20, Joe Pfeiffer wrote:
>> Soviet_Mario <SovietMario@CCCP.MIR> writes:
>>
>>> On 30/09/2019 14:02, Bonita Montero wrote:
>>>> I know alloca() neither is an official part of the C nor C++
>>>> program-
>>>> ming-language. But I use it for performance-reasons. Can anyone name
>>>> compilers that don't support alloca()?
>>>
>>>
>>> sorry, mine is not an answer but a related question
>>>
>>> Since when (if at any time) was variable size automatic array
>>> supported ?
>>>
>>> I mean a temporary array local to a function whose size becomes known
>>> only at runtime (seems to me a generalization of variadic functions,
>>> which, too, does not know at compile time how much stack space will
>>> consume).
>>>
>>> If implemented, It seems equivalent to alloca () ... is it there some
>>> limitation then in ORDER of automatic variable creations ?
>>
>> There is no such limitation on your C program.  The VLA can be first,
>> last, or in the middle.  And you can have more than one of them.
>>
>> Where in the activation record a compiler chooses to put it is, AFAIK,
>> not specified.
>>
> 
> 
> I have QT that does not supports them, but, if sb would be so kind to 
> copy a minimal asm generated code for some
> 
> int Funz (int A, int B)
> {
> int C = 3;
> int Buf [A];
> int D = 2;
> Buf [A-1] = B;
> return (A + B * D - C);
> }
> 
> int main (void)
> {
> return Funz (4, 3);
> }
> 
> I'd like to examine the assembler generated in order to figure out how 
> Buf (and D, beyond it apparently) are addressed
> 
> ah, if not to annoying, TURNING OFF most if not all optimizationz (maybe 
> the example is too minimal to be sort of resolved at compile time :\)
> 
> tnx in advance
> 

AFAIU this is a feature of the language and compiler, not of QT, so 
probably your limitation is not because you use QT per se, but instead 
because C++ does not have VLAs.

Trying to force VLAs via asm in C++ would probably open a can of worms 
not worth the benefit.
A more viable alternative could be having the code that needs VLAs 
implemented in C modules linked to C++, or switch to std::vector.
If it is directly coupled to QT itself, e.g. GUI handlers, then the 
performance gap of using std::vector is most probably neglectable.
(and, of course, there still is _alloca() if it is supported by the 
compiler)

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

#146529

From"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date2019-10-02 02:35 -0700
Message-ID<qn1r0n$b77$1@gioia.aioe.org>
In reply to#146432
On 9/30/2019 5:02 AM, Bonita Montero wrote:
> I know alloca() neither is an official part of the C nor C++ program-
> ming-language. But I use it for performance-reasons. Can anyone name
> compilers that don't support alloca()?

Fwiw, the last time I use alloca was to offset threads stacks, using a 
thread id, to get around the 64k aliasing problem on old Intel 
hyperthreaded processors. It was needed to get around false sharing wrt 
thread stacks! alloca was a simple convenience hack to get the damn job 
done. Iirc, it was mentioned in an Intel paper. Well, I have something 
even more hackish. The region allocator that can be stack based. It can 
be fed with memory reaped from alloca:

http://pastebin.com/raw/f37a23918

https://groups.google.com/forum/#!original/comp.lang.c/7oaJFWKVCTw/sSWYU9BUS_QJ

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

#146535

FromAnton Shepelev <anton.txt@gmail.com>
Date2019-10-02 16:26 +0300
Message-ID<20191002162609.52a3f122331a7c7dd7040fe6@gmail.com>
In reply to#146529
Chris M. Thomasson:

> Well, I have something even more hackish. The region
> allocator that can be stack based. It can be fed with
> memory reaped from alloca:
> http://pastebin.com/raw/f37a23918

I find it hard to comprehend because the code has no
comments and uses macros extensively.  Do I understand
aright that you have written, as it were, a secondary memory
manager that uses a C memory block instead of RAM and does
not support deallocation except by flushing the whole thing?

When is it more convenient than, say, local fixed arrays for
dynamic structures of limited size?

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

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

#146537

Fromjadill33@gmail.com
Date2019-10-02 08:00 -0700
Message-ID<9fa88375-81de-45bf-a471-2fdc8b3dc86a@googlegroups.com>
In reply to#146535
On Wednesday, October 2, 2019 at 9:26:18 AM UTC-4, Anton Shepelev wrote:
> Chris M. Thomasson:
> 
> > Well, I have something even more hackish. The region
> > allocator that can be stack based. It can be fed with
> > memory reaped from alloca:
> > http://pastebin.com/raw/f37a23918
> 
> I find it hard to comprehend because the code has no
> comments and uses macros extensively.  Do I understand
> aright that you have written, as it were, a secondary memory
> manager that uses a C memory block instead of RAM and does
> not support deallocation except by flushing the whole thing?
> 
> When is it more convenient than, say, local fixed arrays for
> dynamic structures of limited size?

Here is a snippet of some code I've played with of an algorithm that
uses small buffer optimization using region allocators.  The idea is to
trade space for speed by allocating stack space in your algorithm,
attempt to allocate from it and if it fails, switches to use malloc.
Of course with anything like this, you trade simplicity and additional
maintenance costs to try to get more performance, so YMMV.

\code snippet
int r_levenshtein( const char* s1, const char* s2 );
size_t small_buffer_optimization = 0;

struct string_pair
{
  char* lhs;
  char* rhs;
};

int main( void )
{
  int distance;
  char tmp_str[40];
  size_t idx;

  struct string_pair tests[] =
  {
    { "kitten",        "sitting" },
    { "gamble",        "gumbo" },
    { "accomodate",    "accommodate" },
    { "mispell",       "misspell" },
    { "pasttime",      "pastime" },
    { "barbecue",      "barbeque" },
    { "beleive",       "believe" },
    { "Saturday",      "Sunday" },
    { "levenshtein",   "meilenstein" },
    { "strawberry",    "raspberry" },
    { "null",          "" },
    { "",              "empty" },
    { "",              "" },
    { "identical",     "identical" },
  };

  printf( " -----------------------------------------------------\n" );
  printf( "|        LHS        |        RHS        | Levenshtein |\n" );
  printf( " -----------------------------------------------------\n" );
  for ( idx = 0; idx < c_sizeof_array (tests); ++idx )
  {
    distance = r_levenshtein( tests[idx].lhs, tests[idx].rhs );

    snprintf( tmp_str, sizeof (tmp_str), "\"%s\"", tests[idx].lhs );
    printf( "  %-17s", tests[idx].lhs ? tmp_str : "(null)" );

    snprintf( tmp_str, sizeof (tmp_str), "\"%s\"", tests[idx].rhs );
    printf( "   %-17s", tests[idx].rhs ? tmp_str : "(null)" );

    printf( "   %d\n", distance );
  }

  printf( "\n" );
  printf( "small buffer optimization count = %" PRIuSIZE "\n",
          small_buffer_optimization );

  return 0;
}

int r_levenshtein( const char* s1, const char* s2 )
{
  int distance;

  size_t m, n;
  int* proximity_matrix;

  struct c_region pm_region;
  unsigned char pm_workspace[sizeof (int) * 64];
  bool c_malloc_used = false;

  c_return_value_if_fail( s1 != NULL, -1 );
  c_return_value_if_fail( s2 != NULL, -1 );

  m = strlen( s1 );
  n = strlen( s2 );

  /* If one of the strings is empty "", the edit distance is equal to
     the length of the non-empty string. */
  if ( m == 0 || n == 0 ) {
    return m + n;
  }

  c_region_initialize( &pm_region, pm_workspace, sizeof pm_workspace );

  ++m;
  ++n;
  proximity_matrix = c_region_allocate( &pm_region,
                                        sizeof (int) * m * n,
                                        alignof (int) );
  if ( proximity_matrix == NULL )
  {
    proximity_matrix = c_malloc( sizeof (int) * m * n );
    c_malloc_used = true;
  }
  else {
    ++small_buffer_optimization;
  }

  if ( proximity_matrix )
  {
    gc_compute_levenshtein_matrix( proximity_matrix, m, n, s1, s2 );
    distance = proximity_matrix[m*n-1];

    if ( c_malloc_used ) {
      c_free( proximity_matrix );
    }
  }
  else {
    distance = -1;
  }

  return distance;
}
\endcode

Best regards,
John D.

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

#146540

FromAnton Shepelev <anton.txt@gmail.com>
Date2019-10-03 02:38 +0300
Message-ID<20191003023833.b8a5eaa935db4ea86a3356f0@gmail.com>
In reply to#146537
John D.:

> Here is a snippet of some code I've played with of an
> algorithm that uses small buffer optimization using region
> allocators.  The idea is to trade space for speed by
> allocating stack space in your algorithm, attempt to
> allocate from it and if it fails, switches to use malloc.
> Of course with anything like this, you trade simplicity
> and additional maintenance costs to try to get more
> performance, so YMMV.
> [...]

My mileage in that land is zero, but I should start with
something like

   int levenstein( int** buf, char* a, char* b );

where buf is a geometrically growing block allocated on the
heap.  If it is too small, the function shall realloc() it
by a constant factor or by len(a) * len(b), depending on
which is greater.  With this approach, the number of
reallocations is asymptotically zero.

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

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

#146553

Fromjadill33@gmail.com
Date2019-10-03 08:42 -0700
Message-ID<1a2c63f9-49c6-40b5-a795-6fee108caf45@googlegroups.com>
In reply to#146540
On Wednesday, October 2, 2019 at 7:38:41 PM UTC-4, Anton Shepelev wrote:
> John D.:
> 
> > Here is a snippet of some code I've played with of an
> > algorithm that uses small buffer optimization using region
> > allocators.  The idea is to trade space for speed by
> > allocating stack space in your algorithm, attempt to
> > allocate from it and if it fails, switches to use malloc.
> > Of course with anything like this, you trade simplicity
> > and additional maintenance costs to try to get more
> > performance, so YMMV.
> > [...]
> 
> My mileage in that land is zero, but I should start with
> something like
> 
>    int levenstein( int** buf, char* a, char* b );
> 
> where buf is a geometrically growing block allocated on the
> heap.  If it is too small, the function shall realloc() it
> by a constant factor or by len(a) * len(b), depending on
> which is greater.  With this approach, the number of
> reallocations is asymptotically zero.

Sure, if you're willing to maintain that heap allocation for the entire
lifetime of any task that needs use of a levenshtein call.

I don't particularly like holding onto a global memory workspace between
independent function calls because managing the lifetime of that memory
can become an issue, e.g. you have a bunch of dictionary comparisons that
use small memory but every once in a while a large one comes in.  How
long do you want to maintain the memory overhead?

It's the same issue with regions where one object hangs around, so the
entire region is maintained even though the utilization of that memory is
low.  Your option is a valid one to consider though if the use case fits.
For the most part, I responded cause I feel its a viable alternative to
using alloca.

Best regards,
John D.

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

#146538

From"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date2019-10-02 12:33 -0700
Message-ID<qn2u1n$1m5p$1@gioia.aioe.org>
In reply to#146535
On 10/2/2019 6:26 AM, Anton Shepelev wrote:
> Chris M. Thomasson:
> 
>> Well, I have something even more hackish. The region
>> allocator that can be stack based. It can be fed with
>> memory reaped from alloca:
>> http://pastebin.com/raw/f37a23918
> 
> I find it hard to comprehend because the code has no
> comments and uses macros extensively.  Do I understand
> aright that you have written, as it were, a secondary memory
> manager that uses a C memory block instead of RAM and does
> not support deallocation except by flushing the whole thing?

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

> 
> When is it more convenient than, say, local fixed arrays for
> dynamic structures of limited size?
>

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

#146539

FromAnton Shepelev <anton.txt@gmail.com>
Date2019-10-03 01:47 +0300
Message-ID<20191003014754.39250b808212c3b7c3a755b3@gmail.com>
In reply to#146538
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]

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

#146608

From"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date2019-10-05 14:08 -0700
Message-ID<qnb0nj$odf$1@gioia.aioe.org>
In reply to#146539
On 10/2/2019 3:47 PM, Anton Shepelev wrote:
> 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
[...]

I was using it for systems that did not have malloc. Here is a example 
usage:

This region allocator does not force all allocations to be aligned up to 
a so-called maximum alignment like `malloc' and friends are required to 
do. For instance, allocations for a single char will not be forced to 
waste the extra alignment space. This can have benefits in space 
constrained environments (e.g., embedded devices). Also, its static in 
nature and can be fed with a buffer residing on the stack. There are no 
underlying calls to `malloc'. This can be useful in free standing 
environments that do not support heap allocation. One other thing. Its a 
pure region allocator which means you do not need to free individual 
objects. You can free the entire region. This is more efficient than 
calling `malloc()/free()' for each object. For instance, you can destroy 
all the nodes in a linked list just by freeing the region(s) in which 
the nodes were allocated from. There is no need to traverse the list to 
free its nodes. Its a sort of "manual" garbage collection... ;^)


You can use it like:
_________________________________________________________________
#include <ralloc.h>


struct foo {
   struct foo* next;
};


#include <stdio.h>


void crunch() {
   char local_buffer[1024];
   struct region local_region;
   struct foo* head1 = NULL;
   struct foo* head2 = NULL;
   size_t i, r;

   rinit(&local_region, local_buffer, sizeof(local_buffer));

   for (r = 0; r < 1024; ++r) {
     size_t c = 0;

     for (i = 0; i < 64; ++i) {
       struct foo* foo = ralloct(&local_region, 2, struct foo);
       if (foo) {
         foo->next = head1;
         head1 = foo;
         ++foo;
         foo->next = head2;
         head2 = foo;
         c += 2;
       }
     }

     while (head1) {
       head1 = head1->next;
       --c;
     }

     while (head2) {
       head2 = head2->next;
       --c;
     }

     assert(! c);

     rflush(&local_region);
   }
}


int main(void) {
   crunch();
   crunch();
   crunch();
   return 0;
}
_________________________________________________________________

[toc] | [prev] | [standalone]

Page 6 of 6 — ← Prev page 1 2 3 4 5 [6]

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

csiph-web