Re: [boost] Re: Formal Review for Interval Library beginning

From: Guillaume Melquiond (gmelquio_at_[hidden])
Date: 2002-09-04 05:07:21

On Wed, 4 Sep 2002, Gennadiy Rozental wrote:

> > The library manipulates interval with closed bounds. But it doesn't mean
> > that it is not usable for intervals with open bounds; it's just a matter
> > of correctly choosing the base number type. Here is an example:
> >
> > [...]
> >
> > I only described one half of the addition in this example. But I hope it's
> > clear that it can be extended to the other operations and that it
> > correctly defines arithmetic operations on interval whose bounds are not
> > always included.
> 
> I think it should be part of the library implementation and interface.
> Tweaking rounding policy to achieve open intervals does not seem for
> end-user obvious IMO.

It's not a question of tweaking the rounding policy. It's a question of
using a new base type, because you need additional capabilities. And
because you define a new type, you also need to define operations on this
type; and it's the purpose of the rounding policy.

My purpose wasn't to show that the library can deal with this particular
case. I just wanted to explain that the library can be used in a lot of
situation if you give it a bit of thought. It really is a library for
general use.

> I must admit that I may be underestimate the complexity of some operation
> over list of pairs, but:
> 1. It's implementation details. The main question is should Interval library
> support this notion or not. Not how to implement it.

Maybe I was not clear enough when I was explaining the situation. It's not
only a matter of implementation detail. There is also an huge impact on
the interface.

Indeed, you must provide the library with a lot of information. For
example, what must be the underlying structure? Lists, heaps,
trees? Should they be sorted or not? Should overlapping be forbidden? How
will the memory be allocated for all these complex structures? etc.

Moreover, a lot of the functions of the library will not work
anymore. What about lower, upper, median, bisect, width, etc?
How will you extract an interval of the structure? How will you add an
interval to the structure?

The library was meant to provide a C++ framework in the STL-style to all
the people that were using other interval libraries. In some cases, it was
designed to replace them. In other cases, it was only supposed to provide
an interface to the implementation offered by other libraries (for
example, MPFI is a good C interval library, and the Boost library could be
easily used to provide an interface to its functionalities).

So, if we add all you seem to expect from an interval library, the whole
purpose of this library will be lost. It won't offer anymore a
standardized interface to interval arithmetic.

> 2. This problem a not new. I pretty sure that there are already algorithms
> in a field that do the job pretty efficiently. So you won't need to invent
> the wheel.

I didn't say I had to reinvent the wheel. I just wanted to say that the
complexity of such an implementation should be the object of a library
built on the top of this one rather than added to the library (which is
already quite complex).

> 3. Whatever algorithms you will implement it most probably (I think) will
> be better if any non-specialist person will start to implement it from
> scratch using your simple Interval as a base.

Do you really think a non-specialist person will want to use
multi-interval values rather than plain old intervals? :-)  Multi-interval
values are something really specific and using it the general case would
be like using a sledgehammer to crack a nut.

> 4. It's obvious that if we use list of pairs instead of one pair all the
> operation with intervals will take more time. But what if problem require
> namely multi-interval values.

Just use a specialized library. :-)
You don't expect this library to directly be able to do the static
analysis of a program, or have functions able to solve a 100x100
inequations system, do you?

> 5. Independent from how you implement algorithms working over list of pair
> single pair intervals won't be affected in terms of performance More exactly
> should not. Even more exactly may be affected but difference should be
> negligible.

Yes, if we were living in the best of the worlds, it would probably be
true. But first, think about compile-time. This library (4000 lines
long) is already a pain to compile; what will be the compile-time when it
will be 10 times bigger?

Now, let's speak about runtime performance. Actually, the substraction is
defined in a few lines and it can be inlined with just three asm
instructions. What if, because your new function would suddenly be 500
lines long due to the complex list manipulations, the compiler suddenly
decides to no more inline the function. I have made some tests; what you
call "negligible" makes a scientific program two to three times slower.

> So real question still: does the problem justify the efforts needed to solve
> it?

Sorry, I don't understand your question. But I suppose you have understood
that I think it is really not the job of this library to support such a
monster (on the implementation point of view, and on the interface point
of view!).

> I still convinced that support for multy-pair intervals is essential. It may
> become more clear once we will see the results of domain analysis I proposed
> in other post.
> 
> Gennadiy.

Regards,

Guillaume