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

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

lalloc() -- local stack allocation

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

Contents

  lalloc() -- local stack allocation "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2015-07-12 02:23 -0700
    Re: lalloc() -- local stack allocation Johannes Bauer <dfnsonfsduifb@gmx.de> - 2015-07-12 11:48 +0200
      Re: lalloc() -- local stack allocation Johannes Bauer <dfnsonfsduifb@gmx.de> - 2015-07-12 11:48 +0200
    Re: lalloc() -- local stack allocation Philipp Klaus Krause <pkk@spth.de> - 2015-07-12 13:33 +0200
    Re: lalloc() -- local stack allocation Robert Wessel <robertwessel2@yahoo.com> - 2015-07-12 06:54 -0500
    Re: lalloc() -- local stack allocation Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-12 06:17 -0700
      Re: lalloc() -- local stack allocation Johannes Bauer <dfnsonfsduifb@gmx.de> - 2015-07-12 16:47 +0200
        Re: lalloc() -- local stack allocation Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-12 11:12 -0700
        Re: lalloc() -- local stack allocation supercat@casperkitty.com - 2015-09-08 11:53 -0700
          Re: lalloc() -- local stack allocation "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2015-09-08 12:16 -0700
            Re: lalloc() -- local stack allocation supercat@casperkitty.com - 2015-09-08 15:46 -0700
              Re: lalloc() -- local stack allocation "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2015-09-08 16:12 -0700
          Re: lalloc() -- local stack allocation Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-08 20:32 +0100
          Re: lalloc() -- local stack allocation jadill33@gmail.com - 2015-09-08 13:25 -0700
    Re: lalloc() -- local stack allocation "Chris M. Thomasson" <nospam@nospam.nospam> - 2015-07-12 10:17 -0700
    Re: lalloc() -- local stack allocation gordonb.zziiu@burditt.org (Gordon Burditt) - 2015-07-27 22:41 -0500
      Re: lalloc() -- local stack allocation Keith Thompson <kst-u@mib.org> - 2015-07-28 08:35 -0700

#65394 — lalloc() -- local stack allocation

Does C define a type of lalloc() function for local / stack allocation?

On x86 (which has an expand-down stack):

    void reverse(char* data, int n)
    {
        int i;
        char* p = lalloc(n);

        for (i=0; i < n; i++)
            p[i] = data[n - i - 1];

        memcpy(data, p, n);
    }

-----
Assembly operation:

    // p = lalloc(n);
    mov rax, n
    // [alignment fixup applied]
    mov _lalloc_size_p, rax
    sub rsp, rax
    mov p, rsp
// [I can't remember off the top of my head if
//  on x86 I need to add 8 to p here or not]
    // p was allocated in local / stack space

    // Function code goes here

    // automatic lfree(p); executed at return
    add rsp, _lalloc_size_p 
    ret

Best regards,
Rick C. Hodgin

[toc] | [next] | [standalone]

#65396

On 12.07.2015 11:23, Rick C. Hodgin wrote:
> Does C define a type of lalloc() function for local / stack allocation?

alloca?

Cheers,
Johannes


-- 
>> Wo hattest Du das Beben nochmal GENAU vorhergesagt?
> Zumindest nicht öffentlich!
Ah, der neueste und bis heute genialste Streich unsere großen
Kosmologen: Die Geheim-Vorhersage.
 - Karl Kaos über Rüdiger Thomas in dsa <hidbv3$om2$1@speranza.aioe.org>

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

#65397

On 12.07.2015 11:48, Johannes Bauer wrote:
> On 12.07.2015 11:23, Rick C. Hodgin wrote:
>> Does C define a type of lalloc() function for local / stack allocation?
> 
> alloca?

Thinking about this, probably not C, but OS specific.

Cheers,
Johannes


-- 
>> Wo hattest Du das Beben nochmal GENAU vorhergesagt?
> Zumindest nicht öffentlich!
Ah, der neueste und bis heute genialste Streich unsere großen
Kosmologen: Die Geheim-Vorhersage.
 - Karl Kaos über Rüdiger Thomas in dsa <hidbv3$om2$1@speranza.aioe.org>

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

