Mail Archives: djgpp-workers/2002/02/19/18:46:31
> The outer loop isn't in malloc, it is in the application, which
> has the array or linked list or whatever of allocated memory to
> free.
>
> > for (bp=freelist[bu]; bp; bpp=&(bp->next), bp=bp->next)
>
> This is the only thing that matters. It makes each merge O(n),
> and must be executed O(n) times, thus O(n*n).
I agree this code should be improved. We should not search a
list - especially in a linear search. If we can't find a a quick
way to merge blocks, we shouldn't merge blocks.
> At most dividing into sublists changes the constant factor. The
> O(n*n) will always dominate. The search has to go on until either
> an adjacency is found or the whole list has been searched and none
> has been found. Sublists don't change this.
If there was some way to do a binary search in a sorted list we could
make that a log(n) type behavior which would IMO be acceptable, but
O(n) is bad.
> I can easily make a portion of the revised memblock compatible
> with the original, in that the size and freelist pointer will be
> at the same (-ve) offsets from the user pointer. That would
> forbid the safety improvement I am making to guard against
> off-by-one indexed operations. Publishing the offsets of those
> two items in implementation space would allow gradual conversion
> of unclean software that uses them, so that eventually the module
> would be truly independant If the other software uses only the
> size that is better. I envision a globally available variable:
>
> const int __msize_offset = offsetof(memblock, data)
> - offsetof(memblock, size);
>
> and the header contains:
>
> extern const int __msize_offset;
>
> which is initially constrained (and documented) to be the same as
> the present.
Be aware that alignment is also a very important issue here that we
just discussed about a week ago - I don't think we've decided which
of the 2 ways we should pick yet to fix our occasional alignment
offset issue. I'm pretty uncomfortable making any major changes to
malloc() for many reasons if it can be avoided.
- Raw text -