A solution for a fast std::list::size() *and* a fast std::list::splice()

Collapse
This topic is closed.
X
X
 
  • Time
  • Show
Clear All
new posts
  • Juha Nieminen

    #1

    A solution for a fast std::list::size() *and* a fast std::list::splice()

    If I'm not completely mistaken, the only reason why std::list::size ()
    may be (and usually is) a linear-time operation is because they want
    std::list::spli ce() to be a constant-time operation, and if you execute
    the latter, the size of the resulting lists cannot be known without
    explicitly counting the sizes of the new lists.

    I was thinking: What if size() was an O(n) operation only *after*
    a splice() operation has been performed (and only the first time size()
    is called after that), but O(1) otherwise?

    In other words, keep a size variable in the list class and update
    it as necessary, and additionally keep a flag which tells if this
    size variable is valid. As long as the flag tells that it's valid,
    list::size() can return the value of the variable. Only if the flag
    says it's invalid, then the O(n) counting will be performed, updating
    the variable, after which the flag can be set to valid.

    A splice() operation would set the flag to invalid in both lists.

    This way splice() will always be O(1), and size() will be O(n) only
    once after a splice(), but O(1) otherwise. You will get speed benefits
    in all cases except if you alternatively call splice() and size()
    repeatedly (in which case you just get the same behavior as in most
    current list implementations , so it's not like the result would be
    worse).
  • tony_in_da_uk@yahoo.co.uk

    #2
    Re: A solution for a fast std::list::size () *and* a fast std::list::spli ce()

    On Oct 10, 9:50 am, Juha Nieminen <nos...@thanks. invalidwrote:
    In other words, keep a size variable in the list class and update
    it as necessary, and additionally keep a flag which tells if this
    size variable is valid. As long as the flag tells that it's valid,
    list::size() can return the value of the variable. Only if the flag
    says it's invalid, then the O(n) counting will be performed, updating
    the variable, after which the flag can be set to valid.
    >
    A splice() operation would set the flag to invalid in both lists.
    All sensible and in my opinion useful, but there are people who're
    already using lists who wouldn't want them to slow down, or grow their
    data member size - even a little bit - to maintain this extra state.
    You can easily provide this in a wrapper class around the STL, and
    publish it if you think others would want it. Maybe even submit it to
    boost....

    Tony

    Comment

    • Jerry Coffin

      #3
      Re: A solution for a fast std::list::size () *and* a fast std::list::spli ce()

      In article <470c2093$0$278 15$39db0f71@new s.song.fi>,
      nospam@thanks.i nvalid says...
      If I'm not completely mistaken, the only reason why std::list::size ()
      may be (and usually is) a linear-time operation is because they want
      std::list::spli ce() to be a constant-time operation, and if you execute
      the latter, the size of the resulting lists cannot be known without
      explicitly counting the sizes of the new lists.
      >
      I was thinking: What if size() was an O(n) operation only *after*
      a splice() operation has been performed (and only the first time size()
      is called after that), but O(1) otherwise?
      This is a perfectly legitimate way of implementing std::list. It's not
      required, of course, but you can do it if you want to. Then again, you
      can't count on it in general.

      --
      Later,
      Jerry.

      The universe is a figment of its own imagination.

      Comment

      • Juha Nieminen

        #4
        Re: A solution for a fast std::list::size () *and* a fast std::list::spli ce()

        tony_in_da_uk@y ahoo.co.uk wrote:
        All sensible and in my opinion useful, but there are people who're
        already using lists who wouldn't want them to slow down
        This solution would only speed it up. The alternative is to use
        the current typical solution, which is an O(n) size() function.
        or grow their data member size
        The size of the list elements would not change at all. Only the
        size of the std::list class would grow by one flag and one size
        variable. Hardly catastrophical (especially taking into account
        how much it speeds up size()).
        You can easily provide this in a wrapper class around the STL
        Can I? I would have to reimplement most of the list member functions.
        Not a trivial task.

        Comment

        • Juha Nieminen

          #5
          Re: A solution for a fast std::list::size () *and* a fast std::list::spli ce()

          Jerry Coffin wrote:
          This is a perfectly legitimate way of implementing std::list.
          If it's a perfectly working solution, why aren't they using it
          to implement std::list? It sounds quite an obvious solution to me.

          Comment

          • Michael DOUBEZ

            #6
            Re: A solution for a fast std::list::size () *and* a fast std::list::spli ce()

            Juha Nieminen a écrit :
            Jerry Coffin wrote:
            >This is a perfectly legitimate way of implementing std::list.
            >
            If it's a perfectly working solution, why aren't they using it
            to implement std::list? It sounds quite an obvious solution to me.
            Perhaps because nobody needs it and if you need it, it is
            straightforward to add it.

            From a design point of view, you rarely need to know the size of a list.

            Michael

            Comment

            • =?UTF-8?B?RXJpayBXaWtzdHLDtm0=?=

              #7
              Re: A solution for a fast std::list::size () *and* a fast std::list::spli ce()

              On 2007-10-10 15:31, Juha Nieminen wrote:
              Jerry Coffin wrote:
              >This is a perfectly legitimate way of implementing std::list.
              >
              If it's a perfectly working solution, why aren't they using it
              to implement std::list? It sounds quite an obvious solution to me.
              First figure out who have not implemented list in that way (there are
              many vendors of C++ standard libraries) and then ask them. My guess
              would be that the value of optimisations not guaranteed in the standard
              is debatable, the users could never depend on them.

              --
              Erik Wikström

              Comment

              • Bo Persson

                #8
                Re: A solution for a fast std::list::size () *and* a fast std::list::spli ce()

                Juha Nieminen wrote:
                :: Jerry Coffin wrote:
                ::: This is a perfectly legitimate way of implementing std::list.
                ::
                :: If it's a perfectly working solution, why aren't they using it
                :: to implement std::list? It sounds quite an obvious solution to me.

                But it still makes the size() call O(n). The fact that it sometimes
                (often) is O(1) doesn't help me writing a function that uses
                list::size().

                How would I know if someone had called splice recently? So I would
                still have to assume O(n) !



                Bo Persson


                Comment

                • P.J. Plauger

                  #9
                  Re: A solution for a fast std::list::size () *and* a fast std::list::spli ce()

                  ----- Original Message -----
                  From: "Juha Nieminen" <nospam@thanks. invalid>
                  Newsgroups: comp.lang.c++
                  Sent: Tuesday, October 09, 2007 20:50
                  Subject: A solution for a fast std::list::size () *and* a fast
                  std::list::spli ce()
                  If I'm not completely mistaken, the only reason why std::list::size ()
                  may be (and usually is) a linear-time operation
                  It's a constant time operation in our implementation, and always
                  has been.
                  is
                  because they want
                  std::list::spli ce() to be a constant-time operation, and if you execute
                  the latter, the size of the resulting lists cannot be known without
                  explicitly counting the sizes of the new lists.
                  There are three forms of splice:

                  -- splice a single element from this or another list

                  -- splice the entire contents of another list

                  -- splice partial contents of another list

                  The resultant size of the donee list is well known, as is that of any
                  donating list, in all but the last case. The C++ Standard has
                  always required that all but the last case be constant time, while
                  the last one can be linear time.

                  Moreover, in all but the last case it's a trivial matter to preserve
                  the integrity of both donor and donee. In the last case the only
                  way to avoid pirating the head node of another list is to walk
                  the donated sublist looking for that head node. It's a trivial
                  matter to count up the nodes while you're doing this very useful
                  checking. Some of us think this checking is absolutely essential.
                  I was thinking: What if size() was an O(n) operation only *after*
                  a splice() operation has been performed (and only the first time size()
                  is called after that), but O(1) otherwise?
                  >
                  In other words, keep a size variable in the list class and update
                  it as necessary, and additionally keep a flag which tells if this
                  size variable is valid. As long as the flag tells that it's valid,
                  list::size() can return the value of the variable. Only if the flag
                  says it's invalid, then the O(n) counting will be performed, updating
                  the variable, after which the flag can be set to valid.
                  >
                  A splice() operation would set the flag to invalid in both lists.
                  >
                  This way splice() will always be O(1), and size() will be O(n) only
                  once after a splice(), but O(1) otherwise. You will get speed benefits
                  in all cases except if you alternatively call splice() and size()
                  repeatedly (in which case you just get the same behavior as in most
                  current list implementations , so it's not like the result would be
                  worse).
                  This discussion comes up about once a year, and this solution is
                  offered each time. I consider it mooted by the need to check a
                  partial splice anyway, which takes linear time. Other disagree,
                  so YMMV.

                  P.J. Plauger
                  Dinkumware, Ltd.


                  Comment

                  • Kai-Uwe Bux

                    #10
                    Re: A solution for a fast std::list::size () *and* a fast std::list::spli ce()

                    Jerry Coffin wrote:
                    In article <470cd502$0$319 2$39db0f71@news .song.fi>,
                    nospam@thanks.i nvalid says...
                    >Jerry Coffin wrote:
                    [snip]
                    Then again, I have to admit that I tend to think the presence of
                    std::list does more harm than good, since its presence seems to give
                    soem people the idea that they should use it, and over time I've become
                    convinced that suitable uses for linked lists are about as common as
                    magnetic monopoles (i.e. they should theoretically exist, but the few
                    times people think they might have seen one in reality, confirmation
                    seems impossible).
                    What about this one:

                    class command_bag {
                    public:

                    typedef std::tr1::funct ion< void(void) command;

                    private:

                    typedef std::list< command command_list;

                    command_list the_list;

                    public:

                    typedef command_list::i terator removal_ticket;

                    template < typename Command >
                    removal_ticket insert ( Command c ) {
                    the_list.push_f ront( command( c ) );
                    return ( removal_ticket( the_list.begin( ) ) );
                    }

                    void remove ( removal_ticket t ) {
                    the_list.erase( t );
                    }

                    void execute ( void ) const {
                    for ( command_list::c onst_iterator iter = the_list.begin( );
                    iter != the_list.end(); ++iter ) {
                    (*iter)();
                    }
                    }

                    };

                    A command_bag allows you to register an action. You get a ticket which you
                    can use to unregister the action. This can be useful if you have some
                    observers that want to be notified of certain events but may lose interest
                    at some point in the future.

                    The guarantees of std::list about invalidation of iterators are _exactly_
                    what you want in this case.


                    Best

                    Kai-Uwe Bux

                    Comment

                    • Juha Nieminen

                      #11
                      Re: A solution for a fast std::list::size () *and* a fast std::list::spli ce()

                      Jerry Coffin wrote:
                      Given the frequency with
                      which I've seen good uses for std::list::size () (i.e. essentially never)
                      I'm not sure that would be a good tradeoff.
                      In my proposed solution splice() would still be constant-time. Only
                      size() would be faster (except immediately after a splice()). I see
                      no "tradeoff" here. It's pure speedup with no negative side-effects.

                      Granted, in the vast majority of cases where lists are useful knowing
                      its size is usually unneeded (because a list is the kind of data
                      structure where its size is not really that important because more often
                      than not you are only interested in either the first/last item, or all
                      the items at the same time, and even if you are interested in one single
                      item somewhere in the list, you are going to have to traverse it anyways).

                      However, the problem with list::size() is that most people who don't
                      know it can be linear time may well assume it's constant-time because
                      it's constant-time in all the other STL data containers too, and thus
                      they will carelessly use list::size() without giving it a second
                      thought, thus resulting in needlessly inefficient programs. If
                      list::size() can be made faster without affecting negatively anything
                      else, I don't see any reason why it couldn't be done.
                      Then again, I have to admit that I tend to think the presence of
                      std::list does more harm than good, since its presence seems to give
                      soem people the idea that they should use it, and over time I've become
                      convinced that suitable uses for linked lists are about as common as
                      magnetic monopoles (i.e. they should theoretically exist, but the few
                      times people think they might have seen one in reality, confirmation
                      seems impossible).
                      I have used std::list for useful purposes many times. Linked lists
                      have certain useful properties when you know how to use them.

                      It would be a real pain to have to re-implement linked lists every
                      time I need one.

                      Comment

                      • Juha Nieminen

                        #12
                        Re: A solution for a fast std::list::size () *and* a fast std::list::spli ce()

                        P.J. Plauger wrote:
                        -- splice partial contents of another list
                        >
                        The resultant size of the donee list is well known, as is that of any
                        donating list, in all but the last case. The C++ Standard has
                        always required that all but the last case be constant time, while
                        the last one can be linear time.
                        I can imagine that any algorithm which needs list splicing assumes
                        that the splicing is constant-time. If splice() cannot be assumed to be
                        constant-time, then I suppose it becomes a completely useless function
                        for any purpose you may want to need that operation. Any algorithm
                        needing list splicing would have to implement a list of their own.

                        So the question is: If splice() cannot be assumed to be constant-time,
                        why support it at all? Better just remove it completely.

                        Compare this to eg. std::vector not having a push_front() function:
                        Since it cannot be done faster than linear time, it's not supported at all.

                        Comment

                        • Jerry Coffin

                          #13
                          Re: A solution for a fast std::list::size () *and* a fast std::list::spli ce()

                          In article <fekgic$n0c$1@m urdoch.acc.Virg inia.EDU>, jkherciueh@gmx. net
                          says...

                          [ I had mentioned the rarity of examples of good uses for linked lists ]
                          What about this one:
                          [ code elided .... ]
                          A command_bag allows you to register an action. You get a ticket which you
                          can use to unregister the action. This can be useful if you have some
                          observers that want to be notified of certain events but may lose interest
                          at some point in the future.
                          >
                          The guarantees of std::list about invalidation of iterators are _exactly_
                          what you want in this case.
                          While I'll admit that in theory this is true, I also have to say that
                          when I've encountered similar situtations, it really didn't work out.
                          What you're doing is essentially equivalent to handing out a pointer to
                          the object's internal data, which we all know is generally a poor idea.

                          When I've encountered situations roughly similar to this, it ended up
                          being much cleaner to use a set. Instead of giving the client a unique
                          key in exchange for their function, when they register a function, you
                          return nothing. When they want to de-register the function, they just
                          tell you the function they want to de-register, and you look it up and
                          remove it from the set.

                          Theoretically, this should be marginally less efficient -- inserting and
                          removing items from a set is logarithmic instead of constant. Likewise,
                          traversing a set is theoretically marginally slower as well. In reality,
                          the difference between logarithmic and constant is usually quite small.
                          In addition, registering and unregistering functions doesn't happen
                          extremely often anyway. The difference in run-time speed wasn't even
                          dependably measureable, but the difference in the cleanliness of the
                          interface substantial and almost immediately obvious.

                          In the end, the validity of iterators matters primarily when you "hand
                          out" iterators to the object's data. I would posit that this is really
                          no different from handing out pointers to the object's data, which we've
                          all known for years is usually a bad idea (in fact, I believe that's the
                          theme of an item in one of Scott Meyers's books).

                          --
                          Later,
                          Jerry.

                          The universe is a figment of its own imagination.

                          Comment

                          • =?UTF-8?B?RXJpayBXaWtzdHLDtm0=?=

                            #14
                            Re: A solution for a fast std::list::size () *and* a fast std::list::spli ce()

                            On 2007-10-11 12:54, Juha Nieminen wrote:
                            Jerry Coffin wrote:
                            >Given the frequency with
                            >which I've seen good uses for std::list::size () (i.e. essentially never)
                            >I'm not sure that would be a good tradeoff.
                            >
                            In my proposed solution splice() would still be constant-time. Only
                            size() would be faster (except immediately after a splice()). I see
                            no "tradeoff" here. It's pure speedup with no negative side-effects.
                            The problem is that when you specify that size() have constant
                            complexity except after a call to splice() you just defined size() to
                            have linear complexity. Remember that it is the worst case that is
                            given, and with your solution that would be after a call to splice(). So
                            what you suggest is that we keep size() as it is and make the last case
                            of splice() (splicing a partial sequence from another list) constant.
                            Only problem is that the only real expert on library implementation who
                            have said anything claims that this is a bad thing to do.

                            --
                            Erik Wikström

                            Comment

                            • P.J. Plauger

                              #15
                              Re: A solution for a fast std::list::size () *and* a fast std::list::spli ce()

                              "Juha Nieminen" <nospam@thanks. invalidwrote in message
                              news:470e0161$0 $27822$39db0f71 @news.song.fi.. .
                              P.J. Plauger wrote:
                              >-- splice partial contents of another list
                              >>
                              >The resultant size of the donee list is well known, as is that of any
                              >donating list, in all but the last case. The C++ Standard has
                              >always required that all but the last case be constant time, while
                              >the last one can be linear time.
                              >
                              I can imagine that any algorithm which needs list splicing assumes
                              that the splicing is constant-time.
                              You can imagine it. Indeed, several other people have imagined just
                              that over the past several years. One or two of the brighter ones even
                              tried to contrive use cases where a partial splice absolutely positively
                              had to be constant time or the algorithm would be too slow. Every
                              one of those cases I saw could easily be transmogrified to a case
                              where the spliced sublist could be made into an entire list, and hence
                              would splice in constant time.

                              An obvious case is list::sort, which does a Towers of Hanoi merge
                              sort by building sublists. The easiest way to implement this is to
                              minimize the number of temporary lists and splice sublists. But the
                              common implementation, based on the original H-P STL, uses
                              more sublists and does complete sublist splices. Hence, the sort
                              is fastern 'n blazes.
                              If splice() cannot be assumed to
                              be
                              constant-time, then I suppose it becomes a completely useless function
                              for any purpose you may want to need that operation.
                              What a crass overstatement. Moreover, in my extensive experience
                              algorithms with terrible theoretical time complexity almost always
                              have satisfactory real-world performance because a) data sets
                              seldom get large enough to matter and b) computers are blindingly
                              fast for most uses to begin with. In any case, others will find uses
                              for a linear splice even if you can't.
                              >
                              Any algorithm
                              needing list splicing would have to implement a list of their own.
                              Or get one of the implementations that aren't afraid to damage lists
                              occasionally in the interest of getting fast results all the time.
                              So the question is: If splice() cannot be assumed to be constant-time,
                              why support it at all? Better just remove it completely.
                              See above.
                              Compare this to eg. std::vector not having a push_front() function:
                              Since it cannot be done faster than linear time, it's not supported at
                              all.
                              Well, that would be one solution -- simply remove the partial splice option.
                              Note, however, that single-element splice and full-list splice are still
                              reliably constant-time operations. Or would you have us ditch these too
                              because people might *fear* they're not going to be fast enough?

                              P.J. Plauger
                              Dinkumware, Ltd.


                              Comment

                              Working...