#65404

On 12.07.2015 11:23, Rick C. Hodgin wrote:
> Does C define a type of lalloc() function for local / stack allocation?
> 
> On x86 (which has an expand-down stack):
> 
>     void reverse(char* data, int n)
>     {
>         int i;
>         char* p = lalloc(n);

char p[n];

> 
>         for (i=0; i < n; i++)
>             p[i] = data[n - i - 1];
> 
>         memcpy(data, p, n);
>     }
> 

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

#65405

On Sun, 12 Jul 2015 02:23:58 -0700 (PDT), "Rick C. Hodgin"
<rick.c.hodgin@gmail.com> wrote:

>Does C define a type of lalloc() function for local / stack allocation?
>
>On x86 (which has an expand-down stack):
>
>    void reverse(char* data, int n)
>    {
>        int i;
>        char* p = lalloc(n);
>
>        for (i=0; i < n; i++)
>            p[i] = data[n - i - 1];
>
>        memcpy(data, p, n);
>    }
>
>-----
>Assembly operation:
>
>    // p = lalloc(n);
>    mov rax, n
>    // [alignment fixup applied]
>    mov _lalloc_size_p, rax
>    sub rsp, rax
>    mov p, rsp
>// [I can't remember off the top of my head if
>//  on x86 I need to add 8 to p here or not]
>    // p was allocated in local / stack space
>
>    // Function code goes here
>
>    // automatic lfree(p); executed at return
>    add rsp, _lalloc_size_p 
>    ret


alloca(), while non-standard, is fairly commonly available.  Or in C99
and later, VLAs might be available (note that VLA support is optional
in C11).

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

#65408

On Sunday, July 12, 2015 at 10:24:10 AM UTC+1, Rick C. Hodgin wrote:
> Does C define a type of lalloc() function for local / stack allocation?
> 
You can easily write your own.
It doesn't allocate on the function stack, but on its own private stack
that is a file scope global. You also need lfree(), and to be rigorous
in balancing allocations and frees. 
Most functions that need dynamic memory for workspace rather than
for creating graphs lend themselves very easily to lalloc(),
lfree(), and the operations resolve to a few machine instructions.

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

#65411

On 12.07.2015 15:17, Malcolm McLean wrote:
> On Sunday, July 12, 2015 at 10:24:10 AM UTC+1, Rick C. Hodgin wrote:
>> Does C define a type of lalloc() function for local / stack allocation?
>>
> You can easily write your own.
> It doesn't allocate on the function stack, but on its own private stack
> that is a file scope global. You also need lfree(), and to be rigorous
> in balancing allocations and frees.

Which completely defies the purpose of using the system stack. Because
there you don't have to free because free is implicit at the end of a
function scope when the stackframe is cleared.

> Most functions that need dynamic memory for workspace rather than
> for creating graphs lend themselves very easily to lalloc(),
> lfree(), and the operations resolve to a few machine instructions.

A few machine instructions in userspace plus a few thousand instructions
in kernel space where the actual memory is allocated in case there's a
pagefault. No matter if on the stack or on the heap, there needs to be
code somewhere which does the MMU programming.

Cheers,
Johannes

-- 
>> Wo hattest Du das Beben nochmal GENAU vorhergesagt?
> Zumindest nicht öffentlich!
Ah, der neueste und bis heute genialste Streich unsere großen
Kosmologen: Die Geheim-Vorhersage.
 - Karl Kaos über Rüdiger Thomas in dsa <hidbv3$om2$1@speranza.aioe.org>

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

#65431

