[ANN] NTL "Nonstandard Template Library"

[Mirek Fidler]

We would like to introduce the NTL, "Nonstandard Template Library", at

www.ntllib.org

NTL is meant as either extension or even replacement for STL. We believe
that NTL provides significantly better productivity and performance over
STL.

NTL was created to solve following problems we used to encounter when
using
STL:

Copy-constructible requirements
---------------------------------
STL requires the elements stored in containers to meet the requirements
of
copy-constructible and assignable types. This causes two problems:
- Elements that do not satisfy these requirements cannot be directly
stored
in STL containers.
- For many types of elements, including STL containers themselves,
copy-constructor and assign operator is a very expensive
operation, that is why often they cannot be stored in STL containers
effectively.
NTL addresses this problem by introducing Vector and Array flavors of
containers (www.ntllib.org/overview.html, www.ntllib.org/moveable.html).

Value transfer
--------------
Content of STL containers can be transfered only using expensive
deep-copy
constructor/assigment operator. This causes performance problems
especially
when using STL containers as function return values, but lack of better
functionality is missing elsewhere too. NTL provides transfer semantics
concepts to deal with this problem. (www.ntllib.org/pick.html)

Random access and random access notation
---------------------------------------------
STL uses iterators as the preferred way how to access and identify
elements
in containers. While this is generally the most generic way, real-life
problems often require or at least benefit from random access using
indices.
NTL provides fast random access to all kinds of containers and NTL
interfaces prefer notation using indices. As a side effect, NTL user can
completely avoid using iterators in favor of indices, which in current
C++
results in much simpler and less verbose syntax (using modern optimizing
compilers there is no difference in performance).

Index
------
A completely new type of associative container, Index, is introduced, as
an
ideal building block for all kinds of associative operations.
(www.ntllib.org/aindex.html)

Algorithm requirements
------------------------
Requirements of STL algorithms are very loosely defined. NTL tries to
provide more specific requirements and also minimal ones. This allows
e.g.
direct sorting of Array of polymorphic elements.

Minor improvements
---------------------
There are also some minor improvements like
- Besides reserve present in STL, NTL provides also Shrink method to
minimize a container's memory consumption.
- Iterators can be assigned a NULL value.
- Associative containers are based on hashing to provide better
performance.
Utility classes and functions are provided to support building correct
hashing functions.

 

[tom_usenet]

We would like to introduce the NTL, "Nonstandard Template Library", at

www.ntllib.org

NTL is meant as either extension or even replacement for STL. We believe
that NTL provides significantly better productivity and performance over
STL.

I've got a few comments, after a look through your site.

NTL was created to solve following problems we used to encounter when
using
STL:

Copy-constructible requirements
---------------------------------
STL requires the elements stored in containers to meet the requirements
of
copy-constructible and assignable types. This causes two problems:
- Elements that do not satisfy these requirements cannot be directly
stored
in STL containers.
- For many types of elements, including STL containers themselves,
copy-constructor and assign operator is a very expensive
operation, that is why often they cannot be stored in STL containers
effectively.
NTL addresses this problem by introducing Vector and Array flavors of
containers (www.ntllib.org/overview.html, www.ntllib.org/moveable.html).

Your moveable concept is of course undefined behaviour for non-pod
types, although, as you say, it will tend to work for quite a large
number of non-pod types.

For nicer, portable versions of the moveable concept, see this
possible future language feature:
http://std.dkuug.dk/jtc1/sc22/wg21/docs/papers/2002/n1377.htm
and this library solution:
http://www.cuj.com/documents/s=8246/cujcexp2102alexandr/

Random access and random access notation
---------------------------------------------
STL uses iterators as the preferred way how to access and identify
elements
in containers. While this is generally the most generic way, real-life
problems often require or at least benefit from random access using
indices.
NTL provides fast random access to all kinds of containers and NTL
interfaces prefer notation using indices. As a side effect, NTL user can
completely avoid using iterators in favor of indices, which in current
C++
results in much simpler and less verbose syntax (using modern optimizing
compilers there is no difference in performance).

I don't see any difference from the STL here, which also provides
indexing for random access containers. What does your library provide
here that the STL doesn't?

Value transfer
--------------
Content of STL containers can be transfered only using expensive
deep-copy
constructor/assigment operator. This causes performance problems
especially
when using STL containers as function return values, but lack of better
functionality is missing elsewhere too. NTL provides transfer semantics
concepts to deal with this problem. (www.ntllib.org/pick.html)

