Re: [Boost-bugs] [Boost C++ Libraries] #2810: Optimization for list::merge performance

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #2810: Optimization for list::merge performance
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2009-02-28 17:49:34

#2810: Optimization for list::merge performance
---------------------------+------------------------------------------------
  Reporter:  andysem       |       Owner:  igaztanaga            
      Type:  Patches       |      Status:  new                   
 Milestone:  Boost 1.39.0  |   Component:  intrusive             
   Version:  Boost 1.38.0  |    Severity:  Optimization          
Resolution:                |    Keywords:  list merge performance
---------------------------+------------------------------------------------

Comment(by igaztanaga):

 I think your proposal has a bug in the first loop (it shouldn't be
 "!p(*bx, b)"?). I've tested the following:

    template<class Predicate>
    void merge(list_impl& x, Predicate p)
    {
       const_iterator e(this->cend()), ex(x.cend());
       const_iterator b(this->cbegin());
       while(!x.empty()){
          const_iterator ix(x.cbegin());
          while (b != e && !p(*ix, *b)){
             ++b;
          }
          if(b == e){
             //Now transfer the rest to the end of the container
             this->splice(e, x);
             break;
          }
          else{
             size_type n(0);
             do{
                ++ix; ++n;
             } while(ix != ex && p(*ix, *b));
             this->splice(b, x, x.begin(), ix, n);
          }
       }
    }

 And similarly for slist:

    template<class Predicate>
    iterator merge(slist_impl& x, Predicate p)
    {
       const_iterator e(this->cend()), ex(x.cend()),
 bb(this->cbefore_begin()),
                      bb_next, last_inserted(e);
       while(!x.empty()){
          const_iterator ibx_next(x.cbefore_begin()), ibx(ibx_next++);
          while (++(bb_next = bb) != e && !p(*ibx_next, *bb_next)){
             bb = bb_next;
          }
          if(bb_next == e){
             //Now transfer the rest to the end of the container
             last_inserted = this->splice_after(bb, x);
             break;
          }
          else{
             size_type n(0);
             do{
                ibx = ibx_next; ++n;
             } while(++(ibx_next = ibx) != ex && p(*ibx_next, *bb_next));
             this->splice_after(bb, x, x.before_begin(), ibx, n);
             last_inserted = ibx;
          }
       }
       return last_inserted.unconst();
    }

 Those are not thorougly tested so let me know if you find any error.

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/2810#comment:1>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.