On Sunday, July 12, 2015 at 3:47:45 PM UTC+1, Johannes Bauer wrote:
> On 12.07.2015 15:17, Malcolm McLean wrote:
> > On Sunday, July 12, 2015 at 10:24:10 AM UTC+1, Rick C. Hodgin wrote:
> >> Does C define a type of lalloc() function for local / stack allocation?
> >>
> > You can easily write your own.
> > It doesn't allocate on the function stack, but on its own private stack
> > that is a file scope global. You also need lfree(), and to be rigorous
> > in balancing allocations and frees.
> 
> Which completely defies the purpose of using the system stack. Because
> there you don't have to free because free is implicit at the end of a
> function scope when the stackframe is cleared.
> 
It's convenient  not to have to write pop_stack() before return,
but that's just a detail. The system stack is handy because it's
already available, and because it's likely to be in the cache.
The latter is a bit of a two edged sword if you're allocating 
large objects, because you can damage the cache coherence of the
stack by over-filling it.

> > Most functions that need dynamic memory for workspace rather than
> > for creating graphs lend themselves very easily to lalloc(),
> > lfree(), and the operations resolve to a few machine instructions.
> 
> A few machine instructions in userspace plus a few thousand instructions
> in kernel space where the actual memory is allocated in case there's a
> pagefault. No matter if on the stack or on the heap, there needs to be
> code somewhere which does the MMU programming.
> 
I don't believe that. The lalloc() stack is simply a global buffer,
accessing it is no different to write access to any global object via pointer:offset where the system can't determine that the offset 
variable is bounded within the page at compile time.
You can also easily implement your own stack overflow protection.
It's a single comparison.

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

#69952

On Sunday, July 12, 2015 at 9:47:45 AM UTC-5, Johannes Bauer wrote:
> Which completely defies the purpose of using the system stack. Because
> there you don't have to free because free is implicit at the end of a
> function scope when the stackframe is cleared.

A well-designed stack-allocate mechanism would have included a stack-free
function and required that code must use it to free objects in the reverse
order of allocation.  Such requirements would have meant that every platform
that can run a reasonable dialect of C could support code using such
functions merely by chaining them to "malloc" and "free", but platforms which
can benefit from distinguishing between temporary and persistent objects
could make use of that knowledge.  Even platforms would require that such
objects be allocated on the heap rather than the CPU stack may be able to
benefit from having separate functions for temporary allocations (e.g. by
maintaining a pre-allocated area for such allocations which is separate from
the main heap).

The lack of a "free" function is bad in a number of ways:

1. It's incompatible with a pattern of "read size, allocate array, read and
   process data, release array, read next size, etc." since memory that gets
   stack-allocated within a method can't be freed.

2. On many platforms it makes it impossible to use a compatibility library
   to allow code which is written to use alloca() to be run on a platforms
   which doesn't include explicit support for it.

3. Unless a compiler adds some rather sophisticated alloca-related support,
   it precludes the possibility of alloca() using a heap allocation rather
   than a stack allocation in cases where stack memory is scarce.

Having a function which allocates memory take care of releasing it isn't
hard, and while I could see semantic benefit to having a compiler squawk if
stack-allocate/stack-free calls aren't balanced, I don't see any upside to
the implicit freeing of alloca() memory which are even remotely close to
outweighing the drawbacks.

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

#69954

On Tuesday, September 8, 2015 at 2:54:18 PM UTC-4, supe...@casperkitty.com wrote:
> On Sunday, July 12, 2015 at 9:47:45 AM UTC-5, Johannes Bauer wrote:
> > Which completely defies the purpose of using the system stack. Because
> > there you don't have to free because free is implicit at the end of a
> > function scope when the stackframe is cleared.
> 
> A well-designed stack-allocate mechanism would have included a stack-free
> function

Agree.

> and required that code must use it to free objects in the reverse
> order of allocation.

Disagree.  Any self-respecting implementation of an algorithm to
allocate data on the stack would have to have its own type of
local stack walk algorithm which allows it to have previously
allocated and de-allocated "holes" which exist, which can be
re-used if needed.

> Such requirements would have meant that every platform
> that can run a reasonable dialect of C could support code using such
> functions merely by chaining them to "malloc" and "free", but platforms which
> can benefit from distinguishing between temporary and persistent objects
> could make use of that knowledge.