Your solution of using "pick" is horrible and extremely error prone
compared to the approach taken by the Mojo library (see the link
above).

Algorithm requirements

In what way? Do you mean that the implementation of the algorithms is
loosely defined by the standard, or that the requirements of the
objects you pass to the algorithms are loosely defined?

NTL tries to

provide more specific requirements and also minimal ones. This allows
e.g.
direct sorting of Array of polymorphic elements.

In what way are the requirements more specific for your algorithms
that for the standard ones?

Why do you have your own swap and iterator swaps? This means that
users have to remember to specialize both Swap and std::swap for their
types.

Minor improvements

That's a worthwhile addition, although the STL has the well-known
shrink to fit idiom.

- Iterators can be assigned a NULL value.

To achieve this your iterators are less efficient than the STL
alternative (possibly depending on the compiler). Also, you provide
operator bool, which enables such nonsense as:

it i3 = i1 + i2; //i2 converted to bool, then int, for operator+.

Consider providing operator const void* instead.

- Associative containers are based on hashing to provide better
performance.

Sorted containers have more predictable performance - most hash maps
degenerate into linear lists if the hashing algorithm doesn't
differentiate the data well.

It is a good idea to provide both hashed and sorted so the user can
decide.

Tom

 

[Chris Jefferson]

....

Indexing for ALL containers. Or, ALL containers are random access.
Including Index/ArrayIndex (which covers functionality of set and
multiset) and VectorMap/ArrayMap (covers map and multimap).

I don't really understand this..

can't I already index over every random access container? also I find
having non-random access containers to be very useful. Do you have none
at all? As then I expect some of my code is going to become harder to
write, or quite inefficent, as I'm not sure how random-access containers
can be compatable with O(1) insertion in the middle of functions.

Also, I'd be interested to have an example of STL's
not-sufficently-exacty specification of how long functions take to run,
I thought they were as accurate as you could get except in a couple of
places.

Chris

 

[Mirek Fidler]

Indexing for ALL containers. Or, ALL containers are random
access.

I don't really understand this..

can't I already index over every random access container? also I find
having non-random access containers to be very useful. Do you have none
at all?

Yes. Only container without random access is One and that cannot
store more than one element

As then I expect some of my code is going to become harder to
write, or quite inefficent, as I'm not sure how random-access containers
can be compatable with O(1) insertion in the middle of functions.

Sure, it is impossible. OTOH, I believe that O(1) insertion for
std::list is no that big win as everybody expects - first of all, you
must know WHERE to insert - and finding such a place involves iteration
that usually spoils any benefits of O(1) insert. In any case, std::list
iteration is slower than NTL Vector Insert.

Also, I'd be interested to have an example of STL's
not-sufficently-exacty specification of how long functions take to run,
I thought they were as accurate as you could get except in a couple of
places.

Hm, I do not exactly understand what are you speaking about here and
if I do, I do not know how this relates to NTL. Anyway if you are
speaking about O(x) specification, all I can tell you that they usually
say about real performance pretty little. On modern CPU, too much is
driven by CPU caches, TLB, memory bandwith and so on. That is why I
believe only to empiric benchmarks.

Mirek

 

[tom_usenet]

Yes. OTOH, actual memcpy is library implementation thing - let us
say that if you will follow requirements for moveable, library will do
its job. You are not required to perform memcpy of non-PODs yourself...
Your contract is between you and library, not between you and undefined
behaviour.

It would be nice if the standard were to allow memcpy on a larger
number of types than just PODs, but I understand why it doesn't - it
might limit what constructors can do or effect garbage collectors.

Incidently, why don't you use malloc/realloc to gain a bit more
performance?

These are of course well known to me. But please do differentiate
between moveable concept and transfer semantics. Above proposals and
techniques are about transfer semantics - they can be used for what
moveable is aimed to, but they are less effective in that (about 50%
slower).

Transfer and move are just two versions of the same concept. Your
"moveable" is just a destructive move, and your "transfer" is a
non-destructive move. Both possibilities are being considered for the
next standard, although destructive moves bring problems with base
classes (One way or another you end up with an object with a
destructed base part but constructed derived part - a "lame duck"
object).

