RE: [avr-libc-dev] malloc improvement

[Weddington, Eric]

Hi Gerben,

Could you please post your patch to the avr-libc patch trackers? That
way it won't get lost.

Personally, I like the "about 10% smaller" part of this patch. :-)
Especially at the cost of only two pointers.

Eric

> -----Original Message-----
> From: 
> address@hidden 
> [mailto:address@hidden
> org] On Behalf Of Gerben van den Broeke
> Sent: Thursday, June 26, 2008 5:41 PM
> To: address@hidden
> Subject: [avr-libc-dev] malloc improvement
> 
> Current implementation:
> malloc loops trough all the holes in the freelist, checking 
> if there is a hole with exactly the right size (len), in 
> which case it takes the hole and returns it.
> While looping it also notes down the size of the smallest 
> hole it has found that is still big enough (size > len).
> If it cannot find a hole with exactly the right size, it will 
> use this noted hole.
> But because it only noted the size of the hole, it loops 
> through all the holes again until it has found a hole with 
> that size, then uses that hole.
> 
> Improvement:
> By not only noting down the size of the smallest hole, but 
> also noting its addrress, the second loop is not necessary anymore.
> 
> The cost:
> 2 more pointers are needed (both the found hole and the hole 
> before it must be remembered), so it might add 4 pushes at 
> the beginning and 4 pops at the end of the function.
> In the first loop two movw's are needed to note down the hole 
> address, which are executed everytime a smaller hole is found.
> 
> The gain:
> The whole second loop can be removed, which saves much 
> program space (whole malloc becomes about 10% smaller) and 
> even more execution time.
> 
> 
> By the way, I also found a little problem with malloc that 
> occurs when __malloc_heap_end has not been defined (quite 
> normal), so cp = STACK_POINTER() - __malloc_margin is used as 
> heap end, and the available space is calculated as avail = cp 
> - __brkval;
> If the stack pointer would have become lower than __brkval + 
> __malloc_margin, then avail (being a size_t) would become 
> less than zero = very much, so malloc would allocate the 
> space which belongs to the stack.
> This can happen easily when the heap is filled (almost) up to 
> the stackpointer - __malloc_margin, then just one or maybe a 
> few pushes are done so there is less than __malloc_margin 
> between heap end and stackpointer, and then malloc is called.
> I suggest the cp and __brkval should first be compared: if 
> (cp < __brkval) return 0; or avail could be a signed integer 
> (which is no problem as long as there is less than 32KB of 
> memory); note that this fix is *not* included in the attached patch.
> 
> Gerben
>