We're talking about C here ... what persistent objects are there that
aren't explicitly created with an alloc() function?  And it would be
a given on lalloc() that they are not persistent, but only have a
lifetime of the function call.

> Even platforms would require that such
> objects be allocated on the heap rather than the CPU stack may be able to
> benefit from having separate functions for temporary allocations (e.g. by
> maintaining a pre-allocated area for such allocations which is separate from
> the main heap).

This is done today with local variables.

> The lack of a "free" function is bad in a number of ways:
> 
> 1. It's incompatible with a pattern of "read size, allocate array, read and
>    process data, release array, read next size, etc." since memory that gets
>    stack-allocated within a method can't be freed.

An implementation could allow for local pointers used for allocation to
go through a lalloc_squeeze() or lalloc_crunch() function which allows
out-of-order holes created by lfree() calls to be squeezed together,
thereby, at the expense of some performance, reclaim that memory.  The
use of local pointers would allow those values to be known using a type
of lalloc(&myptr, size) rather than myptr = lalloc(size).  But I still
argue that it's not necessary.  The purpose of lalloc() would be for
very high speed allocation of limited size for limited duration, and
no such lfree() function should be required.  If you have such a need,
switch to malloc().

> 2. On many platforms it makes it impossible to use a compatibility library
>    to allow code which is written to use alloca() to be run on a platforms
>    which doesn't include explicit support for it.

This type of lalloc() function would be a new feature distinct from
alloca().  It would not break alloca(), but would behave differently.

> 3. Unless a compiler adds some rather sophisticated alloca-related support,
>    it precludes the possibility of alloca() using a heap allocation rather
>    than a stack allocation in cases where stack memory is scarce.

The purpose of lalloc() would be to always use the stack on systems
where the stack is available.  Where it's not, it's simply a wrapper
to malloc(), one which then (on those systems where the stack is not
available) performs the automatic cleanup when the function exits.

> Having a function which allocates memory take care of releasing it isn't
> hard, and while I could see semantic benefit to having a compiler squawk if
> stack-allocate/stack-free calls aren't balanced, I don't see any upside to
> the implicit freeing of alloca() memory which are even remotely close to
> outweighing the drawbacks.

The stack grows as functions are entered, providing a relative memory
for that instance of the function call without additional overhead
because the machine provides for it in hardware.  To note have this
type of lalloc() ability, because it is such a widely available feature
on hardware, seems a failure on behalf of the C standard maintainers.

These are my thoughts on this subject.  I do plan to add lalloc() to
RDC, and I think it is a requisite function, one of the true language
fundamentals.

Best regards,
Rick C. Hodgin

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

#69990

On Tuesday, September 8, 2015 at 2:16:49 PM UTC-5, Rick C. Hodgin wrote:
> Disagree.  Any self-respecting implementation of an algorithm to
> allocate data on the stack would have to have its own type of
> local stack walk algorithm which allows it to have previously
> allocated and de-allocated "holes" which exist, which can be
> re-used if needed.

If you want something that can reuse holes, use the heap.  The benefit to
using the stack-based allocation is that on many implementations allocation
will require an add, compare, and store, and deallocation may require either
an add and a store, or just a store.

>>
> We're talking about C here ... what persistent objects are there that
> aren't explicitly created with an alloc() function?  And it would be
> a given on lalloc() that they are not persistent, but only have a
> lifetime of the function call.
<<

Some platforms may have a stack which is too small for a stack-alloc
function to do much good, and even on platforms with a decent-sized stack,
a version that uses a temporary-storage pool stored on the heap could be
safer.  A good API design should free the application from having to worry
about how the temporary-allocation mechanism is handled.

>>
> > Even platforms would require that such
> > objects be allocated on the heap rather than the CPU stack may be able to
> > benefit from having separate functions for temporary allocations (e.g. by
> > maintaining a pre-allocated area for such allocations which is separate from
> > the main heap).
> 
> This is done today with local variables.
<<

