Binary tree

[karthikbalaguru]

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

So, kindly let me know a Binary tree that
will help in overcoming the above problem ?

Thx in advans,
Karthik Balaguru

 

[Ben Bacarisse]

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

So, kindly let me know a Binary tree that
will help in overcoming the above problem ?

Why change if you know (or suspect) it will be slower? How do you
know that there will be a problem with using dynamic allocation?

The choice of the right data structure for any given application is
complex and there is just not enough information here to give anything
by very general advice. So in that spirit: dynamic data structures
are often worth implementing. The extra cost of memory allocation is
often insignificant compared to the gains to be had from a fast
algorithm.

 

[user923005]

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

So, kindly let me know a Binary tree that
will help in overcoming the above problem ?

I suggest
Ben Pfaff is likely to answer, and he's a real tree expert.

For fast, disk based trees, I doubt if you will beat this groovy
thing:
http://sourceforge.net/projects/stxxl/

If you are determined to use binary trees, and they need to stay in
memory, I would suggest the use of a self-balancing tree structure,
because they are less prone to perverse cases (e.g. all the data
arrives in order and you get a linear list).

Also, a memory efficient skiplist is another good idea. Fast and
stingy on memory use. You can find one on sourceforge.

HTH

 

[Ben Pfaff]

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

Have you really measured dynamic memory allocation to be too
slow, or are you just worried that it is too slow? If it is the
latter, I would try it first, to see.

You can implement balanced binary tree without dynamic memory
allocation. Here is one example:
http://git.savannah.gnu.org/cgit/pspp.git/tree/src/libpspp/bt.h
http://git.savannah.gnu.org/cgit/pspp.git/tree/src/libpspp/bt.c
http://git.savannah.gnu.org/cgit/pspp.git/tree/tests/libpspp/bt-test.c
Note how the implementation in bt.[ch] does not use dynamic
memory allocation at all.

 

[Ben Pfaff]

Ben Pfaff is likely to answer, and he's a real tree expert.

Heh, now I *have* to give an answer I guess

 

[Chris M. Thomasson]

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

So, kindly let me know a Binary tree that
will help in overcoming the above problem ?

You can use a static buffer to allocate the nodes from. Since you were using
a static array, I assume that your database is finite in size. Here is a
static region allocator that can operate on a buffer of your choice:

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

You may find it fairly useful. Also, you can use this in conjunction with a
freelist which will give you the ability to reuse individual nodes, not just
an entire region of them at a time.

 

[Kaz Kylheku]

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

So, kindly let me know a Binary tree that
will help in overcoming the above problem ?

As a programming newbie, you should worry about getting it right, not about
performance.

If the performance truly was critical, the development task would have been
assigned to someone who doesn't need continuous help from comp.lang.c.

 

[CBFalconer]

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

So, kindly let me know a Binary tree that will help in overcoming
the above problem ?

Well, I could recommend a couple of self balancing trees. But that
would require that you read the literature, and our experience here
is that you don't bother.

 

[karthikbalaguru]

I suggest

I have started a specific thread w.r.t AVL
trees without malloc in comp.programming /
comp.lang.c

Ben Pfaff is likely to answer, and he's a real tree expert.

For fast, disk based trees, I doubt if you will beat this groovy
thing:http://sourceforge.net/projects/stxxl/

If you are determined to use binary trees, and they need to stay in
memory, I would suggest the use of a self-balancing tree structure,
because they are less prone to perverse cases (e.g. all the data
arrives in order and you get a linear list).

Also, a memory efficient skiplist is another good idea.  Fast and
stingy on memory use.  You can find one on sourceforge.

Interesting,
I found some info from the below link
http://en.literateprograms.org/Skip_list_(C)#chunk def:Allocate memory for SkipSet
But is there any skiplist implementation in C that
does not use malloc ?

Thx in advans,
Karthik Balaguru

 

[user923005]

I have started a specific thread w.r.t AVL
trees without malloc in comp.programming /
comp.lang.c





