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: > [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED] > org] On Behalf Of Gerben van den Broeke > Sent: Thursday, June 26, 2008 5:41 PM > To: avr-libc-dev@nongnu.org > 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 > _______________________________________________ AVR-libc-dev mailing list AVR-libc-dev@nongnu.org http://lists.nongnu.org/mailman/listinfo/avr-libc-dev