As for "&& proposal", I welcome it a lot - but it is just a proposal
! You will not be able to use it until 2008 at least. And I will be
extremly happy to replace that ugly "pick_" by "&&" then.

As for MOJO, it is very nice idea, but cannot be effectively used
for client types - it is horrible hard to MOJOize class, at least
compared with no costs to implement default pick constructor (at least
for composite class).

Still, a pick constructor can cause unexpected problems, since it
gives you move semantics without requiring anything explicit from the
user.

Indexing for ALL containers. Or, ALL containers are random access.
Including Index/ArrayIndex (which covers functionality of set and
multiset) and VectorMap/ArrayMap (covers map and multimap).

I agree that non-random access containers are of fairly rare utility,
but the main benefit of them is the fact that
references/pointers/iterators to elements aren't invalidated by
modifications to the container. I assume your containers can't offer
this guarantee except in a few circumstances.

I know MOJO rather well. I agree that from first encounter, "pick_"
seems like weak point of NTL - but problem is that current C++ gives us
no better option.

Anyway, pick transfer semantics is nothing new - auto_ptr has it for
years.

Well, it had it, but before the standard was released they settled on
semantics much more similar to mojo, with the auto_ptr_ref. I think
MSVC6 has the pre-standard implementation that had a mutable pointer.
The committee decided that this code was just too dangerous:

void foo(auto_ptr<int> p);

const auto_ptr<int> p(new int(10));
foo(p);
//here const auto_ptr has changed!

and so changed to the cunning rvalue detection mechanism now employed
(using auto_ptr_ref).

Obviously your pick thing suffers the same problem.

Requirements for iterators passed to algorithms are loosely defined.
What are e.g. requirements for iterators and types pointed to by
iterators for std::sort ?

std::sort requires random access iterators.

Important thing here is that NTL Sort requires just IterSwap to be
defined and ordering predicate, nothing more.

But surely that limits your possible implementations? A basic
quicksort is terrible in pathological cases (O(n*n)), and I believe
many of the alternatives require more than IterSwap.

std::sort sometimes

requires iter_swap, sometimes it requires copy contructor, sometimes
swap - based on implementation. Standard is completely silent about it.

None of these cause problems though - iter_swap is defined for all
iterators, even user defined ones (it should call std::swap on the
elements by default, although some implementations manually swap the
values - a defect report states that it must swap).

Basically, you need copy constructible, assignable elements (as
required by containers), with std::swap optionally specialized to
possibly improve performance.

Why ? Is there any technical reason ?

Just that your iterators carry around both a container and an index,
whereas usually random access iterators just carry around a pointer.

Anyway, NULL is just very

minor improvement, you do not need iterators in NTL

Without iterators you often need to write the same algorithm several
times. e.g. you can partition anything with forward iterators (like a
singly linked list), but if you write the algorithm for your random
access containers, you'll just have to write it again if you need it
for anything else. In addition, iterators give you a point of
interception for transformations of elements. See the boost iterator
adapters library.

Iterators and algorithms are the central part of the STL - the
containers are separate and not intended to be exhaustive. By all
means create new containers (with different implementations), but you
may as well provide optimal iterators to go with them (e.g. hold a
pointer rather than a container and an index).

Yes. That is why things like GetHashValue, mem_hash and CombineHash
exist in NTL to support creating right hashing functions.


