Passing variable-size data between trampolines 
Author Message
 Passing variable-size data between trampolines

Hello.

Is there any remotely portable way of passing variable-size data between
{*filter*}oline calls _without_ using heap (for efficiency) or globals (for
re-entrancy)?

So this is the situation: a {*filter*}oline, T, is a function that takes a
pointer to an array of N arguments. It either returns a value, _or_ it
returns a pointer to another {*filter*}oline, U, and a pointer to M arguments
to that.

When a {*filter*}oline is called, if it returns a plain value, we pass it on
and are done with it. But if it returns a new {*filter*}oline and arguments
to that, we call the new one, etcetera until we finally get a plain value.

So this is basically a way to do tail recursion in constant space in C.

Anyway, the question is: where should T store the M arguments that it
calculates? While T is running, the M arguments are most likely
somewhere in automatic memory in T's block. Somehow that information
should be passed to the calling function (which is the wrapper that does
the iteration described in the third paragraph), which then passes it on
to the {*filter*}oline U.

So how can we do this? One option would be to have a static store of
sufficient length. The M arguments are written there, and then the
wrapper would copy them to its own automatic space (well, stack, in
practice), and then pass to U a pointer to the newly allocated automatic
array.

However, using globals is not thread-safe, so I kind of dislike this
choice, although it would probably be most efficient. If we didn't care
about any sort of re-entrancy(ie if we couldn't nest {*filter*}oline calls),
then there wouldn't even be need to copy the data out of the global
array.

The second option is simple: T allocates an array of sufficient size
from heap, and returns a pointer to that. Then the wrapper either copies
the data to automatic space and frees the array (unless we have GC), or
just passes on the heap pointer until {*filter*}oline U returns.

Again I'm not really satisfied with this idea. Allocating heap takes a
while, and it does seem kind of overkill, especially when we are going
to free the very same memory very soon.

The third way to do this would be for the wrapper to have a local array
that could contain the maximum possible number of arguments. Then
{*filter*}oline T just writes the M arguments into that array, and U reads
them from there.

This would work, but the problem is that if we have very deep nested
{*filter*}oline calls, and most {*filter*}olines only take a couple of arguments
but the maximum number is very high, then the stack (or equivalent) will
grow very large, and will have lots of empty space (all those wrappers
with their maxlen arrays that are mostly unused). Furthermore, I don't
like the idea of imposing any fixed maximum limit for the number of
arguments. This is a problem also with the first option.

So what would I _like_ to do? I'd like to have {*filter*}oline T allocate the
array of M arguments locally, then return a pointer to that. Then the
wrapper would copy that array to its own newly allocated local space.

Well, obviously, this is as illegal as you can get. Once T returns, any
pointers to its local storage are invalid. However, from a very
low-level point of view this _might_ work in practice in some
circumstances. If T's local array of M arguments is very deep in the
stack, then the wrapper probably won't overwrite it immediately upon
returning. Then, when the wrapper starts copying the array to its local
space, it probably gets overwritten by the copy of itself, but by then
it won't matter (because the elements have already been copied before
they're overwritten).

Obviously, all of these techniques require alloca. That can be assumed
to be available.

So, in pure assembly tail recursion can be implemented by just adjusting
the stack pointer appropriately and jumping to the new function, without
using heap or static data. Can the same be done in C?

Any insights? A technique I have missed? Hints for implementing my last
method so that it at least often works in practice, even though it
violates the language? Or should I just give it up and use static data
or heap or fill the stack with air?

Thanks for any comments.

Lauri Alanko

--



Mon, 25 Mar 2002 03:00:00 GMT  
 Passing variable-size data between trampolines

Quote:

> Hello.

> Is there any remotely portable way of passing variable-size data between
> {*filter*}oline calls _without_ using heap (for efficiency) or globals (for
> re-entrancy)?

<snip>

> Anyway, the question is: where should T store the M arguments that it
> calculates? While T is running, the M arguments are most likely
> somewhere in automatic memory in T's block. Somehow that information
> should be passed to the calling function (which is the wrapper that does
> the iteration described in the third paragraph), which then passes it on
> to the {*filter*}oline U.

What about using heap memory, but reusing the allocated memory to avoid the
cost of frequently freeing and reallocating more memory?  Something like:

struct {*filter*}oline_args {
   size_t size;
   void* args;

Quote:
};

You could pass the structure in as the argument list to each {*filter*}oline
function.  It copies the arguments into locals, and then checks that size
is at least large enough for the arguments to the next function.  If not
it realloc's args with the larger size, and sets size appropriately.

/peter
--



Tue, 26 Mar 2002 03:00:00 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. Passing variable size arrays by value

2. Passing variable size arrays of structs with COM using size_is

3. What's the size limit to pass data between server and client

4. How to pass the data from URL parameter to the member variable

5. Reading variable size text data sets....

6. Passing variable args to a variable arg function

7. About local variables and variable size???

8. Find size of variable size structure?

9. Data passed to a method having [in.out] does not get back change data

10. How to pass HTML form data to a data tier

11. BUG in C++: array size passed to a C# code

12. Passing 2-D arrays of non-constant size

 

 
Powered by phpBB® Forum Software