1. Home
  2. Embedded Programming
  3. Re: dynamic memory allocation

Re: dynamic memory allocation

True statement, but how do I determine this bound?

> > >> > > >> > >> > >>Hi there, > >> > >>I'm experimenting with dynamic storage allocation for hard real time > >>embedded systems and I've come across two of interest: the Lea > allocator > >>and the TLSF allocator. Lea allocator as many of you probably know is > one > >>of the best out there but I couldn't find any information on using it > in > >>hard real time systems. But according to the internal documentation it > >>has bounded operations. TLSF is specifically designed for real time > and > >>claims fast response times with worst case O(1) time for malloc and > free. > >>But in my own tests, it appears the Lea allocator outperforms TLSF. > Has > >>anyone used either and what are your thoughts? > > > > > >I've not used either one, and generally use fixed-size buffer pools > >when dynamic memory allocation is required in a real-time app. But I > >have a couple observations. > > > >"O(1)" means (essentially) fixed cost. It doesn't mean that cost is > >always 1. > > > >"Bounded" says the cost never exceeds a particular value. An O(1) > >process is likewise "bounded" to the fixed cost > > > >If the average time for an Lea operation is 50, while the average time > >for a TLSF is 100, then the Lea will "outperform" the TLSF. However, > >if the upper bound on the Lea is 1000, the TLSF is 100, and your > >application will not withstand any memory allocation operation longer > >than 500, then the TLSF will be acceptable and the Lea will not. Fast > >enough is fast enough, and too long is too long.

If I remember correctly, both Lea and TLSF put free blocks in "bins" based on size. Each bin corresponds to a range of sizes. For small blocks (up to 512 bytes I think), Lea puts only one size in each bin. But for larger sizes, there are multiple size blocks in each bin. Lea does a linear search of the bin for the best fit. So Lea is hard to beat if you only allocate small blocks, and slow (but good) for large blocks. TLSF never searches its bins for best fit, but the "wasted" space is limited to I think less than 2% or so of the block size.

This is an allocator I wrote that always does best-fit for any size block, but has O(log N) time complexity.

formatting link

I'd be curious to know how similar our approaches to allocator benchmarking are.

Have you seen this site with a TLSF allocator?

formatting link

Reply to
wkaras
Loading thread data ...

is

it

it

time

Fast

I'm using c++ at the moment and as a result I've overriden new and delet to use the allocator's malloc and free. my methods of benchmarking ar quite simple, normally just simple tests such as

delete new T (T is some object) and delete [] new [] kind of thing. I us the clock() call to measure the time from start to finish. If you hav more accurate ways, I'd be interested.

From what I've read, it appears Lea is O(n) where n == bits in size_t. S this usually amounts to O(32) on a 32 bit system. I have seen the TLS allocator that you linked to, it's the very one I'm playing with righ now. Even when I'm allocating fairly large blocks (7000+) Lea is stil proving to be faster. For the most part Lea seems to be doing better an only in some cases TLSF will do better, such as malloc'ing a bunch o different spaces, freeing some, and then trying to malloc random sizes.

Question is, contemplating use in a real time system, which one would b better. My tests are pointing towards Lea, but theoretically, Lea has higher bound than TLSF ( O(32) vs O(1) )

Reply to
kibaboy

kibaboy wrote: ...

O(32) and O(1) mean the same thing (constant time complexity). I tried to find a good link to page that describes big O notation, but I couldn't find one. If you get the chance, you may want to go to your local university library and find a good book on algorithms to learn more about time complexity categorization.

You have to mix allocs and frees to measure the performance of an allocator. This allocator:

static int a[1

Reply to
wkaras

So

TLSF

still

and

sizes.

be

a

You're right, I knew the line about O(32) and O(1) sounded a little weir to me when I was thinking about the post afterwards, I guess it pays t listen to your intuition more often.

Reply to
kibaboy

right

has

weird

I guess what it all boils down to is would anyone recommend TLSF 2.0 ove Lea for a real time system?

Reply to
kibaboy

Generally, for any two allocators A and B, some applications will have acceptable performance using A or B, some with A but not B, some with B but not A, some with neither A nor B.

If you don't have the time to understand and evaluate what's best for your application, and you don't have the money to hire someone to help you, my free-and-worth-every-penny advice is to use TLSF.

Reply to
wkaras

... snip ...

Color me ignorant, but I have no idea what TLSF nor Lea are. However I have built a malloc system for use with DJGPP which attempts to remain as close as possible to standard C (but isn't) and ensures that all operations are O(1). The system primarily relies on conversion between pointers and integers, and acquisition of row memory blocks via the sbrk() call. Another area is non-standard and uses the GCC form of variadic macros for debugging, which does not affect the actual code.

A useful package for debugging and verifying the health of the arena is included.

The system is available (source and testing code) at:

If you use it, attribution would be appreciated.

--
"The power of the Executive to cast a man into prison without
 formulating any charge known to the law, and particularly to
 deny him the judgement of his peers, is in the highest degree
 odious and is the foundation of all totalitarian government
 whether Nazi or Communist." -- W. Churchill, Nov 21, 1943
Reply to
CBFalconer

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.