AVL tree without malloc in C

[karthikbalaguru]

Hi,

Is there any AVL tree implementation
in C that does not use malloc ?

Currently, I am using a static array for
a database that will be frequently
searched / updated, but i would like
AVL trees. But the constraint is that
the processor consumes more time
for dynamic memory allocation and
hence it affects the speed.

So, Is there any AVL tree in C that
has been implemented without using
malloc ?

Thx in advans,
Karthik Balaguru

 

[Keith Thompson]

Is there any AVL tree implementation
in C that does not use malloc ?

Currently, I am using a static array for
a database that will be frequently
searched / updated, but i would like
AVL trees. But the constraint is that
the processor consumes more time
for dynamic memory allocation and
hence it affects the speed.

So, Is there any AVL tree in C that
has been implemented without using
malloc ?

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.

 

[CBFalconer]

Is there any AVL tree implementation in C that does not use
malloc ?

Currently, I am using a static array for a database that will be
frequently searched / updated, but i would like AVL trees. But
the constraint is that the processor consumes more time for
dynamic memory allocation and hence it affects the speed.

So, Is there any AVL tree in C that has been implemented without
using malloc ?

Good. You have finally begun reading literature in place of
interminable questions. Also look up red-black trees.

Dynamic memory allocation only takes time if you have to make an
allocation. That depends on your usage of the tree. If you are
considering other forms the items stored must be of constant size,
or can be so treated. Now the optimum depends on the overall
system. For example, if you are using deletion from the tree
(which is more complex) then you can simply put the deleted memory
portions in a pile for reuse as needed, and possibly avoid most of
the time spent.

The point about using malloc is that you don't need to worry
(within reason) about how many items are to be stored.

If time remains critical, simply allocate a large enough array, and
use array indices in place of pointers. Test both versions. You
will probably be surprised.

 

[Darren Cubitt]

Hi,

Is there any AVL tree implementation
in C that does not use malloc ?

I have been working on an AVL tree implementation as part of a larger
project.

The tree is implemented using a struct avltreelink_t, which is embedded
into the struct you wish to insert into the tree. The tree API functions
all take a pointer to the embedded struct, and can be converted back to
a pointer to your struct using a macro, struct_from_field().

All the storage allocation is left up to you to handle, along with
keeping track of the tree root pointer (which is all too easy to forget
at times).

It's still a work in progress, but I haven't had any issues with it so
far, and since it seems to snugly suit your purpose, I've put it online
for you.

http://darrencubitt.googlepages.com/avltreelink.zip

The documentation has just been thrown together with doxygen and is
incomplete. I have included a short example (demo.c) to try and clear up
the general usage.

If you find any bugs, let me know.

HTH

 

[Darren Cubitt]

If I do not see as far as others, it is because
I stand in the footprints of giants.

I am so stealing that...

 

[Ben Bacarisse]

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).

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.

 

[Ralph Boland]

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.

I strongly implore that you demonstrate that malloc is a serious
performance bottleneck
before abandoning it (as was pointed out earlier).
Assume malloc is a serious problem then write a method avl_malloc
which on first invocation
allocated an array of (say) 100 empty avl tree nodes and returns a
pointer to the first one.
Subsequent calls to avl_malloc return pointers to unused empty avl
tree nodes until all 100 are
used and then allocates another bunch of 100.
This should resolve the performance issue with malloc.
If you are doing avl tree node deletes then this gets more complicated
but can also be handled.

Ralph Boland

 

[karthikbalaguru]

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.

--

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

 

[Nate Eldredge]

Hi,

Is there any AVL tree implementation
in C that does not use malloc ?

Currently, I am using a static array for
a database that will be frequently
searched / updated, but i would like
AVL trees. But the constraint is that
the processor consumes more time
for dynamic memory allocation and
hence it affects the speed.

So, Is there any AVL tree in C that
has been implemented without using
malloc ?

Where would you like to get the memory to create new nodes, if not from
malloc?

 

[karthikbalaguru]

Where would you like to get the memory to create new nodes, if not from
malloc?- Hide quoted text -

So, does it mean that AVL tree is not
possible without malloc ?
Are there no alternative approach for
AVL tree without malloc ?

Thx in advans,
Karthik Balaguru

 

[Nate Eldredge]

So, does it mean that AVL tree is not
possible without malloc ?
Are there no alternative approach for
AVL tree without malloc ?

No, I didn't say that. The question wasn't rhetorical. If the tree is
going to be useful, you have to be able to add notes to it, yes? So you
need some memory to store those new nodes. You have to get this memory
from somewhere. malloc() is one possibility. Another possibility would
be to have a big array of node objects that you can use, and have some
way of keeping track which ones are available. More exotic things are
possible too, depending on your system.

So I think you should first decide where you want the memory to come
from. This will help determine how the tree algorithm should work.

The issue I think you will discover is that whatever source of memory
you use, you are going to need some way to keep track of what part of it
is in use and what parts are still available for allocation. This will
become more complicated if you want to be able to remove nodes and
reclaim the memory. At some point, I think you may find yourself
effectively writing your own malloc() -- and it probably won't be as
efficient as the one the system already provides.

 

[Chris M. Thomasson]

Where would you like to get the memory to create new nodes, if not from
malloc?

;^D









To the OP:

IMVHO, one can use partitioned region allocation. The partitioning, handling
return of NULL, and, well ect... Can be built on something like this:

http://groups.google.com/group/comp.lang.c/browse_frm/thread/97a1c978a0f20195