Hm, strange thing is that AFAIK any other languge known to me (PHP,
Perl, Java, C#) uses hashing, only C++ uses binary trees. So either C++
library designers know something that is unknown to the rest of computer
science or hashing is better. (Well, I know that in fact hashing should
have been part of library but proposal was too late).

Java provides both (HashSet, TreeSet), but I don't know the other
languages.

Tom

 

[Mirek Fidler]

Your contract is between you and library, not between you and
undefined

It would be nice if the standard were to allow memcpy on a larger
number of types than just PODs, but I understand why it doesn't - it
might limit what constructors can do or effect garbage collectors.

Yes, but that is why there is the Moveable concept. NTL brings
rather precise requirements for Moveable types.

Incidently, why don't you use malloc/realloc to gain a bit more
performance?

What for ?

If you think using malloc instead of new can bring any performance,
you are wrong.

If you expect ANYTHING from realloc than copying to another region
of memory (because that is what will happen with modern memory
allocators, which maintain fixed size blocks), you are wrong too.

Transfer and move are just two versions of the same concept. Your
"moveable" is just a destructive move, and your "transfer" is a
non-destructive move.

Of course, it is not. But perhaps it is just termimology problem. In
my terms, "moveable" are types that can be moved in memory without
problems (e.g. using memcpy).

Transfer semantics is about types that have "move constructors" (to
distinguish this from moveable, we call them "pick constructors"), but
not only about them. It is rather classification of possibilites with
respect to behaviour when transfered.

There is sure some intersection between two terms, but it is
definitely not the same thing. It is not hard to imagine type with pick
transfer semantics that is not moveable.

Also, it can be explained like that "moveable" is about internal
managment of object inside containers, "transfer semantics" is about int
erface behavior.

Still, a pick constructor can cause unexpected problems, since it
gives you move semantics without requiring anything explicit from the
user.

Well, I thing that using NTL could be described as "something
explicit"

I agree that non-random access containers are of fairly rare utility,
but the main benefit of them is the fact that
references/pointers/iterators to elements aren't invalidated by
modifications to the container. I assume your containers can't offer
this guarantee except in a few circumstances.

Sure they can. That is what Array flavor is about. (Well, it does
invalidates references, but in NTL this does not matter anyway). All
ADTs have Vector (perfomance, requires elements to be moveable) and
Array (generic, no requiremnt at all) flavors. BTW, Array flavor is even
more capable, as it can directly store even polymorphic types.

Well, it had it, but before the standard was released they settled on
semantics much more similar to mojo, with the auto_ptr_ref. I think
MSVC6 has the pre-standard implementation that had a mutable pointer.
The committee decided that this code was just too dangerous:

void foo(auto_ptr<int> p);

const auto_ptr<int> p(new int(10));
foo(p);
//here const auto_ptr has changed!

and so changed to the cunning rvalue detection mechanism now employed
(using auto_ptr_ref).

Obviously your pick thing suffers the same problem.

Well, I agree that possibility of changing const object is pretty
awful. But if only there would be simple way in C++ to avoid this !
There simply is not. I was searching for it for last two years. Best you
can get is MOJO, but it is so unpractical for client types....

OTOH, actual errors that this violation brings are pretty rare and
almost immediately catched by runtime assertions. Now we have about 20MB
of codebase using NTL and problem really is not that big as standard
comitee thinks... And there is also nice plan to replace "pick_" by "&&"
in the moment it is possible.

Anyway, if you can for the moment forget about how awful it is, look
at MOJO article and notice one thing - everything that Andrei wishes in
the prolog of article is flawlessly possible in NTL.

So as ever, it is tradeoff. You must be a little bit more careful
when typing "=", but you get a lot !

std::sort requires random access iterators.

Yes. But there is nowhere defined what are requirements for types
pointed to by them.

But surely that limits your possible implementations? A basic
quicksort is terrible in pathological cases (O(n*n)), and I believe
many of the alternatives require more than IterSwap.

No, it does not. IterSwap is all you need. During extensive testing
we found only type of element that slightly benefits from copy
constructor in Sort, and that is "int". It is better to solve this
anomaly by specialization and leave Sort requirements for types minimal.

Basically, you need copy constructible, assignable elements (as
required by containers), with std::swap optionally specialized to
possibly improve performance.

Yes. But in reality, you really need just IterSwap and ordering
predicate. Nothing more.

What you get is possibility to Sort types without deep copy
constructor. That is worth it.

Just that your iterators carry around both a container and an index,
whereas usually random access iterators just carry around a pointer.

No, that is true for some containers where there is no performance
difference to simplify implementation, but e.g. Array and Vector
iterators are as fast as possible.

Anyway, NULL is just very

Without iterators you often need to write the same algorithm several
times. e.g. you can partition anything with forward iterators (like a
singly linked list), but if you write the algorithm for your random
access containers, you'll just have to write it again if you need it
for anything else.

Yes. But trick is that I do not need them for anything else

In addition, iterators give you a point of
interception for transformations of elements. See the boost iterator
adapters library.

Anyway, I did not said that iterators are wrong, NTL supports them
and NTL algorithms use them. I just wanted to say that as a side effect,
you do not need to use them if you do not wish (and I bet you would not,
after several months of using NTL

Iterators and algorithms are the central part of the STL - the
containers are separate and not intended to be exhaustive. By all

Yes. Strange thing is that most of time I am programming, I do need
containers, not iterators or algorithms, to solve my problems....

means create new containers (with different implementations), but you
may as well provide optimal iterators to go with them (e.g. hold a
pointer rather than a container and an index).

Your brief examination of NTL implemention is wrong (anyway, I
appreciate you took time to examine actual sources . If it has sense
for performance reasons (Vector, Array, Index, all maps), I do provide
optimal iterators. Yes, there are containers where I use simple approach
(Segtor, BiVector, BiArray containers), but I have measured that
performance-wise, there is no difference. Also, it is an implementation
detail, it might change it in future if I see any sense in doing that.

Mirek

 

[Mirek Fidler]

Sure they can. That is what Array flavor is about. (Well, it does

invalidates references, but in NTL this does not matter anyway). All

Damn it... It invalidates iterators, not references !

Mirek

 

[tom_usenet]

Yes, but that is why there is the Moveable concept. NTL brings
rather precise requirements for Moveable types.

Those requirements are non-standard requirements that you've
determined empirically on the basis of a couple of compilers and your
experience. There may be compilers for which they don't hold true.
Your types break the requirements in several ways (you seem to think
it is only the presence of a destructor that causes the problem) -
1. access specifiers (which allow the compiler to reorder members, but
this shouldn't cause a problem for memcpy)
2. base classes, which might conceiveable lie outside the bytes on the
object. e.g. the base class might be allocated from a special base
class dynamic pool for no good reason I can think of, but the standard
allows it.
3. constructors. The moved objects haven't been constructed in situ,
so if the the compiler makes constructors do anything clever or
non-obvious then your memcpy would break.
4. destructors. Similar to constructors - destruction might require
something special.

I don't know of any platforms where the memcpy will do anything but
the obvious, but you never know. From a search of google groups, I've
not seen any good reason for the code to fail on current compilers.

What for ?

If you think using malloc instead of new can bring any performance,
you are wrong.

No, I didn't think that, it's just that you can use realloc with
malloc, but not with new.

If you expect ANYTHING from realloc than copying to another region
of memory (because that is what will happen with modern memory
allocators, which maintain fixed size blocks), you are wrong too.

Are you so sure that no common implementations provide a benefit for
realloc!? As it happens, you're wrong on the compilers I have access
to (the same ones as you I think).

Try this program, apparently you will be surprised by the results:

#include <stdlib.h>
#include <iostream>

int main()
{
void* p = malloc(1);
int moves = 0;
for (int i = 2; i < 100000; ++i)
{
void* newp = realloc(p, i);
if (newp != p)
{
p = newp;
++moves;
}
}
free(p);
std::cout << moves << '\n';
}

I got VC 7.1 only moving the memory twice.

Of course, it is not. But perhaps it is just termimology problem. In
my terms, "moveable" are types that can be moved in memory without
problems (e.g. using memcpy).

Your concept of moveable is just a specific version of the more
general concept of destructively moveable types - that is, the move
causes the destruction of the source, so that you mustn't run the
destructor on the source explicitly.

Your move loop (start stuff removed):

int end = start + items;
memcpy(newvector, vector, items * sizeof(T));
delete[] (byte *) vector;

could equally well be written:

int end = start + items;
for (int i = 0; i != items; ++i)
{
destructive_move(vector + i, newvector + i);
}
delete[] (byte *) vector;

If destructive_copy is inlined, then you aren't going to see much
difference in performance, and it gives you the benefit of allowing
your destructive copy to do something special if necessary. e.g. the
default would look like this:

template <class T>
void destructive_move_default(T* source, T* dest)
{
new (dest) T(*source);
source->~T();
}

but for moveable types (including all PODs) you'd have:

template <class T>
void destructive_move_memcpy_safe(T* source, T* dest)
{
memcpy(dest, source, sizeof *source);
//no destructor call
}

for my special type:
template<>
void destructive_move<Special>(Special* source, Special* dest)
{
//whatever
}

and then select between them using traits (obviously this can be
implemented in a number of ways). With a decent memcpy implementation
(e.g. compiler inserted inline assembler) this should be just (or at
least almost) as fast as big memcpy version, but it has the benefit of
allowing non-memcpy moving too.

If you really wanted to do a block memcpy (perhaps because of a poor
optimizer), then you could easily provide two implementations of the
method selected using the same traits - one that just did the block
memcpy, and one that did it one element at a time.

Transfer semantics is about types that have "move constructors" (to
distinguish this from moveable, we call them "pick constructors"), but
not only about them. It is rather classification of possibilites with
respect to behaviour when transfered.

Right, this is more like the && proposal and Mojo - pick is a type of
non-destructive move - the source is left in a constructed state, so
still must be destroyed.

There is sure some intersection between two terms, but it is
definitely not the same thing. It is not hard to imagine type with pick
transfer semantics that is not moveable.

Also, it can be explained like that "moveable" is about internal
managment of object inside containers, "transfer semantics" is about int
erface behavior.

You're just saying how you use them, not what they are about. They are
both about moving, but one is about moving and leaving the source in a
constructed state, and one about moving and leaving the source in a
destructed state. The fact that you only implement the latter for
types that are compatible your "moveable" concept is a deficiency of
the library, not a fundamental problem.

Sure they can. That is what Array flavor is about. (Well, it does
invalidates references, but in NTL this does not matter anyway).

^^
iterators?
References aren't invalidated, are they? Unless you mean references to
pointers?

All

ADTs have Vector (perfomance, requires elements to be moveable) and
Array (generic, no requiremnt at all) flavors. BTW, Array flavor is even
more capable, as it can directly store even polymorphic types.

It does look like it might be rather prone to slicing. Modifying STL
algorithms won't work on the iterators.

Anyway, if you can for the moment forget about how awful it is, look
at MOJO article and notice one thing - everything that Andrei wishes in
the prolog of article is flawlessly possible in NTL.

Having mutable variables is pretty annoying though.

So as ever, it is tradeoff. You must be a little bit more careful
when typing "=", but you get a lot !

It is annoying that moving wasn't considered more at the time of the
original standard, but we can only hope that the next standard
properly considers both destructive and non-destructive moves.

Yes. But there is nowhere defined what are requirements for types
pointed to by them.

Looking through we see that it must be assignable (*i = t is valid).
However, I agree that there isn't any clear requirement for it to be
copyable, although this is, I think, an accidental ommission due to a
defect in the standard.

No, it does not. IterSwap is all you need. During extensive testing
we found only type of element that slightly benefits from copy
constructor in Sort, and that is "int". It is better to solve this
anomaly by specialization and leave Sort requirements for types minimal.

Is it possible to implement an insertion sort using only IterSwap? A
merge sort?

Yes. But in reality, you really need just IterSwap and ordering
predicate. Nothing more.

What you get is possibility to Sort types without deep copy
constructor. That is worth it.

But it does limit the possible algorithms you can use to sort with to
those that don't use any stack elements at all.

No, that is true for some containers where there is no performance
difference to simplify implementation, but e.g. Array and Vector
iterators are as fast as possible.

Ahh, I had assumed you were using the Iterator class for all your
iterators. Apologies.

Anyway, I did not said that iterators are wrong, NTL supports them
and NTL algorithms use them. I just wanted to say that as a side effect,
you do not need to use them if you do not wish (and I bet you would not,
after several months of using NTL

I think this depends on the kind of code your are writing. If it is
heavily algorithmic, you may need node based containers, and iterator
based algorithms are essential for those. In addition, I often use
algorithms on things other than containers (such as plain pointers,
stream iterators, etc.)

Yes. Strange thing is that most of time I am programming, I do need
containers, not iterators or algorithms, to solve my problems....

What domain do you work in?

Your brief examination of NTL implemention is wrong (anyway, I
appreciate you took time to examine actual sources . If it has sense
for performance reasons (Vector, Array, Index, all maps), I do provide
optimal iterators. Yes, there are containers where I use simple approach
(Segtor, BiVector, BiArray containers), but I have measured that
performance-wise, there is no difference. Also, it is an implementation
detail, it might change it in future if I see any sense in doing that.

Agreed, my analysis of your iterators was wrong.

On a more general note, why didn't you implement optimized STL
containers rather than the NTL library? All the things you've done
could easily be done to std::vector, etc., and you could have added
further containers, again in the mould of the STL. If you wanted
container algorithms, you could have easily added them on top of the
STL ones (and added your own swap-only sort algorithm, if desired).

As it is, I doubt you'll get many people other than yourself using
your library, because it provides an unfamiliar interface for no great
gain (compared to an optimized STL using memcpy etc.)

Anyway, your library might stimulate library implementors to produce
better libraries. The use of memcpy is also interesting - I hadn't
considered using memcpy to move non-PODs, having been blinded by the
standardese on the subject. Perhaps the standardese will be updated to
allow a superset of PODs to be memcpyed.

Tom

 

[Mirek Fidler]

That's pretty annoying and surprising that realloc caused a

performance drop - I don't know much about modern general purpose
allocator technology, but I suspect implementations vary greatly
between platforms.

No, it is different - platform uses memory suballocators, that are
inserted by reimplementing global new/delete. That is why malloc and
free are much slower than new/delete.

You could select which to use based on a policy parameter (similar to
std::allocator, but with expand) or possibly just using platform
#ifdefs to choose the best implementation for each platform, settling
on either new or malloc as the default for new platforms.

BTW, if there is something I am considering w.r.t. allocations and
containers, it is possibility to obtain real length of allocated block.
E.g. if with our (sub)allocator you request 450 bytes, you will actually
get 512. It would be nice if during vector expansion extra bytes would
be used...

The obvious thing is to omit the default destructive move
implementation, and hence give an error if the type doesn't have
specialized traits. That way you can support non-memcpy moveable
types, but you'll get an error if you try to make a Vector of a type
you haven't explicitly enabled.

Yes, that would be possible. OTOH, number of non-moveable types that
would work better stored in Vector rather in Array we encountred is
zero. Until I will find counterexample, I see this as waste of time.

Could you please explain "prone to slicing" ? I never heard this
term in this context.

You have a container that can contain a mix of base and derived
objects, but it presents a very similar interface to a container that
has uniform types. e.g the At method returns a reference rather than a
pointer.

Array<Base> myarray;
myarray.Set(10, new Derived1);
//...
Derived2 myobj;
myarray[10] = myobj;

The above is quite likely to cause undefined behaviour, since
myarray[10] will end up with a Derived2 base part in a Derived1
object!

Yes, this is true but inlikely. This kind of types usually does not
have operator= at all (I mean, it is private). There is no difference
between this and

Base& b = *(new Derived1);
Derived2 d2;
b = d2;

It might be clearer if operator[] and At returned pointers rather than
references.

But then obviously Vector and Array would not be interchangeable....

BTW, I often use Array even if I could use Vector - because if speed
does not matter and sizeof(T) is large (about 50 bytes), Array tends to
consume less memory and also instatntiation of Aray is smaller (about
200 bytes typically vs. 600 bytes per Vector).

Of course not, but people don't usually expect slicing when assigning
an iterator's value_type to that iterator.

Hm, and what they do expect to happen when applying modifying
algorithm on polymorphic container then ?

Often the writer of the code doesn't care about the performance of the
operation. Performance in only important in inner loops. Profile
first, then optimize...

Well, I do not care about the performance most of time too. But it
is nice to know, if performance starts to matter, that certain things
are already as fast as possible.

Ahh, that would cover most implementations of std::sort then, which
tend to use variations on introsort.

Well, I am not algorithm expert and I have not implemented our Sort,
but I think it is actually introsort too.

What about heap sort though? Some quicksort algorithms use heap sort
when the chunks get small enough.

Well, I do not know. Perhaps Tomas (sort algorithm author) will
reply this...

I just looked through your algorithms source, and noticed that you do
in fact use the iterator abstraction in general for your algorithms,
but your algorithm documentation only mentions the container versions.
Is there some reason why you don't want users to use the iterator
versions? They are obviously useful if you have, e.g., a plain array
or an istreambuf_iterator, or whatever.

Hm, main reason is that I had to select algorithms for public
release. I selected just those with interfaces different from STL,
because what would be the sense of renameing STL algrithms ?

Except that they don't provide hooks to let the user state how to
destructively move a class, which is, to me, the main benefit of your
library from a performance point of view.

I expect them to provide it in next round.... I also think that if
NTL gets any attention, they will have pretty good reason to do so.

I agree that the latter syntax is simpler, but inserting into the
middle of a vector is O(n), so I hope you don't need it too often!

Quite often. You know, e.g. when creating gui editor widget, you
actually need quite often to insert lines and characters....

Anyway, I do not believe there is a really better option. std::list
iteration is way slower than NTL Insert for the same number of
elements...

This one I disagree with. = should definitely leave the source intact
in most cases, and only be destructive to temporaries and other such.

I agree that this one is definitely hard to swallow

Well, congratulations of making public such an ambitious and
interesting library.

Thanks

Mirek