Except that the memory is allocated when a function starts.  I was thinking
in terms of a malloc'ed allocation which could be dished out piecemeal; if a request is made for more memory than was allocated for the purpose, the
system could create an allocation twice as big and have it hold a reference
to the old one.  Once the last object in the any allocation other than the
newest one is released, the allocation would likewise be released.

> > 1. It's incompatible with a pattern of "read size, allocate array, read and
> >    process data, release array, read next size, etc." since memory that gets
> >    stack-allocated within a method can't be freed.
> 
> An implementation could allow for local pointers used for allocation to
> go through a lalloc_squeeze() or lalloc_crunch() function which allows
> out-of-order holes created by lfree() calls to be squeezed together,
> thereby, at the expense of some performance, reclaim that memory.  The
> use of local pointers would allow those values to be known using a type
> of lalloc(&myptr, size) rather than myptr = lalloc(size).  But I still
> argue that it's not necessary.  The purpose of lalloc() would be for
> very high speed allocation of limited size for limited duration, and
> no such lfree() function should be required.  If you have such a need,
> switch to malloc().

If the memory is used in LIFO fashion, there won't be any holes.

> > 2. On many platforms it makes it impossible to use a compatibility library
> >    to allow code which is written to use alloca() to be run on a platforms
> >    which doesn't include explicit support for it.
> 
> This type of lalloc() function would be a new feature distinct from
> alloca().  It would not break alloca(), but would behave differently.

True, though I would suggest that alloca() should be deprecated in favor of
the form with explicit release, since some platforms would be able to support
the latter but not the former.

> > 3. Unless a compiler adds some rather sophisticated alloca-related support,
> >    it precludes the possibility of alloca() using a heap allocation rather
> >    than a stack allocation in cases where stack memory is scarce.
> 
> The purpose of lalloc() would be to always use the stack on systems
> where the stack is available.  Where it's not, it's simply a wrapper
> to malloc(), one which then (on those systems where the stack is not
> available) performs the automatic cleanup when the function exits.

The problem is that such automatic-cleanup semantics can only be implemented
with compiler support; there's no way to emulate them via library or macro.

> The stack grows as functions are entered, providing a relative memory
> for that instance of the function call without additional overhead
> because the machine provides for it in hardware.  To note have this
> type of lalloc() ability, because it is such a widely available feature
> on hardware, seems a failure on behalf of the C standard maintainers.

In what way would requiring that code explicitly free objects detract from
that?

If stalloc/stfree methods were implemented as I'd like to see them, it would
be possible to write a file "stalloc.h" which, if added to any compiler, would
make it comply with the standard as I'd like to see it; compiler vendors would
be encouraged to provide functions to support the indicated functionality more
efficiently, but programmers could use the new functions without limiting what
compilers could use their code.

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

#69996

On Tuesday, September 8, 2015 at 6:46:10 PM UTC-4, supe...@casperkitty.com wrote:
> On Tuesday, September 8, 2015 at 2:16:49 PM UTC-5, Rick C. Hodgin wrote:
> > The stack grows as functions are entered, providing a relative memory
> > for that instance of the function call without additional overhead
> > because the machine provides for it in hardware.  To note have this
> > type of lalloc() ability, because it is such a widely available feature
> > on hardware, seems a failure on behalf of the C standard maintainers.
> 
> In what way would requiring that code explicitly free objects detract from
> that?

Which branches were taken which allocated memory?  And how do you unwind
from that condition manually?  It's possible ... but problematic and prone
to errors.

> If stalloc/stfree methods were implemented as I'd like to see them, it would
> be possible to write a file "stalloc.h" which, if added to any compiler, would
> make it comply with the standard as I'd like to see it; compiler vendors would
> be encouraged to provide functions to support the indicated functionality more
> efficiently, but programmers could use the new functions without limiting what
> compilers could use their code.

