1

In the worst case, on a section (is this the right term?) of memory of size n, linked-list needs O(n) time to allocate a block of memory in suitable size.

However, if malloc is tree-based, say, an interval tree, only O(logn) time is needed. Furthermore, a tree can satisfied such requirements without extra time (in terms of time complexity) as "Find the smallest block of free memory whose size is larger themx" , "Always allocate on the borders of free memory" and "Free only a part of the allocated memory". A drawback maybe that freeing memory takes O(logn) time.

Thanks

ps. I've seen the question Data structures for traversable memory pool, but the author doesn't seem to have figured it out.

Improve this question
5
  • 7
    What makes you think that malloc uses a linked list? just because one (of many many) implementation used it? Commented Jun 29, 2015 at 7:30
  • @JoachimPileborg I read that ptmalloc2 uses chunks in a linked list, and it's in the latest version of glibc. Commented Jun 29, 2015 at 7:43
  • 1
    Have you actually tried writing your own malloc and free functions, using something else, and measure the time it takes to allocate, compared to current implementations. Commented Jun 29, 2015 at 7:44
  • 1
    @MatsPetersson I wrote a model, playing on an array and pretending that some "programs" ask for memory. Commented Jun 29, 2015 at 7:49
  • 1
    And how did that work out? Was the overall execution time much improved? In trivial programs, I have seen malloc take a large portion of the time. But in non-trivial programs, it's very often not where the time is spent - obviously highly dependent on exactly what the program does! But memory allocation has been around for the past 40 years at least, and the model has, largely, been the same - and I'm sure some people HAVE studied it. Commented Jun 29, 2015 at 7:57

2 Answers 2

Reset to default
4

I don't KNOW the answer, but here's some thoughts:

There is absolutely no REQUIREMENT that malloc is implemented in a particular way. However, an unbalanced tree is just as bad as a linked list in the worst case. A balanced linked list is a lot more maintenance. A tree, where you have two links per node, also takes up more memory than a single-linked list. Removing nodes in a linked list is easier as well as inserting at the end is very easy.

And in most systems, there is (almost) exactly one free for every malloc - so if you make one faster by making the other slower, you gain very little.

It is also relatively common that the "next allocation is the same as the previous one", meaning that if the last allocation is first in list, it's an O(1) operation.

In real-time systems, buckets are often used for allocations, such that there are a number of fixed sizes, and each time something is allocated out of the main heap, the size is rounded to the nearest larger size, and when freed it goes into the bucket of that size (which is a linked list). If there is a free element of that size already, then that allocation is used. Besides the speed of allocation/free being O(1), this has the benefit of reducing fragmentation - it's not completely impossible to "rip all the heap into small pieces, and then not have any large lumps left", but it's at least not possible to take up most of the memory by simply allocating a byte more each time until you have half the heap size in one allocation.

(Also, in Linux's GLIBC, allocations over a certain size do not end up in the linked list at all - they are allocated directly via mmap and released back with munmap when free is called)

Finally, algorithmic complexity is not everything - in real life, it is the actual time spent on something that matters - even if the algorithm has O(n) but each operation is fast, it can beat O(logn). Similarly, particularly in C++, small allocations are highly dominant, which means that overhead of more memory per node is an important factor.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Just because there is exactly one free for every malloc, a malloc based on tree uses O(logn)+O(logn)=O(logn) time, and linked-list, O(n)+O(1)=O(n)
And the allocation is in average O(n), instead of O(1), even with buckets.
Yes, but you also have to take actual time into account.
Buckets guarantee O(1) for both allocation and free - because the items are all the same size in the bucket and you just pick the most recently freed item - or carve out a bit of "fresh" heap if there is nothing in the free list. But I'm sure it's possible to implement something using buckets that is less efficient - one can always do that.
Do you mean that the constants in the time complexity may be large?
|
0

There is no specification which says that malloc needs to be based on a linked list. Between platforms, the implementation may change. On one platform, speed may be crucial and a tree can be implemented, on another platform, memory is more expensive and a linked list (or such) is used in order to save as much memory as possible.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.