How many derived classes is not too much ?

Hello All

We have a system where customer request (of text form) are processed.

The number of different request types is more than a thousand.

With current ( C-langauage ) design request a parsed, type of the
request is determined (and encoded as unsigned int)
and request data is packed in request specific structure.

Then processing function for this type of the request is looked up
in a table by binary search and this function is
called and request specific data is passed to it(as void*).


The system is now being rewritten in C++. Is it practical to
derive each request from a common base class and have virtual function
run()
instead of current 'processing' function?

Is virtual table lookup of such size as fast or faster then binary
search?
Is design with so many derived classes good in this situation?

Best regards, Konstantin Kivi

PS.
It comes to my mind, that Java programmers haven't first
option (as there is no pointer to function). So they
can use only second option.

konstantin.kivi@gmail.com wrote:[color=blue]
> Hello All
>
> We have a system where customer request (of text form) are processed.
>
> The number of different request types is more than a thousand.
>
> With current ( C-langauage ) design request a parsed, type of the
> request is determined (and encoded as unsigned int)
> and request data is packed in request specific structure.
>
> Then processing function for this type of the request is looked up
> in a table by binary search and this function is
> called and request specific data is passed to it(as void*).
>
>
> The system is now being rewritten in C++. Is it practical to
> derive each request from a common base class and have virtual function
> run()
> instead of current 'processing' function?[/color]

Yes, it probably is, and indeed this is a common use of inheritance and
virtual functions. You should look into the Command design pattern
(_Design Patterns_ by Gamma et al.) and object factories (e.g., the one
in chapter 8 of _Modern C++ Design_ by Alexandrescu).
[color=blue]
> Is virtual table lookup of such size as fast or faster then binary
> search?[/color]

You can't do a "virtual table lookup" as such. However, you could have
a (pure) virtual function (run, in your case) in a base class and then
any number of derived classes that implement it for specific types of
requests. What you need then is a way to create an instance of the
particular derived class that corresponds to a particular request. An
object factory will do that for you, but the factory will basically be
a fancy front end to a balanced binary tree lookup with search
complexity O( log N ) if implemented optimally.
[color=blue]
> Is design with so many derived classes good in this situation?[/color]

It can be.
[color=blue]
>
> Best regards, Konstantin Kivi
>
> PS.
> It comes to my mind, that Java programmers haven't first
> option (as there is no pointer to function). So they
> can use only second option.[/color]

I think you must misunderstand what virtual functions are. Java
certainly has the ability to override (pure) virtual functions. All the
pointers to functions and such are done behind the scenes in C++ and in
Java.

Cheers! --M

mlimber wrote:[color=blue]
> konstantin.kivi@gmail.com wrote:[color=green]
> > Hello All
> >
> > We have a system where customer request (of text form) are processed.
> >
> > The number of different request types is more than a thousand.
> >
> > With current ( C-langauage ) design request a parsed, type of the
> > request is determined (and encoded as unsigned int)
> > and request data is packed in request specific structure.
> >
> > Then processing function for this type of the request is looked up
> > in a table by binary search and this function is
> > called and request specific data is passed to it(as void*).
> >
> >
> > The system is now being rewritten in C++. Is it practical to
> > derive each request from a common base class and have virtual function
> > run()
> > instead of current 'processing' function?[/color]
>
> Yes, it probably is, and indeed this is a common use of inheritance and
> virtual functions. You should look into the Command design pattern
> (_Design Patterns_ by Gamma et al.) and object factories (e.g., the one
> in chapter 8 of _Modern C++ Design_ by Alexandrescu).
>[color=green]
> > Is virtual table lookup of such size as fast or faster then binary
> > search?[/color]
>
> You can't do a "virtual table lookup" as such. However, you could have
> a (pure) virtual function (run, in your case) in a base class and then
> any number of derived classes that implement it for specific types of
> requests. What you need then is a way to create an instance of the
> particular derived class that corresponds to a particular request. An
> object factory will do that for you, but the factory will basically be
> a fancy front end to a balanced binary tree lookup with search
> complexity O( log N ) if implemented optimally.[/color]
[snip]

For a simplified example of such a design, see this post:

http://groups.google.com/group/comp....d0d7f5d2dd6126

Cheers! --M

In addition to the other responses, you might also want to read
http://www.gotw.ca/publications/mill18.htm. If you follow it's
recommendations, you'd have something like:

class RequestSuperclass
{
public: void run();
private: virtual void _run() = 0;
};

void RequestSuperclass::run()
{
_run();
}


With regards to the object factory, I usually implement this using
static initialization to register creation functions to the factory so
as to minimize coupling between the factory and the classes it creates.

HTH,
Noel

First of all thank you for such a complete answer. I probably should
put the
question another way.

Is the code that compiler generate behind the scene to call correct
virtual
function effective enough if the number of derived classes is several
thousand.
This is emphasized in the subject.

The process of generating correct concret request processing class
must be simuler to our current design (filling correct data structure )
and is in fact already O(log N).

Concerning virtual function concept I have to say that
I have passed Brainbench C++ in 2000 and earned Master degree with
4.34 . The same cannot said about Written English, (it's only a second
language
for me ) :-)

Best regards, Konstantin Kivi

Konstantin Kivi wrote:
[color=blue]
> Is the code that compiler generate behind the scene to call
> correct virtual function effective enough if the number of
> derived classes is several thousand.[/color]

Let's say you have a setup like this:

struct HandlerBase { virtual void run() = 0; };
struct Handler42 : HandlerBase { void run(); };
HandlerBase* makeHandler(int requestType);

And you write this code:

HandlerBase* handler = makeHandler(42);
handler->run();

Then the pointee of handler has type Handler42, and calling run()
takes a single lookup in the pointee's vtable regardless of how many
other HandlerBase subclasses there are.


Martin

--
Quidquid latine scriptum sit, altum viditur.

That is - effective.
This is exactly what I hoped to hear:-)