[ANN] NTL "Nonstandard Template Library"

Discussion in 'C++' started by Mirek Fidler, Jun 30, 2003.

  1. Mirek Fidler

    Mirek Fidler Guest

    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.
    Mirek Fidler, Jun 30, 2003
    #1
    1. Advertising

  2. Mirek Fidler

    tom_usenet Guest

    On Mon, 30 Jun 2003 13:06:36 +0200, "Mirek Fidler" <>
    wrote:

    >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
    >------------------------
    >Requirements of STL algorithms are very loosely defined.


    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
    >---------------------
    >There are also some minor improvements like
    >- Besides reserve present in STL, NTL provides also Shrink method to
    >minimize a container's memory consumption.


    That's a worthwhile addition, although the STL has the well-known
    shrink to fit idiom.
    std::vector<int>(v).swap(v);

    >- 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
    tom_usenet, Jun 30, 2003
    #2
    1. Advertising

  3. ....
    >>
    >>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?

    >
    >
    > 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
    Chris Jefferson, Jun 30, 2003
    #3
  4. Mirek Fidler

    Mirek Fidler Guest

    > > 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?


    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
    Mirek Fidler, Jun 30, 2003
    #4
  5. Mirek Fidler

    tom_usenet Guest

    On Mon, 30 Jun 2003 17:11:00 +0200, "Mirek Fidler" <>
    wrote:

    >> 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.

    >
    > 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?

    >> 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/

    >
    > 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.

    >
    >> >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?

    >
    > 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.

    >
    >> >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).

    >
    > 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.

    >
    >> >Algorithm requirements
    >> >------------------------
    >> >Requirements of STL algorithms are very loosely defined.

    >>
    >> 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?

    >
    > 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.

    >
    >> >direct sorting of Array of polymorphic elements.

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

    >
    > 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.

    >> >- Iterators can be assigned a NULL value.

    >>
    >> To achieve this your iterators are less efficient than the STL

    >
    > 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).

    >
    >> >- 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.

    >
    > Yes. That is why things like GetHashValue, mem_hash and CombineHash
    >exist in NTL to support creating right hashing functions.
    >
    >> It is a good idea to provide both hashed and sorted so the user can
    >> decide.

    >
    > 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
    tom_usenet, Jul 1, 2003
    #5
  6. Mirek Fidler

    Mirek Fidler Guest

    > >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.


    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.

    > > 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.


    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.

    > > 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.


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

    > > 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.


    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.

    > > 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.


    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 !

    > > 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.


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

    > > 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.


    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.

    > >> To achieve this your iterators are less efficient than the STL

    > >
    > > 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.


    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
    > >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.


    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, Jul 1, 2003
    #6
  7. Mirek Fidler

    Mirek Fidler Guest

    > 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
    Mirek Fidler, Jul 1, 2003
    #7
  8. Mirek Fidler

    tom_usenet Guest

    On Tue, 1 Jul 2003 17:52:18 +0200, "Mirek Fidler" <>
    wrote:

    >> >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.

    >
    > 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.

    >> 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.


    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.

    >> > 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.

    >
    > 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.

    >> 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).

    ^^
    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.

    >
    >> > 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.

    >
    > 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.

    >> > 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.

    >
    > 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?

    >> 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.


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

    >> >> To achieve this your iterators are less efficient than the STL
    >> >
    >> > 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.

    >
    > 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.)

    >> 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....


    What domain do you work in?

    >
    >> 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.


    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
    tom_usenet, Jul 2, 2003
    #8
  9. Mirek Fidler

    Mirek Fidler Guest

    > 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.

    > >> It does look like it might be rather prone to slicing.

    > >
    > > 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).

    > > Anyway, I hope you do not expect any algortihm to work with any
    > >container ? Like sort with std::list ?

    >
    > 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 ?

    > >(I agree that runtime checks are not as good as compiletime checks,

    but
    > >STL has no checks at all !).

    >
    > 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.

    >> >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?

    > >
    > > Yes.

    >
    > 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 ?

    > > Well, it might have been a nice training, but what would be a

    real
    > >benefit of doing it ? I thing current STL implementors are pretty

    good
    > >at what they do.

    >
    > 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.

    > > Also, STL simply does not serve well to my needs. I am too lazy

    to
    > >write nonsense like
    > >
    > > v.insert(v.begin() + n, x);
    > >
    > > instead of
    > >
    > > v.Insert(n, x);
    > >
    > > And most problems I solve need this.

    >
    > 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...

    > > c) "=" common meaning can be without too much pain changed to
    > >"fastest possible transfer" (from "copy").

    >
    > 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
    Mirek Fidler, Jul 3, 2003
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Mike Sampson [MSFT]

    [ANN]: NNTP Server slow downs.

    Mike Sampson [MSFT], Oct 7, 2003, in forum: ASP .Net
    Replies:
    0
    Views:
    397
    Mike Sampson [MSFT]
    Oct 7, 2003
  2. Mike Sampson [MSFT]

    [ANN]: NNTP Server slow downs.

    Mike Sampson [MSFT], Dec 6, 2003, in forum: ASP .Net
    Replies:
    0
    Views:
    484
    Mike Sampson [MSFT]
    Dec 6, 2003
  3. Richard Grimes [MVP]

    ANN: Free .NET Workshops

    Richard Grimes [MVP], Jul 4, 2005, in forum: ASP .Net
    Replies:
    0
    Views:
    495
    Richard Grimes [MVP]
    Jul 4, 2005
  4. Tom Hawkins

    [ANN] Confluence 0.7.1 Released

    Tom Hawkins, Oct 23, 2003, in forum: VHDL
    Replies:
    0
    Views:
    485
    Tom Hawkins
    Oct 23, 2003
  5. Michael Livsey
    Replies:
    3
    Views:
    398
    Michael Livsey
    May 27, 2004
Loading...

Share This Page