No realloc

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

No realloc

Enrico Colombini
I'm considering using Lua on a system offering no realloc(): only malloc() and free().

What loss of performance could I expect by using realloc=free+malloc, assuming the allocator is stupid enough not to immediately recycle the same block when there is enough space?

  Enrico

Reply | Threaded
Open this post in threaded view
|

Re: No realloc

Ralph Hempel
Enrico Colombini wrote:
I'm considering using Lua on a system offering no realloc(): only malloc() and free().

What loss of performance could I expect by using realloc=free+malloc, assuming the allocator is stupid enough not to immediately recycle the same block when there is enough space?

I'd be more worried about loss of data, unless the semantics
were:

  malloc(new) + memcpy(old to new) + free(old)

Many realloc() implementations do exactly this anyways for
security reasons, but you end up with quite some overhead in
time and memory when the blocks are large, and just time
when they are small.

One problem with the classic realloc() is that you may end up
with quite a bit of heap fragmentation if realloc() is generally
reducing the block by a size which is too small to be reused.

It's the little leftover bits that are killing me in my embedded
application and I'm going to instrument what happens if my
realloc() always does a malloc/copy/free instead of a resize...

Can I ask which platform does not have realloc() ?

Ralph

Reply | Threaded
Open this post in threaded view
|

Re: No realloc

Roberto Ierusalimschy
In reply to this post by Enrico Colombini
> I'm considering using Lua on a system offering no realloc(): only 
> malloc() and free().
> 
> What loss of performance could I expect by using realloc=free+malloc, 
> assuming the allocator is stupid enough not to immediately recycle the 
> same block when there is enough space?

Why don't you test? It is quite easy to change the allocation function not
to use realloc; something like this (untested):


void *l_alloc (void *ud, void *block, size_t oldsize, size_t size) {
  if (size == 0) {
    free(block);
    return NULL;
  }
  else {
    void *newblock = malloc(size);  /* alloc a new block */
    if (newblock == NULL) return NULL;
    if (block) {
      size_t commonsize = (oldsize < size) ? oldsize : size;
      memcpy(newblock, block, commonsize);
      free(block);
    }
    return newblock;
  }
}



-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: No realloc

Enrico Colombini
In reply to this post by Ralph Hempel
I'd be more worried about loss of data, unless the semantics
were:

  malloc(new) + memcpy(old to new) + free(old)

You're right, of course :-)

Can I ask which platform does not have realloc() ?

It's a proprietary ARM architecture.

  Enrico

Reply | Threaded
Open this post in threaded view
|

Re: No realloc

Enrico Colombini
In reply to this post by Roberto Ierusalimschy
Roberto Ierusalimschy wrote:
Why don't you test? It is quite easy to change the allocation function not
to use realloc; something like this (untested):

_Many_ thanks! I didn't even realize that both the old and new size were available <blush>. Too many hours in front of a screen, I guess...

I'll report the measured performance to the list.

  Enrico


Reply | Threaded
Open this post in threaded view
|

Re: No realloc

Ralph Hempel
In reply to this post by Enrico Colombini
Enrico Colombini wrote:

Can I ask which platform does not have realloc() ?

It's a proprietary ARM architecture.

Enrico,

I wrote a special version of malloc()/realloc()/free() for the
ARM architecture (in C) that is for embedded (not Linux) systems.

It requires a fixed (non-extendable and contiguous) area of
memory for the malloc() memory pool with a maximum size of
256K and has an overhead of 8 bytes per allocation.

It also has the advantage of traversable free and in-use memory
lists which is useful for finding out if you have fragmentation...

The Lua memory manager reports on how much memory it thinks
it is using but of course, it cannot report on heap fragmantation.

Cheers, Ralph



Reply | Threaded
Open this post in threaded view
|

Re: No realloc

Enrico Colombini
In reply to this post by Roberto Ierusalimschy
Roberto Ierusalimschy wrote:

void *l_alloc (void *ud, void *block, size_t oldsize, size_t size) {
  if (size == 0) {
    free(block);
    return NULL;
  }
  else {
    void *newblock = malloc(size);  /* alloc a new block */
    if (newblock == NULL) return NULL;
    if (block) {
      size_t commonsize = (oldsize < size) ? oldsize : size;
      memcpy(newblock, block, commonsize);
      free(block);
    }
    return newblock;
  }
}

Wouldn't it be better to do nothing and just return 'block' if (size <= oldsize) ?
(or am I missing something here?)

  Enrico

Reply | Threaded
Open this post in threaded view
|

RE: No realloc

Peter Pimley-3
 


> Enrico Colombini
> Wouldn't it be better to do nothing and just return 'block' 
> if (size <=
> oldsize) ?


Hi Enrico,

It depends on your definition of 'better' ;) (i.e. whether you're after
speed or minimal memory usage).  It also depends on your particular
usage patterns.  If you had blocks that became very large and then
shrank to become very small, you might end up using a lot more memory
than you need.

