axis-c-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Kenneth Chiu <ch...@cs.indiana.edu>
Subject RE: STL elimination - Suggestions
Date Wed, 02 Jun 2004 11:38:30 GMT
On Wed, 2 Jun 2004, Roshan Weerasuriya wrote:
> hi Kenneth,
>
> Thanks for your comments.
>
>  >What is the intended use of AxisMap?  Note that
>  >insertion/lookup is now O(N), rather than O(lg N).  Creating
>  >a map is now O(N^2)
>
> Can you elaborate more on this?

Sure.  To insert something in the map, you are doing

    for (int i=0; i < m_iCurrentPosition; i++) {
	if (m_pKeys[i]) {
	    if (pCompareFunction(pKey, m_pKeys[i])) {
		bKeyFoundStatus = true;
		if (m_pValues[i]) {
		    delete m_pValues[i];
		    m_pValues[i] = NULL;
		}
		m_pValues[i] = pValue;
	    }
	}
    }

This basically scans through the current keys, looking for
the key to insert.  If not found, you put it at the end.
This algorithm is O(M), or linear, where M is the number of
items in the map.  If you want to insert N items, the total
time is going to be quadratic, or O(N^2).

The std::map, on the other hand, has guaranteed O(lg M)
insertion time, which means that the build time is
guaranteed O(N lg N).

The situation is similar for lookup.

For a few items, it's not going to matter.  For many items,
it will start to matter.  The point at which it will start
to matter will depend on your usage patterns.

>  >The heavy use of 'void *' means that you are no longer
>  >type-safe
>
> Can you elaborate more on this?

This just means that there are lots of opportunities for
type errors.  For example, suppose you have two classes, Tag
and Element.  Suppose you have a map that contains Tag
objects.  Suppose you accidentally insert an Element object.
You will get no warning from the compiler, because you are
using void *.  Or suppose when you are creating the map, you
accidentally pass in the dealloc function for Element
objects instead of Tag objects.  Again, no warning from the
compiler.

The downside of templates is mainly that the error messages
from the compiler are harder to interpret.  The upside is
that they are type-safe.  There is probably a happy medium
somewhere between heavy use of templates (which can also
slow down compiles), and use of 'void *'.

The downside of RTTI is that it requires all classes
involved to share a common base class.  (C++ has no Object
class.)  Performance may also be a concern, in some
situations.  The upside is that it's run-time type-safe if
you use dynamic_cast.  You will get an immediate abort
instead of some hard-to-track-down random error.

>
>  >In AxixMap::put(), you delete a "void *". Do you mean to
>  >call the value dealloc function instead?
>
> Yes it is a mistake.
>
>  >In ~AxisMap(), you are using the pre-ISO scoping rules for
>  >for-loops.
>
> Corrected it.
>
> rgds,
> Roshan
>
>
>
>
> At 09:39 AM 6/1/2004 -0500, you wrote:
> >On Tue, 1 Jun 2004, Roshan Weerasuriya wrote:
> > > hi all,
> > >
> > > Please have a look at the AxisMap class implemented below and provide your
> > > comments. The implementation files are attached with this mail. The
> > > attachement includes:
> > > 1) AxisMap.h, AxisMap.cpp       //AxisMap implemntaion
> > > 2) AxisMapUtils.h, AxisMapUtils.cpp //Utility methods such as Standard
> > > De-allocator funcitons
> > > 3) TestMap3.cpp  //The sample cpp file which includes example usage of the
> > > above AxisMap implementation
> > >
> > > The idea is to eliminate stl map from the code base and use Axis's own
> > > AxisMap implementation.
> >
> >Some comments:
> >
> >What is the intended use of AxisMap?  Note that
> >insertion/lookup is now O(N), rather than O(lg N).  Creating
> >a map is now O(N^2).  Fine if you don't plan on putting a
> >lot in it.  Otherwise it might be a performance problem.
> >
> >Also, if you are going to be putting a lot of things in it,
> >you might consider growing exponentially.
> >
> >I suggest trying to make the interface look like STL.  Many
> >experienced C++ programmers will already be familiar with
> >STL, which would save them from having to learn yet another
> >interface.
> >
> >The heavy use of 'void *' means that you are no longer
> >type-safe.  I would personally prefer either the use of
> >polymorphism and RTTI, or templates.
> >
> >In AxixMap::put(), you delete a "void *".  Do you mean to
> >call the value dealloc function instead?
> >
> >In ~AxisMap(), you are using the pre-ISO scoping rules for
> >for-loops.
> >
> >
> >
> > > rgds,
> > > Roshan
> > >
> > > At 10:13 AM 5/6/2004 +0530, you wrote:
> > > >What I would suggest -
> > > >1. expose a small set of classes and make the interface stl-free
> > > >2. in your internal classes you can still use stl
> > > >
> > > >Why do you want to remove stl all-together?
> > > >
> > > > > -----Original Message-----
> > > > > From: Kenneth Chiu [mailto:chiuk@cs.indiana.edu]
> > > > > Sent: Thursday, May 06, 2004 9:41 AM
> > > > > To: Apache AXIS C Developers List
> > >
>
>
>

Mime
View raw message