Boost C++ Libraries: Ticket #2810: Optimization for list::merge performance

attachment set

Andrey Semashev — Fri, 27 Feb 2009 20:20:38 GMT

attachment → list.hpp.patch

The patch that applies the optimization to list::merge (against branches/release)

Ion Gaztañaga — Sat, 28 Feb 2009 17:49:34 GMT

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.

Ion Gaztañaga — Sat, 28 Feb 2009 17:53:12 GMT

Sorry, here's the same with preformatted text:

   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);
         }
      }
   }
   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();
   }

Andrey Semashev — Mon, 02 Mar 2009 06:58:49 GMT

Replying to igaztanaga:

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

Yeah, looks like you're right. Thanks for spotting this.

Your corrected version seems to be working flawlessly in my application. At least, the list::merge method. I hope, it will be released in 1.39.

status changed; resolution set

Ion Gaztañaga — Wed, 25 Mar 2009 17:56:42 GMT

status new → closed
resolution → fixed

Applied modified patch. Revision 51971.