Pass a buffer of your choice into the region, and it will allocate virtually
any object you choose. When it craps out, you can do some bookkeeping and
allocate another buffer. Well, of course you do no need to dynamically
allocate anything. Go ahead and pass it a static buffer. No problem.
However, it will return NULL when that buffer is full. It also conserves
space by not forcing every allocation to be rounded up to a "max alignment
value". It just might be of service to you.

 

[karthikbalaguru]

;^D

To the OP:

IMVHO, one can use partitioned region allocation. The partitioning, handling
return of NULL, and, well ect... Can be built on something like this:

http://groups.google.com/group/comp.lang.c/browse_frm/thread/97a1c978...

Pass a buffer of your choice into the region, and it will allocate virtually
any object you choose. When it craps out, you can do some bookkeeping and
allocate another buffer. Well, of course you do no need to dynamically
allocate anything. Go ahead and pass it a static buffer. No problem.
However, it will return NULL when that buffer is full. It also conserves
space by not forcing every allocation to be rounded up to a "max alignment
value". It just might be of service to you.- Hide quoted text -

I tried the code in Visual C++ 2008 Express edition.
It worked fine.
But, is that code only for VC++ 6.0 / .
Is there a version available for gcc ?

Thx in advans,
Karthik Balaguru

 

[Keith Thompson]

[...]

The full URL is

http://groups.google.com/group/comp.lang.c/browse_frm/thread/97a1c978a0f20195

Did your news software really truncate it?

I tried the code in Visual C++ 2008 Express edition.
It worked fine.
But, is that code only for VC++ 6.0 / .
Is there a version available for gcc ?

Why do you assume it's only for VC++ 6.0? It just compiled for me
with no errors using gcc (something you could have found out as easily
as I just did).

 

[Chris M. Thomasson]

[...]

I tried the code in Visual C++ 2008 Express edition.
It worked fine.
But, is that code only for VC++ 6.0 / .
Is there a version available for gcc ?

It works for me in GCC on several different platforms. It compiles on Comeau
as well. If you find a compiler which craps out on it please inform me and
provide exact error information. I would me most interested indeed.

Thanks.

 

[Chris M. Thomasson]

[...]

The full URL is

http://groups.google.com/group/comp.lang.c/browse_frm/thread/97a1c978a0f20195

Did your news software really truncate it?

I tried the code in Visual C++ 2008 Express edition.
It worked fine.
But, is that code only for VC++ 6.0 / .
Is there a version available for gcc ?

Why do you assume it's only for VC++ 6.0?

Perhaps the following lines sort of tweaked his line of thinking:

______________________________________________________________
#if defined (_MSC_VER)
/* warning C4116: unnamed type definition in parentheses */
# pragma warning (disable : 4116)
#endif
______________________________________________________________




I only added that clause because MSVC was giving me a warning.

It just compiled for me
with no errors using gcc (something you could have found out as easily
as I just did).

Yeah. AFAICT, it should go ahead and compile on virtually any modern C
compiler. Can you notice any problems with the code itself Keith? So far, it
looks okay to me.



Thanks for your valuable time and expertise Keith. I really do appreciate
your extensive contributions to this fine group!

 

[Keith Thompson]

Is there any AVL tree implementation
in C that does not use malloc ?

Currently, I am using a static array for
a database that will be frequently
searched / updated, but i would like
AVL trees. But the constraint is that
the processor consumes more time
for dynamic memory allocation and
hence it affects the speed.

So, Is there any AVL tree in C that
has been implemented without using
malloc ?

Here's my suggestion. Find a C implementation of an AVL tree that
uses malloc and free. Use it in your program and measure its
performance.

Then create a modified version of the AVL tree code that doesn't use
malloc or free. Replace each call to malloc with a call to a routine
that grabs the next node from an array. Replace each call to free
with a routine that does nothing. (Yes, this introduces a memory leak
of sorts; bear with me.) Measure the performance of your program with
this modified AVL tree code.

If the modified program's performance isn't *significantly* better
than the first one's, you might as well use the malloc implementation.

If there is a significant improvement, then you can modify the array
code to allow deletion (which will cost you some of the improved
performance).

 

[Ahem A Rivet's Shot]

Here's my suggestion. Find a C implementation of an AVL tree that
uses malloc and free. Use it in your program and measure its
performance.

<snip good advice>

I would go one stage further - and profile the code to see whether
or not the AVL manipulations are in fact a significant factor in the
performance of the code before bothering to fiddle with the implementation.
In fact take the next step - if the application is fast enough don't even
bother to profile it'll do as it is.

 

[Darren Cubitt]

Unless there's some caveat regarding AVL trees slipping my mind, then this
is wrong. You can write an implementation where node data is kept as a
member of the structures/objects you're storing, and the root can be kept in
static or auto storage (the nodes could likewise have come from static or
auto storage).

Oh, dang! This is exactly what the code I posted does. And I thought I
was doing something new and cool

OTOH, my implementation allows you to use the tree to create an
AVL-balanced linked-list. It's like a normal list, but with O(log2(n))
complexity for random access. I guess that's kinda cool, as long as you
don't mind the extra memory footprint of AVL nodes.

allocations and--more importantly--half the error checking. And there's no
additional memory bookkeeping involved whatsoever.

This is a definite plus. A friend of mine who was taking a Uni course on
programming used to talk about how his prof. was an "abstract, abstract,
abstract" kinda guy. But to hijack and mangle a quote from someone I
can't remember, "Abstraction is good, but don't be so abstract that you
forget what you were supposed to be doing".

 

[Guest]

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

I am using a Network Processor and find that it
consumes some time for malloc based operations.

how much time?

So, i am concerned that if i go in for Trees
like AVL, it might impact the performance w.r.t
speed.

"might impact". You need to measure it

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

"thought"- don't guess, measure

<snip>