It's doable.  Having the ability to lalloc() and then just ignore it upon
exit would be more desirable in my book.  No keeping track of how much was
allocated, or how much needed to be de-allocated, just high speed use for
small quantities of memory that don't need to be on the global heap.  It
would be all-around faster (in allocation, but also in use because the
memory on the stack would likely be in the fastest cache as it is constantly
being used), and cleaner (no epilogue code at all).

Best regards,
Rick C. Hodgin

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

#69959

supercat@casperkitty.com writes:

> On Sunday, July 12, 2015 at 9:47:45 AM UTC-5, Johannes Bauer wrote:
>> Which completely defies the purpose of using the system stack. Because
>> there you don't have to free because free is implicit at the end of a
>> function scope when the stackframe is cleared.
>
> A well-designed stack-allocate mechanism would have included a stack-free
> function and required that code must use it to free objects in the reverse
> order of allocation.  Such requirements would have meant that every platform
> that can run a reasonable dialect of C could support code using such
> functions merely by chaining them to "malloc" and "free", but platforms which
> can benefit from distinguishing between temporary and persistent objects
> could make use of that knowledge.  Even platforms would require that such
> objects be allocated on the heap rather than the CPU stack may be able to
> benefit from having separate functions for temporary allocations (e.g. by
> maintaining a pre-allocated area for such allocations which is separate from
> the main heap).
>
> The lack of a "free" function is bad in a number of ways:
>
> 1. It's incompatible with a pattern of "read size, allocate array, read and
>    process data, release array, read next size, etc." since memory that gets
>    stack-allocated within a method can't be freed.
>
> 2. On many platforms it makes it impossible to use a compatibility library
>    to allow code which is written to use alloca() to be run on a platforms
>    which doesn't include explicit support for it.
>
> 3. Unless a compiler adds some rather sophisticated alloca-related support,
>    it precludes the possibility of alloca() using a heap allocation rather
>    than a stack allocation in cases where stack memory is scarce.
>
> Having a function which allocates memory take care of releasing it isn't
> hard, and while I could see semantic benefit to having a compiler squawk if
> stack-allocate/stack-free calls aren't balanced, I don't see any upside to
> the implicit freeing of alloca() memory which are even remotely close to
> outweighing the drawbacks.

I'm not good at assessing advantages and drawbacks, but you can always
make yourself use such a language (in fact I have done so, knowing that
alloca is fast on some target systems and simply absent in others).
I.e. you write salloc and sfree which are either malloc and free or are
alloca and an empty stub.  It's not the same as having mandated features
of course, but I suspect its the kind of thing that is considered by
standards committees.  (And if I understand the intent, you don't get
number 3 as that's on the implementation side.)

-- 
Ben.

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

#69970

On Tuesday, September 8, 2015 at 2:54:18 PM UTC-4, supe...@casperkitty.com wrote:
> On Sunday, July 12, 2015 at 9:47:45 AM UTC-5, Johannes Bauer wrote:
> > Which completely defies the purpose of using the system stack. Because
> > there you don't have to free because free is implicit at the end of a
> > function scope when the stackframe is cleared.
> 
> A well-designed stack-allocate mechanism would have included a stack-free
> function and required that code must use it to free objects in the reverse
> order of allocation.  Such requirements would have meant that every platform
> that can run a reasonable dialect of C could support code using such
> functions merely by chaining them to "malloc" and "free", but platforms which
> can benefit from distinguishing between temporary and persistent objects
> could make use of that knowledge.  Even platforms would require that such
> objects be allocated on the heap rather than the CPU stack may be able to
> benefit from having separate functions for temporary allocations (e.g. by
> maintaining a pre-allocated area for such allocations which is separate from
> the main heap).
> 
> The lack of a "free" function is bad in a number of ways:
> 
> 1. It's incompatible with a pattern of "read size, allocate array, read and
>    process data, release array, read next size, etc." since memory that gets
>    stack-allocated within a method can't be freed.
> 
> 2. On many platforms it makes it impossible to use a compatibility library
>    to allow code which is written to use alloca() to be run on a platforms
>    which doesn't include explicit support for it.
> 
> 3. Unless a compiler adds some rather sophisticated alloca-related support,
>    it precludes the possibility of alloca() using a heap allocation rather
>    than a stack allocation in cases where stack memory is scarce.
> 
> Having a function which allocates memory take care of releasing it isn't
> hard, and while I could see semantic benefit to having a compiler squawk if
> stack-allocate/stack-free calls aren't balanced, I don't see any upside to
> the implicit freeing of alloca() memory which are even remotely close to
> outweighing the drawbacks.

It is possible to declare a buffer within a local scope and do your own
memory management without resorting to alloca.  The only tricky part in
creating your own region allocator is getting the alignment constraints
correct, but I can't see reason why you couldn't do something like this:

\code snippet
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 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 = malloc( sizeof (int) * m * n );
    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 ( malloc_used ) {
      free( proximity_matrix );
    }
  }
  else {
    distance = -1;
  }

  return distance;
}
\endcode

