4

Drawback in linked list is that to malloc() a chunk ,memory allocator has to search the link list and then if that address is found, return it.. So why not use a binary tree to reduce the search-time ?

One of the questions asked by NVIDIA http://www.careercup.com/question?id=9765724

Found a relevant article that discusses it here

Sharat Chandra
  • 4,434
  • 7
  • 49
  • 66
  • Are you talking about searching for a specific element to `free`'? If so, it's still a search problem, unless I'm missing something.. – prelic Mar 08 '12 at 01:57
  • No , as someone pointed out, free is a constant time operation, but malloc() is not , I suppose ? – Sharat Chandra Mar 08 '12 at 01:59
  • haha, that was me, I deleted the comment because I thought I misinterpreted the question. After verification, I'm fairly certain each `free` is a constant-time operation, as it doesn't even need to touch the contents of the pointer, it just internally marks that block available. As for malloc, it would be O(N), but because the memory manager allocates blocks, it's not linearly slower to allocate bigger blocks. – prelic Mar 08 '12 at 02:01
  • 1
    Freeing also causes a search of the free list, to find the proper place to insert the block being freed. If the block being freed is adjacent to a free block on either side, it is coalesced with it into a single bigger block, so storage does not become too fragmented. Determining the adjacency is easy because the free list is maintained in order of decreasing address. From :- http://www.java-samples.com/showtutorial.php?tutorialid=574 – Sharat Chandra Mar 08 '12 at 04:06
  • Are we talking C/C++ memory allocation or Java memory allocation? They are very different mechanisms...one of the biggest differences I would think. My answer and comments are referring to C's `malloc` and `free` tools. – prelic Mar 08 '12 at 04:12
  • Oh.ok .. But does malloc even appear in Java. I'm not so sure..I think it is a general tutorial irrespective of any programming language ? – Sharat Chandra Mar 08 '12 at 05:30
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/8670/discussion-between-prelic-and-sharat-chandra) – prelic Mar 08 '12 at 13:45

1 Answers1

1

If I'm understanding you correctly, check this link out:

Time complexity of memory allocation

Heap allocation can be done by representing free memory as a linked list, but any reasonably sophisticated memory manager will use something faster, such as the AVL tree mentioned in an answer in the question I posted. There is even an O(1) solution called TLSF (Two Level Segregated Fit), also mentioned in the answer.

Community
  • 1
  • 1
prelic
  • 4,450
  • 4
  • 36
  • 46