TLSF is compared with other well known allocators. These allocators are:
- Binary-buddy: This allocator has been used in some real-time applications.
The original buddy system memory allocation algorithm was taken from "The Art of Computer Programming, Volume 1, 3rd Edition", by Donald E. Knuth, pages 442-444.
For more information about the algorithm, please read the excellent written by Knuth.
- Half-fit: This was the first published allocator with constant timing cost.
This is an implementation of the Half-Fit allocator as described Takeshi Ogasawara in the paper: "An Algorithm with Constant Execution Time for Dynamic Storage Allocation"
Extracted form this paper:
This paper has proposed Half-Fit, a new DSA algorithm whose WCET is O(1). This WCET can be accurately estimated by counting a small number of machine instructions. Half-Fit also guarantees a short WCET, because it accesses only a few memory addresses, whereas the binary buddy system whose WCET is also O(1) but which accesses many memory addresses in the worst case, is unpredictable because of data cache misses and TLB entry misses. The simulation results show that Half-Fit has the advantage over the binary buddy system of greater memory efficiency.
T. Ogasawara. An algorithm with constant execution time for dynamic storage allocation. RTCSA '95: Proceedings of the 2nd International Workshop on Real-Time Computing Systems and Applications. (1995)
- Douglas Lea's malloc (DLmalloc): Currently, this allocator is considered to be one of the best existing allocators. It is widely used in general purpose systems.This is one of the most used allocators, which exhibits good average performance for most applications.
All the documentation about the algorithm, as well as the implementation itself, is available at the web site maintained by Douglas Lea.
- AVL based allocator: A best fit implementation using an AVL tree to manage free blocks. It is not a fast allocator, but has a bounded response time. Therefore, it may be suitable for real-time and embedded applications.
All the documentation about the algorithm, as well as the implementation itself, is available at the web site maintained by Walt Karas.
- Sequential Fits: Sequential Fits algorithms are the most basic mechanisms. They search sequentially free blocks stored in a singly or doubly linked list. Examples are first-fit, next-fit, best-fit and worst-fit.
First-fit and Best-fit are two of the most representative sequential fit allocators, both of the are usually implemented with a doubly linked list and used here as reference with respect to other works.