I snipped this from some test code where I was experimenting with my
region allocator.  It sacrifices the speed of alloca, but has the
capability to "rewind" the region pointer to reclaim memory, and you
still get auto cleanup for smaller string comparisons.

There was a thread a (long) while ago where Chris Thomasson was doing
some region allocation stuff that may be of interest.

Best regards,
John D.

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

#65425

> "Rick C. Hodgin"  wrote in message 
> news:e9abe69a-2532-44f3-be7b-aaa236783cfb@googlegroups.com...
> Does C define a type of lalloc() function for local / stack allocation?
> On x86 (which has an expand-down stack):

[...]

No. However, and FWIW, here is a "hack" at a region allocator I wrote a 
while
back that can be fed with a buffer on the stack:

https://groups.google.com/d/msg/comp.lang.C/7oaJFWKVCTw/sSWYU9BUS_QJ

http://pastebin.com/f37a23918

Unfortunately, it uses some non-portable trickery wrt alignment...

Yikes!

;^o


Also, VLA's might be of use to you but I believe they are optional. 

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

#66471

> Does C define a type of lalloc() function for local / stack allocation?

No.

It sounds like you are talking about the GNU alloca() function.
I encountered it long before C11's optional run-time-dimensioned
arrays.

1.  You can trivially define alloca(x) to call malloc(x).  Ignore
the memory leaks, full speed ahead.  You really get no advantages
from this.

