Re: Recursive subroutine for reading null-terminated string
- From: Glen Herrmannsfeldt <gah@xxxxxxxxxxxxxxxx>
- Date: Tue, 25 Nov 2008 13:31:11 -0700
vc4@xxxxxxxxxx wrote:
(someone, previously snipped, wrote)
2. High overhead. You mention that this allocates twice as much memory
as needed. I'd guess that to be a severe underestimate. You appear to be
ignoring the memory involved in the recursive call.
Yes I didn't think/know about this.
Yes. It is somewhat similar to the linked list form, with
one character per list element, except the list is on the
stack along with return addresses, local variables for
each nesting level, and any other call overhead.
(The stack is likely word aligned so that at least
four bytes (eight bytes on 64 bit machines) are used
for each character, in addition to the other overhead.)
Another approach is to gradually increase the size by
realocating on the fly as you read.
I was (wrongly) thinking that this approach is essentially the same
thing as my recursive procedure, but my solution is more elegant/
compact. Of course I did not take into account the overhead.
Just about anything written in recursive form that only calls
itself is better written in non-recursive form.
Another approach to the whole thing is to build a linked list
I have assumed that linked list is a very inefficient way of storing
large arrays. I thought that normal arrays are allocated a single
memory chunk, whereas a linked list is a collection of single
character units with pointers linking each element to the next one.
Hence there is no direct access to elements in the middle, and
everything becomes slow. Am I wrong here? I suppose if the linked list
contains large chunks of data rather than single characters, this will
not be a problem.
Yes. But your recursive form is pretty much the same with even
more overhead. The usual linked list form would be a list of
strings or arrays of a convenient length. When one is full,
allocate the next. The size should be somewhat larger than
the overhead (pointer size).
Is memory allocation in general a serious problem in terms of speed/
overhead? For instance, is repeated reading of chunks of data into a
pre-allocated array significantly better than allocating the exact
size to the array every time the data are read, and deallocating
afterwards?
Memory allocation has a fairly high overhead. Like many things,
it is best kept outside the inner loop. Also, you should watch
for fragmentation when mixing allocate/deallocate.
If you want to test the overhead on the recursive form, put a
read(*,*)i statement (or PAUSE if you like) at the beginning,
and just before the ALLOCATE. Run the program and check
its size at the first pause. (Use Windows task manager,
or unix's ps or top.) Then check the size again at the
second pause. The difference should be the memory allocated
for recursion up to that point.
-- glen
.
- References:
- Prev by Date: Compilation Error
- Next by Date: Re: Compilation Error
- Previous by thread: Re: Recursive subroutine for reading null-terminated string
- Next by thread: Re: Recursive subroutine for reading null-terminated string
- Index(es):
Relevant Pages
|
