AVL tree without malloc in C

[Moi]

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.

There is nothing wrong with using a statically allocated array of AVL-tree
nodes. The size is fixed, so you'll need to handle the case where your
array becomes exhausted. And you'll need to manage your own free list.
(which is not hard because the nodes contain at least two unused pointers)

HTH,
AvK

 

[user923005]

This is good advice, but there are caveats.  If the AVL code is
good it is likely to be reused in other applications.  So it
doesn't suffice to merely ask if it is fast enough in the current
application.  More than that, how do we know if the current
application is fast enough?  It can happen that what seemed fast
enough early on turns into a bottleneck later on.

Real life story:
Someone had a disk based bubble sort injected into a large code base.
I found it and raised a red flag. But the other side showed me
benchmarks that proved it was within specifications.
The test was extended to the live data and still fell within
specifications. My concerns were therefore rejected.

Unfortunately, once the product was released, the data scaled
exponentially. Searches that previously took 5 seconds were now
taking 5 hours.
A million dollar project was scuttled by 150 lines of lame code.
After about three years of use (IIRC), the tool set was abandoned.

It is common enough to warn against premature optimization.  Few
think about the costs of belated optimization.

Both sides of the fence should be examined. It is important to choose
an algorithm that scales well with problem size, if possible.

 

[CBFalconer]

.... snip ...

Real life story:
Someone had a disk based bubble sort injected into a large code
base. I found it and raised a red flag. But the other side
showed me benchmarks that proved it was within specifications.
The test was extended to the live data and still fell within
specifications. My concerns were therefore rejected.

Unfortunately, once the product was released, the data scaled
exponentially. Searches that previously took 5 seconds were
now taking 5 hours. A million dollar project was scuttled by
150 lines of lame code. After about three years of use (IIRC),
the tool set was abandoned.

It sounds as if you had a surprisingly ignorant set of co-workers.
It reminds me of a similar (but much simpler) situation that arose
about ten years ago. I was on a consulting job, and a group did
the lay-out of a small component that adapted an i/o port. I
wanted them to add a single jumper and i/o line so it could be
tested (to a degree) without any external equipment. The cost was
zero. I was obstinate and continued the argument. I eventually
gave up. Then somebody, somewhere, made a reasonable decision and
the modification was incorporated.

I was supposedly doing software, and knew nothing about hardware.

 

[user923005]

user923005 wrote:

... snip ...



It sounds as if you had a surprisingly ignorant set of co-workers.
It reminds me of a similar (but much simpler) situation that arose
about ten years ago.  I was on a consulting job, and a group did
the lay-out of a small component that adapted an i/o port.  I
wanted them to add a single jumper and i/o line so it could be
tested (to a degree) without any external equipment.  The cost was
zero.  I was obstinate and continued the argument.  I eventually
gave up.  Then somebody, somewhere, made a reasonable decision and
the modification was incorporated.

I was supposedly doing software, and knew nothing about hardware.

They had an additional argument about why we need not worry:

Hardware scales exponentially over time. IOW, in 5 years, the
hardware will be about 32 times faster than today.

Of course that is true for:
CPU speed
Ram size
Disk size

Unfortunately, it is not true for:
1. Hard disk speed
2. Memory speed

which scale linearly for hard disk speed and sub-exponentially for
memory speed.

 

[Antoninus Twink]

I was on a consulting job, and a group did the lay-out of a small
component that adapted an i/o port. I wanted them to add a single
jumper and i/o line so it could be tested (to a degree) without any
external equipment.

Here we try to stick to the C language, as defined by the C standard
(the items marked C99 below), and consider things dependent on system
specific features to be off-topic.

Well, gee! What an idiot I am! Obviously I somehow managed to miss the
section in my copy of the C standard that deals with jumpers and i/o
ports.

Then again, I know I have a few other bits missing too, so maybe it can
be found after the sections on CP/M and dirty underwear, and just before
the section on utter, utter hypocrisy.

There are quite a few trolls about that keep trying to divert the
newsgroup - you will learn to identify them quite soon.

You know, I think he will.

 

[karthikbalaguru]

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

This is the method that i had in my mind and hence
posted the query for AVL tree without malloc in C language.

Thx in advans,
Karthik Balaguru

 

[Keith Thompson]

This is the method that i had in my mind and hence
posted the query for AVL tree without malloc in C language.

If you followed my suggestion (which you may or may not choose to do),
you don't *need* a non-malloc AVL tree implementation until after
you've performed the measurements. You might find that the
performance with malloc is good enough, or at least that removing
malloc won't improve it enough to matter. In other words, there would
be no need to search for a non-malloc AVL implementation just yet.

(I almost wrote "malloc-free AVL implementation", but I realized that
would be ambiguous. })

 

[user923005]

If you followed my suggestion (which you may or may not choose to do),
you don't *need* a non-malloc AVL tree implementation until after
you've performed the measurements.  You might find that the
performance with malloc is good enough, or at least that removing
malloc won't improve it enough to matter.  In other words, there would
be no need to search for a non-malloc AVL implementation just yet.

(I almost wrote "malloc-free AVL implementation", but I realized that
would be ambiguous.  })

Something else to consider:
If it is not using malloc() then it is using either auto memory or
static memory.
If it is using auto memory, then it cannot fail gracefully (failure is
catastrophic and non-recoverable)
If it is using static memory then the size must be known before hand.
If the size is known before hand, we can use a much simpler structure
(e.g. load the data into an array, sort it, and use bsearch to find
it).

There are times when malloc() does something bad (e.g. malloc() is
painfully slow; e.g. malloc() fragments memory; etc.)
If malloc() is evil on your own platform, then allocate in huge blocks
write your own suballocator.

IMO-YMMV

 

[Phil Carmody]

(I almost wrote "malloc-free AVL implementation", but I realized that
would be ambiguous. })

Thanks for sharing that - I read it about 4 times before it
clicked!

Phil

 

[Richard Bos]

The topicality hypocrisy is very frustrating, but every time we point
it out, it doesn't seem to accomplish much. So I propose Plan B: Every
time Chuck or one of the other topicality hypocrites decides to pull
out the coffee mug, we'll take it as a cue that it's OK for us to do
the same thing. We'll spawn a subthread from the hypocrite's post
and talk about politics, the latest Linux/BSD news, fashion, books,
Hollywood, laundry techniques, Britney Spears, etc., with cross-posts
to the appropriate newsgroups.

Now, don't be cruel, Han. What has talk.politics.tibet ever done, to
deserve the likes of you?

Richard