2.  alloca() is really intended to use the stack pointer (yes, we
know some implementations don't have one), and automatically free
allocated memory on return of the function in which it is invoked.
You lose a lot of the speed advantage if you insist that alloca()
return NULL on stack overflow.

It's supposed to work to allocate memory inside a loop, so you have
to keep track of how much memory was allocated, or save and restore
the stack pointer at function entry and exit.

It is pretty much impossible to implement an alloca() nontrivially
that works without compiler special treatment of the function.  (If
you are writing your own compiler, that's not a problem.  If you
are trying to retrofit it to an existing compiler, even if you have
source code, it may not be so easy.) A naive compiler will badly
mis-generate code for a function call where the arguments each call
alloca() and the number of arguments well exceeds the square of the
number of (temporary) registers used in passing arguments.  The
stack adjustments for alloca() and the stack adjustments for pushing
arguments on the stack for the call are going to get intermixed.

	sscanf(inputstring, 
		formatstring, 
		alloca(sizeof(int)),
		alloca(sizeof(int)),
		alloca(sizeof(int)),
		alloca(sizeof(int)),
		alloca(sizeof(int)),
...
		alloca(sizeof(double)),
		alloca(sizeof(double)),
		alloca(sizeof(double)),
		alloca(sizeof(double)),
...
		alloca(sizeof(long long)),
		alloca(sizeof(long long)),
		alloca(sizeof(long long)),
		alloca(sizeof(long long)),
		alloca(sizeof(long long)),
		alloca(sizeof(long long)),
		alloca(sizeof(long long)),
		alloca(sizeof(long long)),
		alloca(sizeof(long long))
	)

What is worse, when I presented such a problem, the pro-alloca
camp just said "Well, don't do that", but they couldn't describe the
circumstances I would have to avoid.  A compiler which allocated
and de-allocated variables local to an inner block of a function
at block entry and exit was a potential problem.  As I recall, the
best I could come up with was:

	alloca() may be used in a statement of the following form
	in the outermost block of a function (and it's not guaranteed
	to work anywhere else, like in a loop or block with local variables):
	<pointer variable> = alloca(integer constant expression or integer variable);
	double *z;
	size_t siz;
	int	num = 54;

	z = alloca(sizeof(double));	/* OK */
	z = alloca(num*sizeof(double))	/* *NOT OK* */

	siz = num*sizeof(double); z = alloca(siz);	/* OK */

on a system where (a) the compiler does not treat alloca() specially, or
(b) the compiler treats alloca() specially to perform stack adjustments, but
takes no care whatever to check that it is not in the middle of adjusting
the stack for other purposes (e.g. pushing arguments, or allocating
local variables for inner blocks).


I recall an attempt at an implementation on a 68000 processor.  It
ended up working reasonably for some software that we were trying
to get to work, but certainly not for all cases.  Because of the
way arguments were addressed (stack-pointer-relative, not
stack-frame-pointer relative), it had to allocate 48 bytes (a
compromise value.  Worst case it could need megabytes.) extra per
call to alloca().

A slight improvement on this would read and disassemble the code
of its caller (to figure out how many registers were being
saved/restored).  This sometimes malfunctioned if the compiler did
something clever that the writers of the code hadn't run into yet.

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

#66497

gordonb.zziiu@burditt.org (Gordon Burditt) writes:
> "Rick C. Hodgin" <rick.c.hodgin@gmail.com> writes:
>> Does C define a type of lalloc() function for local / stack allocation?
>
> No.
>
> It sounds like you are talking about the GNU alloca() function.
> I encountered it long before C11's optional run-time-dimensioned
> arrays.

(I re-added an attribution line.)

alloca() is not specific to GNU.

Variable-length arrays were introduced in C99.  C11 made them optional.

[...]

> It's supposed to work to allocate memory inside a loop, so you have
> to keep track of how much memory was allocated, or save and restore
> the stack pointer at function entry and exit.

Does "you" here refer to the compiler? The programmer doesn't have to
keep track of any of this (other than to avoid allocating too much
memory).

> It is pretty much impossible to implement an alloca() nontrivially
> that works without compiler special treatment of the function.  (If
> you are writing your own compiler, that's not a problem.  If you
> are trying to retrofit it to an existing compiler, even if you have
> source code, it may not be so easy.) A naive compiler will badly
> mis-generate code for a function call where the arguments each call
> alloca() and the number of arguments well exceeds the square of the
> number of (temporary) registers used in passing arguments.  The
> stack adjustments for alloca() and the stack adjustments for pushing
> arguments on the stack for the call are going to get intermixed.

The Linux alloca(3) man page says:

    On many systems alloca() cannot be used inside the list of
    arguments of a function call, because the  stack  space
    reserved  by alloca() would appear on the stack in the middle
    of the space for the function arguments.

(It also says that there's no check for stack overflow; again, the
standard would describe this as undefined behavior.)

> What is worse, when I presented such a problem, the pro-alloca
> camp just said "Well, don't do that", but they couldn't describe the
> circumstances I would have to avoid.

A function argument should not include a call to alloca().

>                                       A compiler which allocated
> and de-allocated variables local to an inner block of a function
> at block entry and exit was a potential problem.

I've never heard of an implementation that would have problems calling
alloca() in an inner block, and there's no mention of any such problem
in the Linux man page.  Do you know of a specific example?

As always, I do not grant permission to quote this article without a
proper attribution line.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [standalone]

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

csiph-web