Interesting,
I found some info from the below linkhttp://en.literateprograms.org/Skip_list_(C)#chunk%20def:Allocate%20m...
But is there any skiplist implementation in C that
does not use malloc ?

No. Not in C anyway. I imagine that there are some examples in GC
languages like Java and .NET

P.S.
I think the probability is very close to 1.0 that you are curing a
disease that does not exist.

 

[karthikbalaguru]

You can use a static buffer to allocate the nodes from. Since you were using
a static array, I assume that your database is finite in size. Here is a
static region allocator that can operate on a buffer of your choice:

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

You may find it fairly useful. Also, you can use this in conjunction with a
freelist which will give you the ability to reuse individual nodes, not just
an entire region of them at a time.

How much percentage is this faster than malloc ?

(I have other related groups also in loop)

Thx in advans,
Karthik Balaguru

 

[karthikbalaguru]

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

Have you really measured dynamic memory allocation to be too
slow, or are you just worried that it is too slow?  If it is the
latter, I would try it first, to see.

You can implement balanced binary tree without dynamic memory
allocation.  Here is one example:
       http://git.savannah.gnu.org/cgit/pspp.git/tree/src/libpspp/bt.h
       http://git.savannah.gnu.org/cgit/pspp.git/tree/src/libpspp/bt.c
       http://git.savannah.gnu.org/cgit/pspp.git/tree/tests/libpspp/bt-test.c
Note how the implementation in bt.[ch] does not use dynamic
memory allocation at all.

I find this to be very useful
Interesting link .

But, how much percentage is this code faster
than that of the malloc based tree ?

Thx in advans,
Karthik Balaguru

 

[user923005]

Have you really measured dynamic memory allocation to be too
slow, or are you just worried that it is too slow?  If it is the
latter, I would try it first, to see.

You can implement balanced binary tree without dynamic memory
allocation.  Here is one example:
       http://git.savannah.gnu.org/cgit/pspp.git/tree/src/libpspp/bt.h
       http://git.savannah.gnu.org/cgit/pspp.git/tree/src/libpspp/bt.c
       http://git.savannah.gnu.org/cgit/pspp.git/tree/tests/libpspp/bt-test.c
Note how the implementation in bt.[ch] does not use dynamic
memory allocation at all.

I find this to be very useful
Interesting link .

But, how much percentage is this code faster
than that of the malloc based tree ?

Unless you have a truly terrible implemenation of malloc(), the O(f
(N)) property of the algorithm is dominantly more important than the
speed of malloc().

If there is a terrible implementation of malloc() then it is not hard
to write your own suballocation scheme.

I guess your project is going to be a disaster. You are focusing on
the wrong thing for sure. That is a very, very bad sign.

 

[Chris M. Thomasson]

How much percentage is this faster than malloc ?

(I have other related groups also in loop)

What particular memory allocation algorithm do you have in mind? There are
so many. Alls I can say is that if you pass the region allocator a buffer
residing on the "stack", or even global buffer (e.g. threading aside for a
moment), it will make ZERO system calls. Keep in mind that there are malloc
implementation that have very little overheads; I have created some of
them...

However, if your on an embedded system, I would simply create a static
buffer, then create a fine-grained amount of regions, and feed offsets of
the buffer to them. This can be made to work in certain scenarios. Region
allocation is sort of a go between wart calling malloc/free on every
allocation or GC. Regions are no silver bullet in any way, shape or form;
its a simple tool. Use the right tool for the job.

 

[Ben Pfaff]

But, how much percentage is this code faster
than that of the malloc based tree ?

It's your job to figure out what is the best choice. You can't
expect others to spend time benchmarking for you.

 

[Chris M. Thomasson]

But ,how important is the speed of an event
which only occurs once during the life
of each node?

Are you referring to allocating each node individually? I have experience
significant bottlenecks and performance issues with stock malloc
implementations. However, this was due to multi-threading synchronization
issues. FWIW, I personally would never use malloc to create a single node.
Even if the malloc implementation was perfect and incurred zero-overheads...