It's certainly worth trying the memcpy+malloc+free listed earlier.  Then
measure it and see if it's actually a problem on your particular setup.
The couple of times I've done this, it has turned out to be negligable.

Peter Pimley

__________________________________________________________________________________________________________________________________________
Information contained in this e-mail is intended for the use of the addressee only, and is confidential and may be the subject of Legal Professional Privilege.  Any dissemination, distribution, copying or use of this communication without prior permission of the addressee is strictly prohibited.The views of the author may not necessarily constitute the views of Kuju Entertainment Ltd. Nothing in this email shall bind Kuju Entertainment Ltd in any contract or obligation.

The contents of an attachment to this e-mail may contain software viruses which could damage your own computer system. While Kuju Entertainment has taken every reasonable precaution to minimise this risk, we cannot accept liability for any damage which you sustain as a result of software viruses. You should carry out your own virus checks before opening the attachment.

Kuju Entertainment Ltd trading as Zoe Mode

Registered Office : 10 Woodside Park, Catteshall Lane, Godalming, Surrey, UK, GU7 1LG. Company Number : 3481384. Company Registered in England.
__________________________________________________________________________________________________________________________________________
This email has been scanned by the MessageLabs Email Security System.
For more information please visit http://www.messagelabs.com/email 
_________________________________________________________________________________________________________________________________________


Reply | Threaded
Open this post in threaded view
|

Re: No realloc

Enrico Colombini
Peter Pimley wrote:
It depends on your definition of 'better' ;) (i.e. whether you're after
speed or minimal memory usage).

I may have CPU limits, but it's probably much better to save RAM in my system (and it won't depend on program execution patterns).

It's certainly worth trying the memcpy+malloc+free listed earlier.  Then
measure it and see if it's actually a problem on your particular setup.
The couple of times I've done this, it has turned out to be negligable.

Thanks for the shared experience. As I'm expecting more significant bottlenecks elsewhere, I'll follow this approach.

I now have a working system, but measurements at this point make little sense as I'm not working on the actual target hardware. Any suggestion of 'standard' benchmarks to evaluate (mainly) (re-)allocation, table access and general Lua speed (no libs, no fp calculations)?

(or is there already some sort of repository with Lua performance on varius hardware architectures?)

  Enrico

Reply | Threaded
Open this post in threaded view
|

Re: No realloc

Roberto Ierusalimschy
In reply to this post by Peter Pimley-3
> > Enrico Colombini
> > Wouldn't it be better to do nothing and just return 'block' 
> > if (size <=
> > oldsize) ?
> 
> 
> Hi Enrico,
> 
> It depends on your definition of 'better' ;) [...]

What may be worth is to return 'block' when size == oldsize. (Lua
sometimes does this kind of call.)

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: No realloc

Ivan-Assen Ivanov
In reply to this post by Enrico Colombini
You can also try the TLSF memory allocator:

http://www.baisoku.org/tlsf/

We've been using exclusively it for the Lua VM in our games for about
an year now and have traced no bugs to it.
We're about to ship a game using it very soon.
It's written by somebody from Vicarious Visions, a game development studio
specialized in handheld gaming platforms - some of which are very
resource-constrained embedded ARM systems.

It's very fast (constant-time malloc/free), and has a "real" realloc.
In fact, when we integrated it first about an year ago, it didn't, it
used alloc+memcpy+free, and we had a noticeable performance gain when
TLSF 1.8 introduced a "real" realloc.

Ivan-Assen

Reply | Threaded
Open this post in threaded view
|

Re: No realloc

Enrico Colombini
In reply to this post by Roberto Ierusalimschy
Roberto Ierusalimschy wrote:
What may be worth is to return 'block' when size == oldsize. (Lua
sometimes does this kind of call.)

Good to know. So this should be it (there is no test for (oldsize != 0) before memcpy, but that should be guaranteed when (block != NULL) unless something is broken in the caller):

static void *
l_alloc (void *ud, void *block, size_t oldsize, size_t size)
{
    (void)ud;
    /* free */
    if (size == 0) {
        free(block);
        return NULL;
    }

    /* realloc, same size */
    if (size == oldsize) {
        return block;
    }

    /* allocate for alloc | realloc */
    void *newblock = malloc(size);
    if (newblock == NULL) {
        return NULL;
    }

    /* realloc, different size */
    if (block != NULL) {
        memcpy(newblock, block, (oldsize < size) ? oldsize : size);
        free(block);
    }
    return newblock;
}

In a later phase of development, I'll probably add counters to do some statistics on allocator usage, sizes, etc. with a real program.

  Enrico

Reply | Threaded
Open this post in threaded view
|

Re: No realloc

Enrico Colombini
In reply to this post by Ivan-Assen Ivanov
Ivan-Assen Ivanov wrote:
http://www.baisoku.org/tlsf/

Thanks, it look interesting. I'm saving this information for the optimization phase.

  Enrico