AVL tree without malloc in C

Probably, but can you explain exactly *why* you want to avoid malloc? Where does this requirement come from?

If you've tried using an AVL tree implementation that does use malloc, found that it's too slow for your purposes, profiled the code's performance, and found that malloc (and free) calls are a real performance bottleneck, then your question is reasonable.

If you're doing this for fun, trying to squeeze out the fastest possible performance just because you want to, then that's reasonable too.

But unless you have a specific reason to avoid malloc, then I suggest using a AVL implementation that *does* use malloc. It's likely that it will be fast enough.

--
Keith Thompson (The_Other_Keith) kst-u@mib.org  
Nokia
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

The other obvious possibility is that he's working in an embedded environment that doesn't allow malloc (the idea being that if you statically allocate everything you need up front, you never have the possibility of hitting an out-of-memory condition at runtime; if you never call malloc, you never have to deal with malloc failures).

--
poncho

That is not (to me) an obvious possibility from the information presented so far. If he were in this position, then I would expect him to say so, not express a worry that malloc might not be fast enough.

--
Ben.

cally

f

, you

Now, I have included comp.arch.embedded also.

I am using a Network Processor and find that it consumes some time for malloc based operations. So, i am concerned that if i go in for Trees like AVL, it might impact the performance w.r.t speed.

The possible reasons that are thought for not using malloc are -

1. Every malloc call may involve the Memory Management Unit of the processor and hence some delay might be introduced there.
2. Memory may not be continous in the case of malloc and hence it will take time for the accessing and the processing of it. Processing here refers to the insertion/deletion/searching operations on the database.

3.Interestingly i came across this thought also. Since the memory is not continous, it is not possible to prefetch and have the whole database for processing. But, in the case of arrays, it is easy to prefetch and do the searching/insertion/ deletion operations.

Considering, i am not worried about point number

3 currently. AVL tree implementation that is not based on malloc in C language is of interest to me.

I am using Cavium Octeon CN5860 Processor . Considering that AVL tree is very efficient data structure, Will AVL tree be really helpful as it has malloc in it ? Will malloc operations in AVL tree affect the performance in Octeon Processor ? Basically, can we use Tree like data structure in Cavium Octeon CN5860 processor and its relation with performance interms of speed ? Any ideas ?

Thx in advans, Karthik Balaguru

On Fri, 20 Mar 2009, karthikbalaguru wrote: ...

What is the key size? Payload?? How many records? Is this a RT system with a maximum latency, or are you just trying to be efficient? Are you talking about RAM? Flash? What is your 2nd tier storage? Are you doing insert/delete or simple lookup? Random access or sequential? Would a hash lookup be better?

AVL trees are great for random insertion deletion, but they incur a cost in index rotations to maintain the balance. If you are primarily READING, then AVL might be overkill. Is your data random or sequential? Are you going to be doing insertions/lookups in the same proportion, or do you need to optimize for entry or retrieval?

If you can fit the entire structure (index and/or data) into memory, then you can simply re-write the malloc/free routines to allocate from a pre-allocated pool, and thus the likelihood of finding something off the shelf, also suitably licensed which will work are increased. This is a simple process, particularly if the key/payload size is constant, and allocation amounts to incrementing a pointer, and managing the chains.

You do of course raise some questions regarding attempting to optimize code before you actually implement it. Why not simply try a malloc/free version of an AVL library, and test it out first. If it doesn't work, you can optimize the malloc/free code to used memory pools, if it turns out that memory allocation is indeed your rate limiting step.

Having said all of this ... have you looked at SQLite??

HTH, Rob Sciuk

I'd have thought a good implementation would make storage allocation and the AVL tree itself independent.

how much time?

"might impact". You need to measure it

"thought"- don't guess, measure